Spectral clustering

Спектральная кластеризация — метод, который переводит задачу кластеризации в задачу разбиения графа. **Основная идея:** Объекты рассматриваются как вершины графа, а ребра задают степень сходства между ними. По матрице сходства строится графовый Лапласиан: $L = D - W$, где $W$ — матрица весов ребер, $D$ — диагональная матрица степеней вершин. **Алгоритмическая схема:** 1. строится граф ближайших соседей или матрица сходства; 2. вычисляются собственные векторы Лапласиана; 3. объекты отображаются в новое спектральное пространство; 4. в этом пространстве применяется K-Means или другой простой метод разбиения. **Преимущества:** Метод хорошо выделяет кластеры сложной формы, когда в исходном пространстве они не являются линейно разделимыми. **Ограничения:** Требует выбора способа построения графа и может быть затратным для больших выборок из-за вычисления собственных векторов.