Metody analizy skupień (segmentacja/grupowanie)

meto1

 

Analiza skupień  / grupowanie / segmentacja

Badacze grupują dane w struktury, które powinny być zorganizowane i sensowne. Tu z pomocą przychodzi im analiza skupień. Pojęcie „analiza skupień” obejmuje kilka różnych algorytmów klasyfikacji, to narzędzie do eksploracyjnej analizy danych. Celem analizy skupień jest ułożenie obiektów w grupy w taki sposób, by obiekty należące do tej samej grupy były ze sobą jak najbardziej powiązane, a jednocześnie były jak najmniej związane z obiektami z pozostałych grup. Należy pamiętać o tym, że analiza skupień wykrywa struktury w danych, jednak nie wyjaśnia dlaczego one występują.
Metody analizy skupień mają zastosowanie w fazie eksploracyjnej badań, gdy nie dysponujemy żadnymi hipotezami. Z tego powodu nie testujemy istotności statystycznej, nawet w przypadku gdy podawane są poziomy p (jak przy grupowaniu metodą k-średnich). Analiza skupień znajduje zastosowanie w wielu dziedzinach badań np. w medycynie grupuje się choroby, objawy czy metody leczenia. Grupowanie prowadzi do powstawania użytecznych klasyfikacji.

Algorytm aglomeracji służy do grupowania obiektów w coraz większe zbiory/ skupienia przy zastosowaniu miary podobieństwa lub odległości. Charakterystycznym wynikiem takiego klasyfikowania jest hierarchiczne drzewo. Na początku hierarchicznego wykresu drzewkowego każdy obiekt stanowi swoją własną klasę, każdym krokiem osłabiamy nasze kryterium i coraz więcej elementów wchodzi do tego samego skupienia. W ten sposób coraz więcej elementów wiąże się ze sobą w skupienia coraz bardziej od siebie się różniące. Na ostatnim etapie wszystkiego obiekty są ze sobą połączone. Na wykresie na poziomej osi znajdują się odległości aglomeracyjne, które pozwalają odczytać odległość w której pojawiło się nowe skupienie elementów. Jeśli dane maja wyrazistą strukturę, to często ta struktura przyjmuje w hierarchicznym drzewie kształt oddzielnych gałęzi. Udana analiza przy pomocy łączenia daje możliwość wykrywania skupień (gałęzi) i ich interpretacji.
W metodzie aglomeracji wykorzystuje się różne miary rozbieżności między obiektami.
Można ją obliczyć jako odległość geometryczną w przestrzeni wielowymiarowej, czyli odległość euklidesową. Na odległości euklidesowe duży wpływ mają różnice jednostek między wymiarami, na podstawie których są wyliczane odległości. Dlatego trzeba pamiętać o standaryzacji, aby mieć dane o porównywalnej skali. Odległość euklidesową obliczamy ze wzoru: odległość(x,y) = { i (xi – yi)2 }½
Kwadrat odległości euklidesowej wyznaczamy poprzez podniesienie do kwadratu odległości euklidesowej. Ma to na celu przypisanie większej wagę obiektom, które są bardziej oddalone. Oblicza się ze wzoru: odległość(x,y) = i (xi – yi)2
Odległość miejska (Manhattan, City Block) jest sumą różnic mierzonych wzdłuż wymiarów. Miara ta daje podobne wyniki jak odległość euklidesowa. W przypadku tej miary wpływ obserwacji odstających jest tłumiony. Wzór przedstawia się następująco: odległość(x,y) = i |xi – yi| .
Odległość Czebyszewa to miara odległości stosowana w przypadkach, w których chcemy zdefiniować dwa obiekty jako „inne”, gdy różnią się one w jednym dowolnym wymiarze. Odległość Czebyszewa oblicza się w następujący sposób: odległość(x,y) = Maksimum|xi – yi|
Odległość potęgowa stosowana jest wtedy, gdy chcemy zmniejszyć lub zwiększyć lub wzrastającą wagę przypisaną do wymiarów, w przypadku których odpowiednie obiekty bardzo się od siebie różnią. Odległość potęgowo wyznaczamy ze wzoru: odległość(x,y) = ( i |xi – yi|p)1/r
Niezgodność procentowa używana jest gdy dane dla wymiarów objętych analizą są z natury dyskretne. Wyznaczamy ją ze wzoru: odległość(x,y) = (Liczba xi ≠ yi)/ i
Ważne są także zasady wiązania lub aglomeracji, które określają kiedy dwa skupienia są wystarczająco podobne, aby można je było połączyć. Istnieje wiele zasad wiązania, na przykład:
W przypadku metody pojedynczego wiązania/najbliższego sąsiedztwa 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 tworzą skupienia łącząc się w ciągi, a skupienia wynikowe tworzą długie „łańcuchy”.
Metoda pełnego wiązania (najdalszego sąsiedztwa) polega na tym, że odległość między skupieniami jest zdeterminowana przez największą z odległości między dwoma dowolnymi obiektami należącymi do różnych skupirń (tzn. „najdalszymi sąsiadami”). Metoda ta sprawdza się w przypadkach, kiedy obiekty faktycznie formują naturalnie oddzielone „kępki”. Metoda ta nie jest zaś odpowiednia wówczas, gdy skupienia są w jakiś sposób wydłużone lub mają charakter łańcuchowy.
Metoda średnich połączeń polega na tym, że 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 wydłużonych skupień.
Metoda średnich połączeń ważonych to metoda podobna do metody ś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.
Metoda środków ciężkości. Środek ciężkości skupienia jest średnim punktem w przestrzeni wielowymiarowej. W tej metodzie odległość między dwoma skupieniami jest określona jako różnica między środkami ciężkości.
Metoda ważonych środków ciężkości (mediany). To metoda podobna do poprzedniej, jednak w obliczeniach wprowadza się ważenie, żeby uwzględnić różnice między wielkościami skupień (tzn. liczbą zawartych w nich obiektów). Metoda ta jest lepsza od poprzedniej w sytuacji, gdy istnieją (lub podejrzewamy, że istnieją) znaczne różnice w rozmiarach skupień.
Metoda Warda różni się od pozostałych metod, gdyż do oszacowania odległości między skupieniami wykorzystuje analizę wariancji. Metoda ta zmierza do minimalizacji sumy kwadratów odchyleń dowolnych dwóch skupień, które mogą zostać uformowane na każdym etapie.
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ń.
Grupowanie metodą k-średnich w znaczny sposób różni się od metod Aglomeracji i Grupowania obiektów. Przy pomocy metody k-średnich powstaje utworzonych k skupień, w możliwie największym stopniu różniących się od siebie. Należy zaznaczyć, że optymalna liczba skupień nie jest znana z góry i powinna być wyliczana na podstawie danych. Metoda ta stanowi swoistą odwrotność analizy wariancji. Należy zacząć od k losowych skupień, a następnie przenosić obiekty między tymi skupieniami mając na celu:
a) minimalizację zmienności wewnątrz skupień
b) maksymalizację zmienności między skupieniami.
Dzięki temu 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 takim sensie, że 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 są takie same. Przy grupowaniu metodą k-średnich, staramy się tak przenosić obiekty między grupami, aby uzyskać największy poziom istotności analizy ANOVA. Wielkość statystyki F pochodzącej z analizy wariancji wykonanej w każdym wymiarze jest wskaźnikiem tego, na ile dobrze dany wymiar dyskryminuje skupienia.
Grupowanie metodą EM- algorytm tej metody próbuje oszacować obserwowany rozkład wartości jako mieszaninę rozkładów różnych grup. Algorytm ten potrafi korzystać również ze zmiennych jakościowych. Najpierw losowo przydziela prawdopodobieństwa (wagi) każdej z klas (kategorii) w obrębie każdego skupienia. W kolejnych iteracjach prawdopodobieństwa są zmieniane tak, aby zmaksymalizować wiarygodność danych przy podanej ilości skupień. Algorytm EM mówi o tym, że każda obserwacja należy do każdego ze skupień z określonym prawdopodobieństwem klasyfikacyjnym.
V- krotny sprawdzian krzyżowy to algorytm automatycznie wyznaczający liczbę skupień danych. Jest to bardzo ważne w przypadku, gdy nie testujemy hipotez i nie wiemy jaka jest liczba skupień w próbie. Algorytm ten znajduje zastosowanie na przykład w zadaniach typu „poszukiwanie wzorów”. Algorytm sprawdzianu krzyżowego można zastosować też w analizie skupień.

Autorem testu jest Judyta Borchet

11647379_880289168675562_2028751748_n

Źródło:
statsoft.pl