Spis treści

Analiza skupień

Analiza skupień to szereg metod dzielenia obiektów, bądź cech (zmiennych) na podobne grupy. Zasadniczo metody te dzieli się na dwie klasy: metody hierarchiczne i niehierarchiczne jak metoda k-średnich. W swoich algorytmach obie metody wykorzystują macierz podobieństwa, by na jego podstawie tworzyć skupienia.

Grupowanie obiektów i grupowanie zmiennych odbywa się w analizie skupień dokładnie w ten sam sposób. W rozdziale tym metody grupowania opisane zostaną na przykładzie grupowania obiektów.

Uwaga! Chcąc zapewnić zrównoważony wpływ wszystkich zmiennych na elementy macierzy podobieństwa, dane należy poddać standaryzacji wybierając odpowiednią opcję w oknie analizy. Brak standaryzacji daje większy wpływ na uzyskany wynik zmiennym wyrażonym większymi liczbami.

 

Metody hierarchiczne

Metody hierarchicznej analizy skupień polegają na budowaniu hierarchii skupień poczynając od tych najmniejszych (złożonych z pojedynczych obiektów), a kończąc na tych największych (złożonych z maksymalnej liczby obiektów). Skupienia tworzone są na bazie macierzy podobieństwa obiektów.

PROCEDURA AGLOMERACYJNA

  1. Postępując zgodnie z wskazaną metodą wiązania, algorytm znajduje w macierzy podobieństwa parę podobnych obiektów i łączy je w skupienie;
  2. Wymiar macierzy podobieństwa zostaje zredukowany o jeden (dwa obiekty zastąpiono jednym) a odległości znajdujące się w macierzy wyliczone są ponownie;
  3. Kroki 2-3 są powtarzane aż do uzyskania jednego skupienia zawierającego wszystkie obiekty.

Podobieństwo obiektów

W toku prac związanych z analizą skupień zasadniczą rolę odgrywają miary podobieństwa lub odległości. Wzajemne podobieństwo obiektów umieszczane jest w macierzy podobieństwa. Duża różnorodność metod wyznaczania odległości/niepodobieństwa między obiektami pozwala na wybór takich miar, które najlepiej odzwierciedlają rzeczywiste relacje. Szerzej miary odległości i podobieństwa opisane są w dziale Macierz podobieństwa.

Analiza skupień opiera swoje działania na wyszukiwaniu skupień wewnątrz macierzy podobieństwa. Macierz taka jest budowana w trakcie wykonywania analizy skupień. By analiza skupień przyniosła pożądane skutki, przy wyborze sposobu wyliczania odległości należy pamiętać, że większe wartości liczbowe w macierzy podobieństwa mają wskazywać na większe zróżnicowanie obiektów, a wartości mniejsze na ich podobieństwo.

Uwaga! By zwiększyć wpływ wybranych zmiennych na elementy macierzy podobieństwa, należy wskazać odpowiednie wagi przy ustawianiu sposobu definiowania odległości pamiętając jednocześnie o wystandaryzowaniu danych. Np. Dla osób chcących zaopiekować się psem pogrupowanie psów zgodnie z wielkością, umaszczeniem, długością ogona, charakterem, rasą itp. ułatwi dokonanie wyboru. Jednak, identyczne traktowanie wszystkich cech może spowodować umieszczenie zupełnie niepodobnych psów w jednej grupie. Natomiast dla większości z nas ważniejsza jest wielkość psa i jego charakter niż długość jego ogona, dlatego w grupowaniu należałoby ustawić miary podobieństwa tak, by to właśnie wielkość i charakter miały największe znaczenie w budowaniu skupień.

Metody wiązania obiektów i skupień

  • Metoda pojedynczego wiązania (najbliższe sąsiedztwo) - odległość pomiędzy skupieniami określona jest poprzez odległość tych obiektów każdego skupienia, które znajdują się najbliżej siebie.

\begin{pspicture}(-0.5,-2)(10,3) \pscircle[linewidth=2pt](.5,.5){2} \psdot[dotstyle=*](-.8,1) \psdot[dotstyle=*](1.7,0.1) \psdot[dotstyle=*](0.6,1.2) \pscircle[linewidth=2pt](6,.5){2} \psdot[dotstyle=*](7.2,1.2) \psdot[dotstyle=*](5.1,-0.4) \psdot[dotstyle=*](5.6,1.3) \psline{-}(1.7,0.1)(5.1,-0.4) \end{pspicture}

  • Metoda pełnego wiązania (najdalsze sąsiedztwo) - odległość pomiędzy skupieniami określona jest poprzez odległość tych obiektów każdego skupienia, które znajdują się najdalej siebie.

\begin{pspicture}(-0.5,-2)(10,3) \pscircle[linewidth=2pt](.5,.5){2} \psdot[dotstyle=*](-.8,1) \psdot[dotstyle=*](1.7,0.1) \psdot[dotstyle=*](0.6,1.2) \pscircle[linewidth=2pt](6,.5){2} \psdot[dotstyle=*](7.2,1.2) \psdot[dotstyle=*](5.1,-0.4) \psdot[dotstyle=*](5.6,1.3) \psline{-}(-.8,1)(7.2,1.2) \end{pspicture}

  • Metoda średnich połączeń - odległość pomiędzy skupieniami określona jest poprzez średnią odległość pomiędzy wszystkimi parami obiektów zlokalizowanych w obrębie dwóch różnych skupień.

\begin{pspicture}(-0.5,-2)(10,3) \pscircle[linewidth=2pt](.5,.5){2} \psdot[dotstyle=*](-.8,1) \psdot[dotstyle=*](1.7,0.1) \psdot[dotstyle=*](0.6,1.2) \pscircle[linewidth=2pt](6,.5){2} \psdot[dotstyle=*](7.2,1.2) \psdot[dotstyle=*](5.1,-0.4) \psdot[dotstyle=*](5.6,1.3) \psline{-}(-.8,1)(7.2,1.2) \psline{-}(-.8,1)(5.1,-0.4) \psline{-}(-.8,1)(5.6,1.3) \psline{-}(1.7,0.1)(7.2,1.2) \psline{-}(1.7,0.1)(5.1,-0.4) \psline{-}(1.7,0.1)(5.6,1.3) \psline{-}(0.6,1.2)(7.2,1.2) \psline{-}(0.6,1.2)(5.1,-0.4) \psline{-}(1.7,0.1)(5.6,1.3) \end{pspicture}

  • Metoda średnich połączeń ważonych - analogicznie do metody średnich połączeń polega na wyliczeniu średniej odległości, ale średnia ta ważona jest poprzez liczbę elementów każdego skupienia. W rezultacie powinniśmy wybierać tę metodę, gdy oczekujemy uzyskać skupienia o podobnych licznościach.
  • Metoda Warda - opiera się na zasadzie analizy wariancji - wylicza różnicę między sumami kwadratów odchyleń odległości poszczególnych obiektów od środka ciężkości skupienia, do których te obiekty należą. Metoda ta wybierana jest najczęściej ze względu na jej dość uniwersalny charakter.

\begin{pspicture}(-0.5,-2)(10,3) \pscircle[linewidth=2pt](.5,.5){2} \psdot[dotstyle=*](-.8,1) \psdot[dotstyle=*](1.7,0.1) \psdot[dotstyle=*](0.6,1.2) \psline[linestyle=dashed]{-}(-.8,1)(0.52,0.8) \psline[linestyle=dashed]{-}(1.7,0.1)(0.52,0.8) \psline[linestyle=dashed]{-}(0.6,1.2)(0.52,0.8) \psdot[dotstyle=pentagon*,linecolor=red](0.52,0.8) \pscircle[linewidth=2pt](6,.5){2} \psdot[dotstyle=*](7.2,1.2) \psdot[dotstyle=*](5.1,-0.4) \psdot[dotstyle=*](5.6,1.3) \psdot[dotstyle=pentagon*,linecolor=red](5.85,0.8) \psline[linestyle=dashed]{-}(7.2,1.2)(5.85,0.8) \psline[linestyle=dashed]{-}(5.1,-0.4)(5.85,0.8) \psline[linestyle=dashed]{-}(5.6,1.3)(5.85,0.8) \psline[linestyle=dotted]{-}(0.52,0.8)(5.85,0.8) \psline[linestyle=dotted]{-}(-.8,1)(7.2,1.2) \psline[linestyle=dotted]{-}(-.8,1)(5.1,-0.4) \psline[linestyle=dotted]{-}(-.8,1)(5.6,1.3) \psline[linestyle=dotted]{-}(1.7,0.1)(7.2,1.2) \psline[linestyle=dotted]{-}(1.7,0.1)(5.1,-0.4) \psline[linestyle=dotted]{-}(1.7,0.1)(5.6,1.3) \psline[linestyle=dotted]{-}(0.6,1.2)(7.2,1.2) \psline[linestyle=dotted]{-}(0.6,1.2)(5.1,-0.4) \psline[linestyle=dotted]{-}(1.7,0.1)(5.6,1.3) \end{pspicture}

Wynik analizy skupień prowadzonej metodą hierarchiczną przedstawia się przy pomocy dendogramu. Dendogram jest formą drzewa wskazującego związki pomiędzy poszczególnymi obiektami uzyskane z analizy macierzy podobieństwa. Poziom odcięcia dendogramu decyduje o liczbie skupień, na które chcemy dzielić zgromadzone obiekty. Wybór sposobu odcięcia określamy podając w procentach długość wiązania, przy którym nastąpi cięcie, gdzie 100% stanowi długość ostatniego i jednocześnie najdłuższego wiązania w dendogramie.

Okno z ustawieniami opcji hierarchicznej analizy skupień wywołujemy poprzez menu Statystyki zaawansowane→Grupowanie i Redukcja→Hierarchiczna analiza skupień.

Przykład c.d. (plik iris.pqs)

Analiza przeprowadzona zostanie na klasycznym zestawie danych, dotyczącym podziału kwiatów irysa na 3 odmiany na podstawie szerokości oraz długości płatków i działek kielicha (R.A. Fishera 19361)). Ponieważ w tym zestawie danych znajduje się informacja o rzeczywistej odmianie każdego kwiatu, po przeprowadzonej analizie skupień istnieje możliwość określenia dokładności dokonanego podziału.

Przydziału kwiatów do poszczególnych grup dokonujemy na podstawie kolumn od 2 do 5. Wybieramy sposób wyliczania odległości np. odległość Euklidesową i metodę wiązania np. średnią. Podanie poziomu odcięcia skupień pozwoli na takie odcięcie dendogramu by powstały skupienia - w przypadku tej analizy chcemy uzyskać 3 skupienia i by to osiągnąć zmieniamy poziom odcięcia na 45%. Do raportu dołączamy również dane+skupienia.

Na wykresie typu dendogram, przedstawiono kolejność wiązań i ich długość.

By zbadać czy wyodrębnione skupienia stanowią 3 rzeczywiste odmiany kwiatów irysa, możemy skopiować kolumnę zawierającą informację o przynależności do skupienia z raportu i wkleić do arkusza danych. Podobnie jak skupienia, odmiany opisane są również liczbowo poprzez Kody/Etykiety/Format, dlatego z łatwością można przeprowadzić analizę zgodności. Zgodność naszych wyników z rzeczywistą przynależnością danego kwiatu do odpowiedniego gatunku sprawdzimy metodą Kappa Cohena.

Dla przedstawionego przykładu obserwowaną zgodność przedstawia tabela:

Wnioskujemy z niej, że odmiana virginica może być mylona z versicolor, dlatego obserwujemy tu 14 błędnych zaklasyfikowań. Natomiast współczynnik zgodności Kappa jest istotny statystycznie i wynosi 0.86, co świadczy o dużej zgodności uzyskanych skupień z rzeczywistą odmianą kwiatów.

2015/12/28 12:15 · admin

Metoda k-średnich

Metoda k-średnich (ang. k-means) wzoruje swoje działanie na algorytmie zaproponowanym początkowo przez Stuarta Lloyda i opublikowana w roku 1982 2). W metodzie tej obiekty dzieli się na z góry założoną liczbę $k$ skupień. Początkowe skupienia poprawia się w toku wykonywania procedury aglomeracji, przenosząc pomiędzy nimi obiekty tak by zróżnicowanie obiektów wewnątrz skupienia było jak najmniejsze a odległości skupień jak największe. Algorytm działa w oparciu o macierz odległości euklidesowych pomiędzy obiektami, a parametrami niezbędnymi w procedurze aglomeracji metody k-średnich są: centra startowe i kryterium stopu. Centra startowe są to obiekty od których algorytm rozpocznie budowę skupień, a kryterium stopu to określenie sposobu zatrzymania algorytmu.

PROCEDURA AGLOMERACYJNA

  1. Wybór centów startowych
  2. Bazując na macierzy podobieństwa algorytm przypisuje każdy obiekt do najbliższego centrum
  3. Dla uzyskanych skupień wyznacza się poprawione centra.
  4. Kroki 2-3 są powtarzane aż do momentu spełnienia kryterium stopu.

Centra startowe

Wybór centrów startowych ma zasadniczy wpływ na zbieżność algorytmu k-średnich dla uzyskania odpowiednich skupień. Centra startowe mogą być wybrane na dwa sposoby:

  • k-means++ - to optymalny dobór punktów startowych poprzez wykorzystanie algorytmu k-means++ zaproponowanego w 2007 roku przez David Arthur and Sergei Vassilvitskii 3). Gwarantuje on uzyskanie optymalnego rozwiązania algorytmu k-średnich przy możliwie niewielu iteracjach. Algorytm wykorzystuje w swoim działaniu element losowości, dlatego uzyskiwane wyniki mogą się nieco różnić przy kolejnych uruchomieniach analizy. Jeśli dane nie formułują się w naturalne klastery, lub jeśli nie można skutecznie podzielić danych na rozłączne skupiska, użycie k-means++ spowoduje uzyskanie zupełnie innych wyników w kolejnych uruchomieniach analizy k-średnich. Duża powtarzalność wyników świadczy natomiast o możliwości dokonania dobrego podziału na oddzielne skupienia.
  • n pierwszych - pozwala by użytkownik wskazał punkty będące centrami startowymi poprzez ustawienie tych obiektów na pierwszych miejscach w tabeli danych.

Kryterium stopu jest to moment, w którym nie zmienia się przynależność punktów do klas lub liczba powtórzeń kroku 2 i 3 algorytmu osiągnie zadaną przez użytkownika liczbę iteracji.

Ze względu na sposób działania algorytmu analizy skupień k-średnich, naturalną jej konsekwencją jest porównanie powstałych skupień przy pomocy jednoczynnikowej analizy wariancji (ANOVA) dla grup niezależnych.

Okno z ustawieniami opcji analizy skupień k-średnich wywołujemy poprzez menu Statystyki zaawansowane→Grupowanie i Redukcja→Analiza skupień k-średnich.

Przykład c.d. (plik iris.pqs)

Analiza przeprowadzona zostanie na klasycznym zestawie danych, dotyczącym podziału kwiatów irysa na 3 odmiany na podstawie szerokości oraz długości płatków i działek kielicha (R.A. Fishera 19364)).

Przydziału kwiatów do poszczególnych grup dokonujemy na podstawie kolumn od 2 do 5. Wskazujemy również, że badane kwiaty chcemy podzielić na 3 grupy. W rezultacie przeprowadzonej analizy utworzono 3 skupienia, które różnią się istotnie statystycznie w każdym badanym wymiarze (wyniki ANOVA), czyli dla szerokości płatka, długości płatka, szerokości kielicha jaki i długości kielicha.

Różnicę można zaobserwować na wykresach, gdzie przedstawiamy w wybranych dwóch wymiarach przynależność poszczególnych punktów do skupień:

Powtarzając analizę możemy uzyskać nieco inne wyniki, ale uzyskana zmienność nie będzie duża. Świadczy to o tym, że dane poddane analizie formułują się w naturalne skupiska i przeprowadzanie analizy skupień jest w tym przypadku uzasadnione.

Uwaga 1! Po kilkukrotnym przeprowadzeniu analizy możemy wybrać najbardziej interesujący nas wynik, a następnie ustawić te dane, które stanowią centra startowe na początku arkusza - wówczas analiza przeprowadzona w oparciu o centra startowe wybierane jako N pierwszych obserwacji będzie dawała stale ten wybrany przez nas efekt.

Uwaga 2! By dowiedzieć się czy skupienia stanowią 3 rzeczywiste odmiany kwiatów irysa, możemy skopiować informację o przynależności do skupień z raportu i wkleić do arkusza danych. Zgodność naszych wyników z rzeczywistą przynależnością danego kwiatu do odpowiedniego gatunku możemy sprawdzić analogicznie jak dla hierarchicznej analizy skupień.

2015/12/28 12:25 · admin
1) , 4)
Fisher R.A. (1936), The use of multiple measurements in taxonomic problems. Annals of Eugenics 7 (2): 179–188
2)
Lloyd S. P. (1982), Least squares quantization in PCM. IEEE Transactions on Information Theory 28 (2): 129–137
3)
Arthur D., Vassilvitskii S. (2007), k-means++: the advantages of careful seeding. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. 1027–1035