Как найти границы в данных: простой способ увидеть группы ✎

Оригинал: "A New Spectral Clustering Algorithm"

arXiv:1710.02756 · 2017-10-07 · arXiv non-exclusive · собственный разбор · 1 мин

Машинное обучение Компьютерное зрение Геофизика

Алгоритм SP-MGM находит группы в данных, анализируя резкие изменения в специальных волнах, которые описывают связи между объектами.

Представьте себе реку, которая разделяет два берега. На одном берегу живут одни люди, на другом — другие. Граница между ними видна там, где течение реки резко меняется. Алгоритм SP-MGM ищет такие резкие изменения в данных, чтобы понять, где заканчивается одна группа и начинается другая.

Чтобы найти границы, алгоритм строит специальные волны, которые описывают, как связаны между собой объекты. Если две группы слабо связаны, волна резко меняется на границе между ними. Алгоритм находит самое большое изменение и проводит границу именно там. Так он сам решает, сколько групп должно быть, и не требует заранее задавать это число.

Вместо того чтобы заранее решать, сколько групп должно быть в данных, алгоритм смотрит на сами данные и находит в них естественные разрывы. Это как если бы вы разрезали торт по линиям, которые уже есть в нём, а не по заранее намеченным.

Алгоритм проверили на данных о температуре поверхности океана. Он нашёл семь разных состояний Эль-Ниньо и Ла-Нинья. Это помогает лучше понять, как разные типы этого явления влияют на погоду. Такой метод может пригодиться и в других областях, например, для поиска сообществ в социальных сетях.

Весь граф →

Алгоритм SP-MGM почти всегда выдаёт ровно m+1 кластер при m собственных модах, хотя теоретически их может быть до $2^m$. Это указывает на глубокую связь между разрывами в собственных векторах и структурой графа.

Идея поиска скрытых структур по разрывам в данных напоминает анализ «паттернов» в романе Уильяма Гибсона «Распознавание образов», где героиня интуитивно находит аномалии в видеопотоках. Алгоритм формализует подобный поиск для графов.

L = I - D^{-1/2} A D^{-1/2}

Матрица, описывающая связность графа; её собственные векторы кодируют кластерную структуру.

A_{ij} = \exp(-d_{ij}^2 / (2\sigma))

Элементы матрицы сходства убывают с ростом расстояния между объектами.

\max_{i \neq m} \frac{(n_i - 1) \rho_1}{\lambda_{i,2}} < \frac{1}{4 n_m^{1/2}}

Если межкластерные связи слабы по сравнению с внутрикластерной связностью, алгоритм гарантированно найдёт кластеры.

Понятия

кластеризация нелинейный спектральный анализ Лапласиана кластеризация методом k-средних климатическая сеть метод наименьших квадратов ансамблевый прогноз спектральная картина энсо распознавание образов индекс Эль-Ниньо метод CLs нейронные сети согласованная фильтрация многомерный индекс ЭНСО кросс-корреляция южная осцилляция эль-ниньо накопление сигнала классификация подгонка методом наименьших квадратов поляриметрия с нейронными сетями

Я автор

Как найти границы в данных: простой способ увидеть группы ✎