Woher weiß ich, dass mein k-means Clustering-Algorithmus unter dem Fluch der Dimensionalität leidet?

12

Ich glaube, dass der Titel dieser Frage alles sagt.

Mathieu
quelle
3
Ich denke, Sie müssen uns klarstellen, was Sie unter einem Symptom verstehen.
Mdewey
Wenn es sich bei "Symptom" um eine Hand-Verzicht-Version von "Test" handelt, können Sie möglicherweise Teilstichproben Ihres Datensatzes - möglicherweise 66% der Stichprobengröße - entnehmen, Ihre Analyse durchführen (in Ihrem Fall km-Werte) und dann sehen, wie nervös es ist Die Ergebnisse sind. Sie können beispielsweise sehen, wie oft bestimmte Beobachtungen demselben Cluster zugewiesen werden. Andererseits ist es die Mühe vielleicht nicht wert. Wenn Sie sich Sorgen über die Möglichkeit eines Dimensionsproblems machen, haben Sie wahrscheinlich eines. Sie könnten andere Clustering-Ansätze in Betracht ziehen, die die Dimensionalität etwas reduzieren.
generic_user
@ Generic_user Wenn dieser Kommentar eine Antwort wäre, würde ich es als akzeptierte Antwort zählen :)
Mathieu
1
Diese Frage ist klar genug, um offen zu bleiben, IMO.
Gung - Reinstate Monica
1
Oft genug stoßen Sie früher auf viel schwerwiegendere Probleme mit k-Mitteln als auf den "Fluch der Dimensionalität". k-means kann mit 128 dimensionalen Daten (z. B. SIFT-Farbvektoren) arbeiten, wenn die Attribute gutmütig sind. Bis zu einem gewissen Grad funktioniert es manchmal sogar mit 10000-dimensionalen Textdaten. Das theoretische Modell des Fluches gilt niemals für reale Daten. Die größeren Probleme sind unvergleichliche Funktionen, Sparsamkeit und die Unfähigkeit, das Ergebnis zu visualisieren und zu überprüfen.
Hat aufgehört - Anony-Mousse

Antworten:

18

Es hilft, darüber nachzudenken, was der Fluch der Dimensionalität ist. Es gibt einige sehr gute Themen im Lebenslauf, die es wert sind, gelesen zu werden. Hier ist ein Ausgangspunkt: Erklären Sie einem Kind den „Fluch der Dimensionalität“ .

Ich stelle fest, dass Sie daran interessiert sind, wie dies für Mittel-Clustering gilt. Es ist zu beachten, dass Mittel eine Suchstrategie sind, um (nur) den quadratischen euklidischen Abstand zu minimieren. Vor diesem Hintergrund lohnt es sich darüber nachzudenken, wie sich die euklidische Distanz auf den Fluch der Dimensionalität bezieht (siehe: Warum ist die euklidische Distanz in hohen Dimensionen keine gute Metrik? ). kk

Die kurze Antwort dieser Threads lautet, dass das Volumen (die Größe) des Raums im Verhältnis zur Anzahl der Dimensionen unglaublich schnell zunimmt. Sogar Dimensionen (was mir nicht sehr "hochdimensional" erscheint) können den Fluch hervorrufen. Wenn Ihre Daten gleichmäßig in diesem Bereich verteilt wurden, werden alle Objekte ungefähr gleich weit voneinander entfernt. Wie @ Anony-Mousse in seiner Antwort auf diese Frage feststellt , hängt dieses Phänomen jedoch davon ab, wie die Daten im Raum angeordnet sind. Wenn sie nicht einheitlich sind, haben Sie dieses Problem nicht unbedingt. Dies führt zu der Frage, ob gleichmäßig verteilte hochdimensionale Daten überhaupt sehr häufig sind (siehe: Gibt es in realen Daten tatsächlich einen „Fluch der Dimensionalität“? ). 10

Ich würde argumentieren, dass es nicht unbedingt auf die Anzahl der Variablen (die wörtliche Dimensionalität Ihrer Daten) ankommt, sondern auf die effektive Dimensionalität Ihrer Daten. Unter der Annahme, dass Dimensionen für Mittel "zu hoch" sind, besteht die einfachste Strategie darin, die Anzahl Ihrer Features zu zählen. Wenn Sie jedoch in Bezug auf die effektive Dimensionalität denken möchten, können Sie eine Hauptkomponentenanalyse (PCA) durchführen und untersuchen, wie die Eigenwerte abfallen. Es ist durchaus üblich, dass der größte Teil der Variation in mehreren Dimensionen vorliegt (die normalerweise die ursprünglichen Dimensionen Ihres Datensatzes überschreiten). Das würde bedeuten, dass Sie weniger wahrscheinlich ein Problem mit Mitteln haben, in dem Sinne, dass Ihre effektive Dimensionalität tatsächlich viel kleiner ist. 10kk

Ein komplizierterer Ansatz wäre es, die Verteilung der paarweisen Abstände in Ihrem Datensatz gemäß den in seiner Antwort vorgeschlagenen Linien zu untersuchen, die @ hxd1011 vorschlägt . Wenn Sie sich einfache Randverteilungen ansehen, erhalten Sie einen Hinweis auf die mögliche Gleichmäßigkeit. Wenn Sie alle Variablen so normalisieren, dass sie innerhalb des Intervalls , müssen die paarweisen Abstände innerhalb des Intervalls . Stark konzentrierte Entfernungen verursachen Probleme. Auf der anderen Seite kann eine multimodale Verteilung hoffnungsvoll sein (Sie können ein Beispiel in meiner Antwort hier sehen: Wie werden sowohl binäre als auch kontinuierliche Variablen beim Clustering zusammen verwendet? ).[0, 1]][0, D.]]

Ob Mittel "funktionieren", ist jedoch immer noch eine komplizierte Frage. Unter der Annahme, dass Ihre Daten aussagekräftige latente Gruppierungen enthalten, existieren diese nicht unbedingt in allen Ihren Dimensionen oder in konstruierten Dimensionen, die die Variation maximieren (dh die Hauptkomponenten). Die Cluster könnten sich in Dimensionen mit geringerer Variation befinden (siehe: Beispiele für PCA, bei denen PCs mit geringer Varianz „nützlich“ sind ). Das heißt, Sie könnten Cluster mit Punkten haben, die auf nur wenigen Dimensionen oder auf PCs mit geringerer Variation nahe beieinander liegen und gut voneinander getrennt sind, auf PCs mit hoher Variation jedoch nicht im entferntesten ähnlich sind, was Mittel verursachen würde Um die Cluster zu ignorieren, nach denen Sie suchen, und stattdessen Faux-Cluster auszuwählen (einige Beispiele finden Sie hier:kkWie man die Nachteile von K-Mitteln versteht ).

gung - Monica wieder einsetzen
quelle
Es stellt sich heraus, dass es bereits ein Tag für vielfältiges Lernen gibt (hätte zuerst schauen müssen!). Zusammenfassend für diejenigen, die es vielleicht nicht wissen, ist die Idee, dass hochdimensionale Daten zwar in Bezug auf den gesamten Raum spärlich sind, aber auf einer Hyperfläche innerhalb dieses Raums dicht sein können.
GeoMatt22
+1 für die hervorragende Antwort. Könnten Sie bitte etwas mehr auf den Eigenwertteil eingehen? Wenn die effektive Dimensionalität gering ist, empfehlen Sie dann, PCA durchzuführen und nur die ersten paar Scores mit hohen Eigenwerten beizubehalten?
DataD'oh
@ DataD'oh, das ist sicherlich eine Möglichkeit, aber ich sage, dass du das nicht tun musst. Tatsächlich sind die Daten nicht hochdimensional (wenn nur die ersten Eigenvektoren hohe Eigenwerte haben), sodass Sie nicht unbedingt etwas tun müssen - der Fluch der Dimensionalität trifft einfach nicht zu.
Gung - Reinstate Monica
@gung Ich habe eine neue Frage gestellt . Ich hoffe es ist nicht zu trivial.
DataD'oh
7

Meine Antwort ist nicht auf K-Mittel beschränkt, sondern prüfen Sie, ob wir für entfernungsbasierte Methoden einen Fluch der Dimensionalität haben. K-means basiert auf einem Abstandsmaß (z. B. euklidischer Abstand).

N.0,5N.(N.- -1)

Wenn wir das Problem des Fluches der Dimensionalität haben, werden Sie sehen, dass diese Werte sehr nahe beieinander liegen. Dies scheint sehr kontraintuitiv zu sein, da es bedeutet, dass jeder nahe oder weit von jedem entfernt ist und das Entfernungsmaß im Grunde genommen nutzlos ist.


16xich=01xj=01(xich- -xj)2dxichdxjrunifrnorm

Hier ist die Simulation für die Dimension von 1 bis 500, die Merkmale sind gleichmäßige Verteilung von 0 bis 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}

Geben Sie hier die Bildbeschreibung ein

Haitao Du
quelle
1
P.
Amöbe
1
Ich hatte wegen einer Demonstration des euklidischen Schrumpfungsphänomens unter hohen Dimensionen gestimmt. Die Antwort zeigt jedoch nicht, dass k-Mittel unter dem Fluch leiden . Das Leiden würde bedeuten, dass in hohen Dimensionen einigermaßen gut getrennte Cluster (und nicht einheitliche Zufallsdaten wie Ihre) möglicherweise nicht so erfolgreich aufgedeckt werden wie in niedrigen Dimensionen. Sie haben dieses Thema nicht angesprochen.
ttnphns
P.
@ttnphns danke für deinen Kommentar und deine Gegenstimme. Ich werde sehen, ob ich einen Absatz hinzufügen kann, um die Auswirkungen auf k Mittelwerte zu diskutieren.
Haitao Du