Algoritmi di clustering - Algoritmo di spostamento medio

Introduzione all'algoritmo di spostamento della media

Come discusso in precedenza, è un altro potente algoritmo di clustering utilizzato nell'apprendimento non supervisionato. A differenza del clustering K-means, non fa alcuna ipotesi; quindi è un algoritmo non parametrico.

L'algoritmo di spostamento medio assegna fondamentalmente i punti dati ai cluster in modo iterativo spostando i punti verso la più alta densità di punti dati, cioè il centroide del cluster.

La differenza tra l'algoritmo K-Means e Mean-Shift è che in seguito non è necessario specificare il numero di cluster in anticipo perché il numero di cluster sarà determinato dall'algoritmo rispetto ai dati.

Lavorare con l'algoritmo di spostamento medio

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

  • Step 1 - Innanzitutto, inizia con i punti dati assegnati a un proprio cluster.

  • Step 2 - Successivamente, questo algoritmo calcolerà i centroidi.

  • Step 3 - In questo passaggio, verrà aggiornata la posizione dei nuovi centroidi.

  • Step 4 - Ora, il processo verrà iterato e spostato nella regione a maggiore densità.

  • Step 5 - Alla fine, verrà fermato una volta che i centroidi raggiungeranno una posizione da cui non può spostarsi ulteriormente.

Implementazione in Python

È un semplice esempio per capire come funziona l'algoritmo Mean-Shift. In questo esempio, genereremo prima un set di dati 2D contenente 4 diversi blob e successivamente applicheremo l'algoritmo Mean-Shift per vedere il risultato.

%matplotlib inline
import numpy as np
from sklearn.cluster import MeanShift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets.samples_generator import make_blobs
centers = [[3,3,3],[4,5,5],[3,10,10]]
X, _ = make_blobs(n_samples = 700, centers = centers, cluster_std = 0.5)
plt.scatter(X[:,0],X[:,1])
plt.show()
ms = MeanShift()
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_
print(cluster_centers)
n_clusters_ = len(np.unique(labels))
print("Estimated clusters:", n_clusters_)
colors = 10*['r.','g.','b.','c.','k.','y.','m.']
for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize = 3)
plt.scatter(cluster_centers[:,0],cluster_centers[:,1],
    marker=".",color='k', s=20, linewidths = 5, zorder=10)
plt.show()

Produzione

[[ 2.98462798 9.9733794 10.02629344]
[ 3.94758484 4.99122771 4.99349433]
[ 3.00788996 3.03851268 2.99183033]]
Estimated clusters: 3

Vantaggi e svantaggi

Vantaggi

Di seguito sono riportati alcuni vantaggi dell'algoritmo di clustering Mean-Shift:

  • Non è necessario fare alcuna ipotesi di modello come nei mezzi K o nella miscela gaussiana.

  • Può anche modellare i cluster complessi che hanno una forma non convessa.

  • Ha bisogno solo di un parametro denominato larghezza di banda che determina automaticamente il numero di cluster.

  • Non c'è problema di minimi locali come in K-means.

  • Nessun problema generato da valori anomali.

Svantaggi

Di seguito sono riportati alcuni svantaggi dell'algoritmo di clustering Mean-Shift:

L'algoritmo di spostamento medio non funziona bene in caso di dimensioni elevate, dove il numero di cluster cambia bruscamente.

  • Non abbiamo alcun controllo diretto sul numero di cluster, ma in alcune applicazioni abbiamo bisogno di un numero specifico di cluster.

  • Non può distinguere tra modalità significative e prive di significato.