Clustering spektral

Basic

Clustering spektral | Pengelompokan berbasis eigenvektor

Dibuat: Pembaruan terakhir: Waktu baca: 2 menit
まとめ
  • Clustering spektral membangun graf kesamaan dan menggunakan eigenvektor laplasian untuk memetakan data sebelum menjalankan k-means.
  • Cocok untuk pola non-linear seperti cincin konsentris atau bentuk bulan sabit karena mempertimbangkan konektivitas.
  • Parameter penting: affinity (rbf, nearest_neighbors, dll.), gamma/n_neighbors, serta assign_labels.
  • Setelah mengambil (k) eigenvektor teratas dari laplasian ternormalisasi, normalisasikan barisnya dan jalankan k-means untuk mendapatkan label.

1. Gambaran umum #

Dengan matriks afinitas (W) dan derajat (D), laplasian graf adalah

$$ L = D - W, \qquad D = \mathrm{diag}(d_i),; d_i = \sum_j W_{ij}. $$

Versi normalisasi simetri:

$$ L_{\mathrm{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}. $$

Ambil (k) eigenvektor bernilai eigen terkecil, bentuk matriks (U), normalisasikan setiap baris, lalu jalankan k-means untuk memperoleh klaster.

2. Contoh Python #

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering

X, _ = make_circles(n_samples=500, factor=0.4, noise=0.05, random_state=0)

model = SpectralClustering(
    n_clusters=2,
    affinity="rbf",
    gamma=50,
    assign_labels="kmeans",
    random_state=0,
)
labels = model.fit_predict(X)

plt.figure(figsize=(6, 5))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="coolwarm", s=20)
plt.title("Clustering spektral")
plt.tight_layout()
plt.show()

Contoh clustering spektral

3. Catatan praktis #

  • Untuk graf jarang gunakan affinity="nearest_neighbors" dan sesuaikan n_neighbors.
  • assign_labels="cluster_qr" bisa lebih stabil ketimbang k-means pada embedding berdimensi tinggi.
  • Lakukan standardisasi fitur sebelum menghitung kemiripan supaya skala gamma bermakna.

4. Referensi #

  • Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE TPAMI.
  • Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. NeurIPS.
  • scikit-learn developers. (2024). Spectral clustering. https://scikit-learn.org/stable/modules/clustering.html#spectral-clustering