k-means ++ Algorithmus und Ausreißer

Es ist bekannt, dass der k-means-Algorithmus bei Ausreißern leidet. k-means ++ ist eine effektive Methode zur Initalisierung von Clusterzentren. Ich habe die PPT von den Gründern der Methode, Sergei Vassilvitskii und David Arthur http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf (Folie 28) , durchlaufen, was zeigt, dass die Cluster-Center-Initialisierung ist nicht vom Ausreißer betroffen, wie unten gezeigt.

Gemäß der k-means ++ - Methode sind die am weitesten entfernten Punkte eher die Anfangszentren. Auf diese Weise muss der Ausreißerpunkt (der Punkt ganz rechts) auch ein anfänglicher Clusterschwerpunkt sein. Was ist die Erklärung für die Figur?

Ja, der Ausreißer wird eher ausgewählt. Es gibt aber auch viel mehr Lieferanten, und die Chance, einen von ihnen auszuwählen, ist ebenfalls beträchtlich. Angenommen, Sie haben einen Ausreißer, der 10x weiter entfernt ist, dann ist es 100x wahrscheinlicher, dass er Streikposten ist als ein Ausreißer. Wenn Sie 100 Lieferanten haben, liegen die Chancen bei etwa 50%, und wenn Sie 1000 Lieferanten haben, liegt die Chance, den Ausreißer auszuwählen, bei etwa 10%.

Alles in allem würde ich sagen, dass k-means ++ wahrscheinlich eher Ausreißer als Anfangszentren auswählt (im obigen Beispiel würde es zufällig bei 1% bzw. 0,1% auswählen) und daher wahrscheinlich empfindlicher gegenüber Ausreißern (und tatsächlich) Viele Leute berichten von einer geringen Verbesserung mit k-means ++). Es macht jedoch keinen großen Unterschied: Jede k-means-Methode ist betroffen, da alle das gleiche Ziel optimieren. Die Quadratsumme ist ein Ziel, das für Ausreißer empfindlich ist, unabhängig davon, wie Sie optimieren. Aufgrund des Problems im Ziel kann die Auswahl des Ausreißers als Zentrum zu einem "besseren" Ergebnis führen . Das globale Optimum könnte so aussehen!

Dies scheint auf Folie 27 erklärt zu werden.

Sie schlagen vor, den ersten Cluster-Schwerpunkt nach dem klassischen k-Mittel zufällig auszuwählen. Aber die zweite wird anders gewählt. Wir betrachten jeden Punkt x und weisen ihm ein Gewicht zu, das dem Abstand zwischen x und dem zuerst gewählten Schwerpunkt entspricht, der auf ein Potenz-Alpha angehoben wird. Alpha kann mehrere interessante Werte annehmen.

Wenn Alpha 0 ist, haben wir den klassischen k-means-Algorithmus, da alle Punkte das Gewicht 1 haben und daher alle gleich wahrscheinlich ausgewählt werden.

Wenn Alpha unendlich ist (oder in der Praxis eine sehr große Zahl), haben wir die Methode mit dem weitesten Punkt, bei der der am weitesten entfernte Punkt ein sehr großes Gewicht hat, was es sehr wahrscheinlich macht, dass er ausgewählt wird. Wie auf den Folien 24-26 zu sehen ist, ist es daher empfindlich gegenüber Ausreißern.

Sie schlagen vor, Alpha auf 2 zu setzen. Dies gibt eine gute Wahrscheinlichkeit, Punkte weiter vom ersten ausgewählten Schwerpunkt entfernt auszuwählen, aber nicht automatisch den am weitesten entfernten. Dies gibt ihrer Methode k-means ++ die nette Eigenschaft, weniger empfindlich gegenüber Ausreißern zu sein.