Algorytmy grupowania - Algorytm K-średnich

Wprowadzenie do algorytmu K-średnich

Algorytm grupowania metodą K-średnich oblicza centroidy i wykonuje iteracje, aż znajdziemy optymalną centroidę. Zakłada, że liczba klastrów jest już znana. Nazywa się to równieżflat clusteringalgorytm. Liczba klastrów zidentyfikowanych na podstawie danych przez algorytm jest reprezentowana przez „K” w K-średnich.

W tym algorytmie punkty danych są przypisywane do klastra w taki sposób, że suma kwadratu odległości między punktami danych i centroidą byłaby minimalna. Należy rozumieć, że mniejsza zmienność w obrębie klastrów doprowadzi do większej liczby podobnych punktów danych w tym samym klastrze.

Działanie algorytmu K-średnich

Możemy zrozumieć działanie algorytmu grupowania K-Means za pomocą następujących kroków -

Step 1 - Najpierw musimy określić liczbę klastrów, K, które mają zostać wygenerowane przez ten algorytm.
Step 2- Następnie losowo wybierz K punktów danych i przypisz każdy punkt danych do klastra. W prostych słowach sklasyfikuj dane na podstawie liczby punktów danych.
Step 3 - Teraz obliczy centroidy klastra.
Step 4 - Następnie kontynuuj iterację, aż znajdziemy optymalną centroidę, czyli przypisanie punktów danych do klastrów, które już się nie zmieniają -

4.1 - Najpierw zostanie obliczona suma kwadratów odległości między punktami danych i centroidami.

4.2 - Teraz musimy przypisać każdy punkt danych do klastra, który jest bliżej niż inny klaster (centroid).

4.3 - Na koniec obliczyć centroidy dla klastrów, biorąc średnią ze wszystkich punktów danych tego klastra.

K-oznacza następuje Expectation-Maximizationpodejście do rozwiązania problemu. Krok oczekiwania jest używany do przypisywania punktów danych do najbliższego klastra, a krok maksymalizacji jest używany do obliczania centroidu każdego klastra.

Pracując z algorytmem K-średnich musimy zadbać o następujące rzeczy -

Podczas pracy z algorytmami klastrowania, w tym K-średnich, zaleca się standaryzację danych, ponieważ takie algorytmy wykorzystują pomiar na podstawie odległości do określenia podobieństwa między punktami danych.
Ze względu na iteracyjny charakter K-średnich i losową inicjalizację centroidów, K-średnie mogą trzymać się lokalnego optimum i mogą nie zbiegać się z globalnymi optimum. Dlatego zaleca się stosowanie różnych inicjalizacji centroidów.

Implementacja w Pythonie

Poniższe dwa przykłady implementacji algorytmu grupowania K-średnich pomogą nam w lepszym zrozumieniu:

Przykład 1

To prosty przykład, aby zrozumieć, jak działa k-średnich. W tym przykładzie najpierw wygenerujemy zestaw danych 2D zawierający 4 różne obiekty blob, a następnie zastosujemy algorytm k-średnich, aby zobaczyć wynik.

Najpierw zaczniemy od zaimportowania niezbędnych pakietów -

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeans

Poniższy kod wygeneruje 2D, zawierający cztery obiekty blob -

from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=400, centers=4, cluster_std=0.60, random_state=0)

Następnie poniższy kod pomoże nam zwizualizować zbiór danych -

plt.scatter(X[:, 0], X[:, 1], s=20);
plt.show()

Następnie utwórz obiekt KMean wraz z podaniem liczby klastrów, wytrenuj model i wykonaj prognozę w następujący sposób -

kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)

Teraz za pomocą następującego kodu możemy wykreślić i wizualizować centra klastra wybrane przez estymator Pythona k-średnich -

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=20, cmap='summer')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='blue', s=100, alpha=0.9);
plt.show()

Przykład 2

Przejdźmy do innego przykładu, w którym zastosujemy grupowanie K-średnich na zbiorze danych zawierających proste cyfry. K-mean spróbuje zidentyfikować podobne cyfry bez korzystania z oryginalnych informacji na etykiecie.

Najpierw zaczniemy od zaimportowania niezbędnych pakietów -

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeans

Następnie załaduj cyfrowy zestaw danych ze sklearn i utwórz z niego obiekt. Możemy również znaleźć liczbę wierszy i kolumn w tym zbiorze danych w następujący sposób -

from sklearn.datasets import load_digits
digits = load_digits()
digits.data.shape

Wynik

(1797, 64)

Powyższe dane wyjściowe pokazują, że ten zestaw danych zawiera 1797 próbek z 64 funkcjami.

Możemy przeprowadzić grupowanie, tak jak w przykładzie 1 powyżej -

kmeans = KMeans(n_clusters=10, random_state=0)
clusters = kmeans.fit_predict(digits.data)
kmeans.cluster_centers_.shape

Wynik

(10, 64)

Powyższe dane wyjściowe pokazują, że K-średnie utworzyły 10 klastrów z 64 cechami.

fig, ax = plt.subplots(2, 5, figsize=(8, 3))
centers = kmeans.cluster_centers_.reshape(10, 8, 8)
for axi, center in zip(ax.flat, centers):
   axi.set(xticks=[], yticks=[])
   axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)

Wynik

Jako wynik otrzymamy następujący obraz przedstawiający centra klastrów wyuczone za pomocą k-średnich.

Następujące wiersze kodu będą dopasowywać wyuczone etykiety klastrów do prawdziwych etykiet w nich znalezionych -

from scipy.stats import mode
labels = np.zeros_like(clusters)
for i in range(10):
   mask = (clusters == i)
   labels[mask] = mode(digits.target[mask])[0]

Następnie możemy sprawdzić dokładność w następujący sposób -

from sklearn.metrics import accuracy_score
accuracy_score(digits.target, labels)

Wynik

0.7935447968836951

Powyższe dane wyjściowe pokazują, że dokładność wynosi około 80%.

Zalety i wady

Zalety

Poniżej przedstawiono niektóre zalety algorytmów klastrowania K-średnich -

Jest bardzo łatwy do zrozumienia i wdrożenia.
Gdybyśmy mieli wtedy dużą liczbę zmiennych, K-średnie byłyby szybsze niż grupowanie hierarchiczne.
Po ponownym obliczeniu centroid instancja może zmienić klaster.
Węższe klastry są tworzone za pomocą K-średnich w porównaniu z grupowaniem hierarchicznym.

Niedogodności

Poniżej przedstawiono niektóre wady algorytmów klastrowania K-średnich -

Nieco trudno jest przewidzieć liczbę klastrów, czyli wartość k.
Na wynik silnie wpływają początkowe dane wejściowe, takie jak liczba klastrów (wartość k).
Kolejność danych będzie miała duży wpływ na ostateczny wynik.
Jest bardzo wrażliwy na przeskalowanie. Jeśli przeskalujemy nasze dane za pomocą normalizacji lub standaryzacji, wynik całkowicie się zmieni.
Nie jest dobrze wykonywać zadania związane z grupowaniem, jeśli klastry mają skomplikowany kształt geometryczny.

Zastosowania algorytmu grupowania metodą K-średnich

Główne cele analizy skupień to -

Aby uzyskać sensowną intuicję z danych, z którymi pracujemy.
Następnie przewiduj klastry, w których zostaną zbudowane różne modele dla różnych podgrup.

Aby zrealizować powyższe cele, grupowanie K-średnich działa wystarczająco dobrze. Może być używany w następujących aplikacjach -

Segmentacja rynku
Grupowanie dokumentów
Segmentacja obrazu
Kompresja obrazu
Segmentacja klientów
Analiza trendu na danych dynamicznych