AdaGraph: алгоритм кластеризации, побеждающий проклятие размерности
Группа исследователей опубликовала в arXiv описание AdaGraph — нового алгоритма кластеризации, который решает фундаментальную проблему проклятия размерности. В отличие от традиционных методов, основанных на евклидовых расстояниях, AdaGraph оперирует исключительно топологией графа k-ближайших соседей (kNN), сохраняя значимую структуру данных даже в пространствах с тысячами измерений.
Алгоритм принадлежит новой парадигме Structure-Centric Machine Learning (SC-ML), где вычисления заменяются топологическими. AdaGraph не требует заранее задавать количество кластеров, самостоятельно обрабатывает шум и масштабируется с помощью фреймворка SLCD (Sample-Learn-Calibrate-Deploy). В качестве метрики качества используется Graph-SCOPE — индекс валидности кластеров, также разработанный в рамках SC-ML.
На десяти синтетических наборах данных с размерностью от 10 до 5000 AdaGraph показал средний скорректированный индекс Рэнда (ARI) 0,900 и правильно определил количество кластеров в 9 из 10 случаев. Это значительно превосходит классические индексы, такие как Silhouette, Davies-Bouldin и Calinski-Harabasz.
Практическая значимость подтверждена в трёх научных областях. В геномике при анализе 10 000 генов и 488 пациентов с гепатоцеллюлярной карциномой AdaGraph выделил модули коэкспрессии генов, незаметные для методов WGCNA, ICA, NMF и спектральной бикластеризации. Для кластеризации текстов (датасет 20NG-6cat) AdaGraph достиг ARI 0,751 против 0,464 у HDBSCAN — улучшение на 62%.
В материаловедении алгоритм применили к трём наборам данных сверхпроводников, перовскитов и материалов из JARVIS-DFT с 145-мерными признаками. Во всех случаях AdaGraph показал наивысший балл по Graph-SCOPE среди сравниваемых методов.
Разработка открывает возможности для анализа больших данных в условиях, где традиционные метрики расстояния становятся бесполезными. AdaGraph доступен для использования в научных исследованиях, требующих надёжной кластеризации без потери информации из-за снижения размерности.
