Wie testest du eine Implementierung von k-means?

Haftungsausschluss: Ich habe diese Frage auf Stackoverflow gepostet, dachte aber, dass dies möglicherweise besser für diese Plattform geeignet ist.

Wie testen Sie Ihre eigene k-means-Implementierung für mehrdimensionale Datensätze?

Ich dachte daran, eine bereits vorhandene Implementierung (dh Matlab) für die Daten auszuführen und die Ergebnisse mit meinem Algorithmus zu vergleichen. Dies würde jedoch erfordern, dass beide Algorithmen mehr als ungefähr gleich funktionieren, und die Zuordnung zwischen den beiden Ergebnissen ist wahrscheinlich kein Kinderspiel.

Hast du eine bessere Idee?

Das k-means enthält eine stochastische Komponente, daher ist es sehr unwahrscheinlich, dass Sie dasselbe Ergebnis erzielen, es sei denn, Sie haben genau dieselbe Implementierung und verwenden dieselbe Startkonfiguration. Sie können jedoch feststellen, ob Ihre Ergebnisse mit bekannten Implementierungen übereinstimmen (Sie wissen nichts über Matlab, aber die Implementierung des k-means-Algorithmus in R ist gut erklärt, siehe Hartigan & Wong, 1979 ).

Beim Vergleich von zwei Ergebnisserien gibt es immer noch ein Problem beim Etikettenwechsel, wenn es mehrmals ausgeführt werden soll. Auch im e1071 R-Paket gibt es eine sehr praktische Funktion (; matchClasses()), mit der die beste Zuordnung zwischen zwei Kategorien in einer Zwei-Wege-Klassifizierungstabelle ermittelt werden kann. Grundsätzlich besteht die Idee darin, die Zeilen neu anzuordnen, um ihre Übereinstimmung mit den Spalten zu maximieren, oder einen gierigen Ansatz zu verwenden und Zeilen und Spalten zu permutieren, bis die Summe auf der Diagonale (rohe Übereinstimmung) maximal ist. Ein Übereinstimmungskoeffizient wie die Kappa- Statistik wird ebenfalls bereitgestellt.

Zum Benchmarking Ihrer Implementierung gibt es viele frei verfügbare Daten, oder Sie können einen dedizierten Datensatz simulieren (z. B. über ein Finite-Mix-Modell, siehe MixSim- Paket).

Die Zuordnung zwischen zwei Ergebnissätzen ist einfach zu berechnen, da die Informationen, die Sie in einem Test erhalten, als Satz von drei Tupeln dargestellt werden können: Die erste Komponente ist ein (mehrdimensionaler) Punkt, die zweite eine (beliebige) Clusterbezeichnung wird von Ihrem Algorithmus bereitgestellt, und die dritte ist eine (beliebige) Clusterbezeichnung, die von einem Referenzalgorithmus bereitgestellt wird. Konstruieren Sie das durch$k$$k$Klassifizierungstabelle für die Etikettenpaare: Wenn die Ergebnisse übereinstimmen, handelt es sich um ein Vielfaches einer Permutationsmatrix. Das heißt, jede Zeile und jede Spalte muss genau eine Zelle ungleich Null haben. Das ist eine einfache Prüfung zum Programmieren. Es ist auch einfach, kleine Abweichungen von diesem Ideal zurück zu einzelnen Datenpunkten zu verfolgen, sodass Sie genau sehen können, wie sich die beiden Antworten unterscheiden, wenn sie sich überhaupt unterscheiden. Ich würde mir nicht die Mühe machen, statistische Übereinstimmungsmaße zu berechnen: Entweder gibt es eine perfekte Übereinstimmung (bis zur Permutation) oder es gibt keine, und im letzteren Fall müssen Sie alle Punkte der Uneinigkeit aufspüren, um zu verstehen, wie sie auftreten. Die Ergebnisse stimmen entweder überein oder nicht. Jede Meinungsverschiedenheit, auch nur an einem Punkt, muss überprüft werden.

Möglicherweise möchten Sie verschiedene Arten von Datensätzen zum Testen verwenden: (1) veröffentlichte Datensätze mit veröffentlichten k-means-Ergebnissen; (2) synthetische Datensätze mit offensichtlich starken Clustern; (3) synthetische Datensätze ohne offensichtliche Clusterbildung. (1) ist eine gute Disziplin, wenn Sie ein Mathematik- oder Statistikprogramm schreiben . (2) ist in vielerlei Hinsicht einfach zu tun, beispielsweise indem einige zufällige Punkte erzeugt werden, die als Zentren von Clustern dienen, und dann Punktwolken erzeugt werden, indem die Clusterzentren relativ kleine Mengen zufällig verschoben werden. (3) bietet einige zufällige Überprüfungen, die möglicherweise unerwartete Verhaltensweisen aufdecken; Auch dies ist eine gute allgemeine Testdisziplin.

Darüber hinaus sollten Sie Datensätze erstellen, die den Algorithmus belasten, indem Sie nur an den Grenzen zwischen extremen Lösungen liegen. Dies erfordert Kreativität und ein tiefes Verständnis Ihres Algorithmus (den Sie vermutlich haben!). Ein Beispiel, das ich auf jeden Fall überprüfen möchte, wären Vektorsätze der Form wobei ein Vektor ohne Nullkomponenten ist und sequentielle Integralwerte . Ich würde auch den Algorithmus an Vektorsätzen überprüfen wollen, die gleichseitige Polygone bilden. In beiden Fällen Fällen , in denen ist nicht ein Vielfaches von sind besonders interessant, auch dann, wenn$i \mathbb{v}$$\mathbb{v}$$i$$0, 1, 2, \ldots, n-1$$n$$k$$n$ist kleiner als . Diesen Situationen ist gemeinsam, dass (a) sie alle Dimensionen des Problems verwenden, jedoch (b) die richtigen Lösungen geometrisch offensichtlich sind und (c) es mehrere richtige Lösungen gibt.$k$

(Bilden Sie zufällige gleichseitige Polygone in Dimensionen, indem Sie mit zwei zufällig ausgewählten Vektoren ungleich Null und . (Eine gute Möglichkeit besteht darin, ihre Komponenten unabhängige Standardnormalvariablen sein zu lassen.) Neu skalieren Nennen wir diese und . Entfernen Sie die -Komponente mithilfe der Formel aus$d \ge 2$$\mathbb{u}$$\mathbb{v}$$2d$$\mathbb{x}$$\mathbb{z}$$\mathbb{x}$$\mathbb{z}$

Erhalten Sie indem Sie skalieren, um die Einheitslänge zu erhalten. Wenn Sie möchten, skalieren Sie sowohl als auch gleichmäßig nach dem Zufallsprinzip neu. Die Vektoren und bilden eine orthogonale Basis für einen zufälligen 2D-Unterraum in Dimensionen. Ein gleichseitiges Polygon von Eckpunkten wird erhalten als die Menge von wenn die ganze Zahl von reicht bis .)w x y x y d n cos ( 2 π k / n ) x + sin ( 2 π k / n ) y k 0 n - $\mathbb{y}$$\mathbb{w}$$\mathbb{x}$$\mathbb{y}$$\mathbb{x}$$\mathbb{y}$$d$$n$$\cos(2 \pi k / n) \mathbb{x} + \sin(2 \pi k / n) \mathbb{y}$$k$$0$$n-1$

Ein sehr einfacher "naiver" Ansatz wäre die Verwendung einfacher synthetischer Daten, da jede Implementierung zu denselben Clustern führen sollte.

Beispiel in Python mit import numpy as np:

test_data = np.zeros((40000, 4))
test_data[0:10000, :] = 30.0
test_data[10000:20000, :] = 60.0
test_data[20000:30000, :] = 90.0
test_data[30000:, :] = 120.0

Denn n_clusters = 4es sollte dir eine Permutation von geben[30, 60, 90, 120]

Da k-means Entscheidungen enthält, die zufällig ausgewählt werden (nur der Initialisierungsteil), besteht der beste Weg, Ihren Algorithmus zu testen, darin, die Anfangspunkte auszuwählen und sie zuerst in Ihrem Algorithmus fixieren zu lassen und dann einen anderen Quellcode des Algorithmus und auszuwählen Fixieren Sie die Punkte auf die gleiche Weise. Dann können Sie die Ergebnisse wirklich vergleichen.