Спектральна кластеризація: як власні вектори лапласіана графа виявляють структуру кластерів

Від точок до графа подібності

Спектральна кластеризація починається з відмови від евклідової відстані як основного сигналу і натомість будує граф подібності: зважений граф, де вага ребра w_ij вимірює, наскільки «близькі» точки i та j. Найпоширеніший вибір — гаусове (RBF) ядро, обмежене околом:

Головна ідея: дві точки можуть бути «близькими» у термінах графа — з'єднаними через ланцюжок сусідів — навіть якщо вони далеко одна від одної по прямій. Саме це дозволяє спектральній кластеризації трактувати півмісяць чи спіраль як єдиний зв'язний регіон.

Лапласіан графа

Маючи зважену матрицю суміжності W та діагональну матрицю ступенів D (D_ii = Σⱼ w_ij), неноормалізований лапласіан графа визначається як:

Ця квадратична форма — суть усього: xᵀLx мале саме тоді, коли сильно зв'язаним точкам i, j присвоєні схожі значення xᵢ, xⱼ. Мінімізація цього виразу — це обмеження гладкості на графі, а мінімізатори — це нижні власні вектори L. На практиці перевагу надають нормалізованому лапласіану, оскільки він виправляє сильно різні ступені вузлів:

Вектор Фідлера та розрізи графа

L є додатно напівозначеною, тому всі її власні значення ≥ 0, а найменше з них завжди дорівнює 0 з власним вектором 1 (постійним) — для зв'язного графа рівно одне нульове власне значення. Друге за величиною власне значення λ₂ та відповідний йому власний вектор, вектор Фідлера, кодують найкращу «бісекцію» графа: точки з додатним значенням у векторі Фідлера утворюють одну сторону розрізу з малою вагою, а з від'ємним — іншу.

Нормалізований розріз і трюк релаксації

Формально ми хочемо розбити граф на k груп, мінімізуючи сумарну вагу ребер, розрізаних між групами, нормалізовану за розміром груп, щоб оптимізатор не міг просто ізолювати один вузол-викид (Ncut, Shi & Malik, 2000). Точне розв'язання цієї задачі NP-складне — це дискретна комбінаторна задача. Трюк полягає в тому, щоб релаксувати дискретне обмеження належності до кластера ±1 у неперервні дійсні значення, що перетворює мінімізацію Ncut на:

Релаксований розв'язок — це саме власні вектори узагальненої задачі Lx = λDx (еквівалентно, власні вектори L_rw). Округлення неперервного розв'язку у вигляді власних векторів назад до дискретних міток кластерів — зазвичай простим k-means у просторі власних векторів — дає наближений, але зазвичай чудовий розподіл за Ncut.

Алгоритм на JavaScript

Об'єднуючи все разом: будуємо граф подібності, обчислюємо перші k власних векторів нормалізованого лапласіана, складаємо їх у стовпці, щоб отримати вкладення n×k, потім запускаємо k-means на рядках цього вкладення.

function spectralClustering(points, k, sigma = 1.0, kNN = 10) {
  const n = points.length;
  const W = buildKnnSimilarityGraph(points, kNN, sigma); // розріджені ваги n×n
  const D = W.map(row => row.reduce((a, b) => a + b, 0));

  // Симетричний нормалізований лапласіан: L_sym = I - D^-1/2 W D^-1/2
  const Lsym = identity(n).map((row, i) =>
    row.map((_, j) => (i === j ? 1 : 0) − W[i][j] / Math.sqrt(D[i] * D[j]))
  );

  // k найменших власних векторів (окрім тривіального постійного)
  const { eigenvectors } = symmetricEigenDecomposition(Lsym);
  const embedding = eigenvectors.slice(0, k); // k найменших, стовпці

  // Нормалізація рядків (трюк Ng-Jordan-Weiss), потім кластеризація k-means
  const rows = transposeAndNormalizeRows(embedding, n, k);
  return kMeans(rows, k);
}

Вибір k: евристика власного розриву

На відміну від k-means, спектральна кластеризація дає обґрунтований спосіб обрати k без окремого перебору silhouette-метрики: побудуйте графік відсортованих власних значень λ₁ ≤ λ₂ ≤ … і знайдіть найбільший стрибок (власний розрив) — |λ_k+1 − λ_k|. Великий розрив після λ_k свідчить про k добре розділених кластерів, оскільки k власних значень скупчені біля нуля, а решта різко відскакують.

Де спектральна кластеризація перемагає

Справжня сила спектральної кластеризації в тому, що вона майже не робить припущень про форму кластерів — лише про зв'язність графа — і саме тут центроїдні методи на кшталт k-means зазнають невдачі.

• Сегментація зображень: оригінальне застосування Ncut Ши-Малика — пікселі як вузли, подібність яскравості/текстури як ребра.
• Виявлення спільнот: пошук тісно пов'язаних груп у соціальних або цитатних мережах.
• Ноконвуклі кластери: концентричні кільця, спіралі та переплетені півмісяці, які повністю ламають k-means.
• Зниження розмірності: саме вкладення власних векторів (Laplacian Eigenmaps) використовується як техніка навчання многовидів окремо від кластеризації.
• Сегментація мовлення та аудіо: конвеєри діаризації мовців часто кластеризують графи подібності ембеддінгів спектрально.