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

17

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.

ngub05
źródło

Odpowiedzi:

12

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, .re(x)x
  3. Wybierz następny środek ciężkości spośród pozostałych punktów danych z prawdopodobieństwem proporcjonalnym dore(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.re(x)

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

Ryan J. Smith
źródło
5

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

Jake C.
źródło
Myślę, że pytanie dotyczy inicjalizacji centroidów, czyli {k-średnich ++, losowych lub ndarray} na stronie dokumentacji scikit-learn.org/stable/modules/generated/…
Itachi
4

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.

Pablo Suau
źródło
0

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)
Web Ster
źródło