Algorithmes de clustering - Algorithme K-means

Introduction à l'algorithme K-Means

L'algorithme de clustering K-means calcule les centroïdes et les itère jusqu'à ce que nous trouvions le centroïde optimal. Il suppose que le nombre de clusters est déjà connu. Il est également appeléflat clusteringalgorithme. Le nombre de clusters identifiés à partir des données par algorithme est représenté par «K» dans K-means.

Dans cet algorithme, les points de données sont assignés à un cluster de telle manière que la somme de la distance au carré entre les points de données et le centre de gravité soit minimale. Il faut comprendre qu'une moindre variation au sein des clusters conduira à des points de données plus similaires au sein du même cluster.

Fonctionnement de l'algorithme K-Means

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

  • Step 1 - Tout d'abord, nous devons spécifier le nombre de clusters, K, à générer par cet algorithme.

  • Step 2- Ensuite, sélectionnez au hasard K points de données et attribuez chaque point de données à un cluster. En termes simples, classez les données en fonction du nombre de points de données.

  • Step 3 - Il va maintenant calculer les centres de gravité du cluster.

  • Step 4 - Ensuite, continuez à répéter ce qui suit jusqu'à ce que nous trouvions le centre de gravité optimal qui est l'affectation des points de données aux clusters qui ne changent plus -

4.1 - Premièrement, la somme de la distance au carré entre les points de données et les centres de gravité serait calculée.

4.2 - Maintenant, nous devons attribuer chaque point de données au cluster qui est plus proche que l'autre cluster (centroïde).

4.3 - Calculez enfin les centres de gravité des clusters en prenant la moyenne de tous les points de données de ce cluster.

K-means suit Expectation-Maximizationapproche pour résoudre le problème. L'étape d'attente est utilisée pour attribuer les points de données au cluster le plus proche et l'étape de maximisation est utilisée pour calculer le centre de gravité de chaque cluster.

Tout en travaillant avec l'algorithme K-means, nous devons prendre soin des choses suivantes -

  • Tout en travaillant avec des algorithmes de clustering comprenant des K-Means, il est recommandé de normaliser les données car ces algorithmes utilisent la mesure basée sur la distance pour déterminer la similitude entre les points de données.

  • En raison de la nature itérative des K-Means et de l'initialisation aléatoire des centres de gravité, les K-Means peuvent rester dans un optimum local et ne pas converger vers l'optimum global. C'est pourquoi il est recommandé d'utiliser différentes initialisations des centres de gravité.

Implémentation en Python

Les deux exemples suivants d'implémentation de l'algorithme de clustering K-Means nous aideront à mieux comprendre -

Exemple 1

C'est un exemple simple pour comprendre comment fonctionne k-means. 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 k-means pour voir le résultat.

Tout d'abord, nous allons commencer par importer les packages nécessaires -

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

Le code suivant générera le 2D, contenant quatre blobs -

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)

Ensuite, le code suivant nous aidera à visualiser l'ensemble de données -

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

Ensuite, créez un objet de KMeans en fournissant le nombre de clusters, entraînez le modèle et faites la prédiction comme suit -

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

Maintenant, avec l'aide du code suivant, nous pouvons tracer et visualiser les centres du cluster choisis par l'estimateur 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()

Exemple 2

Passons à un autre exemple dans lequel nous allons appliquer le clustering K-means sur un ensemble de données à chiffres simples. K-means essaiera d'identifier des chiffres similaires sans utiliser les informations d'étiquette d'origine.

Tout d'abord, nous allons commencer par importer les packages nécessaires -

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

Ensuite, chargez l'ensemble de données digitales de sklearn et créez-en un objet. Nous pouvons également trouver le nombre de lignes et de colonnes dans cet ensemble de données comme suit -

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

Production

(1797, 64)

La sortie ci-dessus montre que cet ensemble de données contient 1797 échantillons avec 64 fonctionnalités.

Nous pouvons effectuer le clustering comme nous l'avons fait dans l'exemple 1 ci-dessus -

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

Production

(10, 64)

La sortie ci-dessus montre que K-means a créé 10 clusters avec 64 fonctionnalités.

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)

Production

En sortie, nous obtiendrons l'image suivante montrant les centres de clusters appris par k-means.

Les lignes de code suivantes correspondent aux étiquettes de cluster apprises avec les vraies étiquettes qu'elles contiennent -

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]

Ensuite, nous pouvons vérifier l'exactitude comme suit -

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

Production

0.7935447968836951

La sortie ci-dessus montre que la précision est d'environ 80%.

Avantages et inconvénients

Avantages

Voici quelques avantages des algorithmes de clustering K-Means -

  • Il est très facile à comprendre et à mettre en œuvre.

  • Si nous avons un grand nombre de variables, les K-moyennes seraient plus rapides que le clustering hiérarchique.

  • Lors du recalcul des centres de gravité, une instance peut modifier le cluster.

  • Des clusters plus serrés sont formés avec des K-means par rapport au clustering hiérarchique.

Désavantages

Voici quelques inconvénients des algorithmes de clustering K-Means -

  • Il est un peu difficile de prévoir le nombre de clusters c'est-à-dire la valeur de k.

  • La sortie est fortement impactée par les entrées initiales comme le nombre de grappes (valeur de k).

  • L'ordre des données aura un fort impact sur le résultat final.

  • Il est très sensible au rééchelonnement. Si nous redimensionnons nos données au moyen de la normalisation ou de la standardisation, la sortie changera complètement.

  • Il n'est pas bon de faire un travail de clustering si les clusters ont une forme géométrique compliquée.

Applications de l'algorithme de clustering K-Means

Les principaux objectifs de l'analyse de cluster sont:

  • Pour obtenir une intuition significative à partir des données avec lesquelles nous travaillons.

  • Cluster-puis-prédire où différents modèles seront construits pour différents sous-groupes.

Pour atteindre les objectifs mentionnés ci-dessus, le clustering K-means fonctionne assez bien. Il peut être utilisé dans les applications suivantes -

  • Segmentation du marché

  • Clustering de documents

  • Segmentation d'image

  • Compression d'image

  • Segmentation de la clientèle

  • Analyser la tendance sur les données dynamiques