Статистический кластерный анализ (регулярный семинар)

Материал из MachineLearning.

Версия 09:40, 8 декабря 2015

Описание семинара

Задача кластеризации известна всем, кто имел дело с машинным обучением, и имеет бесчисленное множество практических применений. Кроме того, известно, что задача кластеризации может быть сформулирована разными способами, то есть не имеет чёткой общепринятой постановки. В рамках данного семинара изучаются статистические подходы к задаче кластеризации. Отдельное внимание в работе уделяется кластеризации графов. Целью работы группы является построение алгоритмов кластеризации и кластеризации графов, которые обладают практической эффективностью, и при это допускают теоретический анализ.

Время заседаний

Регулярный семинар, проводится в ИППИ РАН по средам в 18-30, ауд. 615.

Научные руководители семинара

М.Е. Панов, С. Довгаль, В. Г. Спокойный

Организатор семинара

Совместный учебно-научный семинар магистерской программы Математические методы оптимизации и стохастики Факультета Компьютерных наук НИУ ВШЭ, Института проблем передачи информации РАН и Лаборатории ПреМоЛаб МФТИ. Куратор семинара М.Е. Панов

Заседания

13 октября 2015 г.

Игорь Силин "Минимаксное оценивание в Stochastic Block Models"

28 октября 2015 г.

1. Игорь Силин — продолжение рассказа

2. Обсуждение тем курсовых работы для студентов программы ММОС.

11 ноября 2015 г.

Константин Славнов "Методы выделения сообществ в применении к анализу социальных сетей"

Обзорный доклад, который посвящен теме социальных графов и обзору способов выделения сообществ на основе функционала модулярности. Будут рассмотрены некоторые свойства модулярности, 7 алгоритмов выделения структуры сообществ (Betweenness, Fastgreedy, Multilevel, LabelPropogation, Walktrap, Infomap, Eigenvector), а также рассказаны собственные результаты по способам композиции различных методов выделения сообществ.

Презентация, Текст работы «Анализ социальных графов»

18 ноября 2015 г.

Сергей Довгаль "Кластеризация с адаптивными весами"

На докладе мы расскажем об алгоритме AWC (Adaptive Weights Clustering). Мы посмотрим, какие геометрические подзадачи возникают при задаче кластеризации и опишем основные свойства этого алгоритма. Алгоритм исследуется для метрической кластеризации, но его можно применять для произвольных графов, на которых задана матрица расстояний.

2 декабря 2015 г.

Максим Панов "Введение в спектральные методы кластеризации" (Презентация)

В рамках доклада мы расскажем об алгоритме спектральной кластеризации (Spectral clustering). Данный алгоритм прост в реализации и часто превосходит другие традиционные алгоритмы кластеризации. Цель доклада состоит в том, чтобы дать аудитории интуитивное понимание математических идей, лежащих в основе алгоритма. Будут рассмотрены различные виды лапласианов графа и их основные свойства, а также представлены наиболее популярные варианты алгоритма спектральной кластеризации.

9 декабря 2015 г.

• • • Лада Токмакова "Стабильность кластеризации: обзор"***

Современные методы определения количества кластеров выбирают такое оптимальное число разбиений, при котором кластеризация является наиболее стабильной. В ходе доклада будет определен термин стабильности кластеризации, также будет рассказано о некоторых теоретических достижениях для алгоритмов K-means: the idealized K-means algorithm (когда целевая функция сходится к глобальному минимуму) и the actual K-means algorithm (когда целевая функция сходится к локальному минимуму).

Антон Вотинов "Графы ближайших соседей: алгоритмы оценки размерности и плотности"

Графы ближайших соседей часто встречаются в различных приложениях. Несмотря на то, что в таких графах содержится только информация об относительно расположении точек, существует возможность заглянуть глубже. В ходе доклада будут рассмотрены два алгоритма: алгоритм оценки размерности исходного пространства, из которого граф был порождён; оценка распределения наблюдений, на основе которых был построен граф.

Литература

Кластеризация на графах

1. Stochastic block models and graphon estimation

[1] Chao Gao, Yu Lu, Harrison H. Zhou "Rate-optimal Graphon Estimation"

[2] Olga Klopp, Alexandre B. Tsybakov, Nicolas Verzelen "Oracle inequalities for network models and sparse graphon estimation"

2. Кластеризация графов на основе модулярности

[3] Santo Fortunato "Community detection in graphs"

[4] Twan van Laarhoven, Elena Marchiori "Axioms for graph clustering quality functions"

[5] Yunpeng Zhao, Elizaveta Levina, Ji Zhu "Consistency of community detection in networks under degree-corrected stochastic block models"

3. Графы ближайших соседей и их кластеризация

[6] Ulrike von Luxburg, Morteza Alamgir "Density estimation from unweighted k-nearest neighbor graphs: a roadmap"

[7] Matthaus Kleindessner, Ulrike von "Luxburg Dimensionality estimation without distances"

4. Обнаружение пересекающихся сообществ в больших сетях: алгоритм BigCLAM и его обобщения

[8] Jaewon Yang, Jure Leskovec "Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach"

5. Spectral clustering

[9] Ulrike von Luxburg "A Tutorial on Spectral Clustering"

[10] Donghui Yan, Ling Huang, Michael I. Jordan "Fast Approximate Spectral Clustering"

Метрическая кластеризация

1. Задача одномерной оценки плотности

[11] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"

[12] Luc Devroye "A note on the usefulness of superkernels in density estimation"

2. Задача одномерной кластеризации

[13] Kristian Sabo, Rudolf Scitovski, Ivan Vazler "One-dimensional center-based l_1-clustering method"

[14] Andrew Ng "The EM algorithm"

3. Задача многомерной кластеризации и оценки плотности

[15] Alessandro Rinaldo and Larry Wasserman "Generalized Density Clustering

[16] Ingo Steinwart "Fully adaptive density-based clustering"

[17] Alexandre B. Tsybakov "Introduction to Nonparametric Estimation"

4. Стабильность кластеризации

[18] Ulrike von Luxburg "Clustering Stability: An Overview"