[PYTHON] Comprendre k-means ++
introduction
J'ai posté Article sur k-means avant. Puisque k-means a un problème de dépendance aux valeurs initiales, un algorithme appelé k-means ++ a été développé pour le surmonter. Cette fois, j'ai résumé ce que j'ai appris sur k-means ++.
référence
Pour comprendre k-means ++, je me suis référé à ce qui suit.
- Introduction à l'apprentissage automatique pour le traitement du langage (série Traitement du langage naturel) Daiya Takamura (Auteur), Manabu Okumura (supervisé) Éditeur; Corona
- Essence of Machine Learning Koichi Kato (Auteur) Editeur; SB Creative Co., Ltd.
- méthode k-means ++-Wikipedia
À propos de k-means ++
Examen de k-means
Vue d'ensemble des k-means
k-means est un algorithme qui divise d'abord les données en grappes appropriées, puis ajuste les données afin qu'elles soient bien divisées en utilisant la moyenne des grappes. On l'appelle la méthode des k-moyennes (méthode de moyenne des k points) car c'est un algorithme qui crée k groupes de désignation arbitraire.
algorithme k-means
Plus précisément, k-means suit le processus suivant.
- Allouez au hasard des clusters pour chaque point $ x_ {i} $
- Calculez le centre de gravité des points attribués à chaque cluster
- Pour chaque point, calculez la distance par rapport au centre de gravité calculée ci-dessus et réaffectez-la au cluster avec la distance la plus proche.
- Répétez les étapes 2 et 3 jusqu'à ce que le cluster attribué ne change pas.
Problèmes avec les k-means
** Puisque k-means alloue des clusters de manière aléatoire au début, sa valeur initiale peut entraîner un clustering qui est loin d'être optimal. En outre, il faut beaucoup de temps pour que le résultat converge en fonction de la valeur initiale. ** **
k-means++
Vue d'ensemble de k-means ++
k-means ++ est un algorithme qui vise à surmonter le problème de dépendance de valeur initiale ci-dessus. ** k-means ++ est conçu sur la base de l'idée que les centres des clusters initiaux doivent être séparés les uns des autres **, et l'allocation du cluster initial est allouée de manière probabiliste en fonction de la distance entre les points de données. Je vais.
algorithme k-means ++
- Sélectionnez au hasard un point de chaque point $ x_ {i} $ et utilisez-le comme centre du cluster.
- Pour chaque point $ x_ {i} $, calculez la distance $ D (x) $ du centre du cluster existant au centre du cluster le plus proche.
- Sélectionnez au hasard de nouveaux centres de cluster en utilisant la distribution de probabilité pondérée $ \ frac {D (x) ^ 2} {\ sum_ {} D (x) ^ 2} $ pour chaque point $ x_ {i} $
- Répétez les étapes 2 et 3 jusqu'à ce que k centres de cluster puissent être sélectionnés.
Comme mentionné ci-dessus, nous essayons de résoudre le problème de dépendance de la valeur initiale en déterminant de manière probabiliste le point central du cluster initial en fonction de la distance entre les points de données. ** **
Implémenter k-means ++
Implémentation de k-means ++ sans utiliser de bibliothèque
Ce qui suit est une implémentation de la méthode k-means sans utiliser de bibliothèque. Basé sur le code k-means décrit dans Essence of Machine Learning, je l'ai modifié moi-même en passant à k-means ++. Je suis.
import numpy as np
class KMeans_pp:
def __init__(self, n_clusters, max_iter = 1000, random_seed = 0):
self.n_clusters = n_clusters
self.max_iter = max_iter
self.random_state = np.random.RandomState(random_seed)
def fit(self, X):
#Déterminer aléatoirement le premier point de cluster
tmp = np.random.choice(np.array(range(X.shape[0])))
first_cluster = X[tmp]
first_cluster = first_cluster[np.newaxis,:]
#Calculez le carré de la distance entre le premier point de cluster et les autres points de données et divisez chacun par sa somme
p = ((X - first_cluster)**2).sum(axis = 1) / ((X - first_cluster)**2).sum()
r = np.random.choice(np.array(range(X.shape[0])), size = 1, replace = False, p = p)
first_cluster = np.r_[first_cluster ,X[r]]
#Lorsque le nombre de clusters à diviser est de 3 ou plus
if self.n_clusters >= 3:
#Répétez jusqu'à ce que vous puissiez spécifier le nombre spécifié de points de cluster
while first_cluster.shape[0] < self.n_clusters:
#Calculez le carré de la distance entre chaque point de cluster et chaque point de données
dist_f = ((X[:, :, np.newaxis] - first_cluster.T[np.newaxis, :, :])**2).sum(axis = 1)
#Quel point de cluster est le plus proche de vous?
f_argmin = dist_f.argmin(axis = 1)
#Dérivation du carré de la distance entre le point de cluster le plus proche et chaque point de données
for i in range(dist_f.shape[1]):
dist_f.T[i][f_argmin != i] = 0
#Dériver de manière probable de nouveaux points de cluster
pp = dist_f.sum(axis = 1) / dist_f.sum()
rr = np.random.choice(np.array(range(X.shape[0])), size = 1, replace = False, p = pp)
#Ajouter de nouveaux points de cluster comme valeurs initiales
first_cluster = np.r_[first_cluster ,X[rr]]
#Faites le premier étiquetage
dist = (((X[:, :, np.newaxis] - first_cluster.T[np.newaxis, :, :]) ** 2).sum(axis = 1))
self.labels_ = dist.argmin(axis = 1)
labels_prev = np.zeros(X.shape[0])
count = 0
self.cluster_centers_ = np.zeros((self.n_clusters, X.shape[1]))
#Se termine lorsque le cluster auquel appartient chaque point de données ne change pas ou dépasse un certain nombre de répétitions
while (not (self.labels_ == labels_prev).all() and count < self.max_iter):
#Calculez le centre de gravité de chaque cluster à ce moment
for i in range(self.n_clusters):
XX = X[self.labels_ == i, :]
self.cluster_centers_[i, :] = XX.mean(axis = 0)
#Arrondissez la distance entre chaque point de données et le centre de gravité de chaque cluster
dist = ((X[:, :, np.newaxis] - self.cluster_centers_.T[np.newaxis, :, :]) ** 2).sum(axis = 1)
#Souvenez-vous de l'étiquette de cluster précédente. Si l'étiquette précédente et l'étiquette ne changent pas, le programme se termine.
labels_prev = self.labels_
#À la suite du recalcul, attribuez le libellé du cluster le plus proche de la distance
self.labels_ = dist.argmin(axis = 1)
count += 1
self.count = count
def predict(self, X):
dist = ((X[:, :, np.newaxis] - self.cluster_centers_.T[np.newaxis, :, :]) ** 2).sum(axis = 1)
labels = dist.argmin(axis = 1)
return labels
Vérification
Ce qui suit est une vérification pour savoir si le clustering est vraiment possible avec cet algorithme.
import matplotlib.pyplot as plt
#Créez un jeu de données adapté
np.random.seed(0)
points1 = np.random.randn(80, 2)
points2 = np.random.randn(80, 2) + np.array([4,0])
points3 = np.random.randn(80, 2) + np.array([5,8])
points = np.r_[points1, points2, points3]
np.random.shuffle(points)
#Créer un modèle à diviser en 3 clusters
model = KMeans_pp(3)
model.fit(points)
print(model.labels_)
Ensuite, la sortie ressemblera à ceci. Vous pouvez voir que les étiquettes sont brillamment attribuées aux trois.
[2 1 0 2 1 1 0 1 2 0 1 1 0 1 0 0 1 1 0 2 0 1 2 0 1 2 0 2 1 2 1 1 1 0 1 0 1
2 2 1 1 1 1 2 0 1 1 1 0 2 1 0 2 1 0 1 0 2 2 2 2 2 1 0 1 0 0 1 1 1 1 1 0 1
0 0 0 2 1 0 2 0 1 1 0 1 2 0 2 2 2 0 0 0 2 0 0 0 2 0 2 1 1 1 1 1 0 1 2 1 2
0 1 2 2 1 2 0 2 2 2 0 0 2 0 2 1 2 2 0 1 2 1 2 2 2 1 0 2 1 1 2 0 0 0 2 1 1
1 0 0 0 1 1 2 0 1 0 0 0 2 0 0 0 0 0 2 2 1 2 0 2 2 0 1 2 2 2 2 1 0 2 1 2 2
0 2 0 0 0 2 0 1 2 0 0 0 1 1 1 1 2 2 0 2 2 2 0 0 1 1 2 2 0 1 1 2 1 2 2 0 2
1 2 0 2 1 2 0 0 2 2 0 2 0 2 1 2 2 0]
Illustrons cela avec matplotlib.
markers = ["+", "*", "o", '+']
color = ['r', 'b', 'g', 'k']
for i in range(4):
p = points[model.labels_ == i, :]
plt.scatter(p[:, 0], p[:, 1], marker = markers[i], color = color[i])
plt.show()
Voici la sortie. Vous pouvez voir que le clustering est terminé sans aucun problème.
Essayez également de générer le nombre d'essais jusqu'à ce que le clustering converge.
print(model.count)
4
Cette fois, le nombre d'essais jusqu'à la convergence de k-means ++ était de quatre. De même, en comptant le nombre d'essais avec des k-moyennes ordinaires, le résultat était de 3 fois. À l'origine, on dit que k-means ++ prend moins de temps à converger, je voudrais donc le vérifier moi-même.
Next Je voudrais contester le clustering par distribution normale mixte et le clustering par algorithme EM.