Intro
W dzisiejszym artykule omówimy sobie podstawowy algorytm uczenia nienadzorowanego, który wykorzystuje się do grupowania danych, a mianowicie K-means. Nazwa tego algorytmu wzięła się od tego, że dzieli on dane na liczbę klastrów równą K wykorzystując do tego średnie, aby określić jak blisko obserwacje znajdują się pomiędzy sobą. Obserwacje, którą są blisko siebie, należą do tego samego klastra. Algorytm K-means jest stosunkowo prosty, jednak wciąż popularny w uczeniu maszynowym z uwagi na swoją skalowalność i szybkość.
W artykule wytłumaczę zasadę działania algorytmu oraz pokażę przykładową analizę danych z jego wykorzystaniem w języku Python.
Zasada działania algorytmu
K-means jest algorytmem iteracyjnym, to znaczy takim, w którym do rozwiązania problemu dochodzimy stopniowo – zaczynając od losowego 'strzału’, a następnie sekwencyjnie poszukując coraz to lepszego rozwiązania. W przypadku K-means, będzie to polegało na przesuwaniu początkowo rozlosowanych centroidów poszczególnych klastrów w taki sposób, aby coraz lepiej reprezentowały one grupy danych.
Wyzwaniem w algorytmie K-means jest odpowiednie określenie liczby klastrów. Optymalną liczbą klastrów będzie taka, w której punkty wewnątrz klastrów są blisko siebie, a punkty jednego klastra są jak najdalej od punktów innego klastra. Pomocny w ustaleniu liczby klastrów będzie tzw. Silhouette Coefficient (zaimplementujemy go sobie w dalszej części artykułu). W niektórych przypadkach liczba klastrów wynika wprost z kontekstu problemu, który chcemy rozwiązać, np. chcemy podzielić uczniów na tych z predyspozycjami do przedmiotów ścisłych oraz tych z predyspozycjami do przedmiotów humanistycznych – wtedy naturalnie użyjemy dwóch klastrów.
Jak już sobie powiedzieliśmy kluczowym elementem w naszym zagadnieniu jest odległość. Odległość w przestrzeni możemy mierzyć na różne sposoby, w tym celu wykorzystuje się różne metryki. Najpopularniejszą z nich z nich jest metryka euklidesową, która jest przybliżeniem przestrzeni w naszym świecie (to właśnie tej metryki używaliśmy w liceum, aby policzyć odległość od jednego punktu do drugiego na wykresie – czyli dwuwymiarowej przestrzeni euklidesowej). W naszym przypadku liczba wymiarów będzie równa liczbie zmiennych które poddamy analizie. Im większa liczba cech, tym większa liczba wymiarów. Jako ludziom, ciężko jest nam wyobrazić sobie liczbę wymiarów większą niż 3 (a raczej zwizualizować – ponieważ właśnie tyle wymiarów przestrzennych obserwujemy na co dzień), jednak algorytmy uczenia maszynowego nie mają z tym problemu i dzięki narzędziom matematycznym poruszają się w większej liczbie wymiarów swobodnie.
Kroki algorytmu K-means
Działanie algorytmu K-means opisać możemy w następujących krokach.
| Krok 1 | Wybieramy liczbę klastrów k. |
| Krok 2 | W przestrzeni, w której umieściliśmy dane (każda obserwacja jako punkt), losowo umieszczamy k punktów, które są centroidami naszych klastrów. |
| Krok 3 | Obliczamy dystans (według wybranej metryki – standardowo euklidesowej) od każdego z punktów do każdego z k centroidów klastrów. Na przykład jeżeli mamy 200 obserwacji oraz k=2 centroidów, to musimy obliczyć 400 odległości. |
| Krok 4 | Przypisujemy każdy z punktów do najbliższego centroida klastra. |
| Krok 5 | Teraz każda obserwacja (nasz punkt w przestrzeni) ma przypisany centroid. Pamiętajmy jednak, że centroidy umieszczenie centroidów zostało rozlosowane. Musimy sprawdzić, czy nasze centroidy są także środkami ciężkości swoich klastrów. Obliczamy nowe współrzędne centroidów poprzez wyliczenie średniej z punktów przynależących do danego klastra. Ten krok wyjaśnia skąd wzięła się nazwa k-means. |
| Krok 6 | Jeżeli centroidy klastrów przesunęły się w kroku 5, to znaczy, że musimy wrócić do kroku 3. i na nowo przypisać punkty do cetnroidów i utworzyć nowe klastry. Powtarzamy kroki 3-5 tak długo, aż centroidy przestaną się przemieszczać lub gdy następi warunek stopu (np. określona przez nas maksymalna liczba iteracji). |
I to wszystko… Wcale nie takie trudne, prawda?
Warunki stopu
Dla algorytmu K-means domyślnym warunkiem stopu jest sytuacja, w której cetroidy przestaną się przemieszczać. Czasami jednak (podobnie jak i w innych algorytmach uczenia maszynowego), może upłynąć dużo czasu zanim K-means uzyska zbieżność (odnajdzie optymalne rozwiązanie) – zwłaszcza jeżeli analizujemy duże zbiory danych w przestrzeni o wysokiej liczbie wymiarów. Wtedy, zamiast czekania aż algorytm zbiegnie, możemy sobie zdefiniować warunek stopu:
- określając maksymalny czas wykonania algorytmu
- określając maksymalną liczbę iteracji algorytmu
Analiza danych przy użyciu algorytmu K-means [Python]
W tej części artykułu pokażę prostą implementację algorytmu K-Means przy użyciu języka Python i jego popularnych bibliotek.
Import bibliotek
Importujemy potrzebne biblioteki (opis w komentarzach).
# importuję potrzebne biblioteki import numpy as np # obliczenia numeryczne import pandas as pd # przechowywanie, manipulacja i analiza danych import sklearn # algorytm K-means z pakietu sklearn import seaborn as sns # wizualizacje
Dane
Dane do mojej analizy stworzę sobie sam… zaraz wytłumaczę w jaki sposób. W jednym ze swoich artykułów o wstępie do uczenia maszynowego (tutaj), posłużyłem się przykładem, w którym przy użyciu algorytmu K-Means identyfikowałem kobiety i mężczyzn. W tym artykule chciałbym rozwinąć ten przykład.
Zbiór danych zawierał będzie następujące zmienne:
- płeć
- waga
- wzrost
- długość włosów
Następnie zaaplikuję algorytm K-Means dla zmiennych waga, wzrost oraz długość włosów. Zobaczymy czy będą zgadzać się z rzeczywistością (tym, co stworzę). Wartości tych zmiennych stworzę z rozkładu normalnego. Dla przykładu wzrost mężczyzn będziemy losowali z rozkładu normalnego w którym przeciętny mężczyzna ma 180 cm, a odchylenie standardowe wynosi 7 cm. Wymyśliłem sobie te parametry (bo to tylko przykład jak wykorzystać algorytm do analizy). Wagę mężczyzny symulowałem poprzez odjęcie od jego wzrostu wartości 100 i dodanie liczby losowej z rozkładu normalnego o innych parametrach (wszystko będzie w kodzie poniżej). Długości włosów również stworzyłem stosując rozkład normalny (i mały 'myk’ w przypadku mężczyzn).
Przy pomocy pętli i rozkładu normalnego tworzę dane odnośnie długości włosów dla 100 kobiet (1 – krótkie, 2 – średnie, 3 – długie).
# długości włosów dla kobiet
włosy_kobiet = []
for i in range(100):
mu, sigma = 2.5, 0.4
włosy_k = np.random.normal(mu,sigma)
włosy_kobiet.append(włosy_k)
for n,i in enumerate(włosy_kobiet):
if i<=1.5:
i=1
włosy_kobiet[n]=i
elif i>1.5 and i<2.5:
i=2
włosy_kobiet[n]=i
else:
i=3
włosy_kobiet[n]=i
print('Kobiet o krótkich włosach jest: {}'.format(str(włosy_kobiet.count(1))))
print('Kobiet o średnich włosach jest: {}'.format(str(włosy_kobiet.count(2))))
print('Kobiet o długich włosach jest: {}'.format(str(włosy_kobiet.count(3))))Otrzymaliśmy takie wyniki:
Wygląda całkiem realistycznie, prawda? Teraz zrobimy to samo dla mężczyzn, tylko użyjemy innych parametrów dla rozkładu normalnego i w celu urealistycznienia dodamy sobie jeden warunek (korzystając z rozkładu jednostajnego), dzięki, któremu zwiększymy prawdopodobieństwo trafienia jakiegoś długowłosego mężczyzny w zbiorze. Sam proces tworzenia tych danych nie jest specjalnie istotny dla tego artykułu, więc nie musicie poświęcać zbyt wiele czasu na zrozumienie tego co teraz robię, ale jeżeli ktoś jest zainteresowany, to poniżej kod dla tworzenia długości włosów mężczyzn.
# długości włosów dla mężczyzn
for n,i in enumerate(włosy_mężczyzn):
if i<=1.5:
i=1
włosy_mężczyzn[n]=i
elif i>1.5 and i<2.5:
if np.random.uniform()<0.8:
i=2
włosy_mężczyzn[n]=i
else:
i=3
włosy_mężczyzn[n]=i
else:
i=3
włosy_mężczyzn[n]=i
print('Mężczyzn o krótkich włosach jest: {}'.format(str(włosy_mężczyzn.count(1))))
print('Mężczyzn o średnich włosach jest: {}'.format(str(włosy_mężczyzn.count(2))))
print('Mężczyzn o długich włosach jest: {}'.format(str(włosy_mężczyzn.count(3))))Oto wyniki:
Teraz przejdziemy do tworzenia wzrostu i wagi dla kobiet i mężczyzn, stworzymy również listę etykiet dla płci.
# tworzę listy ze wzrostem i wagą dla mężczyzn
wzrost_mężczyzn = []
waga_mężczyzn = []
for i in range(100):
mu, sigma = 180, 7
wzrost_m = np.round(np.random.normal(mu,sigma),0)
wzrost_mężczyzn.append(wzrost_m)
waga_m = np.round(wzrost_m - 100 + np.random.normal(0,5),0)
waga_mężczyzn.append(waga_m)
# tworzę listy ze wzrostem i wagą dla kobiet
wzrost_kobiet = []
waga_kobiet = []
for i in range(100):
mu, sigma = 165, 5
wzrost_k = np.round(np.random.normal(mu,sigma),0)
wzrost_kobiet.append(wzrost_k)
waga_k = np.round(wzrost_k - 100 + np.random.normal(0,12),0)
waga_kobiet.append(waga_k)
# tworzę listy z etykietami dla kobiet i mężczyzn
etykieta_kobiet = ['Kobieta' for i in range(100)]
etykieta_mężczyzn = ['Mężczyzna' for i in range(100)]Dobrze, teraz jeszcze nadajmy naszym danym strukturę i umieśćmy je w DataFramie (taką nazwę mają tabele w bibliotece pandas).
# tworzę Dataframe z utworzonych wcześniej danych
dictionary = {'płeć': etykieta_kobiet+etykieta_mężczyzn,
'wzrost': wzrost_kobiet+wzrost_mężczyzn,
'waga': waga_kobiet+waga_mężczyzn,
'długość włosów': włosy_kobiet+włosy_mężczyzn}
df = pd.DataFrame(dictionary)
dfI otrzymuję taką tabelkę z liczbą rekordów równą 200.
Zatem mamy nasze dane skompletowane, możemy zabierać się do działania.
Skalowanie danych
Jeżeli chcielibyśmy umieścić nasze dane w przestrzeni w surowej formie, to napotkalibyśmy pewien podstawowy merytoryczny problem. Mianowicie, niektóre zmienne wpływałyby mocniej na nasz algorytm niż inne. W naszym przypadku wzrost miałby o wiele większy wpływ na położenie centroidów niż długość włosów. Nie chcemy tego zatem zastosujemy standaryzację. Wartości będziemy skalować według następującego wzoru:
z={(x-u) \above{2pt} s}gdzie u jest średnią ze zbioru, x jest to wartość obserwacji, a s jest to odchylenie standardowe zbioru. Do zaimplementowania tego przekształcenia wykorzystamy funkcję StandardScaler(), którą oferuje pakiet scikit-learn Przeskalujemy sobie każdą z naszych zmiennych i dołączymy przeskalowane wartości do DataFrame’u.
#skalujemy zmienne i tworzymy DataFrame from sklearn.preprocessing import StandardScaler scaler = StandardScaler() df2 = df[['wzrost', 'waga', 'długość włosów']] scaler.fit(df[['wzrost', 'waga', 'długość włosów']]) scaled_data = scaler.transform(df[['wzrost', 'waga', 'długość włosów']]) scaled_data_df = pd.DataFrame(data=scaled_data) scaled_data_df
A tak wyglądają przeskalowane wartości wzrostu, wagi i długości włosów:
Zastosowanie K-Means
Dla tak wyliczonych obserwacji wykorzystujemy algorytm K-Means i według opisanych w pierwszej części kroków wyznaczamy dwa klastry. Do implementacji algorytmu wykorzystujemy popularną bibliotekę scikit-learn. Algorytm określa przynależność obserwacji do klastrów, po czym dołączamy tę klasyfikację do naszego DataFrame’u.
# donujemy grupowania przy uzyciu algorytmu K-Means from sklearn.cluster import KMeans kmeans = sklearn.cluster.KMeans(n_clusters=2).fit(scaled_data_df) prediction = kmeans.labels_.astype(int) #łączymy tabele prediction_df = pd.DataFrame(data=prediction, columns=['klasyfikacja']) df_full = pd.concat([df, scaled_data_df, prediction_df], axis=1) df_full['klasyfikacja'] = np.where(df_full['klasyfikacja']==0, 1, 0) df_full
Świetnie! Główną część mamy już za sobą. Teraz zwizualizujmy sobie jak algorytm sklasyfikował dane i czy pokrywają się one z rzeczywistością. Porównanie można zobaczyć na obrazku poniżej przeciągając suwak.
Interpretacja wyników
Algorytm generalnie dobrze zidentyfikował kobiety i mężczyzn (większość klasyfikacji poprawna, co widać na powyższym wykresie). W zasadzie http://lindner-dresden.de/buchstabe-g/index.html , można powiedzieć, że K-Means odkrył wzorzec według którego wygenerowałem dane. Jeżeli przyjrzymy się na popełnione pomyłki – to jest dosyć ciekawie. Sztuczna Inteligencja uznała za kobiety kilku mężczyzn w okolicach 175-180 cm i 70-80 kg wagi o długich włosach (niebieski kwadraciki na wykresie z klasyfikacją algorytmu) – przecież po opisie wydaje się całkiem prawdopodobne że osoby o takich parametrach mogłyby być kobietami – zwłaszcza przez długie włosy. Za kobiety AI uznała natomiast kilku mniej postawnych mężczyzn (poniżej 170 cm wzrostu i 70 kg wagi) o krótkich włosach. Jak widzimy są to 'pomyłki’ intuicyjne i człowiek mając te same dane mógłby wydać podobne osądy.
Optymalna liczba klastrów
Tak jak wspomniałem wcześniej, optymalną liczbę klastrów da się ustalić wykorzystując specjalny współczynnik. Ten, którego użyjemy nosi nazwę Silhouette Coefficient. Oblicza się go używając średniej odległości wewnątrz klastra (a) i średniej odległości do najbliższego klastra (b) dla każdej z obserwacji. Dla pojedynczej próbki, wzór na rzeczony współczynnik wygląda następująco:
Silhouette.Coefficient={(b-a) \above{2pt} max(a,b)}Ostateczny wynik podaje się wyciągając średnią dla wszystkich obserwacji. Im bliżej 1 tym lepiej, im bliżej -1 tym gorzej. Sprawdźmy więc czy nasza liczba klastrów została dobrana poprawnie według naszego współczynnika. Właściwie to testujemy w ten sposób poprawność działania metody, ponieważ dane generowaliśmy sami i wiemy, że istnieją dwie róże grupy. Chociaż… kto wie? Sprawdźmy.
# obliczamy Silhouette Score dla różnych liczb klastrów
for n in range(2,11):
clusterer = KMeans(n_clusters=n)
preds = clusterer.fit_predict(scaled_data_df)
score = sklearn.metrics.silhouette_score(scaled_data_df, preds)
print("Dla k = {} klastrów, Silhouette Score jest równy {})".format(n, score))
Rzeczywiście, najwyższy wynik współczynnika został osiągnięty dla liczby klastrów równej 2, stąd też nasz wybór jest optymalny.
Ograniczenia K-Means
K-Means zaprojektowany został jako szybki i prosty algorytm. Z uwagi na tę prostotę, algorytm posiada pewne ograniczenia
- musimy samodzielnie wybrać liczbę klastrów
- wpływ na wynik ma początkowe rozmieszczenie centroidów, które jest losowe – za każdym razem możemy otrzymać trochę inny wynik
- algorytm jest wrażliwy na obserwacje odstające
Podsumowanie
W artykule przedstawiliśmy sobie algorytm K-Means, wyjaśniliśmy sobie w jaki sposób działa oraz pokazaliśmy przykładową analizę z wykorzystaniem popularnych bibliotek w języku Python. Mam nadzieję, że zobrazowało to mniej więcej ten prosty i całkiem przyjemny algorytm.
Referencje
- Imran Ahmad, ’40 Algorithms Every Programmer Should Know’, 2020