Maison  >  Article  >  développement back-end  >  Explication détaillée de l'algorithme K-means++ en Python

Explication détaillée de l'algorithme K-means++ en Python

PHPz
PHPzoriginal
2023-06-10 20:25:441816parcourir

L'algorithme K-means est un algorithme d'apprentissage non supervisé courant utilisé pour regrouper les données en différentes catégories. L'algorithme K-means++ est une version améliorée de l'algorithme K-means, visant à améliorer l'efficacité et la précision de la sélection initiale du centre de cluster. Cet article présentera en détail le principe, l'implémentation du code et l'application de l'algorithme K-means++ en Python.

  1. Aperçu de l'algorithme K-means

L'algorithme K-means est un algorithme itératif. Le processus de chaque itération est le suivant : sélectionnez d'abord au hasard K centres de regroupement initiaux, puis attribuez chaque point de données au plus proche dans la catégorie où le Le centre de clustering initial est localisé, les centres de tous les clusters sont ensuite recalculés et les centres de clustering sont mis à jour. Répétez le processus ci-dessus jusqu'à ce que les conditions de convergence soient remplies.

Processus d'algorithme K-means :

  1. Sélectionnez aléatoirement K points de données à partir des données comme centre de clustering initial.
  2. Attribuez des points de données au cluster avec leur centre de cluster le plus proche.
  3. Recalculez le centre de chaque cluster.
  4. Répétez 2-3 jusqu'à ce que les conditions de convergence soient remplies (le centre du cluster ne change plus, le nombre maximum d'itérations est atteint, etc.).
  5. Étapes de l'algorithme K-means++

L'algorithme K-means++ est une version améliorée de l'algorithme K-means, qui optimise principalement la sélection des centres de clustering initiaux. Les étapes initiales de sélection du centre de cluster de l'algorithme K-means++ sont les suivantes :

  1. Sélectionnez au hasard un point de données comme premier centre de cluster.
  2. Pour chaque point de données, calculez sa distance D(x) du centre du cluster le plus proche.
  3. Sélectionnez au hasard un point de données comme prochain centre du cluster. Assurez-vous que plus la distance entre ce point et le centre du cluster existant est grande, plus la probabilité d'être sélectionné est grande :
    a. Calculez la relation entre chaque point de données et l'existant. centre du cluster La distance la plus proche du centre est D(x)^2.
    b. Calculez la somme Sum(D(x)^2) de tous les D(x)^2.
    c. Pondérez chaque point de données en fonction de la proportion de sa distance la plus proche du centre du cluster existant, et la probabilité est D(x)^2/Sum(D(x)^2).
    d. À partir de l'échantillonnage selon la probabilité ci-dessus, sélectionnez un point de données comme prochain centre de cluster.
  4. Répétez l'étape 3 jusqu'à ce que K centres de cluster soient sélectionnés.
  5. Python implémente l'algorithme K-means++

Ci-dessous, nous allons implémenter l'algorithme K-means++ via Python.

Tout d'abord, importez les bibliothèques nécessaires :

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

Ensuite, nous générons un ensemble de données pour le clustering :

n_samples = 1500
random_state = 170
X, y = make_blobs(n_samples=n_samples, random_state=random_state)

Ensuite, nous entraînons le modèle K-means++ via le module KMeans de sklearn :

kmeans = KMeans(init="k-means++", n_clusters=3, n_init=10)
kmeans.fit(X)

Enfin, nous allons visualiser le clustering résultats :

plt.figure(figsize=(12, 12))
h = 0.02
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
Z = kmeans.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.imshow(Z, interpolation="nearest",
          extent=(xx.min(), xx.max(), yy.min(), yy.max()),
          cmap=plt.cm.Pastel1, aspect="auto", origin="lower")
plt.scatter(X[:, 0], X[:, 1], s=30, c=kmeans.labels_, cmap=plt.cm.Paired)
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1],
            marker="^", s=100, linewidths=3,
            color='black', zorder=10)
plt.title("K-means++ clustering")
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.show()
  1. Scénarios d'application de l'algorithme K-means++

L'algorithme K-means convient aux problèmes de regroupement de données sans informations d'étiquette. Comparé à l'algorithme K-means, l'algorithme K-means++ est plus adapté aux situations où il y a beaucoup de données ou où la distribution des données est relativement dispersée afin de garantir la rationalité et l'unicité du centre de clustering initial.

L'algorithme K-means++ peut être utilisé dans l'exploration de données, le traitement d'images, le traitement du langage naturel et d'autres domaines. Les algorithmes de clustering peuvent être utilisés pour trouver des échantillons présentant une plus grande similarité, ce qui est également très utile pour la visualisation du Big Data.

En bref, l'algorithme K-means++ a de bonnes perspectives d'application dans l'exploration de données, l'analyse de clusters, la reconnaissance d'images, le traitement du langage naturel et d'autres domaines.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn