Algorithmes de clustering - Algorithme de décalage moyen

Introduction à l'algorithme de décalage moyen

Comme indiqué précédemment, il s'agit d'un autre algorithme de clustering puissant utilisé dans l'apprentissage non supervisé. Contrairement au clustering K-means, il ne fait aucune hypothèse; c'est donc un algorithme non paramétrique.

L'algorithme de décalage moyen attribue essentiellement les points de données aux clusters de manière itérative en décalant les points vers la densité de points de données la plus élevée, c'est-à-dire le centre de gravité du cluster.

La différence entre l'algorithme K-Means et Mean-Shift est que plus tard, il n'est pas nécessaire de spécifier le nombre de clusters à l'avance car le nombre de clusters sera déterminé par l'algorithme avec les données.

Fonctionnement de l'algorithme de décalage moyen

Nous pouvons comprendre le fonctionnement de l'algorithme de clustering Mean-Shift à l'aide des étapes suivantes -

Step 1 - Commencez par les points de données affectés à leur propre cluster.
Step 2 - Ensuite, cet algorithme calculera les centroïdes.
Step 3 - Dans cette étape, l'emplacement des nouveaux centres de gravité sera mis à jour.
Step 4 - Maintenant, le processus sera itéré et déplacé vers la région de densité plus élevée.
Step 5 - Enfin, il sera arrêté une fois que les centres de gravité atteindront une position d'où il ne peut plus bouger.

Implémentation en Python

C'est un exemple simple pour comprendre le fonctionnement de l'algorithme Mean-Shift. Dans cet exemple, nous allons d'abord générer un jeu de données 2D contenant 4 blobs différents, puis appliquer l'algorithme Mean-Shift pour voir le résultat.

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

Production

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

Avantages et inconvénients

Avantages

Voici quelques avantages de l'algorithme de clustering Mean-Shift -

Il n'est pas nécessaire de faire une hypothèse de modèle comme dans K-means ou mélange gaussien.
Il peut également modéliser les clusters complexes qui ont une forme non convexe.
Il n'a besoin que d'un paramètre nommé bande passante qui détermine automatiquement le nombre de clusters.
Il n'y a pas de problème de minima locaux comme dans K-means.
Aucun problème généré par les valeurs aberrantes.

Désavantages

Voici quelques inconvénients de l'algorithme de clustering Mean-Shift -

L'algorithme de décalage moyen ne fonctionne pas bien en cas de dimension élevée, où le nombre de clusters change brusquement.

Nous n'avons aucun contrôle direct sur le nombre de clusters, mais dans certaines applications, nous avons besoin d'un nombre spécifique de clusters.
Il ne peut pas faire la différence entre les modes significatifs et dénués de sens.