K-means: Quali sono alcuni buoni modi per scegliere un insieme efficiente di centroidi iniziali?

Question

Quando si utilizza un'inizializzazione casuale di centroidi, diverse esecuzioni di K-means producono differenti SSEs totali. Ed è fondamentale nello svolgimento dell'algoritmo. Quali sono alcuni approcci efficaci verso la soluzione di questo problema? approcci recenti sono apprezzati.

Answer 1

Un approccio che produce risultati più consistenti è K-means ++ . Questo approccio riconosce che v'è probabilmente una migliore scelta della località di baricentro iniziali di semplice assegnazione casuale. Specificamente, K-means tende a rendere meglio quando centroidi vengono seminate in modo tale che non li aggregano insieme nello spazio.

In breve, il metodo è il seguente:

1. Scegli uno dei tuoi punti di dati a caso come un baricentro iniziale.
2. Calcolare $ D (x) $, la distanza tra il baricentro iniziale e tutti gli altri punti di dati, $ x $.
3. Scegli la tua prossima baricentro dalle restanti datapoints con probabilità proporzionale a $ D (x) ^ 2 $
4. Ripeti fino a quando sono stati assegnati tutti i baricentri.

Nota: $ D (x) $ dovrebbe essere aggiornato quando si aggiungono più centroidi. Deve essere impostato per essere la distanza tra un punto dati e il baricentro più vicino.

Si può anche essere interessati a leggere questo documento che propone il metodo e descrive le sue prestazioni complessivo atteso.

Answer 2

I può essere equivoco tua domanda, ma di solito k-means sceglie tuoi centroidi a caso per voi in base al numero di cluster si imposta (vale a dire k). La scelta del numero di per k tende ad essere un esercizio soggettivo. Un buon punto di partenza è una trama Gomito / Detriti che può essere trovato qui:

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

Answer 3

L'approccio comune a questo problema è quello di ri-eseguire le algoritmo k-means più volte, con differenti inizializzazioni casuali dei centroidi, e per mantenere la soluzione migliore. Si può fare, valutando i risultati sul i dati di allenamento o per mezzo di validazione incrociata.

Ci sono molti altri modi per inizializzare i baricentri, ma nessuno di loro sta per eseguire la migliore per ogni singolo problema. Si potrebbe valutare questi approcci insieme con l'inizializzazione casuale per il vostro problema particolare.

Answer 4

Sono d'accordo con la trama gomito / Scree. L'ho trovato più intuitivo sensato di un seme casuale. Ecco un esempio di codice di provarlo.

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)