Analiza skupień

Grupowanie (analiza skupień, klasteryzacja) (ang. data clustering) – metoda nienadzorowanej (ang. unsupervised learning) klasyfikacji statystycznej. Jest to metoda dokonująca grupowania elementów we względnie jednorodne klasy. Podstawą grupowania w większości algorytmów jest podobieństwo pomiędzy elementami – wyrażone przy pomocy funkcji (metryki) podobieństwa.

Poprzez grupowanie można również rozwiązać problemy z gatunku odkrywania struktury w danych oraz dokonywanie uogólniania. Grupowanie polega na wyodrębnianiu grup (klas, podzbiorów).

Wybrane cele dokonywania grupowania są następujące:

• uzyskanie jednorodnych przedmiotów badania, ułatwiających wyodrębnienie ich zasadniczych cech,
• zredukowanie dużej liczby danych pierwotnych do kilku podstawowych kategorii, które mogą być traktowane jako przedmioty dalszej analizy,
• zmniejszenie nakładu pracy i czasu analiz, których przedmiotem będzie uzyskanie klasyfikacji obiektów typowych,
• odkrycie nieznanej struktury analizowanych danych,
• porównywanie obiektów wielocechowych.

Pionierem analizy skupień był psycholog Robert Tryon.

Metody grupowania

Grupowanie jako jedna z metod pozyskiwania wiedzy, a tym samym eksploracji danych, jest ściśle uwarunkowana źródłem danych oraz oczekiwaną postacią rezultatów.

Algorytmy analizy skupień dzieli się na kilka podstawowych kategorii:

• metody hierarchiczne – algorytm tworzy dla zbioru obiektów hierarchię klasyfikacji, zaczynając od takiego podziału, w którym każdy obiekt stanowi samodzielne skupienie, a kończąc na podziale, w którym wszystkie obiekty należą do jednego skupienia. Istnieją dwa rodzaje metod hierarchicznych:
  • procedury aglomeracyjne (ang. agglomerative) – tworzą macierz podobieństw klasyfikowanych obiektów, a następnie w kolejnych krokach łączą w skupienia obiekty najbardziej do siebie podobne,
  • procedury deglomeracyjne (ang. divisive) – zaczynają od skupienia obejmującego wszystkie obiekty, a następnie w kolejnych krokach dzielą je na mniejsze i bardziej jednorodne skupienia aż do momentu, gdy każdy obiekt stanowi samodzielne skupienie.
• grupa metod k-średnich (ang. k-means), wpisująca się w katalog algorytmów niehierarchicznych, w której grupowanie polega na wstępnym podzieleniu populacji na z góry założoną liczbę klas (tzw. skupień). Następnie uzyskany podział jest poprawiany w ten sposób, że niektóre elementy są przenoszone do innych klas, tak, aby uzyskać minimalną wariancję wewnątrz każdej z nich - dąży się do zapewnienia jak największego podobieństwa elementów w ramach każdego ze skupień, przy jednoczesnej maksymalnej różnicy pomiędzy samymi klasami (skupieniami). Podstawowy algorytm (J. MacQueen, 1967):
  • wybór środków (centroidów) klas (skupień) - poprzedzony ustaleniem liczby klas (skupień) dobór centroidów dokonany jest m.in.poprzez losowy wybór k obserwacji, wybór k pierwszych obserwacji ze zbioru czy dobór pozwalający na maksymalizację odległości skupień,
  • przypisanie punktów do najbliższych centroidów - każdy element przypisujemy do klasy (skupienia), do którego środka ma najbliżej (miarą podobieństwa jest tu odległość między elementem a centroidem - najczęściej wykorzystuje się odległość euklidesową, jej kwadrat lub też tzw. odległość Czebyszewa),
  • wyliczenie nowych środków skupień - najczęściej nowym środkiem klasy (skupienia) jest ten punkt, którego współrzędne stanowią średnią arytmetyczną współrzędnych elementów należących do tej klasy,
  • powtarzanie algorytmu aż do osiągnięcia kryterium zbieżności (najczęściej jest to krok, w którym nie zmieniła się przynależność punktów do klas lub też zakończenie powtarzania algorytmu warunkowane jest przyjętą liczbą iteracji);
• metody rozmytej analizy skupień (ang. fuzzy clustering), wśród których najbardziej znaną jest metoda c-średnich (c-means). Metody rozmytej analizy skupień mogą przydzielać element do więcej niż jednej kategorii. Z tego powodu algorytmy rozmytej analizy skupień są stosowane w zadaniu kategoryzacji (przydziału jednostek do jednej lub wielu kategorii). Metody rozmytej analizy skupień różnią się pod tym względem od metod klasycznej analizy skupień, w których uzyskana klasyfikacja ma charakter grupowania rozłącznego, którego wynikiem jest to, że każdy element należy do jednej i tylko jednej klasy.
• metody gęstościowe, np. DBSCAN.

Zastosowania

• wstępna analiza danych, polegająca na wyodrębnieniu jednorodnych grup (subpopulacji), które podlegają osobnej dalszej analizie statystycznej lub ekonometrycznej;
• eksploracja danych (ang. data mining), gdzie grupowanie używane jest np. do podziału klientów na pewne podgrupy;
• wyszukiwanie informacji (ang. information retrieval), mająca za zadanie uporządkowanie i uproszczenie dostępu do informacji. Do klasycznych zastosowań należy klasyfikacja dokumentów tekstowych: książek, czy stron internetowych;
  • np.: w wyszukiwarkach internetowych – wykorzystywane do automatycznego wyodrębnienia jednolitych grup i przydziału elementów wyników do poszczególnych z nich; zobacz clustering (wyszukiwarki internetowe)
• segmentacja obrazu (ang. image segmentation), czyli podział obrazu na regiony homogeniczne pod względem pewnej własności obrazu (kolor, tekstura, intensywność). Taki uproszczony obraz jest prostszy do obróbki np. przez algorytmy rozpoznawania obrazu;
• grupowanie zadań w problemie harmonogramowania tak, by zadania intensywnie ze sobą komunikujące się trafiły do tej samej grupy. Taka grupa zostanie w następnym kroku przypisana do wykonania na jednym procesorze (bądź kilku procesorach połączonych szybkimi kanałami komunikacyjnymi).

Bibliografia

• Jain, Murty and Flynn: Data Clustering: A Review, ACM Comp. Surv, 1999. [1]
• A. D. Gordon: Classification. Chapman & Hall, London New York Washington, 1999
• P. Cichosz: Systemy uczące się. WNT, Warszawa, 2000.
• B. S. Everitt, S. Landau, M. Leese, Cluster analysis, London : Arnold ; New York : Oxford University Press, 2001.
• M. S. Aldenderfer, R. K. Blashfield, Cluster analysis (Quantitative Applications in the Social Sciences), Sage Publications, 1984.