und Eigenvektoren sind Schlüsselkonzepte in der linearen Algebra, die auch in der Datenwissenschaft und im maschinellen Lernen eine wichtige Rolle spielen. Zuvor haben wir diskutiert, wie eine Dimensionsreduktion mit Eigenwerten und Eigenvektoren der Kovarianzmatrix durchgeführt werden kann.
Heute werden wir eine weitere interessante Anwendung besprechen: Wie Eigenwerte und Eigenvektoren verwendet werden können, um spektrales Clustering durchzuführen, was bei komplexen Clusterstrukturen intestine funktioniert.
In diesem Artikel untersuchen wir, wie Eigenwerte und Eigenvektoren spektrales Clustering ermöglichen und warum diese Methode herkömmliche Okay-Mittelwerte übertreffen kann.
Wir beginnen mit einer einfachen Visualisierung, die Ihnen die Bedeutung der spektralen Clusterbildung zeigt und Sie motiviert, weiter zu lernen, wie spektrale Clusterbildung mit Eigenwerten und Eigenvektoren durchgeführt werden kann.
Motivation für Spectral Clustering
Eine gute Möglichkeit, spektrales Clustering zu erlernen, besteht darin, es mit einem herkömmlichen Clustering-Algorithmus wie Okay-Means für einen Datensatz zu vergleichen, bei dem Okay-Means Schwierigkeiten hat, eine gute Leistung zu erbringen.
Hier verwenden wir einen künstlich generierten Zwei-Mond-Datensatz, in dem die Cluster gekrümmt sind. Das Scikit-lernen make_moons Der Algorithmus generiert zwei Monde im zweidimensionalen Raum. Dann verwenden wir Scikit-learn KMeans Und SpectralClustering Algorithmen zur Durchführung von Okay-Means und spektralem Clustering. Abschließend vergleichen wir die Cluster-Visualisierungen.
Monddaten erstellen
# Make moon information
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=400, noise=0.05,
random_state=0)
plt.determine(figsize=(4.2, 3))
plt.scatter(X(:,0), X(:,1), s=20)
plt.title("Authentic Moon Information")
plt.savefig("Moon information.png")
Der ursprüngliche Datensatz enthält zwei gekrümmte Clusterstrukturen namens Monde. Deshalb nennen wir es Monddaten.
Anwenden von Okay-Mitteln auf die Monddaten
# Apply Okay-means
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2, random_state=0)
# Predict cluster index for every information level
labels_kmeans = kmeans.fit_predict(X)
# Visualize Clusters
plt.determine(figsize=(4.2, 3))
plt.scatter(X(:,0), X(:,1), c=labels_kmeans, s=20)
plt.title("Okay-Means Clustering")
plt.savefig("Okay-means.png")
Okay-Means gruppiert die Monddaten oft falsch (die Datenpunkte werden falsch gemischt).
Anwenden von spektralem Clustering auf die Monddaten
# Apply spectral clustering
from sklearn.cluster import SpectralClustering
spectral = SpectralClustering(n_clusters=2,
affinity='nearest_neighbors',
random_state=0)
# Predict cluster index for every information level
labels_spectral = spectral.fit_predict(X)
# Visualize Clusters
plt.determine(figsize=(4.2, 3))
plt.scatter(X(:,0), X(:,1), c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral.png")
Jetzt sind die Datenpunkte korrekt den Monden zugeordnet, die den Originaldaten ähneln. Spektrales Clustering funktioniert intestine bei komplexen Clusterstrukturen. Dies liegt daran, dass die Eigenvektoren der Laplace-Matrix die Erkennung komplexer Clusterstrukturen ermöglichen.
Bisher haben wir spektrales Clustering mithilfe der integrierten Funktion implementiert SpectralClustering Algorithmus in Scikit-learn. Als Nächstes erfahren Sie, wie Sie spektrales Clustering von Grund auf implementieren. Dies wird Ihnen helfen zu verstehen, wie Eigenwerte und Eigenvektoren hinter den Kulissen des Algorithmus funktionieren.
Was ist spektrales Clustering?
Spektrales Clustering gruppiert Datenpunkte anhand ihrer Ähnlichkeiten statt anhand von Entfernungen. Dies ermöglicht es, nichtlineare, komplexe Clusterstrukturen aufzudecken, ohne den Annahmen des traditionellen k-Means-Clusterings zu folgen.
Die Instinct hinter der Durchführung der spektralen Clusterbildung ist folgende:
Schritte zur Durchführung der spektralen Clusterbildung
- Holen Sie sich Daten
- Bauen Sie die Ähnlichkeit auf Matrix
- Erstellen Sie die Gradmatrix
- Erstellen Sie die Laplace-Matrix (Graph Laplace)
- Finden Sie Eigenwerte und Eigenvektoren der Laplace-Matrix. Eigenvektoren offenbaren die Clusterstruktur (wie Datenpunkte gruppiert werden) und fungieren als neue Merkmale, und Eigenwerte geben die Stärke der Clustertrennung an
- Wählen Sie die wichtigsten Eigenvektoren aus, um die Daten in eine niedrigere Dimension einzubetten (Dimensionalitätsreduzierung).
- Anwenden von Okay-Means auf den neuen Characteristic-Area (Clustering)
Spektrales Clustering kombiniert Dimensionsreduktion und Okay-Means-Clustering. Wir betten die Daten in einen niedrigerdimensionalen Raum ein (wo Cluster leichter zu trennen sind) und führen dann Okay-Means-Clustering für den neuen Merkmalsraum durch. Zusammenfassend lässt sich sagen, dass Okay-Means-Clustering im ursprünglichen Merkmalsraum funktioniert, während Spektral-Clustering im neuen reduzierten Merkmalsraum funktioniert.
Spectral Clustering implementieren – Schritt für Schritt
Wir haben die Schritte zur Durchführung einer spektralen Clusterbildung mit Eigenwerten und Eigenvektoren der Laplace-Matrix zusammengefasst. Lassen Sie uns diese Schritte mit Python implementieren.
1. Daten abrufen
Wir verwenden die gleichen Daten wie zuvor.
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=400, noise=0.05,
random_state=0)2. Erstellen Sie die Ähnlichkeitsmatrix (Affinitätsmatrix).
Spektrales Clustering gruppiert Datenpunkte basierend auf ihren Ähnlichkeiten. Daher müssen wir die Ähnlichkeit zwischen Datenpunkten messen und diese Werte in eine Matrix aufnehmen. Diese Matrix heißt Ähnlichkeitsmatrix (W). Hier messen wir die Ähnlichkeit mit a Gaußscher Kernel.
Wenn ja N Anzahl der Datenpunkte, die Kind von W Ist (n, n). Jeder Wert stellt die Ähnlichkeit zwischen zwei Datenpunkten dar. Höhere Werte in den Matrix-Mittelpunkten sind ähnlicher.
from sklearn.metrics.pairwise import rbf_kernel
W = rbf_kernel(X, gamma=20)3. Erstellen Sie die Gradmatrix
Die Gradmatrix (D) enthält die Summe der Ähnlichkeiten für jeden Knoten. Dies ist eine Diagonalmatrix und jeder Diagonalwert zeigt die Gesamtähnlichkeit dieses Punktes mit allen anderen Punkten. Alle nicht diagonalen Elemente sind Null. Die Kind der Gradmatrix ist ebenfalls (n, n).
import numpy as np
D = np.diag(np.sum(W, axis=1))np.sum(W, axis=1)summiert jede Zeile der Ähnlichkeitsmatrix.
4. Erstellen Sie die Laplace-Matrix
Die Laplace-Matrix (L) stellt die Struktur des Ähnlichkeitsgraphen dar, wobei Knoten jeden Datenpunkt darstellen und Kanten ähnliche Punkte verbinden. Daher wird diese Matrix auch als Matrix bezeichnet Graph Laplace und ist wie folgt definiert.
In Python ist es so
L = D - WD – W für L stellt mathematisch sicher, dass spektrales Clustering Gruppen von Datenpunkten findet, die innerhalb der Gruppe stark, aber schwach mit anderen Gruppen verbunden sind.
Die Laplace-Matrix (L) ist ebenfalls eine (n, n) quadratische Matrix. Diese Eigenschaft ist wichtig für L da die Eigenzerlegung nur für quadratische Matrizen definiert ist.
5. Eigenzerlegung der Laplace-Matrix
Eigenzerlegung der Laplace-Matrix ist der Prozess der Zerlegung (Faktorisierung) dieser Matrix Eigenwerte Und Eigenvektoren (ref: Eigenzerlegung einer Kovarianzmatrix mit NumPy)
Wenn die Laplace-Matrix (L) hat N Eigenvektoren können wir es wie folgt zerlegen:
Wo:
- X = Matrix der Eigenvektoren
- Λ = Diagonalmatrix der Eigenwerte
Die Matrizen X Und Λ lässt sich wie folgt darstellen:
Die Vektoren x1, x2 Und x3 sind Eigenvektoren und λ1, λ2 Und λ3 sind ihre entsprechenden Eigenwerte.
Die Eigenwerte und Eigenvektoren kommen paarweise vor. Ein solches Paar ist als bekannt Eigenpaar. Additionally, Matrix L kann mehrere Eigenpaare haben (siehe: Eigenzerlegung einer Kovarianzmatrix mit NumPy)
Die folgende Eigenwertgleichung zeigt die Beziehung zwischen L und eines seiner Eigenpaare.
Wo:
- L = Laplace-Matrix (sollte eine quadratische Matrix sein)
- X = Eigenvektor
- λ = Eigenwert (Skalierungsfaktor)
Berechnen wir alle Eigenpaare der Laplace-Matrix.
eigenvalues, eigenvectors = np.linalg.eigh(L)6. Wählen Sie die wichtigsten Eigenvektoren aus
Beim spektralen Clustering verwendet der Algorithmus die kleinsten Eigenvektoren der Laplace-Matrix. Wir müssen additionally die kleinsten auswählen Eigenvektoren Matrix.
Den kleinsten Eigenwerten entsprechen die kleinsten Eigenvektoren. Der acht() Die Funktion gibt Eigenwerte und Eigenvektoren in aufsteigender Reihenfolge zurück. Wir müssen uns additionally die ersten Werte von ansehen Eigenwerte Vektor.
print(eigenvalues)
Wir achten auf den Unterschied zwischen aufeinanderfolgenden Eigenwerten. Dieser Unterschied ist bekannt als Eigenlücke. Wir wählen den Eigenwert aus, der die Eigenlücke maximiert. Es stellt die Anzahl der Cluster dar. Diese Methode heißt Eigenlücken-Heuristik.
Gemäß der Eigenlücken-Heuristik die optimale Anzahl von Clustern ok wird an dem Punkt ausgewählt, an dem der größte Sprung zwischen aufeinanderfolgenden Eigenwerten auftritt.
Falls vorhanden ok Es wird sehr kleine Eigenwerte geben ok Cluster! In unserem Beispiel deuten die ersten beiden kleinen Eigenwerte auf zwei Cluster hin, was genau das ist, was wir erwarten. Dies ist die Rolle von Eigenwerten bei der spektralen Clusterbildung. Sie sind sehr nützlich, um die Anzahl der Cluster und die kleinsten Eigenvektoren zu bestimmen!
Wir wählen die ersten beiden Eigenvektoren aus, die diesen kleinen Eigenwerten entsprechen.
ok = 2
U = eigenvectors(:, :ok)
Diese beiden Eigenvektoren in der Matrix U stellen einen neuen Characteristic-Area namens dar spektrale Einbettung, wo Cluster linear trennbar werden. Hier ist die Visualisierung der spektralen Einbettung.
import matplotlib.pyplot as plt
plt.determine(figsize=(4.2, 3))
plt.scatter(U(:,0), U(:,1), s=20)
plt.title("Spectral Embedding")
plt.xlabel("Eigenvector 1")
plt.ylabel("Eigenvector 2")
plt.savefig("Spectral embedding.png")
Dieses Diagramm zeigt, wie Eigenvektoren die Originaldaten in einen neuen Raum transformieren, in dem Cluster linear trennbar werden.
7. Wenden Sie Okay-Mittel auf die spektrale Einbettung an
Jetzt können wir einfach Okay-Means bei der spektralen Einbettung (neuer Eigenvektorraum) anwenden, um Cluster-Labels zu erhalten, und diese Labels dann den Originaldaten zuweisen, um Cluster zu erstellen. Okay-means funktioniert hier intestine, da Cluster im neuen Eigenvektorraum linear trennbar sind.
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=ok)
labels_spectral = kmeans.fit_predict(U)
# U represents spectral embedding
plt.determine(figsize=(4.2, 3))
# Assign cluster labels to unique information
plt.scatter(X(:,0), X(:,1), c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral Handbook.png")
Das ist das Gleiche, was wir von der Scikit-learn-Model erhalten haben!
Den richtigen Wert für Gamma wählen
Wenn wir die Ähnlichkeitsmatrix erstellen oder die Ähnlichkeit mithilfe eines Gaußschen Kernels messen, müssen wir den richtigen Wert für definieren Gamma Hyperparameter, der steuert, wie schnell die Ähnlichkeit mit dem Abstand zwischen Datenpunkten abnimmt.
from sklearn.metrics.pairwise import rbf_kernel
W = rbf_kernel(X, gamma=?)Bei kleinen Gammawerten nimmt die Ähnlichkeit langsam ab und viele Punkte erscheinen ähnlich. Dies führt daher zu falschen Clusterstrukturen.
Bei großen Gammawerten nimmt die Ähnlichkeit sehr schnell ab und nur sehr nahe beieinander liegende Punkte sind verbunden. Daher werden Cluster stark getrennt.
Bei mittleren Werten erhalten Sie ausgewogene Cluster.
Es ist besser, mehrere Werte auszuprobieren, z. B. 0,1, 0,5, 1, 5, 10, 15, und die Clusterergebnisse zu visualisieren, um den besten auszuwählen.
Schlussgedanken
Beim spektralen Clustering wird ein Datensatz als Diagramm und nicht als Sammlung von Punkten dargestellt. In diesem Diagramm ist jeder Datenpunkt ein Knoten und die Linien (Kanten) zwischen Knoten definieren, wie ähnliche Punkte miteinander verbunden sind.
Der spektrale Clustering-Algorithmus benötigt diese Diagrammdarstellung in mathematischer Kind. Aus diesem Grund haben wir eine Ähnlichkeitsmatrix (Affinitätsmatrix) (W) erstellt. Jeder Wert in dieser Matrix misst die Ähnlichkeit zwischen Datenpunkten. Große Werte in der Matrix bedeuten, dass zwei Punkte sehr ähnlich sind, während kleine Werte bedeuten, dass zwei Punkte sehr unterschiedlich sind.
Als nächstes haben wir die Gradmatrix (D) erstellt, eine Diagonalmatrix, in der jeder Diagonalwert die Gesamtähnlichkeit dieses Punktes mit allen anderen Punkten anzeigt.
Mithilfe der Gradmatrix und der Ähnlichkeitsmatrix haben wir die Laplace-Matrix des Graphen erstellt, die die Struktur des Graphen erfasst und für die spektrale Clusterbildung wesentlich ist.
Wir haben die Eigenwerte und Eigenvektoren von berechnet Laplace-Matrix. Die Eigenwerte helfen dabei, die beste Anzahl an Clustern und die kleinsten Eigenvektoren auszuwählen. Sie zeigen auch die Stärke der Clustertrennung an. Die Eigenvektoren offenbaren die Clusterstruktur (Clustergrenzen oder wie Datenpunkte gruppiert werden) und werden verwendet, um einen neuen Merkmalsraum zu erhalten, in dem stark verbundene Punkte im Diagramm in diesem Raum nahe beieinander liegen. Cluster lassen sich leichter trennen und Okay-Means funktioniert im neuen Raum intestine.
Hier ist der vollständige Arbeitsablauf des spektralen Clusterings.
Datensatz → Ähnlichkeitsdiagramm → Laplace-Diagramm → Eigenvektoren → Cluster
Dies ist das Ende des heutigen Artikels.
Bitte lassen Sie mich wissen, wenn Sie Fragen oder Suggestions haben.
Wir sehen uns im nächsten Artikel. Viel Spaß beim Lernen!
Entworfen und geschrieben von:
Rukshan Pramoditha
2025–03–08