Spectral Clustering

อัปเดต 2020-05-06 อ่าน 1 นาที

สรุป

สร้างกราฟความคล้ายของข้อมูล แล้วใช้เวกเตอร์ลักษณะเฉพาะของ Laplacian ฝังข้อมูลลงในมิติที่ต่ำกว่าก่อนค่อยทำ k-means
เหมาะกับข้อมูลโครงสร้างไม่เชิงรัศมี เช่น วงแหวนหรือรูปร่างที่คดเคี้ยว ซึ่ง k-means จัดกลุ่มได้ยาก
พารามิเตอร์สำคัญ ได้แก่ วิธีคำนวณ affinity (rbf, nearest neighbors), ค่าพารามิเตอร์ของเคอร์เนล และวิธีจัดกลุ่มหลังฝัง (assign_labels)
ต้องคำนวณค่าเฉพาะตามจำนวนคลัสเตอร์ จึงใช้หน่วยความจำและเวลามากขึ้นเมื่อจำนวนจุดเยอะ

สัญชาตญาณ #

การเข้าใจวิธีนี้ควรดูสมมติฐานของโมเดล ลักษณะข้อมูล และผลของการตั้งค่าพารามิเตอร์ต่อการทั่วไปของโมเดล

คำอธิบายโดยละเอียด #

สูตรสำคัญ #

ให้เมทริกซ์ความคล้าย $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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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()

Spectral clustering แยกข้อมูลวงกลมซ้อนได้

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

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