Wenn k-means Clustering eine Form der Gaußschen Mischungsmodellierung ist, kann es verwendet werden, wenn die Daten nicht normal sind?

Ich lese Bishop über den EM-Algorithmus für GMM und die Beziehung zwischen GMM und k-means.

In diesem Buch heißt es, dass k-means eine schwer zuzuordnende Version von GMM ist. Ich frage mich, ob dies bedeutet, dass ich k-means nicht verwenden kann (oder zumindest nicht verwenden kann), wenn die Daten, die ich zu gruppieren versuche, nicht Gaußsch sind. Was ist zum Beispiel, wenn es sich bei den Daten um Bilder handgeschriebener Ziffern handelt, die aus 8 × 8 Pixeln mit dem Wert 0 oder 1 bestehen (und davon ausgehen, dass sie unabhängig sind, sodass es sich um eine Mischung aus Bernoulli handeln sollte)?

Ich bin ein bisschen verwirrt und werde alle Gedanken zu schätzen wissen.

clustering data-mining k-means gaussian-mixture eddie.xie
quelle

Wenn Sie fragen, ob es gültig ist, ein k-Means-Clustering für nicht normale Daten durchzuführen, lautet die Antwort "Ja", wenn angenommen wird, dass die Daten kontinuierlich sind. Binärdaten sind nicht kontinuierlich. Einige Leute machen k-means mit solchen Daten, was heuristisch zulässig, aber theoretisch ungültig ist.

TTNPHNS

Es gibt kein Wahrscheinlichkeitsmodell für k-means, daher gibt es keine Normalitätsannahme, die für ungültig erklärt werden könnte. (bedeutet aber nicht, dass es gut funktionieren wird)

Vermutungen

@conjectures Hmm ... Aber k-menas ist gleichbedeutend mit GMM und GMM geht von normal aus.

eddie.xie

@ttnphns Danke für deine Antwort! Wenn ich also TF-IDF verwende, um Text in Partituren zu übertragen und fortlaufend zu machen, kann ich mich dann bewerben und es ist gültig?

eddie.xie

Plötzlich wird mir klar, dass GMM eine Mischung (Summe von) ein paar Gaußschen ist und dass es in der Lage sein sollte, die Verteilung bei ausreichender Mischung auszudrücken. Selbst wenn GMM und K-Mittelwerte gleichwertig sind, bedeutet dies nicht, dass K-Mittelwerte keine nicht normalen Daten verwenden können, da GMM eine beliebige Verteilung ausdrücken kann. Ist das korrekt?

eddie.xie

Antworten:

In typischen EM-GMM-Situationen werden Varianz und Kovarianz berücksichtigt. Dies wird nicht mit k-means gemacht.

Tatsächlich ist eine der populären Heuristiken für k-means (Anmerkung: k-means ist ein Problem, kein Algorithmus) - der Lloyd-Algorithmus - im Wesentlichen ein EM-Algorithmus, der ein Schwerpunktmodell (ohne Varianz) und harte Zuweisungen verwendet.

Wenn Sie k-means style clustering (dh Varianzminimierung) durchführen, tun Sie dies

zufällig den quadratischen euklidischen Abstand minimieren, da der Varianzbeitrag von WCSS (innerhalb der Cluster-Summe der Quadrate) gleich dem quadratischen euklidischen Abstand ist
Ordnen Sie Objekte zufällig nach euklidischer Entfernung dem nächsten Cluster zu, da die sqrt-Funktion monoton ist (beachten Sie, dass der Mittelwert nicht die euklidischen Entfernungen optimiert, sondern die WCSS-Funktion).
stellen Cluster dar, die nur einen Schwerpunkt verwenden
man erhält Voronoi-Zellhaufen, dh Polygone
es funktioniert am besten mit sphärischen Clustern

{argmin}_{S} \sum_{i = 1}^{k} \sum_{x_{j} \in S_{i}} \sum_{d = 1}^{D} {(x_{j d} - μ_{i d})}^{2}

$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$

S = {S_{1} \dots S_{k}}

$S=\{S_1 \ldots S_k\}$

k

$k$

D

$D$

x_{j d}

$x_{jd}$

j

$j$

d

$d$

Es wird allgemein gesagt, dass k-means kugelförmige Cluster annimmt. Es wird auch allgemein anerkannt, dass k-Mittelwert-Cluster Voronoi-Zellen sind, dh nicht kugelförmig. Beide sind richtig und beide sind falsch. Erstens sind die Cluster keine vollständigen Voronoi-Zellen, sondern nur die bekannten Objekte darin. Es ist nicht erforderlich, den Totraum zwischen den Clustern als Teil eines Clusters zu betrachten, da ein Objekt dort das Algorithmusergebnis beeinflussen würde. Aber es ist auch nicht viel besser, es "sphärisch" zu nennen, nur weil der euklidische Abstand sphärisch ist. K-means kümmert sich nicht um die euklidische Distanz. Alles, was es ist, ist eine Heuristik, um die Abweichungen zu minimieren . Und genau das sollten Sie als k-means bezeichnen: Varianzminimierung.

Anony-Mousse
quelle

Lassen Sie mich Ihnen vorschlagen, einige Ihrer Ausdrücke ein wenig zu verfeinern - für mehr Genauigkeit. Was ist zum Beispiel zu minimize squared euclidean distanceoder minimize the variances? Es muss Wörter wie "Summe von" oder "gepoolt" geben, weil wir 2+ Cluster haben, nicht wahr?

TTNPHNS

Übrigens, da k-means die gepoolte Cluster-Summe von d ^ 2 dividiert durch die Anzahl der Objekte im jeweiligen Cluster minimiert , ist Ihr Punkt coincidentally minimize Euclidean distance, because the sqrt function is monotonegenau genommen nicht korrekt.

TTNPHNS

Die richtige Zielfunktion, für die Sie die Konvergenz nachweisen können, ist WCSS, eine Cluster-Quadratsumme . Tatsächlich minimiert es nicht die euklidischen Abstände, aber es ist auch die optimale WCSS-Zuordnung.

Anony-Mousse

Ihr Wortlaut bleibt leider zweifelhaft . Was bedeutet Begriff minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance bedeutet ? Wollen Sie damit sagen „squared d's zwischen den Objekten in Cluster minimieren erhalten , weil WCSS Abweichungen minimieren bekommen“, oder einfach „WCSS Abweichungen minimieren erhalten, die - die Abweichungen - sind euklidische Entfernungen von der Natur“? Oder noch etwas?

TTNPHNS

Offensichtlich ist k-means nur dann eine gute Wahl, wenn Sie ein Schwerpunktmodell Ihrer Daten wünschen. Wenn Sie paarweise Abstände optimieren möchten, verwenden Sie hierarchisches Clustering.

Anony-Mousse

GMM verwendet überlappende Hügel, die sich bis ins Unendliche erstrecken (aber praktisch nur für 3 Sigma zählen). Jeder Punkt erhält die Wahrscheinlichkeitswerte aller Hügel. Außerdem sind die Hügel "eiförmig" [okay, sie sind symmetrische Ellipsen ] und können unter Verwendung der vollständigen Kovarianzmatrix geneigt werden .

K-means ordnet einem einzelnen Cluster einen Punkt fest zu , sodass die Punktzahlen der anderen Cluster-Zentren ignoriert werden (implizit auf Null zurückgesetzt / egal). Die Hügel sind kugelförmige Seifenblasen. Wenn sich zwei Seifenblasen berühren, wird die Grenze zwischen ihnen zu einer flachen (Hyper-) Ebene. So wie beim Blasen eines Schaums aus vielen Seifenblasen die Blasen im Inneren nicht flach, sondern kastenförmig sind, so bilden die Grenzen zwischen vielen (Hyper-) Kugeln tatsächlich eine Voronoi-Partition des Raums. In 2D sieht dies in der Regel vage aus wie eine hexagonale Packung, denken Sie an einen Bienenstock (obwohl natürlich nicht garantiert ist, dass Voronoi-Zellen Sechsecke sind). Ein K-bedeutet Hügel ist rund und wird nicht gekippt, daher hat er weniger Darstellungskraft. Aber es ist viel schneller zu berechnen, besonders in den höheren Dimensionen.

Da K-means die euklidische Distanzmetrik verwendet, wird davon ausgegangen, dass die Dimensionen vergleichbar und gleich schwer sind. Wenn also die Dimension X Einheiten von Meilen pro Stunde hat, die von 0 bis 80 variieren, und die Dimension Y Einheiten von Pfund hat, die von 0 bis 400 variieren, und Sie Kreise in diesen XY-Raum einpassen, dann eine Dimension (und ihre Ausbreitung) wird mächtiger sein als die andere Dimension und wird die Ergebnisse überschatten. Deshalb ist es üblich die Daten bei der Verwendung von K-Mitteln normalisieren .

Sowohl GMM als auch K-means modellieren die Daten, indem sie die angegebenen Werte bestmöglich angleichen. GMM passt auf gekippte Eier und K-bedeutet passt auf ungekippte Kugeln. Die zugrunde liegenden Daten könnten jedoch beliebig geformt sein, es könnte sich um eine Spirale oder ein Picasso-Gemälde handeln, und jeder Algorithmus würde weiterhin ausgeführt und seine beste Aufnahme machen. Ob das resultierende Modell den tatsächlichen Daten ähnelt, hängt vom zugrunde liegenden physischen Prozess ab, der die Daten generiert. (Beispielsweise sind Zeitverzögerungsmessungen einseitig; passt ein Gaußscher Wert? Vielleicht.)

$R^n$ von Datenachse / Domäne Sie zu gruppieren versuchen. Ordnungsgemäße Ganzzahlzählungen lassen sich gut auf Real abbilden. Geordnete Symbole, wie z. B. Farben in einem Spektrum, sind nicht so schön. Binäre Symbole, ehn. Ungeordnete Symbole werden überhaupt nicht auf reelle Symbole abgebildet (es sei denn, Sie verwenden seit 2000 kreative neue Mathematik).

Daher wird Ihr 8x8-Binärbild im ersten Hyperquadranten als 64-dimensionaler Hyperwürfel interpretiert. Die Algorithmen verwenden dann geometrische Analogien, um Cluster zu finden. Entfernung mit K-Mitteln zeigt sich als euklidische Entfernung im 64-dimensionalen Raum. Es ist eine Möglichkeit, es zu tun.

Drachen Lord
quelle

Beachten Sie, dass beide Algorithmen implizit davon ausgehen, dass die Raumachsen an allen Punkten gleich dicht sind, sodass eine Anpassung exponentiell, logarithmisch oder sinusförmig variierender Daten in der Regel von einer Vortransformation zur erneuten Zuordnung der Daten in einen sich ungefähr linear ändernden Bereich profitiert.

DragonLord