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.

• Deux types de $ \ mathbf {m} $ ont été proposés. ――Il sera décidé au hasard. --Lorsque le composant principal est analysé pour l'échantillon dans le cluster et que le premier composant principal est $ \ mathbf {s} $ et la valeur intrinsèque du composant principal (dispersion du composant principal) est $ \ lambda $, $ \ mathbf {m} = \ mathbf {s} \ sqrt {2 \ lambda / \ pi} $. [^ 3]

[^ 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).

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

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?

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?

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.

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

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! !! !!