Работа стоит на отшибе: рядом почти никого, ближайший сосед на расстоянии 0.523. Вокруг лежат исследования по крупномасштабной структуре Вселенной, машинному обучению и свёрточным нейросетям, но они решают другие задачи. Данная статья восполняет пробел в спектральной кластеризации, предлагая метод, который не требует заранее заданного числа кластеров и опирается на внутреннюю структуру данных.
Алгоритм SP-MGM строит матрицу сходства, вычисляет собственные векторы ненормализованного лапласиана, соответствующие наименьшим положительным собственным значениям. Для каждого вектора компоненты сортируются по возрастанию, и находится максимальный разрыв между соседними значениями. Этот разрыв делит вершины на два подмножества. Пересекая такие бинарные разбиения для нескольких собственных векторов, алгоритм формирует кластеры. Математическое обоснование опирается на теорию возмущений собственных векторов: если кластеры хорошо разделены, разрывы в собственных векторах точно указывают границы кластеров.
На эталонных графах LFR с 50 и 100 узлами SP-MGM стабильно превосходил KMEANS, спектральный KMEANS и агломеративную кластеризацию по метрикам NMI и ARS во всём диапазоне параметра смешивания. При малом среднем степени и низком смешивании только SP-MGM давал разумные результаты. Для больших сетей он работал сравнимо или лучше, уступая агломеративному методу лишь при очень больших размерах. Алгоритм автоматически определял число кластеров: при m собственных модах почти всегда получалось m+1 кластер. На данных температуры поверхности океана в регионе Niño 3.4 за 1955–2016 годы SP-MGM выделил семь кластеров, соответствующих разным фазам Эль-Ниньо, Ла-Нинья и нейтральным состояниям, причём кластеры не определялись только индексом ONI, что указывает на разные «вкусы» явления.
В отличие от соседних работ, которые применяют машинное обучение к космологическим данным или изображениям, эта статья предлагает новый алгоритм кластеризации с математическим обоснованием и проверкой на климатических данных. Она показывает, что простой анализ разрывов в собственных векторах может конкурировать с популярными методами и автоматически выявлять структуру без внешних параметров. Это расширяет инструментарий спектральной кластеризации и даёт способ обнаруживать тонкие различия в климатических режимах.
Алгоритм можно масштабировать на большие сети через иерархический подход, когда спектральные методы применяются к подмножествам данных. Возможна адаптация к другим типам графов и сравнение с более широким набором алгоритмов, включая методы на основе глубокого обучения. Для климатических приложений интересно исследовать, как выделенные кластеры связаны с региональными осадками и температурой.
Метод может быть полезен в нейронауке, социальных сетях, компьютерном зрении и цифровой криминалистике, где требуется выявление естественных групп. В климатологии он помогает классифицировать состояния Эль-Ниньо и улучшать прогнозы.
Провести систематическое сравнение SP-MGM с другими спектральными алгоритмами на разнообразных эталонных наборах. Исследовать поведение алгоритма на графах с перекрывающимися кластерами и шумом.
В климатологии остаётся открытым вопрос о том, как различные «вкусы» Эль-Ниньо влияют на региональный климат. Работа показывает, что кластеризация пространственно-распределённых аномалий температуры может выявить такие подтипы, но их физическая интерпретация и предсказательная ценность требуют дальнейшего изучения.
Алгоритм SP-MGM почти всегда выдаёт ровно m+1 кластер при m собственных модах, хотя теоретически их может быть до $2^m$. Это указывает на глубокую связь между разрывами в собственных векторах и структурой графа.
Идея поиска скрытых структур по разрывам в данных напоминает анализ «паттернов» в романе Уильяма Гибсона «Распознавание образов», где героиня интуитивно находит аномалии в видеопотоках. Алгоритм формализует подобный поиск для графов.