Data Mining, k-means ++ ist ein Algorithmus für die Auswahl der Anfangswerte für die k-Mittel-Cluster-Algorithmus. Es wurde 2007 von David Arthur und Sergej Vassilvitskii vorgeschlagen, als Näherungsalgorithmus für den NP-schwer k-means Problem, einen Weg zur Vermeidung der manchmal schlecht Clusterings von der Norm festgestellt k-means-Algorithmus. Es ist ähnlich wie die erste von drei Aussaat Verfahren vorgeschlagen, in selbständiger Arbeit, im Jahr 2006 von Rafail Ostrovsky, Yuval Rabani, Leonard Schulman und Chaitanya Swamy.

Hintergrund

Die k-means Problem ist, zu finden Clusterzentren, die den innerKlasse Varianz zu minimieren, dh die Summe der quadrierten Distanzen von jedem Datenpunkt an seiner Clusterzentrum gebündelt. Obwohl der Suche nach einer genauen Lösung für das k-means Problem für beliebige Eingangs NP-schwer ist, die Standard-Ansatz zu finden, eine Näherungslösung ist weit verbreitet und häufig findet vernünftige Lösungen schnell.

Jedoch weist das k-means-Algorithmus mindestens zwei Haupt theoretischen Mängel auf:

• Erstens hat es sich gezeigt, dass der schlechteste Fall Laufzeit des Algorithmus ist super-Polynom im Eingangsgröße.
• Zweitens stellte die Approximation beliebig schlecht in Bezug auf die Zielfunktion im Vergleich zu der optimalen Clusterbildung sein.

Die k-means ++ Algorithmus befasst sich mit der zweiten dieser Hindernisse durch die Angabe eines Verfahrens, um die Clusterzentren, bevor mit den Standard-k-Mittel-Optimierung Iterationen fortfahren zu initialisieren. Mit den k-means ++ Initialisierung wird der Algorithmus immer eine Lösung, die O wettbewerbsfähig optimalen k-Mittel-Lösung zu finden.

Initialisierungsalgorithmus

Die Intuition hinter diesem Ansatz ist, dass Ausbreitung der k anfänglichen Clusterzentren ist eine gute Sache: die erste Clusterzentrum gleichmäßig zufällig aus den Datenpunkten, wobei gruppiert sind, wonach jeder nachfolgende Clusterzentrum wird von den verbleibenden Datenpunkte gewählt gewählt mit Wahrscheinlichkeit proportional zu seiner quadratischen Abstand von dem Punkt engster bestehenden Clusterzentrum.

Der genaue Algorithmus ist wie folgt:

• Wählen Sie eines Zentrum einheitlich nach dem Zufallsprinzip aus den Datenpunkten.
• Für jeden Datenpunkt x, berechnen D, den Abstand zwischen x und zum nächsten Zentrum, das bereits gewählt wurde.
• Wählen Sie einen neuen Datenpunkt zufällig als neue Mitte, unter Verwendung eines gewichteten Wahrscheinlichkeitsverteilung in dem ein Punkt x mit Wahrscheinlichkeit proportional zu D. gewählt
• Wiederholen Sie die Schritte 2 und 3 bis k Zentren wurden ausgewählt.
• Nun, da die anfängliche Zentren wurden ausgewählt, gehen Sie mit Standard-k-means Clustering.

Das Seeding Methode liefert erhebliche Verbesserung in der letzten Fehler von k-means. Obwohl die erste Auswahl in der Algorithmus nimmt zusätzliche Zeit, die k-means Teil selbst konvergiert sehr schnell nach dieser Aussaat und damit der Algorithmus tatsächlich verringert die Rechenzeit. Die Autoren testeten ihre Methode mit echten und synthetischen Datensätze und 2fachen Verbesserungen in der Geschwindigkeit der Regel erhalten wird, und für bestimmte Datenmengen in der Nähe der 1000-fach für eine verbesserte Fehler. In diesen Simulationen das neue Verfahren fast immer mindestens sowie Vanille k-means in Geschwindigkeit und Fehler führen.

Darüber hinaus berechnen die Autoren eine Approximationsgüte für ihre Algorithmus. Der K-Means-Algorithmus ++ garantiert eine Näherung Verhältnis O in der Erwartung, wobei die Anzahl der Cluster verwendet wird. Dies steht im Gegensatz zu Vanille k-Mittel, die Clusterings willkürlich schlechtere als die optimale erzeugen kann.

Beispiel schlimmen Fall

Um das Potenzial des k-means-Algorithmus zu veranschaulichen, um willkürlich schlecht in Bezug auf die Zielfunktion zum Minimieren der Summe der quadrierten Entfernungen der Häufungspunkte, um den Flächenschwerpunkt ihrer zugewiesenen Cluster durchführen, sollten am Beispiel von vier Punkten in der R die eine Achse bilden, -aligned Rechteck ist, dessen Breite größer ist als ihre Höhe.

Wenn k = 2 und die beiden anfänglichen Clusterzentren an den Mittelpunkten der oberen und unteren Strecken des von den vier Datenpunkte gebildet Rechtecks ​​liegen, das k-means-Algorithmus konvergiert sofort, ohne sich zu bewegen, diese Clusterzentren. Folglich sind die beiden unteren Datenpunkte zusammen gruppiert, und die beiden Datenpunkte bilden den oberen Teil des Rechtecks ​​zusammen eine suboptimale Clustern gruppiert, weil die Breite des Rechtecks ​​größer ist als dessen Höhe.

Nun sei Dehnen des Rechtecks ​​horizontal an einer willkürlichen Breite. Die Standard-k-means-Algorithmus wird weiter die Punkte suboptimal Cluster und durch Erhöhung der horizontale Abstand zwischen den zwei Datenpunkte in jedem Cluster, können wir den Algorithmus auszuführen willkürlich schlecht bezüglich des k-means-Zielfunktion.

Anwendungen

Der K-Means ++ Ansatz hat seit ihrem ursprünglichen Vorschlag angewandt. In einer Rezension von Shindler, die viele Arten von Clustering-Algorithmen beinhaltet, ist das Verfahren, sagte, um erfolgreich zu überwinden einige der Probleme, mit anderen Möglichkeiten zur Definition der anfänglichen Clusterzentren für die k-means Clustering zugeordnet. Lee et al. berichten über eine Anwendung von k-means ++ auf geografische Cluster von Fotografien auf der Grundlage der Längen- und Breitengrad, um die Bilder als Anlage zu erstellen. Ein Antrag auf finanzielle Diversifizierung wird von Howard und Johansen gemeldet. Weitere Unterstützung für das Verfahren und die anhaltende Diskussion ist auch online verfügbar. Da das k-means ++ Initialisierung benötigt k über die Daten laufen, ist es nicht sehr gut, auch große Datenmengen. Bahman Bahmani et al. haben eine skalierbare Variante des k-means ++ genannte k-Mittel vorgeschlagen || wonach die gleichen theoretischen Garantien und doch ist hoch skalierbar.

Software

• ELKI Data-Mining-Framework enthält mehrere k-Mittel-Varianten, einschließlich der k-means ++ für die Aussaat.
• GNU R enthält k-Mittel, und die "flexclust" Paket kann k-means do ++
• OpenCV Umsetzung
• Weka enthält k-Mittel-und x-means Clustering.
• David Arthur-Implementierung
• Apache Commons Math Java-Implementierung
• CMU GraphLab GraphLab Effizient, Open-Source-Clustering auf Multicore.