Clustering G-means qui détermine automatiquement le nombre de clusters

Cet article est l'entrée pour le 6ème jour du Freee Data People Advent Calendar 2019. J'ai commencé à écrire au milieu de la nuit la veille et j'ai écrit en disant hehehe.

introduction

Connaissez-vous une bibliothèque appelée PyClustering? PyClustering est une bibliothèque spécifique au clustering disponible à partir de Python et C ++. Un algorithme appelé G-means a été récemment implémenté dans un tel PyClustering v0.9.2. J'ai vu le nom G-means pour la première fois + je n'ai pas trouvé d'article en japonais, alors je l'ai recherché et je l'ai résumé. Puisque l'algorithme lui-même est simple, il peut être plus facile de lire directement le papier. ne pas.

G-means

G-means est une extension de K-means et est un algorithme qui détermine automatiquement le nombre de clusters, qui était un paramètre de K-means. Il existe une méthode similaire appelée X-means, mais il existe "J'ai étudié la méthode X-means qui estime automatiquement le nombre de clusters" Il est introduit d'une manière facile à comprendre avec le code. (À propos, dans Pyclustering, X-means peut également être utilisé)

algorithme

L'algorithme est le suivant. C'est la même chose que X-means de commencer avec un petit nombre de clusters et de le subdiviser uniquement avec des conditions d'arrêt différentes.

  1. Déterminez certains points centraux, le cas échéant.
  2. Effectuez le regroupement par K-means en utilisant le point central déterminé en 1. comme valeur initiale.
  3. Effectuez un test statistique (test d'Anderson – Darling) pour voir si l'échantillon de chaque cluster créé en 2. suit la distribution gaussienne. [^ 1]
  4. Si l'hypothèse nulle est rejetée, divisez le cluster en deux. Si l'hypothèse nulle n'est pas rejetée, déterminez le cluster. [^ 2]
  5. Répétez les étapes 2 et 4 jusqu'à ce que le cluster ne soit plus divisé.

[^ 1]: G-means est comme le G. de Gaussien. [^ 2]: Bien que $ \ alpha = 0,0001 $ soit utilisé dans l'article, [Pyclustering](https://github.com/annoviko/pyclustering/blob/3457a2457c9aa385f625d628cec19dd6fada8326/pyclustering/cluster/gmeans.py#L292-L292 Ensuite, il semble que cela soit fait avec $ \ alpha = 0,01 $. Le papier dit qu'il vaut mieux réduire la probabilité d'erreur de type I (faux positif), alors cette implémentation est-elle correcte? Je penserai.

C'est tout pour l'algorithme, mais dans le papier

――Comment déterminer un nouveau point central lorsque le cluster est divisé en 4. --Anderson-Ingenuity pour faciliter le test de Darling

Est également mentionné.

Comment déterminer une nouvelle valeur initiale de point central lors de la division d'un cluster

--Lorsque le point central du cluster est $ \ mathbf {c} $, les deux points de $ \ mathbf {c} \ pm \ mathbf {m} $ sont définis comme les nouvelles valeurs initiales du point central.

[^ 3]: Est-ce une image si vous divisez l'axe dans la direction dans laquelle les échantillons sont dispersés?

Dans l'article, il a été dit que la méthode utilisant le deuxième composant principal a été adoptée, mais dans Pyclustering [il semble adopter la première méthode](https://github.com/annoviko/pyclustering/ blob / 3457a2457c9aa385f625d628cec19dd6fada8326 / pyclustering / cluster / gmeans.py # L331).

Ingéniosité pour faciliter le test d'Anderson-Darling

Si l'échantillon à regrouper est laissé tel quel, il est difficile d'effectuer des tests statistiques dans des dimensions élevées, il est donc projeté dans une dimension. Plus précisément, l'échantillon $ \ mathbf {x} $ est projeté sur le $ x ^ {\ prime} $ unidimensionnel comme suit.

x^{\prime} = \frac{\langle \mathbf{x}, \mathbf{v} \rangle}{\| \mathbf{v} \|^2}

Cependant, $ \ mathbf {v} $ est respectivement $ \ mathbf {c} \ _1 $ et $ \ mathbf {c} \ pour les deux points déterminés dans "Comment déterminer la nouvelle valeur initiale du point central lors de la division d'un cluster". C'est $ \ mathbf {c} \ _1 $ - $ \ mathbf {c} \ _2 $ quand c'est _2 $. Est-ce pour tester si elle suit une distribution normale en se projetant sur la première composante principale (l'axe dans le sens de l'épandage)?

Entraine toi

Maintenant que nous connaissons l'algorithme, j'aimerais réellement effectuer un clustering en utilisant Pyclustering. Pour le moment [ici](https://qiita.com/deaikei/items/8615362d320c76e2ce0b#%E3%81%95%E3%82%89%E3%81%AB%E3%83%A2%E3%83%A4% E3% 83% 83% E3% 81% A8% E3% 81% 97% E3% 81% 9F% E3% 83% 87% E3% 83% BC% E3% 82% BF% E3% 82% 92% E3% 82% AF% E3% 83% A9% E3% 82% B9% E3% 82% BF% E3% 83% AA% E3% 83% B3% E3% 82% B0% E3% 81% 95% E3% 81% J'ai essayé de cibler les mêmes données que 9B% E3% 81% A6% E3% 81% BF% E3% 82% 8B).

Génération de données factices
from sklearn.datasets import make_blobs

X, Y = make_blobs(n_samples=500,
                  n_features=2,
                  centers=8,
                  cluster_std=1.5,
                  center_box=(-10.0, 10.0),
                  shuffle=True,
                  random_state=1)

Étiquette de réponse correcte

Corriger le tracé des étiquettes
import seaborn as sns
sns.set(style="whitegrid")
sns.scatterplot(
    X[:, 0], X[:, 1], hue=Y, legend="full"
);

Puisque centres = 8, 8 couleurs sortiront naturellement.

正解ラベル

G-means

Eh bien, le sujet principal est d'ici. À quoi cela ressemble-t-il lorsque vous essayez d'utiliser G-means?

gmeans result plot
from pyclustering.cluster import gmeans
import numpy as np
import itertools

gmeans_instance = gmeans.gmeans(X).process()

clusters = gmeans_instance.get_clusters()
centers = gmeans_instance.get_centers()

labels_size = len(
    list(itertools.chain.from_iterable(clusters))
)
labels = np.zeros((1, labels_size))
for n, n_th_cluster in np.ndenumerate(clusters):
    for img_num in n_th_cluster:
        labels[0][img_num] = n[0]
labels = labels.ravel()

sns.scatterplot(
    X[:, 0], X[:, 1], hue=labels, legend="full"
)

Oh. Le nombre de clusters n'est pas de huit, mais ils sont regroupés de manière confortable. N'est-ce pas plutôt cool?

G-means

Si vous souhaitez regrouper dans une situation où vous n'avez aucune idée du nombre de clusters que vous avez, l'utilisation de G-means semble être une bonne option.

Le X-means du cheval rival est ...

Enfin, j'aimerais essayer d'utiliser les X-means de Pyclustering comme rival et comparer les résultats.

xmeans résultat plot
from pyclustering.cluster import xmeans
import numpy as np
import itertools

xmeans_instance = xmeans.xmeans(X).process()

clusters = xmeans_instance.get_clusters()
centers = xmeans_instance.get_centers()

labels_size = len(
    list(itertools.chain.from_iterable(clusters))
)
labels = np.zeros((1, labels_size))
for n, n_th_cluster in np.ndenumerate(clusters):
    for img_num in n_th_cluster:
        labels[0][img_num] = n[0]
labels = labels.ravel()

sns.scatterplot(
    X[:, 0], X[:, 1], hue=labels, legend="full"
)

Oh? [Article référencé sur X-means](https://qiita.com/deaikei/items/8615362d320c76e2ce0b#%E3%81%95%E3%82%89%E3%81%AB%E3%83%A2% E3% 83% A4% E3% 83% 83% E3% 81% A8% E3% 81% 97% E3% 81% 9F% E3% 83% 87% E3% 83% BC% E3% 82% BF% E3% 82% 92% E3% 82% AF% E3% 83% A9% E3% 82% B9% E3% 82% BF% E3% 83% AA% E3% 83% B3% E3% 82% B0% E3% 81% C'est complètement différent de 95% E3% 81% 9B% E3% 81% A6% E3% 81% BF% E3% 82% 8B).

X-means

Le document G-means contient également des résultats expérimentaux selon lesquels X-means surévalue et surestime le nombre de clusters, de sorte que les résultats sont inconfortables ... (Je n'ai pas pu creuser profondément ici) En ce qui concerne Pyclustering, il semble préférable d'utiliser G-means plutôt que X-means.

en conclusion

Nous avons résumé l'algorithme G-means récemment implémenté dans Pyclustering (?) Et les résultats de l'utilisation réelle. G-means a donné de meilleurs résultats que X-means lorsque je l'ai utilisé à la légère, il peut donc être préférable d'utiliser G-means lorsque vous voulez "essayer le clustering pour le moment!".

Huh. Le calendrier de l'Avent a réussi à arriver à temps ... Tu veux te coucher ... C'est tôt le matin! !! !!

Recommended Posts

Clustering G-means qui détermine automatiquement le nombre de clusters
[Python] Un programme qui compte le nombre de vallées
10. Compter le nombre de lignes
Obtenez le nombre de chiffres
Réutiliser les résultats du clustering
Calculez le nombre de changements
Un outil qui transforme automatiquement le gacha de Soshage
Comment trouver le nombre optimal de clusters pour les k-moyennes
[Baies non paramétriques] Estimation du nombre de clusters à l'aide du processus Diricle
Obtenez le nombre de vues de Qiita
Obtenez le nombre d'abonnés Youtube
[Python] Un programme qui calcule le nombre de segments de chocolat qui remplissent les conditions
J'ai fait un calendrier qui met à jour automatiquement le calendrier de distribution de Vtuber
[Python] Un programme qui calcule le nombre de chaussettes jumelées
L'histoire du développement d'une application WEB qui génère automatiquement des copies de capture [MeCab]
Ceci et celui de la notation d'inclusion.
Compter / vérifier le nombre d'appels de méthode.
Compter le nombre de caractères avec écho
Tensorflow, il semble que même la valeur propre de la matrice puisse être automatiquement différenciée
Faisons un clustering qui donne une belle vue d'ensemble de l'ensemble de données texte
Réglez la couleur du côté de l'affiche pour que la couleur du sous-titre Youtube change automatiquement.
[Python] Totale automatiquement le nombre total d'articles publiés par Qiita à l'aide de l'API
paramètres zsh qui facilitent l'utilisation de virtualenv
Calculez le nombre total de combinaisons avec python
Divisez la chaîne de caractères en le nombre de caractères spécifié
Une doublure qui répertorie les couleurs de matplotlib
Trouvez le nombre de jours dans un mois
Minimisez le nombre de polissages en optimisant la combinaison
Déterminez le nombre de classes à l'aide de la formule Starges
Un script python qui obtient le nombre de travaux pour une condition spécifiée sur Indeed.com
[Python] Un programme qui trouve le nombre d'étapes le plus court dans un jeu qui traverse les nuages
Un script qui peut effectuer des tests de résistance en fonction du nombre de cœurs CPU
J'ai fait un calendrier qui met à jour automatiquement le calendrier de distribution de Vtuber (édition Google Calendar)