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

13

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.

JEquihua
źródło
11
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 większości implementacji 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.
ttnphns,
2
@ttnphns To byłaby miła odpowiedź.
2
Myślę, że znacznie lepiej byłoby wybrać ogólny punkt jako jeden punkt i wybrać inne, które są daleko od tego centrum w różnych kierunkach.
Michael R. Chernick
1
Ma sens. Jak miałbym szukać informacji o tych 5 punktach, które są daleko od siebie? Dziękuję Ci!
JEquihua
@JEquihua, opublikowałem swój komentarz jako odpowiedź i dodałem szczegóły, o które prosisz.
ttnphns,

Odpowiedzi:

16

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.

ttnphns
źródło
1
Po wykonaniu tego, co opisałeś, jakiej statystyki mógłbym użyć do ustalenia, który punkt inicjalizacji prowadzi do lepszej partycji? Dziękuję za wszystko.
JEquihua
Stosując najwyższe oczekiwania punktów początkowych centrów raz nie gwarantuje uzyskania najlepszej partycję w końcu Myśleli (w porównaniu do przypadkowych pierwszych ośrodków) zrobić zmniejsza szanse na uzyskanie uwięziony w „lokalnym optimum”, a oni przyspieszyć proces konwergencji . Kolejność przypadków różnej, czy całej partycji k-means 2-5 razy, zapisz końcowe uzyskane ośrodki, uśrednić je i wprowadzić jako początkowych te dla jednej ostatecznej klasteryzacji. Ta partycja jest z pewnością najlepsza. W rzeczywistości nie potrzebujesz żadnych specjalnych statystyk, aby to sprawdzić, chyba że zamierzasz porównać części różnych k.
ttnphns,
1
Chcę porównać partycje różnych k. Czego mogę użyć? Jaki jest dobry pomysł? dziękuję, że bardzo mi pomogłeś. @ttnphns.
JEquihua
Istnieją na wielką liczbę „wewnętrznych” kryteriów grupowania . Jednym z najbardziej odpowiednich dla k-średnich jest Calinski-Harabasz (wielowymiarowy F Fishera). Google dla niego lub dla innych.
ttnphns
7

Ś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

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Czytam to. Wygląda to dość intuicyjnie, ale wydaje mi się, że nie zostało jeszcze udowodnione, że działa lepiej niż zwykłe pobieranie wielu losowych punktów inicjalizacji. Znalazłem ten prosty kod na wypadek, gdybyś chciał go wypróbować: kmpp <- funkcja (X, k) {n <- nrow (X) C <- numeryczna (k) C [1] <- próbka (1: n, 1) dla (i w 2: k) {dm <- distmat (X, X [C,]) pr <- stosuje się (dm, 1, min); pr [C] <- 0 C [i] <- próbka (1: n, 1, prob = pr)} kmeans (X, X [C,])}
JEquihua
Wiadomo, że znacznie zmniejsza liczbę iteracji do konwergencji i daje średnio lepsze wyniki. Mogę potwierdzić, że w moich własnych eksperymentach kmeans ++ jest właściwą drogą. Korzystam z implementacji ELKI.
Ma ZAKOŃCZENIE - Anony-Mousse
Co to jest implementacja ELKI? gdzie mogę to sprawdzić? Pozdrowienia!
JEquihua
en.wikipedia.org/wiki/ELKI
Ma ZAKOŃCZENIE - Anony-Mousse
4

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.

Mężczyzna
źródło
Po wykonaniu tego, co opisałeś, jakiej statystyki mógłbym użyć do ustalenia, który punkt inicjalizacji prowadzi do lepszej partycji? Dziękuję za wszystko.
JEquihua
2

k

gregmacfarlane
źródło
Ma sens. Czy mogę prosić o to samo, o co prosiłam Amana? Załóżmy, że biorę zillion losowych początkowych punktów. Czego mogę użyć, aby określić, która z powstałych partycji jest najlepsza? Pozdrowienia! @gmacfarlane
JEquihua
k
k