Initialisierung von K-Means-Zentren durch zufällige Unterproben des Datensatzes?

13

Wenn ich einen bestimmten Datensatz habe, wie intelligent wäre es dann, Cluster-Zentren mithilfe von Zufallsstichproben dieses Datensatzes zu initialisieren?

Angenommen, ich möchte 5 clusters. Ich nehme 5 random samplesvon sagen wir, size=20%des ursprünglichen Datensatzes. Könnte ich dann den Mittelwert jeder dieser 5 Zufallsstichproben als meine 5 anfänglichen Cluster-Zentren verwenden? Ich weiß nicht, wo ich das lese, aber ich wollte wissen, was ihr über die Idee denkt.


UPDATE: Bitte lesen Sie diesen Thread Initialisierung von K-means Clustering: Welche Methoden gibt es? für die allgemeine Diskussion über die verschiedenen Initialisierungsmethoden.

JEquihua
quelle
11
Wenn Sie die Stichprobe zufällig in 5 Teilstichproben aufteilen, stimmen Ihre 5 Mittelwerte fast überein. Was bedeutet es, solche engen Punkte zu den anfänglichen Clusterzentren zu machen? In den meisten K-means-Implementierungen basiert die Standardauswahl der anfänglichen Cluster-Zentren auf der entgegengesetzten Idee: Finden der 5 Punkte, die am weitesten voneinander entfernt sind, und Festlegen der anfänglichen Zentren.
TTNPHNS
2
@ttnphns Das wäre eine nette Antwort.
2
Ich würde denken, dass es viel besser wäre, den Gesamtmittelwert als einen Punkt auszuwählen und andere auszuwählen, die in verschiedenen Richtungen weit von diesem Zentrum entfernt sind.
Michael R. Chernick
1
Macht Sinn. Wie würde ich vorgehen, um diese 5 Punkte zu finden, die weit voneinander entfernt sind? Vielen Dank!
JEquihua
@JEquihua, ich habe meinen Kommentar als Antwort gepostet und Details hinzugefügt, die Sie anfordern.
TTNPHNS

Antworten:

16

Wenn Sie die Stichprobe zufällig in 5 Teilstichproben aufteilen, stimmen Ihre 5 Mittelwerte fast überein. Was bedeutet es, solche engen Punkte zu den anfänglichen Clusterzentren zu machen?

In vielen K-means-Implementierungen basiert die Standardauswahl der anfänglichen Clusterzentren auf der entgegengesetzten Idee: Finden der 5 Punkte, die am weitesten voneinander entfernt sind, und Festlegen der anfänglichen Zentren. Sie fragen sich vielleicht, wie Sie diese weit auseinander liegenden Punkte finden können? Hier ist, was SPSS 'K-means dafür tut:

Nehmen Sie alle k Fälle (Punkte) des Datensatzes als Anfangszentren. In allen übrigen Fällen wird geprüft, ob sie durch die folgenden Bedingungen als Ausgangszentren ersetzt werden können:

  • a) Befindet sich der Fall weiter von dem ihm am nächsten gelegenen Zentrum entfernt als der Abstand zwischen zwei am nächsten gelegenen Zentren, so ersetzt der Fall das Zentrum der beiden letzteren, zu dem er näher liegt.
  • b) Befindet sich der Koffer weiter vom ihm nächstgelegenen Mittelpunkt als der Abstand zwischen dem ihm nächstgelegenen Mittelpunkt und dem diesem nächstgelegenen Mittelpunkt, so ersetzt der Koffer den ihm nächstgelegenen Mittelpunkt.

Wenn die Bedingung (a) nicht erfüllt ist, wird die Bedingung (b) geprüft; Ist dies nicht der Fall, wird der Fall auch nicht zum Zentrum. Als Ergebnis einer solchen Lauf durch Fällen erhalten wir k äußerste Fälle in der Wolke , die die ersten Zentren werden. Das Ergebnis dieses Algorithmus ist zwar robust genug, jedoch nicht völlig unempfindlich gegenüber der Startauswahl von "any k cases" und der Sortierreihenfolge der Fälle im Datensatz. es sind also immer noch mehrere zufällige Startversuche erwünscht, wie es bei K-means immer der Fall ist.

Siehe meine Antwort mit einer Liste der gängigen Initialisierungsmethoden für k-means. Die Methode der Aufteilung in zufällige Unterproben (hier von mir und anderen kritisiert) sowie die von SPSS verwendete beschriebene Methode - stehen ebenfalls auf der Liste.

ttnphns
quelle
1
Welche Statistik kann ich verwenden, um zu bestimmen, welcher Initialisierungspunkt zu einer besseren Partition führt, wenn ich das getan habe, was Sie beschreiben? Danke für alles.
JEquihua
Die einmalige Verwendung von äußersten Punkten als Anfangszentren garantiert nicht, dass am Ende die beste Partition erzielt wird , obwohl sie (im Vergleich zu zufälligen Anfangszentren) die Wahrscheinlichkeit verringern, in ein "lokales Optimum" geraten zu können, und den Konvergenzprozess beschleunigen . Unterschiedliche Reihenfolge der Fälle: Machen Sie die gesamte k-means-Partition 2-5 Mal, speichern Sie die erhaltenen endgültigen Zentren, mitteln Sie sie und geben Sie sie als erste für eine endgültige Clusterisierung ein. Diese Partition ist sicherlich die beste. Sie benötigen tatsächlich keine spezielle Statistik, um dies zu überprüfen, es sei denn, Sie vergleichen Partinionen mit unterschiedlichem k.
TTNPHNS
1
Ich möchte Partitionen verschiedener k vergleichen. Was könnte ich benutzen? Was ist eine gute Idee? Danke, dass du mir so geholfen hast. @ttnphns.
JEquihua
Es gibt eine große Anzahl von „intern“ Clustering criterions . Eines der am besten geeigneten Mittel für k ist Calinski-Harabasz (multivariates Fisher's F). Google dafür oder für andere.
TTNPHNS
7

Die Mittel werden viel zu ähnlich sein. Sie können auch den Datensatzmittelwert finden und dann die Anfangsschwerpunkte in einem kleinen Kreis / einer kleinen Kugel um diesen Mittelwert platzieren.

Wenn Sie mehr Sound-Initialisierungsschema für k-means sehen möchten, schauen Sie sich k-means ++ an. Sie haben eine ziemlich clevere Methode entwickelt, um k-means zu säen.

  • Arthur, D. und Vassilvitskii, S. (2007).
    k-means ++: die Vorteile einer sorgfältigen Aussaat ".
    Vorträge des achtzehnten jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen

Folien des Autors: http://www.ima.umn.edu/~iwen/REU/BATS-Means.pdf

Hat aufgehört - Anony-Mousse
quelle
Ich habe dies gelesen. Es sieht intuitiv vorteilhaft aus, aber ich denke, es ist noch nicht bewiesen, dass es besser funktioniert, als einfach eine Menge zufälliger Initialisierungspunkte zu nehmen. Ich habe diesen einfachen Code gefunden, falls Sie ihn ausprobieren möchten: kmpp <- function (X, k) {n <- row (X) C <- numerisch (k) C [1] <- sample (1: n, 1) für (i in 2: k) {dm <- distmat (X, X [C,]) pr <- gilt (dm, 1, min); pr [C] <- 0 C [i] <- Probe (1: n, 1, prob = pr)} kmeans (X, X [C,])}
JEquihua
Es ist bekannt, die Anzahl der Iterationen bis zur Konvergenz signifikant zu reduzieren und im Durchschnitt bessere Ergebnisse zu erzielen. Ich kann bestätigen, dass in meinen eigenen Experimenten kmeans ++ der richtige Weg ist. Ich verwende die ELKI-Implementierung.
Hat aufgehört - Anony-Mousse
Was ist die ELKI-Implementierung? wo kann ich es nachschlagen Schöne Grüße!
JEquihua
en.wikipedia.org/wiki/ELKI
Hat aufgehört - Anony-Mousse
4

Wenn Sie die Mittel der Zufallsstichproben verwenden, erhalten Sie das Gegenteil von dem, was Sie benötigen, wie ttnphns in seinem Kommentar ausgeführt hat. Was wir brauchen, ist eine Möglichkeit, Datenpunkte zu finden, die ziemlich weit voneinander entfernt sind.

Im Idealfall können Sie alle Punkte durchlaufen, die Abstände zwischen ihnen ermitteln und bestimmen, wo die Abstände am größten sind ...

Die Absicht des OP nicht zu umgehen, aber ich denke, die "Lösung" ist in den k-means-Algorithmus eingebaut. Wir führen mehrere Iterationen durch und berechnen Cluster-Zentroide basierend auf den vorherigen Iterationen neu. Normalerweise führen wir den kmeans-Algorithmus auch mehrmals aus (mit zufälligen Anfangswerten) und vergleichen die Ergebnisse.

Wenn man über A-priori- Kenntnisse und Domänenkenntnisse verfügt, kann dies zu einer überlegenen Methode führen, um festzustellen, wo sich anfängliche Cluster-Zentren befinden sollten. Andernfalls müssen wahrscheinlich zufällige Datenpunkte als Anfangswerte ausgewählt und dann mehrere Läufe und mehrere Iterationen pro Lauf verwendet werden.

Ein Mann
quelle
Welche Statistik kann ich verwenden, um zu bestimmen, welcher Initialisierungspunkt zu einer besseren Partition führt, wenn ich das getan habe, was Sie beschreiben? Danke für alles.
JEquihua
2

Die vorgeschlagenen Antworten sind alle effektiv, jedoch viel schwieriger zu operationalisieren als Ihr ursprünglicher Vorschlag. Eine sehr einfache Methode zum Initialisieren ist takekzufällige Beobachtungen als die ursprünglichen Punkte. Die Wahrscheinlichkeit, dass zwei Anfangspunkte nahe beieinander liegen, ist recht gering, und der Algorithmus wird für alle Fälle, mit Ausnahme der extremsten, schnell ausgeführt.

gregmacfarlane
quelle
Das ergibt sehr viel Sinn. Könnte ich Sie genauso fragen, wie ich Aman gefragt habe? Angenommen, ich nehme eine Million zufälliger Anfangspunkte. Was könnte ich verwenden, um zu bestimmen, welche der resultierenden Partitionen am besten ist? Schöne Grüße! @gmacfarlane
JEquihua
Typischerweise k- Bedeutet, dass Algorithmen iterieren, bis der mittlere quadratische Fehler (oder der mittlere absolute Fehler) zwischen den Iterationen minimiert und stabil ist. In jedem gegebenen Datensatz gibt es eine endliche Anzahl von Kombinationen, die diese MSE wirklich minimieren. Aus zig Durchläufen resultieren wahrscheinlich zwischen einem und zehn Partitionsschemata (abhängig von der Seltsamkeit Ihrer Daten), und ich würde das mit der niedrigsten MSE unter allen Gruppen auswählen.
Gregmacfarlane
Ich sollte beachten, dass, wenn Ihre Partitionen für die Auswahl der Anfangspunkte sehr empfindlich sind, dies bedeutet, dass Ihre Daten keine natürlichen Cluster und a haben k-Mittel Clustering-Algorithmus ist möglicherweise nicht die beste Sache zu verwenden. Oder Sie versuchen, mehr Cluster als die natürlich vorhandenen Daten anzupassen.
Gregmacfarlane