K-oznacza: Jakie są dobre sposoby wyboru skutecznego zestawu początkowych centroidów?

Gdy stosowana jest losowa inicjalizacja centroidów, różne serie K-średnich dają różne całkowite SSE. I ma to kluczowe znaczenie dla wydajności algorytmu. Jakie są skuteczne podejścia do rozwiązania tego problemu? Najnowsze podejścia są mile widziane.

Podejście, które daje bardziej spójne wyniki, to K-znaczy ++ . Podejście to potwierdza, że ​​prawdopodobnie jest lepszy wybór początkowych lokalizacji środka ciężkości niż proste losowe przypisanie. Konkretnie, środki K mają tendencję do osiągania lepszych wyników, gdy centroidy są zaszczepione w taki sposób, że nie zlepiają ich w przestrzeni.

Krótko mówiąc, metoda jest następująca:

1. Wybierz jeden z losowych punktów danych jako początkową centroid.
2. Oblicz , odległość między początkową centroidem a wszystkimi innymi punktami danych, .$D(x)$$x$
3. Wybierz następny środek ciężkości spośród pozostałych punktów danych z prawdopodobieństwem proporcjonalnym do$D(x)^2$
4. Powtarzaj, aż wszystkie centroidy zostaną przypisane.

Uwaga: należy aktualizować wraz z dodawaniem kolejnych centroidów. Powinien być ustawiony jako odległość między punktem danych a najbliższym środkiem ciężkości.$D(x)$

Być może zainteresuje Cię również ten artykuł, w którym zaproponowano metodę i opisano jej ogólną oczekiwaną wydajność.

Być może źle rozumiem twoje pytanie, ale zwykle k-średnich wybiera losowo dla ciebie centroidy w zależności od liczby ustawionych przez ciebie klastrów (tj. K). Wybór liczby dla k jest zwykle subiektywnym ćwiczeniem. Dobrym miejscem do rozpoczęcia jest fabuła Elbow / Scree, którą można znaleźć tutaj:

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

Zwykle podejście do tego problemu polega na kilkakrotnym ponownym uruchomieniu algorytmu K-średnich, z różnymi losowymi inicjalizacjami centrroidów i utrzymaniu najlepszego rozwiązania. Możesz to zrobić, oceniając wyniki na danych treningowych lub poprzez wzajemną weryfikację.

Istnieje wiele innych sposobów inicjalizacji centroidów, ale żaden z nich nie będzie działał najlepiej w przypadku każdego problemu. Możesz ocenić te podejścia wraz z losową inicjalizacją konkretnego problemu.

Zgadzam się z fabułą Elbow / Scree. Uznałem to za bardziej intuicyjnie sensowne niż przypadkowe nasiona. Oto przykładowy kod, aby go wypróbować.

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)