Algoritmi di clustering - Algoritmo K-means

Introduzione all'algoritmo K-Means

L'algoritmo di clustering K-means calcola i centroidi e itera finché non trova il centroide ottimale. Si presume che il numero di cluster sia già noto. È anche chiamatoflat clusteringalgoritmo. Il numero di cluster identificati dai dati mediante algoritmo è rappresentato da "K" in K-mean.

In questo algoritmo, i punti dati vengono assegnati a un cluster in modo tale che la somma della distanza al quadrato tra i punti dati e il centroide sia minima. È chiaro che una minore variazione all'interno dei cluster porterà a punti dati più simili all'interno dello stesso cluster.

Utilizzo dell'algoritmo K-Means

Possiamo comprendere il funzionamento dell'algoritmo di clustering K-Means con l'aiuto dei seguenti passaggi:

Step 1 - Innanzitutto, dobbiamo specificare il numero di cluster, K, che devono essere generati da questo algoritmo.
Step 2- Quindi, seleziona casualmente K punti dati e assegna ogni punto dati a un cluster. In parole semplici, classificare i dati in base al numero di punti dati.
Step 3 - Ora calcolerà i centroidi del cluster.
Step 4 - Successivamente, continua a ripetere quanto segue finché non troviamo il centroide ottimale che è l'assegnazione dei punti dati ai cluster che non cambiano più -

4.1 - In primo luogo, verrà calcolata la somma della distanza al quadrato tra i punti dati e i centroidi.

4.2 - Ora, dobbiamo assegnare ogni punto dati al cluster più vicino di altri cluster (centroide).

4.3 - Infine calcola i centroidi per i cluster prendendo la media di tutti i punti dati di quel cluster.

Segue K-significa Expectation-Maximizationapproccio per risolvere il problema. Il passaggio Expectation viene utilizzato per assegnare i punti dati al cluster più vicino e il passaggio Maximization viene utilizzato per calcolare il centroide di ciascun cluster.

Mentre lavoriamo con l'algoritmo K-means dobbiamo occuparci delle seguenti cose:

Mentre si lavora con algoritmi di clustering inclusi K-Means, si consiglia di standardizzare i dati perché tali algoritmi utilizzano la misurazione basata sulla distanza per determinare la somiglianza tra i punti dati.
A causa della natura iterativa delle medie K e dell'inizializzazione casuale dei centroidi, le medie K possono rimanere in un ottimo locale e potrebbero non convergere all'ottimo globale. Questo è il motivo per cui si consiglia di utilizzare diverse inizializzazioni dei centroidi.

Implementazione in Python

I seguenti due esempi di implementazione dell'algoritmo di clustering K-Means ci aiuteranno a comprenderlo meglio:

Esempio 1

È un semplice esempio per capire come funziona k-means. In questo esempio, genereremo prima un set di dati 2D contenente 4 diversi blob, dopodiché applicheremo l'algoritmo k-means per vedere il risultato.

Innanzitutto, inizieremo importando i pacchetti necessari:

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

Il codice seguente genererà il 2D, contenente quattro 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)

Successivamente, il codice seguente ci aiuterà a visualizzare il set di dati:

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

Quindi, crea un oggetto di KMeans oltre a fornire il numero di cluster, addestra il modello ed esegui la previsione come segue:

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

Ora, con l'aiuto del codice seguente possiamo tracciare e visualizzare i centri del cluster selezionati dallo stimatore Python k-means -

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()

Esempio 2

Passiamo a un altro esempio in cui applicheremo il clustering K-means su set di dati a cifre semplici. K-means tenterà di identificare cifre simili senza utilizzare le informazioni sull'etichetta originale.

Innanzitutto, inizieremo importando i pacchetti necessari:

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

Quindi, carica il set di dati delle cifre da sklearn e creane un oggetto. Possiamo anche trovare il numero di righe e colonne in questo set di dati come segue:

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

Produzione

(1797, 64)

L'output sopra mostra che questo set di dati ha 1797 campioni con 64 funzionalità.

Possiamo eseguire il raggruppamento come abbiamo fatto nell'esempio 1 sopra -

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

Produzione

(10, 64)

L'output sopra mostra che K-means ha creato 10 cluster con 64 funzionalità.

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)

Produzione

Come output, otterremo la seguente immagine che mostra i centri dei cluster appresi con k-means.

Le seguenti righe di codice faranno corrispondere le etichette del cluster apprese con le vere etichette trovate in esse -

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]

Successivamente, possiamo verificare l'accuratezza come segue:

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

Produzione

0.7935447968836951

L'output sopra mostra che la precisione è di circa l'80%.

Vantaggi e svantaggi

Vantaggi

Di seguito sono riportati alcuni vantaggi degli algoritmi di clustering K-Means:

È molto facile da capire e implementare.
Se disponiamo di un numero elevato di variabili, K-means sarebbe più veloce del clustering gerarchico.
Durante il ricalcolo dei centroidi, un'istanza può modificare il cluster.
I cluster più stretti sono formati con K-means rispetto al clustering gerarchico.

Svantaggi

Di seguito sono riportati alcuni svantaggi degli algoritmi di clustering K-Means:

È un po 'difficile prevedere il numero di cluster, ovvero il valore di k.
L'output è fortemente influenzato dagli input iniziali come il numero di cluster (valore di k).
L'ordine dei dati avrà un forte impatto sull'output finale.
È molto sensibile al riscalaggio. Se riscaleremo i nostri dati mediante normalizzazione o standardizzazione, l'output cambierà completamente.
Non è utile eseguire un lavoro di raggruppamento se i cluster hanno una forma geometrica complicata.

Applicazioni dell'algoritmo di clustering K-Means

Gli obiettivi principali dell'analisi dei cluster sono:

Per ottenere un'intuizione significativa dai dati con cui stiamo lavorando.
Cluster-then-prevede dove verranno costruiti modelli diversi per sottogruppi diversi.

Per soddisfare gli obiettivi sopra menzionati, il clustering K-means sta funzionando abbastanza bene. Può essere utilizzato nelle seguenti applicazioni:

Segmentazione del mercato
Clustering dei documenti
Segmentazione delle immagini
Compressione dell'immagine
Segmentazione della clientela
Analisi dell'andamento sui dati dinamici