Wybór odpowiedniego algorytmu. Część 4 – algorytmy grupujące

W cyklu „Wybór odpowiedniego algorytmu” przyszedł czas na omówienie algorytmów grupujących.

Obiektywnie, w kwestii doboru odpowiedniego algorytmu grupowanie jest znacznie bardziej złożone niż regresja, czy klasyfikacja. W przypadku grupowania trudno o jedną, spójną statystykę, którą można porównać działanie różnych algorytmów. Sytuacja komplikuje się jeszcze bardziej, gdy weźmiemy pod uwagę transformacje, które musimy wykonać na zbiorze, by dostosować go do wymagań danego algorytmu.

Artykuł ten jest czwartą częścią cyklu „Wybór odpowiedniego algorytmu”. Cały cykl składa się z następujących artykułów:
Część 1 – wprowadzenie.
Część 2 – algorytmy klasyfikacyjne.
Część 3 – algorytmy regresyjne.
Część 4 – algorytmy grupujące.

1. Wstęp.

W tym wpisie spróbuję zmierzyć się z powyższym wyzwaniem i przedstawić zestaw wskazówek, które być może pomogą Ci w wyborze metody klastrowania dostosowanej do zestawu danych, którymi dysponujesz.

Artykuł ten jest również podsumowaniem tego, co działo się w ciągu ostatnich miesięcy na blogu. Powstało 17 wpisów, w tym 2 dłuższe projekty. Skupiałem się w nich na omówieniu różnych aspektów związanych z analizą skupień. Przedstawiałem różne rodziny algorytmów segmentacyjnych, podejścia do grupowania i optymalizacji parametrów.

Pomimo że grupowanie nie jest najpoczytniejszym tematem w uczeniu maszynowym, to chciałem Ci nieco przybliżyć jego ideę. Od początku moim celem było kompleksowe opisanie problemu i zainspirowanie Cię do zgłębiania tego niedocenianego tematu. Mam nadzieję, że przynajmniej w niewielkim stopniu mi się to udało. 🙂

2. Założenia

Zanim przejdziemy do omawiania metod segmentacji, chciałbym przedstawić kilka założeń:

• Większość porad, którymi się z Tobą dzielę, wynika zarówno z mojego doświadczenia, sposobu działania algorytmów, jak i ogólnie przyjętych zasad „poprawnego modelowania”.
• Przyjmuję pewne uproszczenia i nie wchodzę głęboko w szczegóły. W rzeczywistości należy starannie przeanalizować problem, założenia biznesowe i dane, które badamy. Przy dwóch pozornie identycznych zagadnieniach, najlepszy wynik może być uzyskany przy pomocy różnych algorytmów. Nie ma dwóch identycznych przypadków.
• Przedstawiam jedynie zestaw reguł, pomagający „przefiltrować” najpopularniejsze algorytmy i zawęzić poszukiwania.
• Wpis ten należy traktować raczej jak kompas, niż GPS, który doprowadzi Cię zakręt po zakręcie do celu.

Reasumując: wszystko, o czym piszę, pomoże Ci lepiej zrozumieć działanie i charakterystykę najpopularniejszych algorytmów. Wartością dodaną będzie również zaoszczędzony na poszukiwaniach czas. Przy podejmowaniu ostatecznej decyzji zawsze:

1. Zrozum cel biznesowy.
2. Dobrze zdefiniuj problem.
3. Zapoznaj się z procesem generowania danych.
4. Zrozum dane.
5. Wybierz odpowiedni algorytm.

3. Opis problemu

Problemem grupowania w uczeniu maszynowym nazywamy podział próby (zbioru) na grupy obserwacji, które cechują się podobnymi właściwościami. Algorytmy używane w grupowaniu należą do rodziny określanej uczeniem bez nadzoru. W przeciwieństwie do klasyfikacji, czy regresji nie uświadczymy tu zmiennej celu. Podział dokonywany jest zatem na podstawie wszystkich wybranych zmiennych.

Wynikiem działania algorytmów grupujących są grupy obserwacji. Nie wszystkie jednak obserwacje zostają przydzielone do grup. W zależności od wybranej metody grupowania może się zdarzyć, że niektóre obserwacje nie zostanę przypisane do żadnej grupy. Powodem jest fakt, że na płaszczyźnie wielowymiarowej są one odległe od wszystkich pozostałych obserwacji. Nazywamy je wtedy obserwacjami nietypowymi.

4. Miary używane w grupowaniu

Zwykło się mówić o problemach, które rozwiązują algorytmy segmentacyjne – uczenie bez nadzoru. Nie jest to do końca trafne określenie. O ile same algorytmy segmentacyjne nie posiadają wbudowanej metody optymalizacji pod kątem statystyki bazującej na którejkolwiek zmiennej, to już ich kalibracja, jak i interpretacja wyników wymagają nadzoru eksperta.

Poniżej prezentuję trzy najpopularniejsze miary używane w grupowaniu:

1. Miara wewnętrzna – wskaźnik sylwetkowy (ang. silhouette score).
   Silhouette nazywany jest miarą wewnętrzną, ponieważ wykorzystuje w swej ocenie średnią odległość pomiędzy obserwacjami wewnątrz grupy (a) i średnią odległość obserwacji do najbliższej „obcej” grupy (b). Silhouette obliczany jest dla każdej obserwacji w następujący sposób: (a – b)/max(a, b). W zależnosci od implementacji funkcja zwraca średnią wartość dla każdej obserwacji lub średnią dla całego zbioru.
2. Miara zewnętrzna – wskaźnik czystości (ang. purity score).
   Do wyznaczenia tej miary niezbędna jest znajomość prawdziwych (lub oczekiwanych) klas poszczególnych obserwacji. Wykorzystujemy ją przy problemach semi-supervised i w problemach klasyfikacji wieloklasowej. W uproszczeniu: mierzy ona spójność w przydziale obserwacji do grup. W idealnej sytuacji wszystkie obserwacje oznaczone tym samym numerem trafiają do tej samej grupy.
3. Inercja (ang. inertia).
   Ostatnia i najbardziej intuicyjna miara. Dotyczy ona głównie algorytmu k-średnich. Inercja jest sumą kwadratów odległości obserwacji wewnątrz segmentu od jego centrum. W implementacji k-means w bibliotece sklearn inercją mierzona jest jakość segmentacji. Algorytm minimalizuje ją i spośród kilku wykonań wybierane jest to, w którym wartość inercji jest najmniejsza.

5. Algorytmy

5.1. Algorytm grupowania aglomeracyjnego

Należy do rodziny algorytmów hierarchicznych. Swą nazwę bierze od hierarchii, którą budują algorytmy implementujące to podejście. Ma ona strukturę drzewa (wizualizowanego na wykresie zwanym dendrogramem), które przedstawia proces działania algorytmu i budowy grup (poprzez podział bądź scalanie). Na osi x uporządkowane są grupy, a z osi y w łatwy sposób można odczytać odległość pomiędzy łączonymi grupami.

W podejściu aglomeracyjnym (wstępujące lub łączące) algorytm zaczyna swe działanie w momencie, gdy liczba grup równa się liczbie obserwacji – każda obserwacja stanowi odrębną grupę. Następnie w sposób iteracyjny grupy są scalane w taki sposób, by wariancja wewnątrz nich była możliwie najmniejsza, a pomiędzy grupami możliwie duża. Algorytmy te reprezentują podejście „od szczegółu do ogółu”. Podejście zaimplementowane w algorytmach aglomeracyjnych sprawdza się, gdy decydujemy się na poszukiwanie małych grup (po kilku iteracjach proces może zostać przerwany).

1. Rodzina algorytmów: hierarchiczne.
2. Założenia i ograniczenia:
   • nie wymaga wcześniejszego podania docelowej liczby grup (choć w przypadku implementacji sklearn wymagane jest określenie liczby grup),
   • liczbę grup możemy określić dopiero po np. wnikliwej analizie dendrogramu,
   • wysoka złożoność obliczeniowa.
3. Obsługiwane typy zmiennych: tylko numeryczne.
4. Szybkość: niska (odpowiedni tylko dla relatywnie niewielkich zbiorów).
5. Więcej informacji:
   • wprowadzenie teoretyczne,
   • praktyczne użycie.

5.2. Algorytm grupowania deglomeracyjnego

Kolejny algorytm z rodziny hierarchicznych. Bardzo podobny do algorytmu aglomeracyjnego. Główna różnica polega na tym, że rozpoczyna on swe działanie, gdy wszystkie obserwacje znajdują się w jednej grupie. W kolejnych iteracjach działania algorytmu grupy są dzielone, mając na uwadze te same kryteria, co w przypadku algorytmów aglomeracyjnych: wariancję i miary odległości pomiędzy grupami. Tego typu algorytmy sprawdzają się, gdy zależy nam na znalezieniu dużych grup (podejście „od ogółu do szczegółu”).

1. Rodzina algorytmów: hierarchiczne.
2. Założenia i ograniczenia: identyczne jak w przypadku algorytmu grupowania aglomeracyjnego.
3. Obsługiwane typy zmiennych: tylko numeryczne.
4. Szybkość: niska.
5. Więcej informacji:
   • wprowadzenie teoretyczne.

5.3. K-średnich

O algorytmie k-średnich słyszał chyba każdy, kto zetknął się z problemem grupowania. Swą popularność zawdzięcza on prostocie i szybkości działania.

Swoje działanie k-średnich opiera na centroidach (utworzonych na podstawie średniej ze współrzędnych punktów w grupie), podobnie jak to miało miejsce w przypadku metod hierarchicznych. Jest on zaliczany do metod iteracyjno-optymalizacyjnych ze względu na schemat działania. W kolejnych iteracjach wykonywana jest optymalizacja wyniku działania algorytmu przedstawionego w postaci odległości wszystkich obserwacji danej grupy względem jej centroidu. Dąży on zatem do minimalizacji wariancji wewnątrz grup i jej maksymalizacji pomiędzy grupami.

Schemat działania algorytmu k-średnich:

1. Losowanie k-punktów startowych w przestrzeni (losujemy k pierwszych centroidów).
2. Przyporządkowanie wszystkich obserwacji do najbliższego centroidu z pomocą danej miary odległości (w przypadku k-średnich jest to odległość euklidesowa).
3. Dla każdej z k-grup wyznaczamy nowy centroid.
4. Powtarzamy krok 2 i 3 aż do osiągnięcia warunku stopu, którym może być:
   1. Osiągnięcie zbieżności, ew. „znacznej” poprawy względem wybranej miary jakości grupowania (w przypadku implementacji dostępnej w bibliotece sklearn jest to suma kwadratów odległości wszystkich obserwacji od centroidu się nie zmienia).
   2. Osiągnięcie momentu, w którym przydział obserwacji do grup się nie zmienia.
   3. Osiągnięcie zakładanej liczby iteracji.

1. Rodzina algorytmów: iteracyjno-optymalizacyjne.
2. Założenia i ograniczenia:
   • wymaga od użytkownika ustalenia liczby grup a priori,
   • wrażliwość na dobór punktów startowych,
   • wrażliwość na wpływ obserwacji odstających i szum,
   • każda powstała grupa posiada przybliżoną liczbę obserwacji,
   • zakłada sferyczność grup (tu znajduje wpis dedykowany ograniczeniom algorytmu k-średnich, wraz ze sposobami na ich obejście),
3. Obsługiwane typy zmiennych: tylko numeryczne.
4. Szybkość: wysoka. W zależności od implementacji i zbioru jest to jeden z najszybszych algorytmów.
5. Więcej informacji:
   • wprowadzenie teoretyczne,
   • praktyczne użycie,
   • projekt segmentacji behawioralnej z użyciem algorytmu k-średnich.

5.4. K-median

K-median jest algorytmem grupującym, należącym do rodziny algorytmów iteracyjno-optymalizacyjnych. W swoim działaniu jest on bardzo zbliżony do algorytmu k-średnich. Główna różnica polega na tym, że dla każdej z grup używa on mediany współrzędnych obserwacji zamiast centroidu (ze wszystkimi konsekwencjami takiego zabiegu, czyli np. brakiem wrażliwości na wartości odstające).

1. Rodzina algorytmów: iteracyjno-optymalizacyjne.
2. Założenia i ograniczenia: niemal identyczne, jak w przypadku k-średnich, z wyłączeniem wrażliwości na wartości odstające.
3. Obsługiwane typy zmiennych: tylko numeryczne.
4. Szybkość: wysoka.
5. Więcej informacji:
   • wprowadzenie teoretyczne i praktyka.

5.5. K-modes

Algorytm bardzo podobny do algorytmu k-średnich, rozszerzający jego możliwości o wsparcie dla zmiennych kategorycznych. Nazwa algorytmu pochodzi od angielskiego mode (moda/dominanta/wartość modalna/wartość najczęstsza) – użyta jest tu jako reprezentant tendencji centralnej danej grupy. Jest to obiekt będący reprezentantem danej grupy obserwacji. Jest odpowiednikiem centroidu z algorytmu k-średnich.

Zamiast dystansu (jak w k-średnich) używa on miary odmienności. Im mniejsza jej wartość, tym większe podobieństwo pomiędzy obserwacjami. Miara odmienności jest przedstawiona jako suma niedopasowań poszczególnych zmiennych kategorycznych pomiędzy obserwacjami.

Schemat działania algorytmu k-modes:

1. Losowe wybranie k unikalnych obserwacji ze zbioru jako inicjalnych k-dominant.
2. Przeliczenie miary odmienności pomiędzy dominantami a wszystkimi obserwacjami.
3. Przypisanie obserwacji do najbardziej podobnej dominanty.
4. Wybranie nowych k-dominant dla każdej grupy obserwacji. Jeżeli dominanty się nie zmieniły, to algorytm kończy działanie. W przeciwnym wypadku powtarzane są kroki 2, 3 i 4.

Algorytm jest mało popularny. Ciężko znaleźć na jego temat wartościowe informacje w sieci. Być może wynika to z faktu, że wspiera on tylko i wyłącznie zmienne kategoryczne, a nieczęsto spotykamy się ze zbiorami zawierającymi same zmienne dyskretne.

1. Rodzina algorytmów: iteracyjno-optymalizacyjne.
2. Założenia i ograniczenia:
   • wymaga ustalenia liczby grup a priori,
   • wrażliwy na dobór punktów startowych,
   • używa jedynie zmiennych kategorycznych.
3. Obsługiwane typy zmiennych: tylko kategoryczne (obsługuje braki danych).
4. Szybkość: wysoka.
5. Więcej informacji:
   • wprowadzenie teoretyczne i praktyka,
   • k-modes vs k-średnich – porównanie na przykładowym zbiorze.

5.6. K-prototypów

Ze względu na schemat działania algorytm ten jest zaliczany do metod iteracyjno-optymalizacyjnych. Jest on kolejną ewolucją algorytmów k-średnich i k-modes. Zachowuje wszystkie zalety swoich protoplastów, eliminując przy tym kilka istotnych wad.

W kolejnych iteracjach działania algorytmu wykonywana jest optymalizacja wyniku przedstawionego w postaci odległości wszystkich obserwacji danej grupy względem jej „prototypu”.

Nazwa k-prototypes odnosi się do k-prototypów będących reprezentantami tendencji centralnej danej grupy. Prototyp jest obiektem będącym reprezentantem danej grupy obserwacji. Jest odpowiednikiem centroidu z algorytmu k-średnich i mody z algorytmu k-modes. Algorytm ten jest połączeniem k-średnich i k-modes.

Zamiast dystansu (jak w k-średnich) używa on miary odmienności, będącej zmodyfikowaną wersją miary odmienności zaimplementowanej w algorytmie k-modes. Jest ona hybrydą odległości z k-średnich i miary odmienności k-modes.

Algorytm dąży do minimalizacji wariancji wewnątrz grup i jej maksymalizacji pomiędzy grupami. Dla zmiennych ciągłych algorytm bazuje na centroid, natomiast dla zmiennych kategorycznych algorytm bazuje na częstościach występowania kategorii.

Im mniejsza wartość miary odmienności, tym większe podobieństwo pomiędzy obserwacjami. Miara odmienności jest przedstawiona jako suma niedopasowań poszczególnych zmiennych kategorycznych pomiędzy obserwacjami.

1. Rodzina algorytmów: iteracyjno-optymalizacyjne.
2. Założenia i ograniczenia:
   • wymaga ustalenia liczby grup a priori,
   • wrażliwy na dobór punktów startowych.
3. Obsługiwane typy zmiennych: numeryczne i kategoryczne (obsługuje braki w danych).
4. Szybkość: średnia/wysoka (w zależności od zbioru).
5. Więcej informacji:
   • wprowadzenie teoretyczne,
   • projekt z użyciem algorytmu k-prototypów.

5.7. DBSCAN

Bodaj najpopularniejszy reprezentant rodziny algorytmów gęstościowych. Segmenty buduje na podstawie informacji o zagęszczeniu obserwacji w przestrzeni. Poprzez zagęszczenie należy rozumieć odległości dzielące poszczególne obserwacje w danym obszarze. W mojej ocenie jest ono najbardziej intuicyjną metodą grupowania.

O odróżnieniu od algorytmów iteracyjno-optymalizacyjnych znakomicie radzi sobie przy identyfikacji segmentów o nieregularnych (niewypukłych) kształtach. Daje możliwość budowania grup o różnych kształtach (brak założenia o sferyczności grup, tak, jak w przypadku algorytmu k-średnich).

W przypadku DBSCAN nie wszystkie obserwacje muszą zostać przypisane do grup. Obserwacje niespełniające zakładanych kryteriów są uznawane za obserwacje odstające. Dzięki temu bywa on używany przy problemach detekcji anomalii.

DBSCAN posiada jedynie dwa parametry, których optymalizację trzeba wykonać. Ich dobór w taki sposób, by powstała „odpowiednia” liczba grup i by obserwacje nietypowe nie stanowiły znaczącej części zbioru, jest jednak dosyć poważnym wyzwaniem.

1. Rodzina algorytmów: gęstościowe.
2. Założenia i ograniczenia:
   • nie daje możliwości definiowania a priori liczby grup,
   • dobór odpowiednich parametrów bywa dosyć problematyczny.
3. Obsługiwane typy zmiennych: tylko numeryczne.
4. Szybkość: średnia/wysoka (w zależności od zbioru i implementacji).
5. Więcej informacji:
   • wprowadzenie teoretyczne,
   • praktyczne użycie.

6. Podsumowanie

Ufff.. Dobrnęliśmy do końca. Miało być podsumowanie cyklu wpisów, a wyszedł jeden z dłuższych wpisów na blogu. 🙂 Mam ogromna nadzieję, że wiedza, którą tu zawarłem, nie pójdzie na marne i choć w minimalnym stopniu okaże się dla Ciebie pomocna. Jeśli tak się stanie, to podziel się swoimi przemyśleniami w komentarzu pod tym wpisem! 😉

Już w kolejnym artykule podzielę się z Tobą planami dotyczącymi przyszłości bloga. Nakreślę główne cele i opiszę sposób, w jaki będę blogować w najbliższych miesiącach.

7. Źródła

• Seria wpisów o algorytmach grupujących.
• Porównanie czasu wykonywania algorytmów grupujących.
• Porównanie czasu wykonywania i wyników algorytmów grupujących – sklearn.

photo: pixabay.com (Free-Photos)