Analiza skupień na przykładzie algorytmu k-średnich

Jednym z ciekawszych, a jednocześnie nie jednym z pierwszych zagadnień, na które można natrafić w uczeniu maszynowym, jest analiza skupień. Brzmi to trochę groźnie, ale tak naprawdę chodzi o sensowne grupowanie obserwacji w celu uzyskania jakiejś dodatkowej informacji.

Analiza skupień to jedna z dziedzin uczenia nienadzorowanego. Dziedzina ta należy do uczenia nienadzorowanego, gdyż nie mamy wzorcowego rozwiązania. Nie mamy informacji, jak wygląda idealne rozwiązanie naszego problemu. Możemy (a raczej musimy) tak długo pracować z danymi, aż uzyskamy satysfakcjonujący wynik lub stwierdzimy, że mamy już dość. Jest więc to nieco trudniejsza klasa problemów niż problemy z uczenia nadzorowanego. Uzyskane informacje też niekoniecznie mogą mieć natychmiastowe przełożenie na zyski biznesowe. Z drugiej strony – czemu nie, przecież taki proces nie cofnie nas w projekcie.

Algorytm k-średnich

Najłatwiejszym algorytmem pozwalającym wgryźć się w analizę skupień jest algorytm k-średnich. Przed rozpoczęciem algorytmu decydujemy, na ile grup chcemy podzielić nasze obserwacje. Następnie w kilku powtarzających się krokach będziemy szukali takich grup, które będą maksymalnie blisko środków wyznaczonych we wszystkich wymiarach. Omówmy go krok po kroku.

1. Wybór ilości klastrów

Przed działaniem arbitralnie decydujemy, ile klastrów chcemy uzyskać. Czasem może to wynikać z kontekstu – np. przeczytaliśmy artykuł, że w motoryzacji na ogół dokonuje się podziału na 5 klas cenowych samochodów osobowych (informacja wymyślona). Jeśli mamy więc dane np. z komisu to możemy przyjąć sobie, że pasuje nam podział na 5 grup. Co ciekawe, algorytm po zakończeniu pracy może nam wyprodukować podział, który zupełnie nie będzie pasował do sztywnego podziału cenowego. Albo podział ten może pokrywać się w np. 90%. W pierwszym przypadku mogłoby to oznaczać, że w naszym komisie cena może nie być aż tak różnorodna, jak inne cechy pojazdów. A w drugim przypadku, może okaże się, że cechy samochodów są zależne od ich ceny i inne podziały nie mają sensu.

W każdym razie, nawet jeśli nie mamy pojęcia jak wybrać tę liczbę, musimy się podjąć tego zadania. Jest to hiperparametr tego algorytmu, więc od niego będzie zależeć prawie wszystko.

2. Rozmieszczenie startowe centroid

Gdy już wybraliśmy, ile chcemy mieć grup, czas przystąpić do ich wstępnego rozmieszczenia. Tak, drugim krokiem tego algorytmu jest wyznaczenie miejsc, wokół których będziemy budować nasze grupy. Nieco śmiesznie to wygląda, jeśli na samym początku pracy wybieramy rozwiązanie. Ale spokojnie, nie jest to rozwiązanie ostateczne, ale pierwsza przymiarka. A żeby było ciekawiej, rozmieszczenie to zrobimy losowo w przestrzeni obserwacji.

Jak to zrobić? Otóż tworzymy sobie n pustych pseudo – obserwacji, gdzie n to liczba klastrów. Te pseudo-obserwacje będą mieć tyle samo takich samych wymiarów jak prawdziwe obserwacje. Dla każdej pseudo-obserwacji przechodzimy po każdym wymiarze i losujemy wartość mieszczącą się w zakresie obserwowanych wartości dla tego wymiaru. I w ten sposób zapełniamy wszystkie pseudo-obserwacje.

Jak by to wyglądało w dwóch wymiarach? Wyobraźmy sobie ramkę danych z cechami A i B. Mamy tutaj różne obserwacje i chcemy je podzielić na trzy grupy. Tworzymy więc pierwszą pseudo-obserwację i losujemy jej wartości. Wartość A dla tej pseudo-obserwacji będzie się zawierać w przedziale [min(A), max(A)], a wartość B będzie losowana z przedziału [min(B), max(B)]. Czyli jeśli obserwowane wartości w kolumnie A były od 0 do 10, a w kolumnie B od 30 do 40, to nasza pierwsza pseudo-obserwacja będzie miała wartość np. 7 i 32 w kolumnach A i B. I tak tworzymy sobie dwie kolejne pseudo-obserwacje.

3. Wyznaczanie najbliższych sąsiadów

Super, mamy już n pseudo-obserwacji, możemy więc przejść do następnego kroku. Wyliczamy odległość każdej obserwacji do każdej pseudo-obserwacji. Jak tą odległość będziemy wyliczać to już temat na inny artykuł, na potrzeby aktualnego przykładu możemy przyjąć odległość euklidesową. Gdy już mamy odległości, to przechodzimy po każdej obserwacji i wybieramy najbliższą jej pseudo-obserwację. Każda obserwacja zostanie przyporządkowana więc do jakiejś (najprawdopodobniej jednej) pseudo-obserwacji. Czyżbyśmy dotarli do końca algorytmu?

4. Wyznaczanie środka grupy.

Nie tak szybko. Okazuje się, że skoro nasze pseudo-obserwacje były wybrane losowo, to przy pierwszym przejściu cały podział też będzie po prostu przypadkowy. Fakt, skoro przyporządkowywaliśmy najbliższe obserwacje do pseudo-obserwacji to podział ten nie będzie najgorszy, ale pewnie daleko mu do optymalnego.

Żeby więc poprawić nasz podział, przejdziemy przez każdą grupę i przyjrzymy się jej. Weźmy więc pierwszą grupę stworzoną z pseudo-obserwacji i przyporządkowanych do niej obserwacji. Skupmy się na samych obserwacjach. Chcielibyśmy wyliczyć środek w danym wymiarze w tej grupie. Żeby to zrobić, wystarczy wyznaczyć wartość średnią z tych wartości. Jeśli przejdziemy przez każdy wymiar, to wyznaczymy w ten sposób środek tej grupy. I teraz możemy sobie sprawdzić, czy przypadkiem środek tej grupy nie jest też naszą pseudo-obserwacją. Jeśli jest, to cieszymy się z tego, i oznaczamy sobie, że ta grupa jest „ogarnięta”. Jeśli nie jest to ten sam punkt, to przesuwamy naszą pseudo-obserwację na miejsce tego punktu środkowego. Czyli po prostu kopiujemy te współrzędne.

Przechodzimy w ten sposób przez wszystkie grupy. Jeśli wszystkie są „ogarnięte” to kończymy nasz algorytm. Jeśli chociaż jedna grupa miała przesuniętą odpowiadającą jej pseudo-obserwację, to wracamy do punktu 3-go.

Możemy też natrafić na jeszcze jedną sytuację, wynikającą z obliczeniowych ograniczeń komputerów. Otóż może zdarzyć się, że przy dużej ilości punktów będziemy się przesuwać w stronę środka grupy bardzo małymi kroczkami. Kroczki te będą co rundę coraz mniejsze. Może więc okazać się, że bez sensu jest czekać na zakończenie się procesu, który nie za bardzo da znacząco lepsze wyniki. Z tego powodu możemy więc ustalić minimalną odległość przesunięcia, która jest dla nas sensowna albo maksymalną ilość kroków, które chcemy zrealizować w tym algorytmie. Jeśli więc odległość potencjalnego przesunięcia będzie wystarczająco mała albo wyczerpiemy limit kroków, to również możemy zakończyć algorytm.

5. Zakończenie

Jeśli wszystkie grupy mamy ogarnięte, czyli że pseudo-obserwacje są w ich środkach, to możemy zakończyć nasz proces. Nasze pseudo-obserwacje stają się wtedy centroidami grup. Wynik tego procesu daje nam niejako trzy „informacje”.

Efekt zastosowania algorytmu k-średnich

Pierwszym najbardziej widocznym efektem powyższego algorytmu jest przyporządkowanie każdej obserwacji do jakiejś z n grup. Nasz zbiór został więc podzielony na grupy, które teoretycznie mają dość podobne do siebie elementy. Jeśli była to na przykład część procesu podziału pracy, to możemy rozdać te grupy n pracownikom do rozpracowania.

Drugim efektem jest uzyskanie bazy do przyporządkowywania nowych obserwacji. Wystarczy bowiem, że zapiszemy sobie powstałe centroidy. Wtedy, gdy pojawi się nowa obserwacja, wyliczymy sobie odległości do tych centroid. Gdy znajdziemy najbliższą, znajdziemy też grupę, do której wpadnie nasza nowa obserwacja. Fakt, jeśli nasze zjawisko zmienia się w czasie i podlega np. modom, to warto byłoby co jakiś czas powtórzyć cały proces również z nowymi danymi.

Trzecim efektem są same centroida. Centroid taki, mimo iż nie jest faktyczną obserwacją, może nam dać wskazówkę, jak mogłaby wyglądać najbardziej przeciętna obserwacja w danej grupie. Warto podejść z rezerwą to tych wartości (no bo nieco trudno oczekiwać np. telewizora o przekątnej 47.721 cala), ale może akurat komuś się przyda do wizualizacji w głowie przy dalszych przemyśleniach.

Graficzne przedstawienie algorytmu

Wikipedia posiada całkiem przystępne graficzne „streszczenie” powyższego algorytmu. Sądzę, że warto je tutaj pokazać.

Widzimy tutaj szare obserwacje w przestrzeni dwu wymiarowej i trzy wylosowane pseudo-obserwacje. Jedyna różnica jest taka, że czerwona obserwacja została wylosowana poza przestrzenią obserwacji (jest powyżej najwyższej widzianej wartości). Jednakże nie zmienia to nic w algorytmie, gdyż i tak będziemy ją przesuwać „do środka”.

Policzyliśmy odległości szarych obserwacji do „kółeczek” i daliśmy im kolor zgodnie z tym, które kółeczko było najbliżej. Dodatkowo na tym rysunku widzimy granice, które pokazują do którego „koloru” wpadłyby obserwacje, gdyby było ich więcej. Przesuńmy więc „kółeczka” do środków grup.

Przesuwamy „kółeczka” w odpowiednie miejsca. Zwróćmy uwagę, że jeśli grupa ma jedną obserwację, to „kółeczko” wyląduje dokładnie w tym miejscu.

Powtarzamy proces przyporządkowywania do najbliższego „kółeczka” (zwanego u mnie pseudo-obserwacją). Widzimy, że czerwona grupa zyskała, a zielona straciła. Proces ten będzie powtarzany, aż kółeczka przestaną się przesuwać, albo nam się znudzi (patrz ostatni akapit 4-go punktu powyżej).

Wady

Okej, porozmawiajmy teraz o wadach tego algorytmu. Pierwszą i największą wadę już poznaliśmy. Jest to konieczność odgórnego określenia, na ile grup chcemy dzielić nasz zbiór obserwacji. O ile mamy jakiś konkretny cel do zrealizowania, z którego wynika ilość grup (np. podział pracy) to nie jest to aż tak duży problem. Jeśli jednak eksplorujemy dane, to równie dobre dla nas mogą być podziały na trzy, jak i na dwadzieścia grup. Jest co najmniej jedna technika, która trochę pomaga w określeniu optymalnej ilości grup, ale o niej w innym artykule.

Drugą wadą omawianego algorytmu jest problem lokacji startowej. Lokację tę wybieramy losowo. Może zdarzyć się, że jeśli obserwacje są od siebie bardzo mocno odseparowane, to centroidy będą walczyły ze sobą o relatywnie małą grupę obserwacji, a inne zdecydowanie za duże potencjalne grupy nie zostaną w ogóle podzielone. Jest to tak zwany problem minimum lokalnego, gdzie optymalizujemy jakieś ułamkowe wartości, a o wiele więcej byśmy mogli ugrać, gdybyśmy spróbowali od początku i innymi pozycjami startowymi. Bardzo fajnie widać to na kolejnym przykładzie z Wikipedii:

Widzimy tutaj, że wśród obserwacji „ewidentnie” możemy wyznaczyć cztery grupy. Jednak z powodu niefortunnego losowania pozycji startowej centroid w lewym górnym rogu, tamta grupa obserwacji będzie dzielona miedzy dwie centroidy, natomiast dwie grupy na dole zostają „przejęte” przez jedną centroidę. Nie jest to raczej sytuacja pożądana. Kilka tęgich głów myślało (i pewnie dalej myśli) nad tym problemem i wymyśliło algorytm startowy k-means++ który zdaje się pomagać w takich sytuacjach i ogólnie przyspiesza znalezienie rozwiązania.

Trzecią wadą jest fakt, że korzystając z centroid i odległości od nich, grupujemy obserwacje koncentrycznie. Najłatwiej to sobie uświadomić oglądając różne kształty i ich grupowanie na płaszczyźnie. Na przykładzie po prawej stronie widzimy wyraźnie, że nie uda nam się w ten sposób wydzielić niektórych  „oczywistych” grup. Warto o tym pamiętać, gdy badamy dane niejako po omacku.

Przykład

Czas więc na przykład „z życia wzięty”. Wyobraźmy sobie, że jesteśmy kolekcjonerami znaczków turystycznych (notabene nasze rodzinne hobby – polecamy). Postanowiliśmy, że raz w miesiącu, przez cały rok, zorganizujemy sobie wyprawę w jakiś region Polski i będziemy odwiedzać w nim znaczkowe miejsca turystyczne. Chcielibyśmy, żeby miejsca te nie były zbyt blisko siebie – wtedy jest ryzyko, że miejsca za szybko nam się wyczerpią, bo będą się pokrywać. Nie chcemy też wybierać najbardziej możliwie oddalonych od siebie miejsc na mapie, bo wtedy do niektórych znaczków możemy mieć dość daleko. Przypominamy sobie, że znamy algorytm k-średnich, może więc go użyjemy do rozwiązania tego problemu?

Okazuje się, że nasz ulubiony Scikit-Learn ma bardzo wygodną (jak to zwykle w Scikit-Learn bywa) implementację w postaci funkcji KMeans. Pobierzmy więc dane o lokalizacji znaczków i do dzieła.

Zacznijmy od wczytania danych:

# Kod 1

import pandas as pd

znaczki = pd.read_excel("../input/wykaz-zt-polski.xls", skiprows = 4)

znaczki.rename(columns={"GPS":"lat", "Unnamed: 5":"lon"}, inplace=True)

znaczki["lat"] = znaczki["lat"].astype(float)
znaczki["lon"] = znaczki["lon"].astype(float)

Użyty przez nas plik z danymi jest przygotowany raczej dla człowieka niż maszyny, musimy więc troszkę pokombinować, żeby go sensownie wczytać. Ale jak widać powyżej, nie był to duży problem. Dokonajmy więc grupowania:

# Kod 2

from sklearn.cluster import KMeans

n_clusters = 12

kmeans = KMeans(n_clusters = n_clusters, random_state = 42)

coordinates = znaczki[["lat", "lon"]]

kmeans.fit(coordinates)

znaczki["grupa"] = kmeans.labels_

znaczki.head()

Okazuje się, że użycie odpowiedniej funkcji sprowadza ten problem to bardzo prostego rozwiązania. Obejrzyjmy jeszcze początek naszej wynikowej ramki danych:

	LP.	Numer znaczka	Nazwa znaczka	Województwo	lat	lon	grupa
0	1	No. 001	Rysy – najwyższy szczyt polskich Tatr	małopolskie	49.179628	20.087987	1
1	2	No. 002	Schronisko „Murowaniec” na Hali Gąsienicowej	małopolskie	49.244167	20.007222	1
2	3	No. 003	Babia Góra – najwyższy szczyt Beskidu Żywieckiego	małopolskie	49.573055	19.529444	4
3	4	No. 004	Schronisko Morskie Oko	małopolskie	49.201378	20.071276	1
4	5	No. 005	Schronisko Głodówka	małopolskie	49.302124	20.116664	1

W czasie realizacji tego przykładu przyjąłem, że skoro wszystkie punkty znajdują się na terenie Polski, różnica między szerokością a długością geograficzną może zostać pominięta i potraktuję te wartości równorzędnie. Bazując na pliku pobranym na początku stycznia, uzyskałem następującą mapę:

Jak widać, wygląda to nawet sensownie. Jeżeli skorzystamy z atrybutu cluster_centers_ to uzyskamy współrzędne środków tych grup. Jeśli więc chcielibyśmy wycisnąć maksymalnie dużo w ciągu tych 12 podróży, powinniśmy mieszkać w hotelach jak najbliżej tych środków. Albo rozwiązać problem komiwojażera w każdej z tych grup ;).

Podsumowanie

Jeśli wpadły nam w ręce jakieś ciekawe dane, a nie mamy konkretnego problemu do rozwiązania za ich pomocą, zawsze możemy spróbować je pogrupować i zobaczyć czy do czegoś sensownego uda nam się dojść. Najprostszym (według mnie) algorytmem grupowania jest algorytm k-średnich i nawet jeśli nasz ulubiony język programowania go nie wspiera, możemy go sobie sami sensownie zaimplementować. Algorytm ten nie da nam fajnych wyników przy fikuśnych zbiorach danych, ale gdy dane są trochę pogrupowane i trochę jednorodne to może mieć do całkiem dużo sensu. Problemem pozostanie jeszcze wybranie, ile grup chcemy zobaczyć, ale to też da się rozwiązać ( pokażę w którymś kolejnym artykule). Także, mimo iż algorytm ten jest bardzo prosty, może być również całkiem przydatny.

Pełen kod użyty w przykładzie, wraz z kodem odpowiedzialnym za stworzenie mapki, znajduje się tutaj.