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.

À 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.

  1. Allouez au hasard des clusters pour chaque point $ x_ {i} $
  2. Calculez le centre de gravité des points attribués à chaque cluster
  3. 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.
  4. 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 ++

  1. Sélectionnez au hasard un point de chaque point $ x_ {i} $ et utilisez-le comme centre du cluster.
  2. Pour chaque point $ x_ {i} $, calculez la distance $ D (x) $ du centre du cluster existant au centre du cluster le plus proche.
  3. 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} $
  4. 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.

ダウンロード.png

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.

Recommended Posts

Comprendre k-means ++
Comprendre la méthode k-means
Kmeans débutants
Comprendre Word2Vec
Comprenez base64.
k-means et kernel k-means
Comprendre l'axe de numpy
kmeans ++ avec scikit-learn