W poprzednich wpisach omawiałem algorytm k-średnich. Dziś przedstawiam kolejnego przedstawiciela grupy algorytmów iteracyjno-optymalizacyjnych, który jest świetną alternatywą dla popularnego k-meansa.
Opis algorytmu¶
K-median jest algorytmem grupującym, należącym do rodziny algorytmów iteracyjno-optymalizacyjnych. W swoim działaniu jest on bardzo zbliżony do opisywanego przeze mnie w jednym z poprzednich artykułów 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).
W kolejnych iteracjach działania algorytmu wykonywana jest optymalizacja wyniku przedstawionego w postaci odległości wszystkich obserwacji danej grupy względem mediany. K-median dąży zatem do minimalizacji wariancji wewnątrz grup i jej maksymalizacji pomiędzy grupami.
Schemat działania algorytmu k-średnich:
- Losowanie k-punktów startowych w przestrzeni (losujemy k pierwszych median).
- Przyporządkowanie wszystkich obserwacji do najbliższej mediany z pomocą danej miary odległości (w przypadku k-median jest to odległość euklidesowa).
- Dla każdej z k-grup wyznaczamy nową medianę.
- Powtarzamy krok 2 i 3 aż do osiągnięcia warunku stopu, którym może być:
- Osiągnięcie zbieżności, ew. „znacznej” poprawy względem wybranej miary jakości grupowania.
- Osiągnięcie momentu, w którym przydział obserwacji do grup się nie zmienia.
- Osiągnięcie zakładanej liczby iteracji.
Wady i zalety¶
Stosując algorytm k-median warto mieć również na uwadze zarówno wszystkie jego ograniczenia, jak i mocne strony.
Wady:
- Wymaga 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żliwy na dobór punktów startowych – w pierwszej iteracji swojego działania algorytm losowo dobiera punkty startowe (ew. możesz je ręcznie zdefiniować). To jak dobre wyniki uzyska, zależy zatem w pewnym stopniu od czynnika losowego.
- Każdy klaster ma w przybliżeniu tę samą liczbę obserwacji.
- Zakłada, że grupy są sferyczne.
- Używa jedynie zmiennych numerycznych – by wyznaczyć mediany ze współrzędnych obserwacji, konieczne jest używanie zmiennych numerycznych (zmiana kodowania wprowadza szum).
Zalety:
- W przeciwieństwie do algorytmu k-średnich, k-median nie jest wrażliwy na wpływ obserwacji odstających i szum – mediana jest mniej wrażliwa na wpływ obserwacji odstających niż średnia.
- Szybszy 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-median 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.
Przykład działania¶
By zademonstrować działanie algorytmu, posłużę się przykładowym, wygenerowanym zbiorem danych. Do przeprowadzenia grupowania użyję implementacji algorytmu dostępnej w świetnej bibliotece: PyClustering. Sposób korzystania z dostępnych algorytmów w niej algorytmów jest wprawdzie nieco inny niż w przypadku sklearn, ale można do niej przywyknąć. 😉
Importuję niezbędne biblioteki.
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
from pyclustering.cluster.kmedians import kmedians
from pyclustering.cluster.kmeans import kmeans
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
from sklearn.datasets.samples_generator import make_blobs
pd.set_option('float_format', '{:.3f}'.format)
Generuję zbiór.
x, y_true = make_blobs(n_samples=200, centers=2, cluster_std=0.99, random_state=3042019)
df = pd.DataFrame(x, columns = ['f1', 'f2'])
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, scatter_kws={"color": "#eb6c6a"}).set(title = 'Wykres obserwacji zawartych w zbiorze')
plt.show()
Tworzę instancję algorytmu k-median.
# Posłużę się "inicjatorem" punktów startowym, dostepnym w bibliotece PyClustering.
initial_medians = kmeans_plusplus_initializer(df[['f1', 'f2']].values, 2).initialize()
kmedians_instance = kmedians(df[['f1', 'f2']].values, initial_medians)
kmedians_instance.process()
clusters = kmedians_instance.get_clusters()
centers = kmedians_instance.get_medians()
for x in range(0,len(clusters)):
df.loc[df.index.isin(clusters[x]),'kmedians'] = str(x)
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'kmedians', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup')
plt.scatter([i[0] for i in centers], [i[1] for i in centers], c='black', s=100, alpha=0.5)
plt.show()
Podsumowanie¶
Kiedy zatem stosować algorytm k-median? Odpowiedź jest relatywnie prosta - gdy mamy do czynienia ze zbiorem opisanym zmiennymi numerycznymi (bez jakichkolwiek zmiennych nominalnych), z których przynajmniej część zawiera wartości odstające. W takim przypadku k-median poradzi sobie lepiej niż k-średnich.
W kolejnych wpisach będę opisywać kolejne algorytmy z rodziny algorytmów iteracyjno-optymalizacyjnych (k-modes i k-prototypes). Każdy kolejny algorytm będzie eliminować wady poprzedniego. K-median (względem algorytmu k-średnich) zniwelował niekorzystny wpływ obserwacji odstających na proces grupowania.
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. 🙂
A czy ten algorytm nie nada się dla zmiennych nienumerycznych ale w skali porządkowej (np wykształcenie podstawowe-średnie-wyższe)? Wg statystyki można dla takiej zmiennej podać medianę.
Hej Adam! 🙂 Przyznam, że nigdy wcześniej nie rozpatrywałem takiego przypadku dla k-median, dlatego bardzo dziękuję za ciekawy komentarz. Teoretycznie algorytm można użyć dla opisanego przez Ciebie problemu. Czy będzie to jednak w 100% poprawne i optymalne rozwiązanie? W mojej ocenie nie do końca. We wspomnianym przez Ciebie przypadku zdecydowanie lepiej się sprawdzi algorytm k-modes (na blogu już jutro), lub k-prototypes (w przypadku, gdy mamy mieszane zmienne numeryczne i kategoryczne). 🙂