Grupowanie iteracyjno-optymalizacyjne. Algorytm k-średnich – teoria

W tym wpisie na tapetę biorę k-średnich, czyli prawdopodobnie najpopularniejszy algorytm wykorzystywany w grupowaniu.

Z tego artykułu dowiesz się:
1. Czym jest grupowanie iteracyjno-optymalizacyjne?
2. Jak działa algorytm k-średnich?
3. O czym należy pamiętać, wykonując grupowanie z użyciem tego algorytmu?

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. Nawet na studiach wykładowcy zazwyczaj zaczynają opisywać problem „klastrowania” od właśnie niego. 🙂

Artykuł dotyczący algorytmu k-średnich ze względu na objętość postanowiłem podzielić na dwie części. W tym wpisie przedstawiam podstawy teoretyczne i schemat działania, tak byś mógł zbudować w sobie pewną intuicję na temat działania tego algorytmu. Druga część, która pojawi się w kolejnym, to przykład praktycznego użycia algorytmu z zastosowaniem kilku popularnych bibliotek oraz porównanie ich działania na różnych zbiorach.

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

Założenia

Algorytm k-średnich posiada kilka istotnych założeń. W zależności od analizowanego zbioru potrafią one przysporzyć sporych problemów, a nawet sprawić, że sam algorytm staje się bezużyteczny.

1. Wszystkie zmienne są numeryczne.
2. Każda z rzeczywistych grup ma w przybliżeniu tę samą liczbę obserwacji.
3. Średnia współrzędna jest optymalną wartością do oceny położenia grupy.
4. „Rzeczywiste” grupy są sferyczne (to założenie, będące jednocześnie ograniczeniem będzie dobrze widoczne w jednym z przykładów).

Sprawdź również wpis dotyczący algorytmów hierarchicznych

Wady i zalety

Stosując algorytm k-średnich warto mieć również na uwadze zarówno wszystkie jego ograniczenia, jak i mocne strony.

Wady:

• Wymagają ustalenia liczby grup – zanim uruchomimy algorytm, musimy a priori podać liczbę grup, które mają zostać wyznaczone. Bez uprzedniego wizualizowania zbioru lub wykonania dodatkowych analiz jest to dosyć trudne.
• Wrażliwe na dobór punktów startowych – w pierwszej iteracji swojego działania algorytm losowo dobiera punkty startowe. To jak dobre wyniki uzyska, zależy zatem w pewnym stopniu od czynnika losowego.
• Wrażliwy na wpływ obserwacji odstających i szum – podobnie jak wartość średnia, tak i algorytm k-średnich jest wrażliwy na wpływ obserwacji odstających. Przyczyna jest błaha: do wyznaczenia przeciętnej obserwacji używana jest wartość średnia współrzędnych wszystkich obserwacji danej grupy.
• Każdy klaster ma w przybliżeniu tę samą liczbę obserwacji.
• Zakłada, że grupy są sferyczne (problem ten będzie znakomicie widoczny w kolejnym wpisie, gdy przedstawię działanie algorytmu na różnych zbiorach).
• Używa jedynie zmiennych numerycznych – by liczyć średnie ze współrzędnych obserwacji konieczne jest używanie zmiennych numerycznych (zmiana kodowania wprowadza szum).

Zalety:

• Szybsze na dużych zbiorach niż algorytmy hierarchiczne – wynika to bezpośrednio ze sposobu jego działania. Niższa złożoność obliczeniowa sprawia, że w porównaniu z grupowaniem aglomeracyjnym, algorytm k-średnich działa błyskawicznie. Wielkość zbioru przestaje więc być tak dużym problemem.
• Bardzo szybki (relatywnie niska złożoność obliczeniowa: iteracje * liczba_grup * instancje * wymiary) – złożoność obliczeniowa każdej iteracji to: O(k * N), gdzie N-liczba obserwacji w grupie. Problemem jest liczba iteracji potrzebna do osiągnięcia zbieżności.

Pozostałe algorytmy iteracyjno-optymalizacyjnie

Algorytm k-średnich to najpopularniejszy reprezentant algorytmów iteracyjno-optymalizacyjnych. Warto zaznaczyć, że do tej samej grupy należą inne algorytmy, które potrafią niwelować niektóre z ograniczeń popularnego „k-meansa”. Poniżej wymieniam najpopularniejsze z nich i hasłowo je omawiam. Szerzej opiszę ich działanie w kolejnych wpisach.

• K-median – zbliżony do k-średnich. Dla każdej z grup używa on mediany współrzędnych zamiast centroidu  (ze wszystkimi konsekwencjami takiego zabiegu, czyli np. brakiem wrażliwości na wartości odstające)
• K-medoidów – często jest mylony z algorytmem k-median. Bywa nazywany również PAM (ang. Partitioning Around Medoids) z uwagi na sposób działania.
• K-modes – algorytm służy do grupowania obserwacji opisanych za pomocą zmiennych kategorycznych. Bazuje na częstościach występowania kategorii.
• K-prototypes – kombinacja k-modes i k-średnich.

Podsumowanie

W następnym wpisie przedstawię część praktyczną. Skupię się na pokazaniu użycia algorytmu k-średnich na kilku różnych zbiorach, oraz porównam wyniki jego grupowania z algorytmem aglomeracyjnym.

Jeśli masz jakieś pytania, to proszę podziel się nimi w komentarzu pod wpisem – zapraszam do dyskusji. Jeśli artykuł przypadł Ci do gustu, to proszę, podziel się nim w mediach społecznościowych ze swoimi znajomymi. Będę bardzo wdzięczny. 🙂

—

Linki:

• Schemat działania k-średnich
• Implementacja algorytmu k-średnich w bibliotece sklearn
• Implementacja algorytmu k-średnich w bibliotece SciPy
• Alternatywna implementacja algorytmu k-średnich w bibliotece SciPy

photo: pixabay.com (manfredrichter)