K-means: Was sind einige gute Möglichkeiten, um einen effizienten Satz von Anfangsschwerpunkten zu wählen?

Wenn eine zufällige Initialisierung von Zentroiden verwendet wird, erzeugen unterschiedliche Läufe von K-Mitteln unterschiedliche Gesamt-SSEs. Und es ist entscheidend für die Leistung des Algorithmus. Was sind einige effektive Ansätze zur Lösung dieses Problems? Neuere Ansätze werden geschätzt.

Ein Ansatz, der konsistentere Ergebnisse liefert, ist K-means ++ . Dieser Ansatz erkennt an, dass es wahrscheinlich eine bessere Auswahl an anfänglichen Schwerpunktorten gibt als eine einfache zufällige Zuordnung. Speziell K-means neigen dazu, eine bessere Leistung zu erbringen, wenn Zentroide so ausgesät werden, dass sie im Weltraum nicht zusammenklumpen.

Kurz gesagt ist die Methode wie folgt:

1. Wählen Sie einen Ihrer Datenpunkte nach dem Zufallsprinzip als Anfangsschwerpunkt aus.
2. Berechnen Sie , den Abstand zwischen Ihrem Anfangsschwerpunkt und allen anderen Datenpunkten, x .$D(x)$$x$
3. Wählen Sie Ihren nächsten Schwerpunkt aus den verbleibenden Datenpunkten mit einer Wahrscheinlichkeit proportional zu $D(x)^2$
4. Wiederholen Sie diesen Vorgang, bis alle Schwerpunkte zugewiesen wurden.

$D(x)$

Sie können auch dieses Dokument lesen , das die Methode vorschlägt und deren erwartete Gesamtleistung beschreibt.

Ich kann Ihre Frage falsch verstehen, aber normalerweise wählt k-means Ihre Zentroide zufällig für Sie aus, abhängig von der Anzahl der von Ihnen eingestellten Cluster (dh k). Die Wahl der Zahl für k ist in der Regel eine subjektive Übung. Ein guter Ausgangspunkt ist ein Elbow / Scree-Grundstück, das hier zu finden ist:

http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set#The_Elbow_Method

Der übliche Ansatz für dieses Problem besteht darin, Ihren K-means-Algorithmus mehrmals mit verschiedenen zufälligen Initialisierungen der Zentroide erneut auszuführen und die beste Lösung beizubehalten. Sie können dies tun, indem Sie die Ergebnisse anhand Ihrer Trainingsdaten auswerten oder eine Kreuzvalidierung durchführen.

Es gibt viele andere Möglichkeiten, die Zentroide zu initialisieren, aber keine von ihnen bietet für jedes einzelne Problem die beste Leistung. Sie können diese Ansätze zusammen mit einer zufälligen Initialisierung für Ihr spezielles Problem bewerten.

Ich stimme der Handlung von Elbow / Scree zu. Ich fand es intuitiver als einen zufälligen Samen. Hier ist ein Beispielcode, um es zu versuchen.

Ks=30
mean_acc=np.zeros((Ks-1))
std_acc=np.zeros((Ks-1))
ConfustionMx=[];
for n in range(1,Ks):    
    #Train Model and Predict  
    kNN_model = KNeighborsClassifier(n_neighbors=n).fit(X_train,y_train)
    yhat = kNN_model.predict(X_test)
    mean_acc[n-1]=np.mean(yhat==y_test);
    std_acc[n-1]=np.std(yhat==y_test)/np.sqrt(yhat.shape[0])

plt.plot(range(1,Ks),mean_acc,'g')
plt.fill_between(range(1,Ks),mean_acc - 1 * std_acc,mean_acc + 1 * std_acc, alpha=0.10)
plt.legend(('Accuracy ', '+/- 3xstd'))
plt.ylabel('Accuracy ')
plt.xlabel('Number of Nabors (K)')
plt.tight_layout()
plt.show()

print( "The best accuracy was with", mean_acc.max(), "with k=", mean_acc.argmax()+1)