Обучение без учителя

Spectral Clustering

Спектральная кластеризация

актуальноТекущий рабочий стандарт

Кластеризация через собственные векторы матрицы Лапласа графа сходства: находит невыпуклые и вложенные структуры.

Ключевые тезисы

Строит граф сходства объектов, затем кластеризует в пространстве собственных векторов.
Находит кластеры-кольца и спирали, недоступные k-means.
Сложность по памяти квадратична — на больших выборках нужны приближения.

Тема также относится к главам:Классическое машинное обучениеКластеризация

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

1

Алгоритм

Кластеризация в пространстве собственных векторов.

Построить матрицу сходства (например, гауссово ядро по расстояниям).
Посчитать лапласиан графа $L = D - W$ и его нормированную версию.
Взять $k$ собственных векторов с наименьшими собственными значениями.
Кластеризовать строки полученной матрицы обычным k-means.

L_{sym} = I - D^{- 1/2} W D^{- 1/2}

2

Когда это нужно

И чем ограничено.

Находит кластеры-кольца, спирали и вложенные структуры, где k-means бессилен.
Естественно работает с данными, заданными графом сходства, а не координатами.
Память $O (n^{2})$ на матрицу сходства — на больших выборках нужен разреженный граф k ближайших соседей.
Число кластеров подсказывает «спектральный зазор» — скачок в собственных значениях.

Связанные темы

Плотностная кластеризация

HDBSCAN85%

HDBSCAN · Обучение без учителя

Иерархическая версия DBSCAN: перебирает плотности автоматически и находит кластеры разной плотности.

DBSCAN85%

DBSCAN · Классическое машинное обучение

Плотностная кластеризация: кластеры — это связные области высокой плотности, остальное объявляется шумом.

Dimensionality Reduction85%

Снижение размерности · Обучение без учителя

Компактное представление данных, сохраняющее важную часть структуры.

Persistent Homology85%

Персистентные гомологии · Топологический анализ данных

Центральный метод TDA: вместо одного порога ε рассматривается вся фильтрация, и отслеживается, когда топологические особенности рождаются и умирают.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.