Wolna encyklopedia

Grupowanie (analiza skupień) (ang. data clustering) - pojęcie z zakresu eksploracji danych oraz uczenia się maszyn, wywodzi się z szerszego pojęcia jakim jest klasyfikacja bezwzorcowa.

Analiza skupień jest metodą tzw. klasyfikacji bez nadzoru (ang. unsupervised learning). 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.

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) w której grupowanie polega na wstępnym podzieleniu populacji na z góry założoną liczbę klas. 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 uzyskanych klas. Podstawowy algorytm (J. MacQueen, 1967):
  • losowy wybór środków (centroidów) klas (skupień),
  • przypisanie punktów do najbliższych centroidów,
  • wyliczenie nowych środków skupień,
  • powtarzanie algorytmu aż do osiągnięcia kryterium zbieżności (najczęściej krok w którym nie zmieniła się przynależność punktów do klas);

• 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.

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, ale 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 sie. WNT, Warszawa, 2000.
• Everitt, B. S., Landau S., Leese M., Cluster analysis, London : Arnold ; New York : Oxford University Press, 2001.
• Aldenderfer, M. S., Blashfield, R. K., Cluster analysis (Quantitative Applications in the Social Sciences), Sage Publications, 1984.