W poprzednim wpisie na temat grupowania gęstościowego skupiłem się na omówieniu podstawowych pojęć i teoretycznym wprowadzeniu. Dziś kolej na część praktyczną. Zapraszam! 🙂
Mam nadzieję, że część teoretyczna była dla Ciebie w miarę przystępna i jasna. W tym wpisie przechodzę do części praktycznej. Wykonam grupowanie z użyciem DBSCAN i kilku "konkurencyjnych" algorytmów i porównam wyniki. Nie przedłużając, wczytajmy zatem biblioteki, zbiór i zaczynajmy! 🙂
1. Wczytanie podstawowych bibliotek.¶
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
import seaborn as sns
from sklearn.datasets.samples_generator import make_blobs, make_moons, make_circles
We wszystkich opisywanych w tym wpisie przykładach posługuję się sztucznie wygenerowanymi i dosyć specyficznymi zbiorami. Uwypuklają one wady i zalety różnych algorytmów znacznie lepiej niż "rzeczywiste" zbiory. Dodatkowo całość wizualizuję na płaszczyźnie dwuwymiarowej dla jeszcze lepszej czytelności wyników.
2. DBSCAN vs k-średnich vs grupowanie hierarchiczne.¶
Porównajmy na różnych zbiorach działanie algorytmu DBSCAN, k-średnich i algorytmu hierarchicznego (aglomeracyjnego). By zachować spójność, użyję biblioteki sklearn.
2.1. Kształt kolisty.¶
X, y_true = make_blobs(n_samples=1000, centers=3, 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 punktowy zbioru')
plt.show()
Algorytm aglomeracyjny.
from sklearn.cluster import AgglomerativeClustering
agglomerative = AgglomerativeClustering(linkage='ward', affinity='euclidean', n_clusters=3).fit(df[['f1', 'f2']])
df['agglomerative_ward'] = agglomerative.labels_
sns.lmplot('f1', 'f2', data = df, hue = 'agglomerative_ward', fit_reg=False, palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup\n algorytm aglomeracyjny')
plt.show()
Algorytm k-średnich.
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=3)
kmeans.fit(df[['f1', 'f2']])
df['k_means'] = kmeans.predict(df[['f1', 'f2']])
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'k_means', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup\n algorytm k-średnich')
plt.show()
Algorytm DBSCAN.
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=8)
dbscan.fit(df[['f1', 'f2']])
df['dbscan'] = dbscan.labels_
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'dbscan', palette = ['#999999', '#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup\n algorytm DBSCAN')
plt.show()
Na pierwszy rzut oka jest bardzo podobnie (bo zbiór jest wybitnie prosty do grupowania). Są oczywiście subtelne, które dosyć ciężko wychwycić wzrokiem. Sprawdźmy zatem miarę silhouette, która często jest brana pod uwagę przy ocenie procesu grupowania. Szerzej postara się ją omówić w jednym z kolejnych wpisów. Z rzeczy istotnych na ten moment warto wiedzieć, że przyjmuje ona wartości z przedziału [-1, 1], gdzie wyższa wartość, to lepsze grupowanie.
from sklearn.metrics import silhouette_score
silhouette_score(df[['f1', 'f2']], df['agglomerative_ward']).round(4)
silhouette_score(df[['f1', 'f2']], df['k_means']).round(4)
silhouette_score(df[df.dbscan != -1][['f1', 'f2']], df[df.dbscan != -1]['dbscan']).round(4)
Tu widoczna jest niewielka różnica: 0.623 vs 0.629 vs 0.665 na korzyść algorytmu DBSCAN. Kilka dodatkowych uwag:
- dla algorytmu hierarchicznego testowałem różne hipotezy i najlepiej wypadała metoda łączenia grup z użyciem kryterium Warda,
- dla algorytmu DBSCAN usunąłem obserwacje oznaczone jako nietypowe,
- dla algorytmu DBSCAN dobrałem parametry metodą "ekspercką", tak by powstały 3 grupy.
2.2. Kształt księżyca.¶
x, y = make_moons(1000, noise=.05, random_state=0)
df_moons = pd.DataFrame(x, columns = ['f1','f2'])
Algorytm k-średnich.
kmeans = KMeans(n_clusters=2)
kmeans.fit(df_moons)
y_kmeans = kmeans.predict(df_moons)
df_moons['k_means'] = y_kmeans
centers = kmeans.cluster_centers_
sns.lmplot(data=df_moons, x='f1', y='f2', fit_reg=False, hue = 'k_means', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm k-średnich')
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=100, alpha=0.5)
plt.show()
Algorytm aglomeracyjny.
agglomerative = AgglomerativeClustering(n_clusters=2, linkage='single')
y_pred = agglomerative.fit_predict(df_moons[['f1','f2']])
df_moons['agglomerative_single'] = y_pred
sns.lmplot(data=df_moons, x='f1', y='f2', fit_reg=False, hue = 'agglomerative_single', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm aglomeracyjny')
plt.show()
Algorytm DBSCAN.
dbscan = DBSCAN(eps=0.1, min_samples=8)
dbscan.fit(df_moons[['f1', 'f2']])
df_moons['dbscan'] = dbscan.labels_
sns.lmplot(data=df_moons, x='f1', y='f2', fit_reg=False, hue = 'dbscan', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm DBSCAN')
plt.show()
Sprawdźmy wartość miary silhouette powyższych przykładów.
print("Grupowanie aglomeracyjne: {}".format(silhouette_score(df_moons[['f1', 'f2']], df_moons['agglomerative_single']).round(4)))
print("Grupowanie k-średnich: {}".format(silhouette_score(df_moons[['f1', 'f2']], df_moons['k_means']).round(4)))
print("Grupowanie DBSCAN: {}".format(silhouette_score(df_moons[['f1', 'f2']], df_moons['dbscan']).round(4)))
W przypadku DBSCAN i grupowania algomeracyjnego mamy w zasadzie idealny podział, czego nie można powiedzieć o algorytmie k-średnich. 😉 Co ciekawe, miara silhouette wskazuje, że k-średnich najlepiej poradził sobie z problemem. Ten przykład pokazuje zatem, że w problemie grupowania nigdy nie powinniśmy w pełni polegać na statystycznych miarach jakości. Nic nie zastąpi wizualizacji i analizy opisowej uzyskanych wyników.
7.3. Kształt pierścienia.¶
X, _ = make_circles(n_samples=1000, random_state=0)
df_circles = pd.DataFrame(X, columns = ['f1', 'f2'])
Algorytm k-średnich.
kmeans = KMeans(n_clusters=2)
kmeans.fit(df_circles)
y_kmeans = kmeans.predict(df_circles)
df_circles['k_means'] = y_kmeans
centers = kmeans.cluster_centers_
sns.lmplot(data=df_circles, x='f1', y='f2', fit_reg=False, hue = 'k_means', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm k-średnich')
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=100, alpha=0.5)
plt.show()
Algorytm aglomeracyjny - metoda połączenia Warda.
model = AgglomerativeClustering(n_clusters=2, linkage='ward')
y_pred = model.fit_predict(df_circles[['f1','f2']])
df_circles['agglomerative_ward'] = y_pred
sns.lmplot(data=df_circles, x='f1', y='f2', fit_reg=False, hue = 'agglomerative_ward', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm aglomeracyjny')
plt.show()
Algorytm aglomeracyjny - metoda pojedynczego połączenia.
model = AgglomerativeClustering(n_clusters=2, linkage='single')
y_pred = model.fit_predict(df_circles[['f1','f2']])
df_circles['agglomerative_single'] = y_pred
sns.lmplot(data=df_circles, x='f1', y='f2', fit_reg=False, hue = 'agglomerative_single', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm aglomeracyjny')
plt.show()
Algorytm DBSCAN.
dbscan = DBSCAN(eps=0.1, min_samples=8)
dbscan.fit(df_circles[['f1', 'f2']])
df_circles['dbscan'] = dbscan.labels_
sns.lmplot(data=df_circles, x='f1', y='f2', fit_reg=False, hue = 'dbscan', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm DBSCAN')
plt.show()
Sprawdźmy jeszcze wartość miary silhouette powyższych przykładów.
print("Grupowanie aglomeracyjne (single): {}".format(silhouette_score(df_circles[['f1', 'f2']], df_circles['agglomerative_single']).round(4)))
print("Grupowanie aglomeracyjne (Ward): {}".format(silhouette_score(df_circles[['f1', 'f2']], df_circles['agglomerative_ward']).round(4)))
print("Grupowanie k-średnich: {}".format(silhouette_score(df_circles[['f1', 'f2']], df_circles['k_means']).round(4)))
print("Grupowanie DBSCAN: {}".format(silhouette_score(df_circles[['f1', 'f2']], df_circles['dbscan']).round(4)))
Tu podobnie jak w przypadku obserwacji układających się w kształt księżyca najlepiej poradziły sobie DBSCAN i metoda grupowania aglomeracyjnego (single).
8. Podsumowanie¶
Mam nadzieję, że powyższe przykłady dały Ci pogląd na wady i zalety algorytmu DBSCAN. Jest bardzo szybki, dosyć intuicyjny i w zdecydowanej większości przypadków uzyskuje lepsze rezultaty niż algorytmy grupowania hierarchiczne i iteracyjno-optymalizacyjnego (k-średnich).
Należy jednak pamiętać, że decydującą rolę odgrywają tu dane. Są przypadki, w których k-średnich i algorytm grupowania hierarchicznego sprawdzą się nieco lepiej niż DBSAN.
Jak zatem wybrać ten odpowiedni algorytm grupujący? W skrócie: poznaj ograniczenia (zasoby sprzętowe, czas, wymagania biznesowe), zbadaj zbiór, określ liczbę grup, wykonać testowe grupowanie i wizualizację grup. Jeśli ciągle nie jesteś pewien wyboru, to posłuż się odpowiednią metryką pomiaru jakości grupowania.
Zarówno o doborze metryki pomiaru jakości grupowania, jak i o wyborze odpowiedniego algorytmu grupującego będę pisać w kolejnych artykułach. 🙂
A jakie Ty masz doświadczenia z algorytmem DBSCAN? Proszę, podziel się nimi w komentarzu pod wpisem.
Dodaj komentarz