Inicjalizowanie centrów K-średnich za pomocą losowych podpróbek zestawu danych?

Jeśli mam określony zestaw danych, jak mądre byłoby inicjowanie centrów klastrowych przy użyciu losowych próbek tego zestawu danych?

Załóżmy na przykład, że chcę 5 clusters. Przyjmuję, 5 random samplespowiedzmy, size=20%oryginalny zestaw danych. Czy mogę wziąć średnią z każdej z 5 losowych próbek i użyć tych środków jako moich 5 początkowych centrów skupień? Nie wiem, gdzie to przeczytałem, ale chciałem wiedzieć, co myślicie o tym pomyśle.

AKTUALIZACJA: Zobacz ten wątek Inicjalizacja K-oznacza grupowanie: jakie są istniejące metody? do ogólnej dyskusji na temat różnych metod inicjalizacji.

Jeśli losowo podzielisz próbkę na 5 podprób, twoje 5 średnich prawie się pokryje. Jaki sens ma uczynienie tak bliskich punktów początkowymi centrami skupień?

W wielu implementacjach K-średnich domyślny wybór początkowych centrów klastrów opiera się na odwrotnej idei: znaleźć 5 punktów, które są najbardziej od siebie oddalone i uczynić z nich centra początkowe. Możesz zapytać, jak można znaleźć te odległe od siebie punkty? Oto, co robi w tym przypadku K-SPSS:

Weź dowolne k przypadków (punktów) zestawu danych jako początkowe centra. Wszystkie pozostałe przypadki są sprawdzane pod kątem możliwości zastąpienia ich jako ośrodków początkowych następującymi warunkami:

• a) Jeżeli obudowa znajduje się dalej od najbliższego środka, niż odległość między dwoma najbliższymi do siebie środkami, obudowa zastępuje środek dwóch ostatnich, do których jest bliżej.
• b) Jeżeli obudowa znajduje się dalej od środka 2-go najbliższego od niej, niż odległość między środkiem najbliższym od niego i środkiem najbliższym temu drugiemu, obudowa zastępuje środek najbliżej niego.

Jeżeli warunek (a) nie jest spełniony, warunek (b) jest sprawdzany; jeśli nie jest spełniony, sprawa nie staje się centrum. W wyniku takiego przebiegu przez przypadkach otrzymujemy k najwyższe oczekiwania przypadków w chmurze, które stają się początkowe centra. Wynik tego algorytmu, choć wystarczająco solidny, nie jest całkowicie niewrażliwy na początkowy wybór „dowolnych k spraw” i na kolejność sortowania spraw w zbiorze danych; dlatego kilka losowych prób rozruchu jest nadal pożądanych, jak zawsze w przypadku środków K.

Zobacz moją odpowiedź z listą popularnych metod inicjalizacji k-średnich. Na liście znajdują się również metody podziału na losowe podpróbki (krytykowane tutaj przeze mnie i innych), a także opisana metoda stosowana przez SPSS.

Środki będą zbyt podobne. Równie dobrze można znaleźć średnią zestawu danych, a następnie umieścić początkowe centroidy w małym kółku / kuli wokół tej średniej.

Jeśli chcesz zobaczyć więcej schematu inicjalizacji dźwięku dla k-średnich, spójrz na k-średnich ++. Opracowali dość sprytną metodę wysiewu k-średnich.

• Arthur, D. i Vassilvitskii, S. (2007).
  k-znaczy ++: zalety ostrożnego wysiewu ".
  Postępy osiemnastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych

Slajdy autorskie: http://www.ima.umn.edu/~iwen/REU/BATS-Means.pdf

Używanie losowych próbek da ci przeciwieństwo tego, czego potrzebujesz, jak zauważył ttnphns w swoim komentarzu. Potrzebujemy sposobu na znalezienie punktów danych, które są dość daleko od siebie.

Idealnie byłoby iterować po wszystkich punktach, znaleźć odległości między nimi, ustalić, gdzie odległości są największe ...

Nie chcę omijać intencji PO, ale myślę, że „rozwiązanie” jest wbudowane w algorytm k-średnich. Wykonujemy wiele iteracji i ponownie obliczamy centroidy klastrowe na podstawie poprzednich iteracji. Zwykle również uruchamiamy algorytm kmeans kilka razy (z losowymi wartościami początkowymi) i porównujemy wyniki.

Jeśli ktoś ma wiedzę a priori, wiedzę domenową, może to prowadzić do lepszej metody określania, gdzie powinny znajdować się początkowe centra skupień. W przeciwnym razie prawdopodobnie chodzi o wybranie losowych punktów danych jako wartości początkowych, a następnie wykorzystanie wielu przebiegów i wielu iteracji na przebieg.

$k$