K-means: Apa beberapa cara yang baik untuk memilih satu set centroid awal yang efisien?

Ketika inisialisasi acak centroid digunakan, berbagai K-means menghasilkan SSE total yang berbeda. Dan itu sangat penting dalam kinerja algoritma. Apa saja pendekatan efektif untuk menyelesaikan masalah ini? Pendekatan terbaru dihargai.

Suatu pendekatan yang menghasilkan hasil yang lebih konsisten adalah K-means ++ . Pendekatan ini mengakui bahwa mungkin ada pilihan yang lebih baik dari lokasi sentroid awal daripada penugasan acak sederhana. Secara khusus, K-means cenderung berkinerja lebih baik ketika centroid diunggulkan sedemikian rupa sehingga tidak menggumpal mereka di ruang angkasa.

Singkatnya, metode ini adalah sebagai berikut:

1. Pilih salah satu titik data Anda secara acak sebagai centroid awal.
2. Hitung , jarak antara centroid awal Anda dan semua titik data lainnya, x .$D(x)$$x$
3. Pilih centroid Anda berikutnya dari titik data yang tersisa dengan probabilitas sebanding dengan $D(x)^2$
4. Ulangi sampai semua centroid telah ditetapkan.

Catatan: harus diperbarui karena lebih banyak centroid ditambahkan. Itu harus diatur menjadi jarak antara titik data dan pusat massa terdekat.$D(x)$

Anda mungkin juga tertarik untuk membaca makalah ini yang mengusulkan metode ini dan menjelaskan kinerja keseluruhan yang diharapkan.

Saya mungkin salah mengerti pertanyaan Anda, tetapi biasanya k-means memilih centroid Anda secara acak untuk Anda tergantung pada jumlah cluster yang Anda tetapkan (yaitu k). Memilih angka untuk k cenderung merupakan latihan yang subyektif. Tempat yang baik untuk memulai adalah plot Elbow / Scree yang dapat ditemukan di sini:

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

Pendekatan biasa untuk masalah ini adalah menjalankan kembali algoritma K-means Anda beberapa kali, dengan inisialisasi acak yang berbeda dari centroid, dan untuk menjaga solusi terbaik. Anda dapat melakukannya dengan mengevaluasi hasil pada data pelatihan Anda atau melalui validasi silang.

Ada banyak cara lain untuk menginisialisasi centroid, tetapi tidak ada yang akan melakukan yang terbaik untuk setiap masalah. Anda dapat mengevaluasi pendekatan ini bersama dengan inisialisasi acak untuk masalah khusus Anda.

Saya setuju dengan plot Elbow / Scree. Saya menemukan itu lebih masuk akal secara intuitif daripada benih acak. Berikut ini contoh kode untuk mencobanya.

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)