Określanie liczby klastrów w zbiorze danych

Określenie liczby klastrów w zbiorze danych , wielkości często oznaczanej jako k , jak w algorytmie k -średnich , jest częstym problemem w klastrowaniu danych i jest odrębnym zagadnieniem od procesu faktycznego rozwiązywania problemu klastrowania.

Dla pewnej klasy algorytmów grupowania (w szczególności k -średnich, k -medoidów i algorytmu maksymalizacji oczekiwań ) istnieje parametr powszechnie określany jako k , który określa liczbę skupień do wykrycia. Inne algorytmy, takie jak algorytm DBSCAN i OPTICS , nie wymagają podania tego parametru; hierarchiczne klastrowanie całkowicie eliminuje ten problem.

Właściwy wybór k jest często niejednoznaczny, a interpretacje zależą od kształtu i skali rozkładu punktów w zbiorze danych oraz pożądanej przez użytkownika rozdzielczości grupowania. Ponadto, zwiększenie k bez kary zawsze zmniejszy ilość błędów w wynikowym grupowaniu, aż do skrajnego przypadku błędu zerowego, jeśli każdy punkt danych jest uważany za własny klaster (tj. gdy k jest równe liczbie punktów danych, n ). Intuicyjnie więc optymalny wybór k zapewni równowagę między maksymalną kompresją danych przy użyciu pojedynczego klastra, a maksymalną dokładnością poprzez przypisanie każdego punktu danych do jego własnego klastra . Jeśli odpowiednia wartość k nie wynika z wcześniejszej wiedzy o właściwościach zbioru danych, trzeba ją jakoś wybrać. Istnieje kilka kategorii metod podejmowania tej decyzji.

Metoda łokciowa

Wyjaśniona wariancja. „Kolanko” jest oznaczone czerwonym kółkiem. Liczba wybranych klastrów powinna zatem wynosić 4.

Metoda łokcia patrzy na procent wyjaśnionej wariancji jako funkcję liczby skupień: Należy wybrać taką liczbę skupień, aby dodanie kolejnego skupienia nie dawało znacznie lepszego modelowania danych. Dokładniej, jeśli wykreśli się procent wariancji wyjaśnionej przez klastry w funkcji liczby klastrów, pierwsze klastry dodadzą wiele informacji (wyjaśnią wiele wariancji), ale w pewnym momencie zysk krańcowy spadnie, dając kąt w wykres. W tym momencie wybiera się liczbę klastrów, stąd „kryterium łokcia”. W większości zbiorów danych to „łokieć” jest niejednoznaczne, co czyni tę metodę subiektywną i zawodną. Procent wyjaśnionej wariancji to stosunek wariancji między grupami do wariancji całkowitej, znany również jako test F. Niewielka odmiana tej metody przedstawia krzywiznę wariancji wewnątrz grupy.

Metodę można prześledzić do spekulacji Roberta L. Thorndike'a w 1953 roku. Chociaż idea metody łokciowej brzmi prosto i prosto, inne metody (opisane poniżej) dają lepsze wyniki.

X oznacza grupowanie

W statystyce i eksploracji danych klastrowanie ze średnimi X jest odmianą grupowania k-średnich , która udoskonala przydział klastrów poprzez wielokrotne próby podziału i utrzymywanie najlepszych wynikowych podziałów, aż do spełnienia kryterium, takiego jak kryterium informacyjne Akaike (AIC) lub Bayesowskie kryterium informacyjne (BIC) został osiągnięty.

Podejście oparte na kryteriach informacyjnych

Innym zestawem metod wyznaczania liczby skupień są kryteria informacyjne, takie jak kryterium informacyjne Akaike (AIC), bayesowskie kryterium informacyjne (BIC) czy kryterium informacyjne dewiacyjne (DIC) — jeśli możliwe jest wykonanie funkcji wiarygodności dla model klastrowania. Na przykład: k -średnich jest „prawie” modelem mieszaniny Gaussa i można skonstruować prawdopodobieństwo dla modelu mieszaniny Gaussa, a tym samym określić również wartości kryteriów informacyjnych.

Podejście informacyjno-teoretyczne

Teoria zniekształceń szybkości została zastosowana do wyboru k zwanego metodą „skoku”, która określa liczbę klastrów, która maksymalizuje wydajność, jednocześnie minimalizując błąd według standardów teorii informacji . Strategia algorytmu polega na wygenerowaniu krzywej zniekształcenia dla danych wejściowych przez uruchomienie standardowego algorytmu grupowania, takiego jak k-średnie dla wszystkich wartości k między 1 a n , i obliczenie zniekształcenia (opisane poniżej) wynikowego grupowania. Krzywa zniekształcenia jest następnie przekształcana przez ujemną moc wybraną na podstawie wymiarowości danych. Skoki w wartościach wynikowych oznaczają wtedy rozsądne wybory dla k , przy czym największy skok reprezentuje najlepszy wybór.

Zniekształcenie grupowania niektórych danych wejściowych jest formalnie zdefiniowane w następujący sposób: Niech zestaw danych będzie modelowany jako p -wymiarowa zmienna losowa , X , składająca się z rozkładu mieszanego składowych G o wspólnej kowariancji , $Γ$ . Jeśli pozwolimy być zbiorem ${1} \ ldots$ klastrów, z najbliższym centrum danej próbki X do 1 … do K. ${K}$ } , to minimalne średnie zniekształcenie na wymiar przy dopasowywaniu środków K do danych wynosi:

{\ Displaystyle d_ {K} = {\ Frac {1} {p}} \ min _{c_{1}\ldots c_{K}}{E[(X-c_{X})^{T}\Gamma ^{-1}(X-c_{X})]}}

Jest to również średnia odległość Mahalanobisa na wymiar między X a najbliższym centrum klastra ${\ displaystyle c_ {X}}$ . Ponieważ minimalizacja wszystkich możliwych zestawów centrów klastrów jest zbyt złożona, zniekształcenie jest w praktyce obliczane przez wygenerowanie zestawu centrów klastrów przy użyciu standardowego algorytmu grupowania i obliczenie zniekształcenia na podstawie wyniku. Pseudokod dla metody skoku z wejściowym zestawem p -wymiarowych punktów danych X to:

 JumpMethod(X):  Niech  Y = (p/2)  Zainicjuj  listę D o rozmiarze n+1  Niech  D[0] = 0  Dla  k = 1 ... n: Klaster X z k klastrami (np. z k- oznacza)  Niech  d = Zniekształcenie wynikowego skupienia D[k] = d^(-Y)  Zdefiniuj  J(i) = D[i] - D[i-1]  Zwróć  k między 1 a n, które maksymalizuje J(k )

Wybór mocy transformacji $z$ rozumowaniem asymptotycznym wyników $pewnego$ dane X pojedynczy, dowolnie - wymiarowy rozkład Gaussa i niech ustalone większego $od$ zera Wtedy zniekształcenie skupienia K klastrów w granicy , gdy p dąży do nieskończoności, wynosi ${\ displaystyle \ alpha ^ {- 2}}$ . Można zauważyć, że $proporcjonalne$ $potęgi$ , definicji jest w przybliżeniu liczbą klastrów K . Innymi słowy, dla pojedynczego rozkładu Gaussa zwiększenie K poza rzeczywistą liczbę skupień, która powinna wynosić jeden, powoduje liniowy wzrost zniekształceń. To zachowanie jest ważne w ogólnym przypadku mieszaniny wielu składników rozkładu.

Niech X będzie mieszaniną G p -wymiarowych rozkładów Gaussa o wspólnej kowariancji. Wtedy dla dowolnego ustalonego K mniejszego niż G zniekształcenie skupienia, gdy p dąży do nieskończoności, jest nieskończone. Intuicyjnie oznacza to, że grupowanie mniejszej niż prawidłowa liczby klastrów nie jest w stanie opisać asymptotycznie wielowymiarowych danych, powodując nieograniczony wzrost zniekształceń. Jeśli, jak opisano powyżej, K uczyni się rosnącą funkcją p , a mianowicie ${\ Displaystyle K = \ lfloor \ alpha ^ {p} \ rfloor}$ , uzyskuje się taki sam wynik jak powyżej, z wartość zniekształcenia w granicy, gdy p dąży do nieskończoności, jest równa ${\ displaystyle \ alpha ^ {- 2}}$ . Odpowiednio, istnieje taka sama proporcjonalna zależność między przekształconym zniekształceniem a liczbą klastrów, K .

$p$ można zauważyć, że dla wystarczająco wysokich wartości , przekształcone zniekształcenie zero dla K < sol , następnie nagle skacze i zaczyna rosnąć liniowo dla K ≥ G . Algorytm skoku do wybierania K wykorzystuje te zachowania do identyfikacji najbardziej prawdopodobnej wartości dla prawdziwej liczby klastrów.

Chociaż matematyczne wsparcie dla metody jest podane w postaci wyników asymptotycznych, algorytm został zweryfikowany empirycznie i działa dobrze w różnych zestawach danych o rozsądnej wymiarowości. Oprócz metody zlokalizowanego skoku opisanej powyżej, istnieje drugi algorytm wyboru K przy użyciu tych samych przekształconych wartości zniekształceń, znany jako metoda linii łamanej. Metoda linii łamanych identyfikuje punkt przeskoku na wykresie przekształconego zniekształcenia, wykonując proste najmniejszych kwadratów dwóch odcinków linii, które teoretycznie będą opadać wzdłuż osi x dla K < G i wzdłuż liniowo rosnącej fazy przekształconego wykresu zniekształcenia dla K ≥ G . Metoda linii łamanych jest bardziej niezawodna niż metoda skoków, ponieważ jej decyzja jest raczej globalna niż lokalna, ale opiera się również na założeniu składników mieszaniny Gaussa, podczas gdy metoda skoków jest w pełni nieparametryczna i wykazano, że jest opłacalna dla ogólne rozkłady mieszanin.

Metoda sylwetki

Średnia sylwetka danych jest kolejnym przydatnym kryterium oceny naturalnej liczby skupień. Sylwetka instancji danych jest miarą tego, jak blisko jest ona dopasowana do danych w swoim klastrze i jak luźno jest dopasowana do danych sąsiedniego klastra, tj. klastra, którego średnia odległość od punktu odniesienia jest najmniejsza. Sylwetka bliska 1 oznacza, że dane znajdują się w odpowiednim skupieniu, podczas gdy sylwetka zbliżona do -1 oznacza, że dane znajdują się w niewłaściwym skupieniu. Techniki optymalizacyjne, takie jak algorytmy genetyczne, są przydatne w określaniu liczby klastrów, które dają największą sylwetkę. Możliwe jest również ponowne przeskalowanie danych w taki sposób, aby zmaksymalizować sylwetkę przy prawidłowej liczbie klastrów.

Walidacja krzyżowa

Można również wykorzystać proces walidacji krzyżowej do analizy liczby klastrów. W tym procesie dane są dzielone na v części. Każda z części jest następnie odkładana na bok jako zbiór testowy, model skupień obliczany na innych v - 1 i wartość funkcji celu (na przykład suma kwadratów odległości do środków ciężkości dla k -średnie) obliczone dla zbioru testowego. Te v oblicza się i uśrednia dla każdej alternatywnej liczby skupień, a numer skupień wybiera się tak, że dalszy wzrost liczby skupień prowadzi tylko do niewielkiej redukcji funkcji celu.

Znajdowanie liczby klastrów w tekstowych bazach danych

W tekstowych bazach danych zbiór dokumentów zdefiniowany przez dokument terminem macierz D (o rozmiarze m×n, gdzie m to liczba dokumentów, a n to liczba terminów), liczbę klastrów można z grubsza oszacować za pomocą wzoru $.$ jest liczbą niezerowych wpisów w D. Zauważ, że w D każdy wiersz i każda kolumna musi zawierać co najmniej jeden element niezerowy

Analiza macierzy jądra

Macierz jądra określa bliskość informacji wejściowych. Na przykład w radialnej funkcji bazowej Gaussa określa iloczyn skalarny danych wejściowych w przestrzeni o wyższych wymiarach, zwanej przestrzenią cech . Uważa się, że dane stają się bardziej separowalne liniowo w przestrzeni cech, a zatem algorytmy liniowe mogą być stosowane do danych z większym powodzeniem.

Macierz jądra można zatem przeanalizować w celu znalezienia optymalnej liczby klastrów. Metoda opiera się na dekompozycji wartości własnej macierzy jądra. Następnie przeanalizuje wartości własne i wektory własne, aby uzyskać miarę zwartości rozkładu wejściowego. Na koniec zostanie narysowany wykres, w którym kolanko tego wykresu wskazuje optymalną liczbę klastrów w zbiorze danych. W przeciwieństwie do poprzednich metod, ta technika nie wymaga wykonywania żadnego grupowania a priori. Bezpośrednio znajduje liczbę klastrów z danych.

Statystyka luki

Robert Tibshirani , Guenther Walther i Trevor Hastie zaproponowali oszacowanie liczby klastrów w zbiorze danych za pomocą statystyki luk. Statystyki luk, oparte na podstawach teoretycznych, mierzą, jak daleko jest zsumowana suma kwadratów wewnątrz klastra wokół centrów klastrów od sumy kwadratów oczekiwanej przy zerowym rozkładzie odniesienia danych. Oczekiwana wartość jest szacowana poprzez symulację zerowych danych referencyjnych o cechach oryginalnych danych, ale bez żadnych skupień. Optymalna liczba klastrów jest następnie szacowana jako wartość k , dla której obserwowana suma kwadratów spada najdalej poniżej zerowego odniesienia.

W przeciwieństwie do wielu poprzednich metod, statystyki luk mogą nam powiedzieć, że nie ma wartości k , dla której istnieje dobre grupowanie.

Statystyka luk jest zaimplementowana jako funkcja clusGap w pakiecie klastrowym w R .

Dalsza lektura

Ralf Wagner , Sören W. Scholz, Reinhold Decker (2005): Liczba klastrów w segmentacji rynku, w: Daniel Baier, Reinhold Decker; Lars Schmidt-Thieme (red.): Analiza danych i wspomaganie decyzji, Berlin, Springer, 157–176.

Linki zewnętrzne

Clustergram – klasterowy wykres diagnostyczny – do wizualnej diagnostyki wyboru ilości ( k ) klastrów ( kod R )
Osiem metod określania optymalnej wartości k dla analizy k -średnich – Odpowiedź na stackoverflow zawierająca kod R dla kilku metod obliczania optymalnej wartości k dla k -średniej analizy skupień
Partycjonowanie i klastrowanie: ile klas? Bezpłatny artykuł seminaryjny dostępny na serwerze HAL, id=hal-02124947: przedstawiono dwie metody nieparametryczne (dostarczono odniesienia bibliograficzne), jedną dla zmiennych numerycznych (działa z tablicą odległości, niekoniecznie euklidesowych), jedną dla zmiennych kategorycznych ( optymalne partycjonowanie; działa również ze znakowanymi odmiennościami).