Wann kombinieren wir Dimensionsreduktion mit Clustering?

16

Ich versuche, Clustering auf Dokumentebene durchzuführen. Ich habe die Term-Document-Frequenzmatrix konstruiert und versuche, diese hochdimensionalen Vektoren mit k-Mitteln zu clustern. Anstatt direkt zu clustern, habe ich zuerst die LSA-Singularvektorzerlegung (Latent Semantic Analysis) angewendet, um die U, S, Vt-Matrizen zu erhalten, eine geeignete Schwelle unter Verwendung des Geröllplots ausgewählt und Clusterbildung auf die reduzierten Matrizen angewendet (speziell Vt, weil es gibt mir eine konzeptdokument-information, die mir gute ergebnisse zu bringen schien.

Ich habe gehört, dass einige Leute sagten, SVD (Singular Vector Decomposition) sei Clustering (unter Verwendung von Cosinus-Ähnlichkeitsmessungen usw.) und nicht sicher waren, ob ich k-means auf die Ausgabe von SVD anwenden könnte. Ich dachte, es wäre logisch korrekt, weil SVD eine Technik zur Reduzierung der Dimensionalität ist und mir eine Reihe neuer Vektoren liefert. k-means hingegen nimmt die Anzahl der Cluster als Eingabe und teilt diese Vektoren in die angegebene Anzahl von Clustern auf. Ist dieses Verfahren fehlerhaft oder gibt es Möglichkeiten, dies zu verbessern? Irgendwelche Vorschläge?

clustering pca dimensionality-reduction text-mining svd Legende
quelle
gute Frage. persönlich habe ich über diese Sachen nachgedacht. aber ich habe keine gute Antwort.
Suncoolsu
1
Es gibt Methoden, die gleichzeitig Dimensionsreduktion und Clustering durchführen. Diese Verfahren streben eine optimal gewählte niedrigdimensionale Darstellung an, um die Identifizierung von Clustern zu erleichtern. Siehe zum Beispiel clustrd package in R und die zugehörigen Referenzen.
Nat

Antworten:

6

Dies ist keineswegs eine vollständige Antwort. Die Frage, die Sie sich stellen sollten, lautet: "Welche Abstände werden bei der Dimensionsreduzierung eingehalten?". Da Clustering-Algorithmen wie K-means nur für Entfernungen verwendet werden, ist die richtige Entfernungsmetrik (theoretisch) die Entfernungsmetrik, die durch die Dimensionsreduktion erhalten bleibt. Auf diese Weise kann der Schritt der Dimensionsreduzierung als eine rechnerische Abkürzung zum Clustering der Daten in einem Raum mit niedrigeren Dimensionen angesehen werden. (auch um lokale Minima usw. zu vermeiden)

Es gibt hier viele Feinheiten, die ich nicht zu verstehen vorgebe (lokale Entfernungen vs. globale Entfernungen, wie relative Entfernungen verzerrt sind usw.), aber ich denke, dies ist die richtige Richtung, um über diese Dinge theoretisch nachzudenken.

gabgoh
quelle
+1 Das ist eine sehr interessante Einstellung zu dieser Frage. Kann in diesem Fall Euklid als eine solche Metrik betrachtet werden? Wenn sich die Dimensionalität verringert, werden die Punkte in einen Raum mit niedrigeren Dimensionen projiziert, was jedoch bedeuten könnte, dass der Begriff der Distanz verloren gehen kann. Es fällt mir schwer zu sehen, wie mit solchen Reduzierungen Abstände eingehalten werden können.
Legende
1
Ich denke, diese Antwort ist im Grunde richtig. Sie möchten etwas Einbettung in einem kleineren Raum finden, der Abstände beibehält (für etwas Begriff des Abstandes). Zwei gute Algorithmen zum Auschecken sind Isomap und Local-Linear Embedding . Die "Nachbarschaftsbewahrung" scheint ein guter Ansatz zu sein, wenn Ihr Ziel die Clusterbildung ist.
Stumpy Joe Pete
5

Als Antwort auf Ihren Titel "Wann kombinieren wir Dimensionsreduzierung mit Clustering?" eher als die vollständige Frage. Ein möglicher Grund liegt auf der Hand: Wenn wir gegen Ausreißer vorgehen wollen. K bedeutet, dass Algo, wenn es keinen Hinweis auf anfängliche Zentren gibt, k am weitesten auseinander liegende Punkte in der Wolke als anfängliche Zentren annimmt. Richtig, dies sind wahrscheinlich Ausreißer. Durch die PCA-Vorbehandlung werden Ausreißer neutralisiert, die entlang der Junior-Komponenten liegen, indem sie auf die wenigen Senior-Komponenten projiziert werden, die in der PCA verbleiben.

ttnphns
quelle