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