Spectral Clustering | จำแนกผ่านเวกเตอร์ลาปลาซเชียน

ภาพรวมเชิงสัญชาติญาณ #

สร้างกราฟที่โหนดคือจุดข้อมูล ส่วนคือน้ำหนักความคล้าย พื้นที่ที่เชื่อมแน่นมีแนวโน้มเป็นคลัสเตอร์ เวกเตอร์ลักษณะเฉพาะลำดับต่ำของ Laplacian จะเน้นทิศทางที่ตัดกราฟได้ “คุ้มค่า” เมื่อนำมาเป็นฟีเจอร์แล้วใช้ k-means จะได้ผลดีแม้รูปทรงซับซ้อน

สูตรสำคัญ #

ให้เมทริกซ์ความคล้าย \(W\), เมทริกซ์ดีกรี \(D\) และ Laplacian \(L = D - W\) แบบปกติย่อส่วน

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

เลือก \(k\) (จำนวนคลัสเตอร์) แล้วนำเวกเตอร์ลักษณะเฉพาะลำดับต่ำสุด \(k\) ตัวมาสร้างเมทริกซ์ \(U\) จากนั้น normalize แถวและใช้ k-means เพื่อให้ผลลัพธ์ใกล้กับการแก้ปัญหา normalized cut

ทดลองด้วย Python #

ตัวอย่างกับข้อมูลรูปลูกศรสองวง (make_circles)

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("Spectral clustering บนข้อมูลวงกลมซ้อน")
plt.tight_layout()
plt.show()

เอกสารอ้างอิง #