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

27 kwietnia 2019 Mateusz Grzyb grupowanie 0

grupowanie, klastrowanie, analiza skupień, segmentacja, k-średnich, k-means, aglorytmy klasteryzacyjne

W pierwszym wpisie na temat grupowania z użyciem algorytmów iteracyjno-optymalizacyjnych skupiłem się na omówieniu podstawowych pojęć i teoretycznym wprowadzeniu. Dziś kolej na część praktyczną. Zapraszam! 🙂

Z tego artykułu dowiesz się: 1. Jak wykonać grupowanie z użyciem k-średnich? 2. Jakie biblioteki wspierają grupowanie metodą k-średnich? 3. O czym należy pamiętać, przeprowadzając proces grupowania tym algorytmem?

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, użyję kilku różnych bibliotek (tych bardziej i mniej znanych) i porównam wynik działania k-średnich z algorytmem grupowania hierarchicznego omawianego w jednym z poprzednich wpisów. Nie przedłużając, wczytajmy zatem biblioteki, zbiór i zaczynajmy! 🙂

1. Wczytanie podstawowych bibliotek.

In [1]:
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

Będziemy operować na dosyć "szerokim" zbiorze, dlatego zmieniam liczbę wyświetlanych kolumn przez bibliotekę Pandas na 30.

In [2]:
pd.options.display.max_columns = 30

2. Wygenerowanie zbioru.

Uczę się na błędach. Tak, przyznaję: ostatni zbiór po szeregu przekształceń i redukcji wymiarów nie wyglądał najlepiej. Ciężko było gołym okiem wnioskować o optymalnej liczbie grup. W tym wpisie posłużę się zatem sztucznie wygenerowanym zbiorem, który będzie zdecydowanie łatwiejszy w analizie dla ludzkiego oka. 🙂

In [3]:
X, y_true = make_blobs(n_samples=1000, centers=3, cluster_std=0.99, random_state=3042019)
df = pd.DataFrame(X, columns = ['f1', 'f2'])
In [4]:
df.head()
Out[4]:
f1 f2
0 -2.059805 -3.100144
1 -1.438699 -2.771644
2 -1.542172 -2.538683
3 -3.523410 3.810432
4 0.182640 -3.555730
In [5]:
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, scatter_kws={"color": "#eb6c6a"}).set(title = 'Wykres punktowy zbioru')
plt.show()

3. K-średnich - biblioteka sklearn.

Wczytuję implementację k-średnich z biblioteki sklearn.

In [6]:
from sklearn.cluster import KMeans
In [7]:
kmeans = KMeans(n_clusters=3)
kmeans.fit(df)
y_kmeans = kmeans.predict(df)
In [8]:
df['sklearn_cluster'] = y_kmeans
sklearn_centers = kmeans.cluster_centers_
In [9]:
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'sklearn_cluster', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup')
plt.scatter(sklearn_centers[:, 0], sklearn_centers[:, 1], c='black', s=100, alpha=0.5)
plt.show()

4. K-średnich - biblioteka SciPy.

In [10]:
from scipy.cluster.vq import kmeans, vq
In [11]:
scipy_centers,_ = kmeans(df,3)
idx,_ = vq(df,scipy_centers)
In [12]:
df['scipy_cluster'] = idx
In [13]:
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'scipy_cluster', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup')
plt.scatter(scipy_centers[:, 0], scipy_centers[:, 1], c='black', s=100, alpha=0.5)
plt.show()

5. K-średnich - biblioteka PyClustering.

PyClustering to biblioteka w pełni dedykowana problemowi segmentacji. Znajduje się w niej wiele implementacji najpopularniejszych algorytmów, mechanizmy do badania jakości procesu segmentacji i niemal wszystko, co jest przydatne podczas grupowania.

Sam proces budowania modelu grupującego jest nieco inny niż w przypadku sklearn. Dla mnie jest to mały minus tej biblioteki.

In [14]:
from pyclustering.cluster.kmeans import kmeans
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
In [15]:
initial_centers = kmeans_plusplus_initializer(df[['f1', 'f2']].values, 3).initialize()
kmeans_instance = kmeans(df[['f1', 'f2']].values, initial_centers)
In [16]:
kmeans_instance.process()
pyclustering_clusters = kmeans_instance.get_clusters()
pyclustering_centers = kmeans_instance.get_centers()
In [17]:
for x in range(0,len(pyclustering_clusters)):
    df.loc[df.index.isin(pyclustering_clusters[x]),'pyclustering_cluster'] = str(x)
In [18]:
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'pyclustering_cluster', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup')
plt.scatter([i[0] for i in pyclustering_centers], [i[1] for i in pyclustering_centers], c='black', s=100, alpha=0.5)
plt.show()

6. Porównanie wyników uzyskanych przez różne biblioteki.

Najprostszym sposobem na porównanie jakości działania trzech różnych bibliotek jest sprawdzenie współrzędnych centroidów.

In [19]:
sklearn_centers
Out[19]:
array([[-6.63225624, -1.04642352],
       [-1.52207719, -2.831294  ],
       [-4.62284578,  2.97166245]])
In [20]:
scipy_centers
Out[20]:
array([[-6.63225624, -1.04642352,  0.        ],
       [-1.52207719, -2.831294  ,  1.        ],
       [-4.62284578,  2.97166245,  2.        ]])
In [21]:
np.round(pyclustering_centers, 8)
Out[21]:
array([[-1.52207719, -2.831294  ],
       [-4.62284578,  2.97166245],
       [-6.63225624, -1.04642352]])

Wyniki są identyczne. Celowo pomijam tu aspekt wydajnościowy, który w przypadku algorytmu k-średnich rzadko jest problemem - algorytm jest dosyć wydajny.

7. K-średnich vs grupowanie hierarchiczne.

Porównajmy jeszcze na różnych zbiorach działanie algorytmu k-średnich i algorytmu hierarchicznego, aglomeracyjnego. By zachować spójność, użyję biblioteki sklearn.

7.1. Kształt kolisty.

Algorytm aglomeracyjny.

In [22]:
from sklearn.cluster import AgglomerativeClustering
In [23]:
agglomerative = AgglomerativeClustering(linkage='ward', affinity='euclidean', n_clusters=3).fit(df[['f1', 'f2']])
df['agglomerative_ward'] = agglomerative.labels_
In [24]:
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.

In [25]:
sns.lmplot(data=df, x='f1', y='f2', fit_reg=False, hue = 'sklearn_cluster', palette = ['#eb6c6a', '#6aeb6c', '#6c6aeb']).set(title='Wizualizacja grup\n algorytm k-średnich')
plt.show()

Na pierwszy rzut oka jest bardzo podobnie. Są oczywiście subtelne, które docyć 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.

In [26]:
from sklearn.metrics import silhouette_score
In [27]:
silhouette_score(df[['f1', 'f2']], df['agglomerative_ward']).round(4)
Out[27]:
0.6233
In [28]:
silhouette_score(df[['f1', 'f2']], df['sklearn_cluster']).round(4)
Out[28]:
0.6291

I tu widać niewielką różnicę: 0.623 vs 0.639 na korzyść algorytmu k-średnich. Dodam, że dla algorytmu hierarchicznego testowałem różne hipotezy i najlepiej wypadała metoda łączenia grup z użyciem kryterium Warda.

7.2. Kształt księżyca.
In [29]:
x, y = make_moons(1000, noise=.05, random_state=0)
df_moons = pd.DataFrame(x, columns = ['f1','f2'])

Algorytm k-średnich.

In [30]:
kmeans = KMeans(n_clusters=2)
kmeans.fit(df_moons)
y_kmeans = kmeans.predict(df_moons)
In [31]:
df_moons['k_means'] = y_kmeans
centers = kmeans.cluster_centers_
In [32]:
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.

In [33]:
agglomerative = AgglomerativeClustering(n_clusters=2, linkage='ward')
In [34]:
y_pred = agglomerative.fit_predict(df_moons[['f1','f2']])
df_moons['agglomerative_ward'] = y_pred
In [35]:
sns.lmplot(data=df_moons, x='f1', y='f2', fit_reg=False, hue = 'agglomerative_ward', palette = ['#eb6c6a', '#6aeb6c']).set(title='Wizualizacja grup\n algorytm aglomeracyjny')
plt.show()

Sprawdźmy wartość miary silhouette dla obu przykładów.

In [36]:
print("Grupowanie aglomeracyjne: {}".format(silhouette_score(df_moons[['f1', 'f2']], df_moons['agglomerative_ward']).round(4)))

Grupowanie aglomeracyjne: 0.4392
In [37]:
print("Grupowanie k-średnich: {}".format(silhouette_score(df_moons[['f1', 'f2']], df_moons['k_means']).round(4)))

Grupowanie k-średnich: 0.4897

Można powiedzieć, że w tym przypadku również wygrał algorytm k-średnich. Sprawdźmy jednak co się stanie, jeśli zmienimy kryterium łączenia grup w algorytmie hierarchicznym.

In [38]:
agglomerative_single = AgglomerativeClustering(n_clusters=2, linkage='single')
y_pred = agglomerative_single.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()

Mamy w zasadzie idealny podział. 🙂 Ten przykład pokazuje, jak wiele zależy od doboru odpowiedniego algorytmu i jego parametrów.

7.3. Kształt pierścienia.
In [39]:
X, _ = make_circles(n_samples=1000, random_state=0)
df_circles = pd.DataFrame(X, columns = ['f1', 'f2'])

Algorytm k-średnich.

In [40]:
kmeans = KMeans(n_clusters=2)
kmeans.fit(df_circles)
Out[40]:
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
    n_clusters=2, n_init=10, n_jobs=None, precompute_distances='auto',
    random_state=None, tol=0.0001, verbose=0)
In [41]:
y_kmeans = kmeans.predict(df_circles)
df_circles['k_means'] = y_kmeans
centers = kmeans.cluster_centers_
In [42]:
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.

In [43]:
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.

In [44]:
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()

8. Podsumowanie

Algorytm k-średnich ma wiele plusów. Jest bardzo szybki, intuicyjny i czasem uzyskuje lepsze rezultaty niż dużo wolniejsze grupowanie hierarchiczne. Należy jednak pamiętać, że decydującą rolę odgrywają tu dane. Są przypadki, w których k-średnich sprawdzi się nieco lepiej niż algorytm hierarchiczny. Kiedy indziej uwidoczni się jego "naiwność" oparta na niewłaściwych dla rozpatrywanego przypadku założeniach (wypukłość grup) i uzyskany rezultat będzie mizerny.

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 k-średnich? Proszę, podziel się nimi w komentarzu pod wpisem.

Linki:

photo: Pixabay.com (manfredrichter)

PODOBAŁ CI SIĘ TEN ARTYKUŁ?

Jeśli tak, to zarejestruj się, by otrzymywać informacje o nowych wpisach.
Dodatkowo w prezencie wyślę Ci bezpłatny poradnik :-)

Podobne wpisy:

grupowanie, klastrowanie, analiza skupień, segmentacja, k-średnich, k-means, aglorytmy klasteryzacyjneGrupowanie iteracyjno-optymalizacyjne. Algorytm k-średnich – teoria segmentacja, grupowanie gęstościowe, dbscan, hdbscanGrupowanie gęstościowe. Algorytm DBSCAN – praktyka grupowanie gęstościowe, dbscan, segmentacja grupowanie, density basedGrupowanie gęstościowe. Algorytm DBSCAN – teoria analiza skupień, grupowanie, klasteryzacja, klastry, klastrowanie, grupowanieGrupowanie hierarchiczne – praktyka

Bądź pierwszy, który skomentuje ten wpis!

Dodaj komentarz

Twój adres email nie zostanie opublikowany.


*