http://www.dataminer.pl/textbook/stathome_stat.html?http%3A%2F%2Fwww.dataminer.pl%2Ftextbook%2Fstcluan.html

© Copyright StatSoft, Inc., 1984-2005

Analiza skupień

• Ogólny cel

• Testowanie istotności statystycznej

• Obszary zastosowań

• Aglomeracja

• Hierarchiczne drzewo

• Miary odległości

• Metody łączenia lub wiązania

• Grupowanie obiektów i cech

• Wprowadzenie

• Grupowanie obiektów i cech

• Grupowanie metodą k-średnich

• Przykład

• Obliczenia

• Interpretacja wyników

• Grupowanie metodą EM

• Wprowadzenie

• Algorytm EM

• Szukanie najlepszej liczby skupień uogólnioną metodą EM i k-średnich: v-krotny sprawdzian krzyżowy

Ogólny cel

Pojęcie analizy skupień (ang. cluster analysis, termin wprowadzony w pracy Tryon, 1939) obejmuje faktycznie kilka różnych algorytmów klasyfikacji. Ogólny problem badaczy wielu dyscyplin polega na organizowaniu obserwowanych danych w sensowne struktury lub grupowaniu danych. Innymi słowy, analiza skupień jest narzędziem do eksploaracyjnej analizy danych, której celem jest ułożenie obiektów w grupy w taki sposób, aby stopień powiązania obiektów z obiektami należącymi do tej samej grupy był jak największy, a z obiektami z pozostałych grup jak najmniejszy. Analiza skupień może być wykorzystywana do wykrywania struktur w danych bez wyprowadzania interpretacji/wyjaśnienia. Mówiąc krótko: analiza skupień jedynie wykrywa struktury w danych bez wyjaśniania dlaczego one występują.

Z klasyfikacją spotykamy się prawie na każdym kroku codziennego życia. Przykładowo, goście dzielący ten sam stolik w restauracji mogą być potraktowani jako grupa ludzi. W sklepach spożywczych produkty podobnego typu, jak np. różne rodzaje mięs czy warzyw, są wystawione w tym samym miejscu bądź bardzo blisko siebie. Istnieje wiele przykładów, w których skupienia/klasyfikacja odgrywa ważną rolę. Na przykład biolodzy zanim będą mogli sensownie opisywać różnice między zwierzętami, muszą klasyfikować je ze względu na gatunki. Zgodnie z nowoczesnym systemem stosowanym w biologii człowiek należy do naczelnych, ssaków, owodniowców, kręgowców i zwierząt. Zauważmy przy tej klasyfikacji, że im wyższy poziom agregacji, tym mniejsze jest podobieństwo pomiędzy członkami poszczególnych klas. Człowiek jest bardziej podobny do wszystkich innych naczelnych (np. małp) niż do bardziej "odległych" ssaków (np. psów) itd. Przegląd ogólnych typów metod analizy skupień znajduje się następnych trzech tematach: Aglomeracja , Grupowanie obiektów i cech (grupowanie blokowe) i Grupowanie metodą k-średnich .

Testowanie istotności statystycznej

Zauważmy, że w powyższej części omówiliśmy algorytmy grupowania i nie wspominaliśmy nic o testowaniu istotności statystycznej. Analiza skupień nie jest testem statystycznym, ale "kolekcją" różnych algorytmów , które "grupują obiekty w skupienia". Chodzi tu o to, że, w odróżnieniu od wielu innych procedur statystycznych, metody analizy skupień są stosowane przeważnie wtedy, gdy nie dysponujemy żadnymi hipotezami a priori, natomiast jesteśmy nadal w fazie eksploracyjnej naszych badań. Dlatego testowanie istotności statystycznej w tradycyjnym rozumieniu tego pojęcia faktycznie nie znajduje tutaj zastosowania, nawet w przypadkach, gdy podawane są poziomy p (jak w grupowaniu metodą k-średnich ).

Obszary zastosowań

Techniki grupowania stosuje się w wielu różnych dziedzinach badawczych. Doskonałego zestawienia wielu opublikowanych studiów informujących o wynikach analiz skupień dostarcza Hartigan (1975). Na przykład, w dziedzinie medycyny grupowanie chorób, metod leczenia lub symptomów chorób może prowadzić do wielu użytecznych klasyfikacji. W psychiatrii poprawna diagnoza wiązek symptomów takich jak paranoja, schizofrenia itd. jest konieczna dla udanej terapii. W archeologii badacze stosując techniki analizy skupień usiłują pogrupować narzędzia kamienne, akcesoria pogrzebowe itd. Mówiąc ogólnie, zawsze wtedy gdy potrzebujemy poklasyfikować "duży" zasób informacji w sensowne grupy, analiza skupień okaże się wartościowym narzędziem.

Indeks

Aglomeracja

• Hierarchiczne drzewo

• Miary odległości

• Metody łączenia lub wiązania

Wprowadzenie

Przykłady przedstawione w części Ogólne cele ilustrują cel algorytmu aglomeracji. Algorytm ten służy do grupowania obiektów (np. zwierząt) w coraz to większe zbiory (skupienia), z zastosowaniem pewnej miary podobieństwa lub odległości. Typowym wynikiem tego typu grupowania jest hierarchiczne drzewo.

Hierarchiczne drzewo

Rozważmy poziomy hierarchicznego wykresu drzewkowego rozpoczynając od lewej strony wykresu, gdzie każdy obiekt stanowi swoją własną klasę. Wyobraźmy sobie teraz, że bardzo małymi krokami "osłabiamy" nasze kryterium tego, na ile jest on lub nie jest wyjątkowy. Innymi słowy, obniżamy próg stanowiący o decyzji przypisania dwóch lub więcej obiektów do tego samego skupienia.

Tym sposobem wiążemy ze sobą coraz to więcej obiektów i agregujemy je w coraz to większe skupienia elementów coraz bardziej różniących się od siebie. W końcu, na ostatnim etapie, wszystkie obiekty zostają ze sobą połączone. Na wykresach tych na osi poziomej odłożone są odległości aglomeracyjne (w pionowych wykresach sopelkowych odległość aglomeracyjna odkładana jest na osi pionowej). Zatem przy każdym węźle na wykresie (gdzie uformowało się nowe skupienie) możemy odczytać odległość, w której odpowiednie elementy zostały powiązane ze sobą tworząc nowe pojedyncze skupienie. Jeśli dane mają wyrazistą "strukturę" w tym sensie, że istnieją skupienia podobnych do siebie obiektów, to często struktura ta znajdzie odbicie na hierarchicznym drzewie w postaci oddzielnych gałęzi. Pomyślna analiza przy pomocy metody łączenia daje możliwość wykrywania skupień (gałęzi) i ich interpretacji.

Miary odległości

W metodzie aglomeracji przy formowaniu skupień wykorzystywane są miary rozbieżności lub odległości pomiędzy obiektami. Na przykład, gdybyśmy mieli pogrupować dania barowe, moglibyśmy wziąć pod uwagę liczbę kalorii, cenę, subiektywne oceny smaku itd. Najbardziej bezpośrednim sposobem obliczenia odległości między obiektami w przestrzeni wielowymiarowej jest obliczenie odległości euklidesowej. Jeśli mamy przestrzeń dwu- lub trójwymiarową, miara ta wyznacza rzeczywistą odległość geometryczną między obiektami w przestrzeni (tzn. taką, jaką uzyskuje się przy pomocy linijki). Z punktu widzenia algorytmu łączenia jest jednak obojętne, czy odległości które mu "zadajemy" są rzeczywistymi odległościami, czy też jakimiś innymi pochodnymi miarami odległości, które dla badacza mają większe znaczenie; zatem tylko od badacza zależy wybór odpowiedniej miary.

Odległość euklidesowa. Jest to prawdopodobnie najczęściej wybierany typ odległości. Czyli po prostu odległość geometryczna w przestrzeni wielowymiarowej. Oblicza się ją następująco:

odległość(x,y) = {
_i (x_i - y_i)² }^½

Zauważmy, że odległości euklidesowe (oraz kwadraty odległości euklidesowych) są wyliczane w oparciu o surowe dane, a nie na podstawie danych standaryzowanych. Metoda ta ma pewne zalety (np. na odległość pomiędzy dwoma dowolnymi obiektami nie ma wpływu dodanie do analizy nowych obiektów, które mogą być obiektami odstającymi). Jednakże na odległości duży wpływ mają różnice jednostek między wymiarami, na podstawie których są wyliczane odległości. Na przykład, jeśli jeden z wymiarów oznacza długość mierzoną w centymetrach, to po przekształceniu go na milimetry (mnożąc odpowiednie wartości przez 10), najczęściej otrzymamy zdecydowanie odmienne odległości euklidesowe i kwadraty odległości euklidesowych (obliczane dla wielu wymiarów). Może to spowodować otrzymanie zupełnie innych wyników analizy skupień. W ogólnym przypadku, dobrze jest stosować standaryzację tak by mieć dane o porównywalnej skali.

Kwadrat odległości euklidesowej. Odległość euklidesową podnosi się do kwadratu, aby przypisać większą wagę obiektom, które są bardziej oddalone. Oblicza się ją następująco (zobacz także na uwagę zamieszczoną powyżej):

odległość(x,y) =
_i (x_i - y_i)²

Odległość miejska (Manhattan, City block). Ta odległość jest po prostu sumą różnic mierzonych wzdłuż wymiarów. W większości przypadków ta miara odległości daje podobne wyniki, jak zwykła odległość euklidesowa. Zauważmy jednakże, że w przypadku tej miary, wpływ pojedynczych dużych różnic (przypadków odstających) jest stłumiony (ponieważ nie podnosi się ich do kwadratu). Odległość miejską oblicza się następująco:

odległość(x,y) =
_i |x_i - y_i|

Odległość Czebyszewa. Taka miara odległości jest stosowna w tych przypadkach, w których chcemy zdefiniować dwa obiekty jako "inne", wtedy gdy różnią się one w jednym dowolnym wymiarze. Odległość Czebyszewa oblicza się następująco:

odległość(x,y) = Maksimum|x_i - y_i|

Odległość potęgowa. Czasami chcemy zwiększyć lub zmniejszyć wzrastającą wagę, która jest przypisana do wymiarów, w przypadku których odpowiednie obiekty bardzo się różnią. Można to osiągnąć przy pomocy odległości potęgowej. Liczy się ją następująco:

odległość(x,y) = (
_i |x_i - y_i|^p)^1/r

gdzie r i p są parametrami zdefiniowanymi przez użytkownika. Kilka przykładowych obliczeń może pokazać jak się "zachowuje" ta miara. Parametr p steruje wzrastającą wagą, która jest przypisana różnicom w poszczególnych wymiarach, parametr r steruje wzrastającą wagą, która jest przypisana większym różnicom między obiektami. Jeśli r i p są równe 2, to odległość ta jest równa odległości euklidesowej.

Niezgodność procentowa. Ta miara jest szczególnie przydatna wtedy, gdy dane dla wymiarów objętych analizą są z natury dyskretne. Odległość liczy się następująco:

odległość(x,y) = (Liczba x_i
y_i)/ i

Metody łączenia lub wiązania

Na pierwszym etapie, gdy każdy obiekt reprezentuje swoje własne skupienie, odległości między tymi obiektami definiuje się przy pomocy wybranej miary odległości. Jak jednak określić odległości między nowymi skupieniami, które powstaną z powiązanych obiektów? Innymi słowy, potrzebujemy zasadę wiązania lub aglomeracji, która określi, kiedy dwa skupienia są dostatecznie podobne, aby można je było połączyć. Istnieje kilka możliwości: na przykład, moglibyśmy powiązać ze sobą dwa skupienia, gdy dowolne dwa obiekty z tych dwóch skupień znajdują się w mniejszej odległości niż odpowiednia odległość wiązania. Innymi słowy, aby określić odległości między skupieniami, wykorzystamy najbliższych sąsiadów między skupieniami; metoda ta nosi nazwę pojedynczego wiązania (ang. single linkage). W wyniku zastosowania tej metody powstają skupienia typu "włóknistego", co oznacza, że są one połączone ze sobą tylko przez pojedyncze obiekty, które leżą najbliżej siebie. Alternatywnie, możemy wykorzystać sąsiadów, którzy są najbardziej od siebie oddaleni; ta metoda nosi nazwę pełnego wiązania (ang. complete linkage). Istnieje jeszcze wiele innych zasad wiązania podobnych do zaproponowanych tutaj.

Metoda pojedynczego wiązania (najbliższego sąsiedztwa). Jak to zostało opisane powyżej, w metodzie tej odległość między dwoma skupieniami jest określona przez odległość między dwoma najbliższymi obiektami (najbliższymi sąsiadami) należącymi do różnych skupień. Zgodnie z tą zasadą obiekty formują skupienia łącząc się w ciągi, a wynikowe skupienia tworzą długie "łańcuchy".

Metoda pełnego wiązania (najdalszego sąsiedztwa). W tej metodzie odległość między skupieniami jest zdeterminowana przez największą z odległości między dwoma dowolnymi obiektami należącymi do różnych skupień (tzn. "najdalszymi sąsiadami"). Metoda ta zwykle zdaje egzamin w tych przypadkach, kiedy obiekty faktycznie formują naturalnie oddzielone "kępki". Metoda ta nie jest odpowiednia, jeśli skupienia są w jakiś sposób wydłużone lub mają naturę "łańcucha".

Metoda średnich połączeń. W metodzie tej odległość między dwoma skupieniami oblicza się jako średnią odległość między wszystkimi parami obiektów należących do dwóch różnych skupień. Metoda ta jest efektywna, gdy obiekty formują naturalnie oddzielone "kępki", ale zdaje także egzamin w przypadku skupień wydłużonych, mających charakter "łańcucha". Zwróćmy uwagę, że Sneath i Sokal w swojej pracy (1973) na określenie tej metody wprowadzili skrót UPGMA (unweighted pair-group method using arithmetic averages).

Metoda średnich połączeń ważonych. Jest to metoda identyczna jak metoda średnich połączeń, z tym wyjątkiem, że w obliczeniach uwzględnia się wielkość odpowiednich skupień (tzn. liczbę zawartych w nich obiektów) jako wagę. Zatem raczej ta metoda niż poprzednia, powinna być stosowana wtedy, gdy podejrzewamy, że liczności skupień są wyraźnie nierówne. Sneath i Sokal (1973) na określenie tej metody wprowadzili skrót WPGMA (weighted pair-group method using arithmetic averages).

Metoda środków ciężkości. Środek ciężkości skupienia jest średnim punktem w przestrzeni wielowymiarowej zdefiniowanej przez te wymiary. W metodzie tej, odległość między dwoma skupieniami jest określona jako różnica między środkami ciężkości. Sneath i Sokal (1973) na oznaczenie tej metody stosują skrót UPGMC (unweighted pair-group method using the centroid average).

Metoda ważonych środków ciężkości (mediany). Jest to metoda identyczna jak poprzednia, z tym wyjątkiem, że w obliczeniach wprowadza się ważenie, aby uwzględnić różnice między wielkościami skupień (tzn. liczbą zawartych w nich obiektów). Zatem, metoda ta jest lepsza od poprzedniej w sytuacji, gdy istnieją (lub podejrzewamy, że istnieją) znaczne różnice w rozmiarach skupień. Sneath i Sokal (1973) na oznaczenie tej metody stosują skrót WPGMC (weighted pair-group method using the centroid average).

Metoda Warda. Ta metoda różni się od wszystkich pozostałych, ponieważ do oszacowania odległości między skupieniami wykorzystuje podejście analizy wariancji. Mówiąc krótko, metoda ta zmierza do minimalizacji sumy kwadratów odchyleń dowolnych dwóch skupień, które mogą zostać uformowane na każdym etapie. Szczegóły na temat tej metody znajdują się w: Ward (1963). Ogólnie, metoda ta jest traktowana jako bardzo efektywna, chociaż zmierza do tworzenia skupień o małej wielkości.

Przegląd dwóch innych metod grupowania znajduje się w tematach: Grupowanie obiektów oraz cech i Grupowanie metodą k-średnich .

Indeks

Grupowanie obiektów i cech

• Wprowadzenie

• Grupowanie obiektów i cech

Wprowadzenie

Poprzednio omawialiśmy tę metodę w kategoriach "obiektów", które mają zostać pogrupowane (patrz Aglomeracja - Wprowadzenie ). We wszystkich innych typach analiz pytanie badawcze jest zwykle wyrażone w kategoriach przypadków (obserwacji) lub zmiennych. Okazuje się, że grupowanie przypadków i zmiennych może doprowadzić do ciekawych wyników. Na przykład, wyobraźmy sobie eksperyment, w którym badacz zgromadził dane o różnych miarach sprawności fizycznej (zmienne) dla próby pacjentów z chorobami serca (przypadki). Badacz może chcieć poklasyfikować przypadki (pacjentów), aby wykryć skupienia pacjentów o podobnych syndromach. Jednocześnie badacz może chcieć poklasyfikować zmienne (miary sprawności), aby wykryć skupienia miar, które dotyczą podobnych zdolności fizycznych.

Grupowanie obiektów i cech.

Po dyskusji w powyższym akapicie dotyczącej tego, czy grupować przypadki, czy zmienne, można spytać dlaczego by nie grupować jednych i drugich jednocześnie? Analiza skupień zawiera procedurę grupowania obiektów i cech, która służy właśnie do tego. Grupowanie obiektów i cech przydaje się w (stosunkowo rzadkich) okolicznościach, gdy oczekujemy, że zarówno przypadki, jak i zmienne jednocześnie przyczyniają się do odkrywania sensownych układów skupień.

Na przykład, wracając do tego samego przykładu, badacz może chcieć zidentyfikować skupienia pacjentów, którzy są podobni ze względu na poszczególne skupienia podobnych miar sprawności fizycznej. Trudność w interpretacji takich wyników może brać się stąd, że podobieństwa między różnymi skupieniami mogą odnosić się do (lub wynikać z) nieco innych podzbiorów zmiennych. Zatem wynikowa struktura (układ skupień) z natury nie jest homogeniczna. Z początku może się to wydawać dość niejasne i faktycznie, porównując z innymi opisanymi metodami grupowania (patrz Aglomeracja i Grupowanie metodą k-średnich ), grupowanie obiektów i cech jest prawdopodobnie wykorzystywane najrzadziej. Niektórzy badacze jednak wierzą, że metoda ta stanowi mocne narzędzie eksploracyjnej analizy danych (szczegółowy opis tej metody znajduje się w: Hartigan, 1975).

Indeks

Grupowanie metodą k-średnich

• Przykład

• Obliczenia

• Interpretacja wyników

Wprowadzenie

Ta metoda grupowania różni się znacznie od metod Aglomeracji i Grupowania obiektów . Załóżmy, że sformułowaliśmy już hipotezę na temat liczby skupień naszych przypadków lub zmiennych. Możemy "powiedzieć" komputerowi, aby uformował dokładnie 3 skupienia, które będą tak różne, jak to tylko możliwe. Temu typowi problemu badawczego odpowiada algorytm grupowania metodą k-średnich. Ogólnie, przy pomocy metody k-średnich zostanie utworzonych k skupień, w możliwie największym stopniu różniących się od siebie. Należy wspomnieć, że optymalna liczba skupień nie jest znana z góry i powinna być wyliczana na podstawie danych (patrz Szukanie najlepszej liczby skupień ).

Przykład.

W przykładzie dotyczącym sprawności fizycznej (patrz Grupowanie obiektów ), badacz może się "domyślać" (na podstawie doświadczenia klinicznego), że pacjenci z chorobami serca zostaną zakwalifikowani do trzech różnych kategorii ze względu na sprawność fizyczną. Może być ciekawy, czy ta intuicja da się sformułować ilościowo, to znaczy, czy zgodnie z oczekiwaniem, analiza skupień metodą k-średnich miar sprawności fizycznej faktycznie utworzy trzy skupienia pacjentów. Jeśli tak, to średnie różnych miar sprawności fizycznej dla każdego skupienia reprezentowałyby ilościowy sposób wyrażenia hipotez lub intuicji badacza (tzn. pacjenci w skupieniu 1 są wysoko według miary 1, nisko według miary 2 itd.).

Obliczenia.

Z punktu widzenia obliczeń, można tę metodę traktować jako "odwrotność" analizy wariancji (ANOVA ). Należy rozpocząć od k losowych skupień, a następnie przenosić obiekty między tymi skupieniami mając na celu (1) minimalizację zmienności wewnątrz skupień i (2) maksymalizację zmienności między skupieniami. Innymi słowy, maksymalne podobieństwo będzie charakteryzowało członków danego skupienia/grupy, a minimalne podobieństwo będzie między członkami danej grupy a pozostałymi obiektami. Jest to "odwrotność" analizy wariancji w tym sensie, iż test istotności w ANOVA porównuje zmienność międzygrupową ze zmiennością wewnątrzgrupową przy przeprowadzaniu testu istotności dla hipotezy, że średnie w grupach nie różnią się od siebie. W grupowaniu metodą k-średnich, staramy się tak przenosić obiekty (np. przypadki) między grupami, aby uzyskać największy poziom istotności analizy ANOVA.

Interpretacja wyników.

Zazwyczaj w wyniku analizy grupowania metodą k-średnich badamy średnie dla każdego skupienia w każdym wymiarze, aby oszacować, na ile nasze skupienia są od siebie różne. W sytuacji idealnej otrzymalibyśmy bardzo różne średnie dla większości, jeśli nie wszystkich wymiarów uwzględnionych w analizie. Wielkość statystyki F pochodzącej z analizy wariancji wykonanej w każdym wymiarze jest wskaźnikiem tego, na ile dobrze dany wymiar dyskryminuje skupienia.

Indeks

Grupowanie metodą EM

• Wprowadzenie

• Algorytm EM

Wprowadzenie

Metody stosowane w przypadku uogólnionej analizy skupień są podobne do metody k-średnich wykorzystywanej w standardowej analizie skupień, tak więc warto zapoznać się z Wprowadzeniem do grupowania metodą k-średnich. Ogólnym celem tych metod jest wykrycie skupień obserwacji (lub zmiennych) i przyporządkowanie obserwacji do skupień. Typowym przykładem analizy tego rodzaju są badania marketingowe, gdzie dla dużej próby respondentów zbierane są pomiary pewnej liczby zmiennych opisujących zachowania konsumenckie. Celem badania jest utworzenia "segmentacji rynku," tzn. wyznaczenie grup respondentów, którzy są w jakiś sposób do siebie podobni (to znaczy podobni w obrębie tego samego skupienia) w odróżnieniu od konsumentów z innych grup. Oprócz wyznaczenia skupień zazwyczaj równie interesujące jest ustalenie w czym skupienia różnią się od siebie, tzn. ustalenie zmiennych i wymiarów, które wyznaczają skupienia oraz określenie w jaki sposób.

Grupowanie metodą k-średnich. Klasyczny algorytm k-średnich został spopularyzowany przez Hartigana (1975; zob. Hartigan i Wong, 1978). Podstawa algorytmu jest stosunkowo prosta: Przy ustalonej liczbie (pożądanej lub przyjętej hipotetycznie) k skupień obserwacje przypisujemy do skupień tak, by średnie w skupieniach (dla wszystkich zmiennych) były jak najbardziej od siebie różne.

Rozszerzenia i uogólnienia. Metody stosowane w uogólnionej analizie skupień metodami EM i k-średnich stanowią rozszerzenie tego podejścia w trzech ważnych aspektach:

1. Zamiast przyporządkowywać przypadki (obserwacje) do skupień tak, by różnice pomiędzy średnimi (zmiennych ilościowych) w grupach były jak największe, algorytm EM (maksymalizacja wartości oczekiwanej) oblicza prawdopodobieństwa przynależności do skupień przy założeniu jednego lub wielu rozkładów prawdopodobieństwa. Celem algorytmu jest maksymalizacja ogólnego prawdopodobieństwa (wiarygodności danych), dla danego podziału na skupienia.

2. W odróżnieniu od klasycznej implementacji k-średnich, algorytm EM może być stosowany zarówno do zmiennych ilościowych jak i jakościowych (zauważmy, że klasyczny algorytm k-średnich może także zmodyfikować tak, by mógł być stosowany do zmiennych jakościowych).

Algorytm EM

Algorytm analizy skupień metodą EM opisany jest szczegółowo w Witten i Frank (2001). Główna idea tej metody jest taka: załóżmy, że obserwujemy dużą próbę pomiarów jednej zmiennej ilościowej. Przypuśćmy dodatkowo, że składają się na nią dwa skupienia obserwacji o różnych średnich (i być może różnych odchyleniach). W każdej próbie rozkład wartości zmiennej ilościowej jest normalny. Wynikowy rozkład wartości zmiennej może wyglądać tak:

Mieszaniny rozkładów. Powyższa ilustracja pokazuje dwa rozkłady normalne z różnymi średnimi i odchyleniami standardowymi, oraz sumę tych dwóch rozkładów. Obserwujemy samą mieszaninę (sumę) tych dwóch rozkładów (z różnymi średnimi i odchyleniami standardowymi). Celem metody EM jest oszacowanie średnich i odchyleń standardowych dla każdej grupy, tak aby zmaksymalizować wiarygodność obserwowanych danych (rozkładu). Mówiąc inaczej, algorytm metody EM próbuje aproksymować obserwowany rozkład watości jako mieszaninę rozkładów różnych grup.

Dzięki metodzie EM zaimplementowanej w programie komputerowym, jesteśmy w stanie wybrać (dla zmiennych ciągłych) różne rozkłady, jak np. rozkład normalny , logarytmiczno-normalny czy Poissona . Możemy także wybrać różne rozkłady dla różnych zmiennych i stąd, wyznaczać grupy z mieszanin różnych typów rozkładów.

Zmienne jakościowe. Implementacja algorytmu EM potrafi korzystać ze zmiennych jakościowych. Najpierw losowo przydziela prawdopodobieństwa (wagi) każdej z klas (kategorii), w każdym ze skupień. W kolejnych iteracjach prawdopodobieństwa są poprawiane tak, by zmaksymalizować wiarygodność danych przy podanej ilości skupień.

Prawdopodobieństwa klasyfikacyjne zamiast klasyfikacji. Wyniki analizy skupień metodą EM są inne niż obliczone metodą k-średnich. Ta ostatnia wyznacza skupienia. Algorytm EM nie wyznacza przyporządkowania obserwacji do klas lecz prawdopodobieństwa klasyfikacyjne. Inaczej mówiąc, każda obserwacja należy do każdego ze skupień z określonym prawdopodobieństwem.

Indeks

Szukanie najlepszej liczby skupień uogólnioną metodą EM i k-średnich: v-krotny sprawdzian krzyżowy

Istotne pytanie, które należy sobie zadać rozpoczęciem analizy metodą grupowania EM i k-średnich dotyczy liczby skupień. Liczba ta nie jest znana "a priori"; możemy w ogóle nie znaleźć jednoznacznej odpowiedzi na to pytanie, tj. jaką wartość k powinniśmy zastosować. W rzeczywistości k jest parametrem modelu, którego określenie może nastręczać kłopotów. Jego wartość możemy uzyskać z posiadanych danych za pomocą metody sprawdzianu krzyżowego. Techniki tworzenia skupień metodami EM i k-średnich są zoptymalizowane i rozbudowane pod kątem typowych zastosowań w data mining. Ogólna koncepcja data mining zakłada, że analityk szuka struktur i "nuggetów" w danych bez jakichkolwiek szczególnych założeń a priori co do tego, co mógłby znaleźć (w przeciwieństwie do typowego dla badań naukowych testowania hipotez). W praktyce analityk nie ma zazwyczaj pojęcia ile skupień jest w próbie. Z tego powodu niektóre programy zawierają implementację v-krotnego sprawdzianu krzyżowego - algorytmu automatycznie wyznaczającego liczbę skupień danych.

Ten unikalny algorytm jest szeroko wykorzystywany do wszelkich zadań typu "poszukiwanie wzorców". Liczba segmentów rynku w badaniach marketingowych, liczba różnych ścieżek zakupów w analizie zachowań klientów, liczba skupień różnych objawów medycznych, liczba różnych typów dokumentów w text mining, liczba wzorców pogody w meteorologii, liczba wzorców uszkodzeń płytek krzemowych, itd.

Algorytm sprawdzianu krzyżowego można zastosować w analizie skupień. Algorytm v-krotnego sprawdzianu krzyżowego opisany jest szczegółowo w kontekście Drzew klasyfikacyjnych , Ogólnych drzew klasyfikacyjnych i regresyjnych (GC&RT) . Idea tej metody polega na podziale całej próby na v podzbiorów, lub wylosowaniu (rozłącznych) pod-prób. Ta sama analiza jest wykonywana kolejno na obserwacja z v-1 podzbiorów (próba ucząca), a wyniki analizy są stosowane do danych z próby v (która nie była używana do oceny parametrów, budowania drzewa, wyznaczania skupień, itp. i pełni rolę próby testowej) i wyznaczana jest jakaś miara siły predykcyjnej. Wyniki v powtórzeń są agregowane (uśredniane) i dają jedną ocenę stabilności modelu, tzn. jego zdolności predykcji nowych obserwacji.

Analiza skupień jest metodą uczenia bez nauczyciela - skupienia są tworem teoretycznym. Rozsądne jest zastąpić pojęcie "trafności" (stosowane w przypadku metod z nauczycielem ) pojęciem "odległości": możemy zastosować metodę v-krotnego sprawdzianu krzyżowego do zakresu liczb lub skupień i obserwować średnią odległość obserwacji (w próbie testowej) od centrów skupień (dla k-średnich), w przypadku analizy skupień metodą EM odpowiednią równoważną miarą byłaby średnia logarytmu wiarygodności obliczonego dla obserwacji z prób testowych.

Przeglądanie wyników v-krotnego sprawdzianu krzyżowego. Wyniki v-krotnego sprawdzianu krzyżowego najlepiej oglądać na prostym wykresie liniowym.

Na ilustracji widzimy wyniki analizy danych, o których powszechnie wiadomo, że zawierają trzy skupienia obserwacji (znany plik danych Iris przedstawiony przez Fishera w 1936, szeroko omawiany w literaturze dotyczącej analizy funkcji dyskryminacyjnej ). Widzimy również (na wykresie po prawej stronie) wyniki analizy losowych liczb z rozkładu normalnego. "Rzeczywiste" dane (po lewej) tworzą charakterystyczny wykres osypiska (zob. także Analiza czynnikowa ), gdzie funkcja kosztu (w tym przypadku jest to 2 razy log-wiarygodności danych sprawdzianu krzyżowego przy danych ocenach parametrów) silnie maleje wraz ze wzrostem ilości skupień, po czym wykres robi się prawie płaski (dla więcej niż 3 skupień), a nawet zaczyna rosnąć, gdy rozpoczyna się przeuczenie . Dane losowe nie mają tej własności, nie ma w tym przypadku praktycznie żadnego spadku funkcji kosztu na początku, a dalej zaczyna ona szybko wzrastać wraz z liczbą skupień (przeuczenie).

Ten prosty przykład pokazuje jak użyteczna może być metoda v-krotnego sprawdzianu krzyżowego przy stosowaniu jej w metodzie k-średnich i EM do wyznaczenia "właściwej" ilości skupień danych.

Indeks

© Copyright StatSoft, Inc., 1984-2005
STATISTICA is a trademark of StatSoft, Inc.

---