Verbesserte Varianten von K-Means

Die Clustering-Analyse ist einer der am häufigsten verwendeten Datenverarbeitungsalgorithmen. Seit über einem halben Jahrhundert ist K-means aufgrund seiner Einfachheit nach wie vor der beliebteste Clustering-Algorithmus. Beim traditionellen K-means-Clustering wird versucht, n Datenobjekte ausgehend von zufälligen Anfangszentren k Clustern zuzuordnen. Die meisten k-means-Varianten neigen jedoch dazu, bei jeder Iteration den Abstand jedes Datenpunkts zu jedem Clusterschwerpunkt zu berechnen. Wir schlagen eine schnelle Heuristik zur Überwindung dieses Engpasses vor, die den mittleren quadratischen Fehler (MSE) nur geringfügig erhöht. Wir beobachten, dass ein Datenpunkt über alle Iterationen von K-means hinweg seine Zugehörigkeit nur zu einer kleinen Teilmenge von Clustern ändert. Unsere Heuristik sagt solche Cluster für jeden Datenpunkt voraus, indem sie nach der ersten Iteration von k-means die nahe gelegenen Cluster betrachtet. Wir erweitern bekannte Varianten von k-means wie Enhanced K-means und K-means with Triangle Inequality mit unserer Heuristik, um ihre Wirksamkeit zu demonstrieren. Für verschiedene Datensätze erreicht unsere Heuristik eine bis zu 3-fache Beschleunigung im Vergleich zu effizienten Varianten von k-means.