Metody inicjowania grupowania K-oznacza

Interesuje mnie obecny stan wiedzy w zakresie selekcji początkowych nasion (ośrodków skupień) dla K-średnich.

Googling prowadzi do dwóch popularnych opcji:

1. losowy wybór nasion początkowych oraz
2. przy użyciu techniki selekcji KMeans ++: Arthur i Vassilvitskii 2006 k-znaczy ++: Zalety ostrożnego siewu

Czy są jakieś inne obiecujące metody, o których ktoś tu wie, które mogą nie być tak popularne?

Pozwólcie mi, nie sięgając daleko, po prostu skopiować i wkleić listę opcji z mojej własnej funkcji !kmini(makro dla SPSS), znalezionej w kolekcji „Clustering” tutaj .

Metoda tworzenia lub wybierania początkowych centrów klastrów. Wybierać:

• RGC - centroidy losowych podpróbek . Dane są dzielone losowo wedługk nakładanie się, członkostwo, grupy i centroidy tych grup są wyznaczane jako początkowe centra. Zatem centra są obliczane, a nie wybrane z istniejących przypadków zbioru danych. Ta metoda daje centra, które leżą blisko siebie i względem ogólnego środka ciężkości danych.
• RP - losowo wybrane punkty . króżne przypadki danych są losowo wybierane jako początkowe centra.
• RUNFP - najdalsze punkty (wybór bieżący). Pierwsze kprzypadki są traktowane jako centra, a następnie podczas przeglądania pozostałych przypadków zbioru danych następuje stopniowa wymiana między centrami; celem zamiany jest uzyskanie kpunktów końcowych najbardziej oddalonych od siebie w przestrzeni zmiennej. Te punkty (przypadki) zajmujące pozycje peryferyjne w chmurze danych są wytworzonymi centrami początkowymi. (Metodę tę stosuje się jako domyślną w procedurze k-średnich SPSS QUICK CLUSTER. Zobacz szczegóły w Algorytmach SPSS. Zobacz także opisane tutaj ).
• SIMFP - najdalsze punkty (prosty wybór). Pierwsze centrum jest wybierane jako przypadek ze zbioru danych. Drugi środek wybierany jest jako przypadek maksymalnie oddalony od tego środka. Trzecie centrum jest wybierane jako przypadek maksymalnie oddalony od tych dwóch (od najbliższego z dwóch), i tak dalej.
• KMPP - losowe najdalsze punkty lub k-znaczy ++. Pierwsze centrum jest wybierane jako przypadek ze zbioru danych. Drugi środek jest również wybierany losowo, ale prawdopodobieństwo wyboru przypadku jest proporcjonalne do odległości (kwadratowy euklidesowy) od tego (pierwszego) środka. Trzecie centrum jest również wybierane losowo, z prawdopodobieństwem wyboru proporcjonalnym do odległości sprawy do najbliższego z tych dwóch centrów - i tak dalej. (Arthur, D., Vassilvitskii, S .. K-znaczy ++: zalety ostrożnego wysiewu. // Postępy 18. dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych. 2007., 1027–1035.)
• GREP - punkty reprezentatywne dla grupy . Pomysł metody - aby zebrać jako centraknajbardziej reprezentatywne, „zastępcze” sprawy. Pierwsze centrum jest traktowane jako przypadek najbliższy ogólnemu cenroidowi danych. Następnie pozostałe centra są wybierane z punktów danych w taki sposób, że każdy punkt jest rozważany pod kątem tego, czy jest on bliższy (i o ile, pod względem kwadratowej odległości euklidesowej) od zestawu punktów niż każdy z tych ostatnich jest do dowolnego z już istniejących centrów. Tj. Każdy punkt jest sprawdzany jako kandydat do reprezentowania pewnej grupy punktów, które nie są jeszcze wystarczająco dobrze reprezentowane przez już zebrane centra. Punkt najbardziej reprezentatywny pod tym względem jest wybierany jako następny środek. (Kaufman, L. Rousseeuw, PJ Znajdowanie grup w danych: wprowadzenie do analizy skupień., 1990. Zobacz także: Pena, JM i wsp. Empiryczne porównanie czterech metod inicjalizacji dla algorytmu K-średnich // Pattern Recognition Lett. 20 (10), 1999 r.,
• [Istnieje również niezła metoda, która nie została jeszcze przeze mnie zaimplementowana w makrze, do generowania kpunktów z losowego jednolitego, ale „mniej losowego niż losowego”, gdzieś pomiędzy losowym a chciwością; zobacz potencjalne podstawy teoretyczne dla tej metody]
• Jeszcze jedną metodą jest hierarchiczne grupowanie metodą Warda. Możesz to zrobić na podpróbce obiektów, jeśli próbka jest zbyt duża. Zatem środkami kwytworzonych przez niego klastrów są początkowe nasiona dla procedury k-średnich. Totemy są lepsze niż inne hierarchiczne metody grupowania, ponieważ mają wspólny cel docelowy z k-średnich.

Metody RGC, RP, SIMFP, KMPP zależą od liczb losowych i mogą zmieniać swoje wyniki z jednego uruchomienia do drugiego.

Metoda RUNFP może być wrażliwa na kolejność wielkości liter w zestawie danych; ale metoda GREP nie jest (poza przypadkami, gdy w danych występuje wiele identycznych przypadków, powiązań). Metoda GREP może nie zebrać wszystkich kcentrów, jeśli kjest duża w stosunku do liczby przypadków w data ( n), szczególnie kiedy k>n/2. [Makro poinformuje, czy dane nie pozwalają tej metodzie na gromadzenie kcentrów]. Metoda GREP jest najwolniejsza, oblicza [w mojej realizacji] macierz odległości między wszystkimi przypadkami, dlatego nie będzie pasować, jeśli istnieje wiele dziesiątek tysięcy lub milionów przypadków. Możesz to jednak zrobić na losowej podpróbce danych.

Nie dyskutuję obecnie, która metoda jest „lepsza” iw jakich okolicznościach, ponieważ do tej pory nie przeprowadzałem obszernego symulacyjnego sondowania tego pytania. Moje bardzo wstępne i powierzchowne wrażenia były takie, że GREP jest szczególnie godny (ale jest drogi) i że jeśli chcesz naprawdę taniej metody wciąż wystarczająco konkurencyjnej, to tylko losowe k punktów, RP, jest dobrym wyborem.

Ostatnim razem, gdy przeprowadziłem obszerny przegląd literatury na ten temat, co prawda, prawie 20 lat temu, dwie główne rekomendacje to:

1. Aby użyć metody Warda (jest to standardowy algorytm hierarchicznej analizy skupień) w celu znalezienia początkowych centrów.
2. Użyj losowych startów.

W aplikacjach big data metoda Warda nie działa tak dobrze, chociaż można ją zastosować do podpróbki.

Przeprowadziłem kilka symulacji, których nigdy nie opublikowałem, i stwierdziłem, że:

• 100 Losowych początków konsekwentnie przewyższało Metodę totemu.
• Domyślny algorytm SPSS dla znalezienia punktów startowych pokonał 100 losowych startpoints.
• Przy 1000 losowych punktach początkowych najlepszą metodą była konsekwentna randomizacja.

Najważniejsze z tego, co wyciągnąłem z tego, jest to, że algorytm SPSS jest zaskakująco dobry, ale jeśli ktoś ma zasoby, należy wybrać ponad 1000 losowych punktów początkowych.

Z nomenklaturą ttnphns przetestowałem RGC, RP i KMPP na:

• Punkty 2D / 3D
• worek słów z dokumentów tekstowych
• $L^2$

Nie polecam RGC, ponieważ powstałe centra są bardzo blisko siebie: średnia wielu punktów jest zbliżona do średniej globalnej (prawo wielkich liczb). Może to znacznie spowolnić konwergencję: zajmuje trochę czasu, zanim klastry zaczną się indywidualizować.

RP jest ogólnie dobra i poleciłaby jako pierwszy łatwy wybór.

KMPP jest bardzo popularny i działa bardzo dobrze w małym wymiarze: w porównaniu do RP ma tendencję do zmniejszania prawdopodobieństwa zakończenia lokalnego minimum.

Jednak kiedy pracowałem nad dużymi zestawami danych (punkty 1M, które są workami słów z dokumentów tekstowych o dużym wymiarze), RP nieznacznie przewyższyło KMPP w tym sensie, że zakończyło się nieco mniejszą liczbą iteracji. Byłem tym zaskoczony. W dużym zbiorze danych / wysokim wymiarze konwergencja do globalnego minimum jest niemożliwa, mierzysz jakość jako „jak dobre jest lokalne minimum” = „jak mały jest końcowy SOD”. Obie metody miały tę samą jakość.

Pamiętaj, że ważne jest użycie metody losowej, jeśli chcesz użyć replikacji w celu poprawy jakości.