Φασματική Ομαδοποίηση

Ενημέρωση 2025-11-05 Ανάγνωση 2 λεπτά

Σύνοψη

Η φασματική ομαδοποίηση χρησιμοποιεί το φάσμα (ιδιοτιμές/ιδιοδιανύσματα) ενός γράφου ομοιότητας για να ενσωματώσει τα δεδομένα σε έναν χώρο όπου ο k-means μπορεί εύκολα να διαχωρίσει τις συστάδες.
Χειρίζεται μη γραμμικά διαχωρίσιμες δομές (π.χ. ομόκεντρους κύκλους, μισοφέγγαρα) αποτυπώνοντας τη συνδεσιμότητα αντί της ωμής ευκλείδειας απόστασης.
Βασικές υπερπαράμετροι περιλαμβάνουν τον ορισμό συγγένειας (rbf, γράφος πλησιέστερων γειτόνων, cosine), την παράμετρο κλίμακας (gamma ή n_neighbors) και τη στρατηγική ανάθεσης ετικετών.
Μετά τον υπολογισμό των πρώτων (k) ιδιοδιανυσμάτων του κανονικοποιημένου Λαπλασιανού, κανονικοποιήστε τις γραμμές τους και εκτελέστε k-means για να λάβετε ετικέτες συστάδων.

Εισαγωγή #

Αυτή η μέθοδος πρέπει να ερμηνεύεται μέσα από τις υποθέσεις της, τις συνθήκες δεδομένων και τον τρόπο με τον οποίο οι επιλογές παραμέτρων επηρεάζουν τη γενίκευση.

Αναλυτική Επεξήγηση #

1. Επισκόπηση #

Δεδομένων σημείων δεδομένων (x_i), δημιουργούμε έναν πίνακα συγγένειας (W) του οποίου οι καταχωρήσεις αντικατοπτρίζουν ανά ζεύγος ομοιότητα. Ο (μη κανονικοποιημένος) Λαπλασιανός γράφου είναι

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

Η φασματική ομαδοποίηση συνήθως χρησιμοποιεί τον συμμετρικό κανονικοποιημένο Λαπλασιανό

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

Πάρτε τα (k) ιδιοδιανύσματα που σχετίζονται με τις μικρότερες ιδιοτιμές του (L_{\mathrm{sym}}), στοιβάξτε τα στον πίνακα (U), κανονικοποιήστε κάθε γραμμή και εκτελέστε k-means σε αυτές τις γραμμές. Οι αναθέσεις που προκύπτουν μεταφράζονται πίσω στα αρχικά δείγματα.

2. Παράδειγμα σε Python #

 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 result")
plt.tight_layout()
plt.show()

Παράδειγμα φασματικής ομαδοποίησης

3. Πρακτικές σημειώσεις #

Για αραιούς γράφους, χρησιμοποιήστε affinity="nearest_neighbors" και ρυθμίστε το n_neighbors.
Η assign_labels="cluster_qr" μπορεί να είναι πιο σταθερή από τον προεπιλεγμένο k-means για ενσωματώσεις υψηλής διαστασιμότητας.
Πάντα κανονικοποιείτε τα χαρακτηριστικά πριν από τον υπολογισμό ομοιοτήτων, διαφορετικά οι κλίμακες gamma/αποστάσεων γίνονται χωρίς νόημα.

4. Αναφορές #

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