[PYTHON] Clustering G-bedeutet, dass die Anzahl der Cluster automatisch bestimmt wird

Dieser Artikel ist der Eintrag für den 6. Tag von Freee Data People Adventskalender 2019. Ich begann am Tag zuvor mitten in der Nacht zu schreiben und schrieb, während ich hehehe sagte.

Einführung

Kennen Sie eine Bibliothek namens PyClustering? PyClustering ist eine clusterspezifische Bibliothek, die in Python und C ++ verfügbar ist. In einem solchen PyClustering [v0.9.2] wurde ein Algorithmus namens G-means neu implementiert (https://github.com/annoviko/pyclustering/releases/tag/0.9.2). Ich habe den Namen G-means zum ersten Mal gesehen + Ich konnte keinen Artikel auf Japanisch finden, also habe ich ihn nachgeschlagen und zusammengefasst. Da der Algorithmus selbst einfach ist, ist es möglicherweise am einfachsten, das Papier direkt zu lesen. nicht.

G-means

G-means ist eine Erweiterung von K-means und ein Algorithmus, der automatisch die Anzahl der Cluster bestimmt, was ein Parameter von K-means war. Es gibt eine ähnliche Methode namens X-means, aber es gibt "Ich habe die X-means-Methode untersucht, mit der die Anzahl der Cluster automatisch geschätzt wird" Es wird auf leicht verständliche Weise mit dem Code eingeführt. (Übrigens kann in Pyclustering auch X-means verwendet werden)

Algorithmus

Der Algorithmus ist wie folgt. Es ist dasselbe wie X-means, mit einer kleinen Anzahl von Clustern zu beginnen und diese nur mit unterschiedlichen Stoppbedingungen zu unterteilen.

1. Bestimmen Sie gegebenenfalls einige Mittelpunkte.
2. Führen Sie die Clusterbildung mit K-Mitteln unter Verwendung des in 1. als Mittelpunkt bestimmten Mittelpunkts durch.
3. Führen Sie einen statistischen Test (Anderson-Darling-Test) durch, um festzustellen, ob die Stichprobe in jedem in 2. erstellten Cluster der Gaußschen Verteilung folgt. [^ 1]
4. Wenn die Nullhypothese abgelehnt wird, teilen Sie den Cluster in zwei Teile. Wenn die Nullhypothese nicht verworfen wird, bestimmen Sie den Cluster. [^ 2]
5. Wiederholen Sie die Schritte 2 und 4, bis der Cluster nicht mehr aufgeteilt ist.

[^ 1]: G-bedeutet wie Gaußsches G. [^ 2]: Obwohl in dem Artikel $ \ alpha = 0,0001 $ verwendet wird, [Pyclustering](https://github.com/annoviko/pyclustering/blob/3457a2457c9aa385f625d628cec19dd6fada8326/pyclustering/cluster/gmeans.py#L292-29 Dann scheint es, dass es mit $ \ alpha = 0.01 $ gemacht wird. Ist diese Implementierung in Ordnung, da das Papier besagt, dass es besser ist, die Wahrscheinlichkeit eines Fehlers vom Typ I (falsch positiv) zu verringern? Ich werde denken.

Das ist alles für den Algorithmus, aber in der Zeitung

――Wie man einen neuen Mittelpunkt bestimmt, wenn der Cluster in 4 unterteilt ist.

• Anderson-Einfallsreichtum, um den Darling-Test zu vereinfachen

Wird auch erwähnt.

So bestimmen Sie einen neuen Mittelpunktanfangswert beim Teilen eines Clusters

• Wenn der Mittelpunkt im Cluster $ \ mathbf {c} $ ist, werden die beiden Punkte von $ \ mathbf {c} \ pm \ mathbf {m} $ als neue Mittelpunktanfangswerte festgelegt.
• Es wurden zwei Arten von $ \ mathbf {m} $ vorgeschlagen. ――Es wird nach dem Zufallsprinzip entschieden. --Wenn die Hauptkomponente für die Stichprobe im Cluster analysiert wird und die erste Hauptkomponente $ \ mathbf {s} $ ist und der innere Wert der Hauptkomponente (Streuung der Hauptkomponente) $ \ lambda $ ist, $ \ mathbf {m} = \ mathbf {s} \ sqrt {2 \ lambda / \ pi} $. [^ 3]

[^ 3]: Ist es ein Bild, wenn Sie die Achse in die Richtung teilen, in die die Proben gestreut werden?

In dem Artikel wurde gesagt, dass die Methode unter Verwendung der zweiten Hauptkomponente übernommen wurde, aber in Pyclustering [es scheint die erste Methode zu übernehmen](https://github.com/annoviko/pyclustering/ blob / 3457a2457c9aa385f625d628cec19dd6fada8326 / pyclustering / cluster / gmeans.py # L331).

Einfallsreichtum, um den Anderson-Darling-Test zu vereinfachen

Wenn die zu gruppierende Probe unverändert bleibt, ist es schwierig, statistische Tests in hohen Dimensionen durchzuführen, sodass sie in einer Dimension projiziert wird. Insbesondere wird das Beispiel $ \ mathbf {x} $ wie folgt auf das eindimensionale $ x ^ {\ prime} $ projiziert.

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

$ \ Mathbf {v} $ ist jedoch $ \ mathbf {c} \ _1 $, $ \ mathbf {c} \ für die beiden Punkte, die unter "So bestimmen Sie den Anfangswert des neuen Mittelpunkts beim Teilen des Clusters" ermittelt wurden. Es ist $ \ mathbf {c} \ _1 $ - $ \ mathbf {c} \ _2 $, wenn es _2 $ ist. Soll geprüft werden, ob es einer Normalverteilung folgt, indem auf die erste Hauptkomponente (die Achse in Ausbreitungsrichtung) projiziert wird?

Trainieren

Nachdem wir den Algorithmus kennen, möchte ich das Clustering mithilfe von Pyclustering durchführen. Vorerst [hier](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% Ich habe versucht, die gleichen Daten wie 9B% E3% 81% A6% E3% 81% BF% E3% 82% 8B) anzuvisieren.

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)

Richtiges Antwortetikett

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

Da "Zentren = 8", kommen natürlich 8 Farben heraus.

G-means

Nun, das Hauptthema ist von hier. Wie sieht es aus, wenn Sie versuchen, G-Mittel zu verwenden?

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. Die Anzahl der Cluster beträgt nicht acht, aber sie werden auf komfortable Weise geclustert. Ist das nicht ziemlich cool?

Wenn Sie in einer Situation gruppieren möchten, in der Sie keine Ahnung haben, wie viele Cluster Sie haben, ist die Verwendung von G-means eine gute Option.

Das X-Mittel des rivalisierenden Pferdes ist ...

Abschließend möchte ich die Ergebnisse vergleichen, indem ich Pyclusterings X-Mittel als Konkurrenzpferd verwende.

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? [Referenzierter X-Mittel-Artikel](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% Es ist völlig anders als 95% E3% 81% 9B% E3% 81% A6% E3% 81% BF% E3% 82% 8B).

Das G-Means-Papier enthält auch experimentelle Ergebnisse, bei denen X-Means die Anzahl der Cluster überpasst und überschätzt, sodass die Ergebnisse unangenehm sind ... (Ich konnte hier nicht tief graben) In Bezug auf Pyclustering scheint es besser zu sein, G-Mittel als X-Mittel zu verwenden.

abschließend

Wir haben den kürzlich in Pyclustering (?) Implementierten G-Means-Algorithmus und die Ergebnisse der tatsächlichen Verwendung zusammengefasst. G-Mittel lieferten bessere Ergebnisse als X-Mittel, wenn ich es leicht benutzte. Daher ist es möglicherweise besser, G-Mittel zu verwenden, wenn Sie "vorerst versuchen möchten, Cluster zu erstellen!".

Huh. Der Adventskalender hat es geschafft, rechtzeitig zu kommen ... Willst du ins Bett gehen ... Es ist früher Morgen! !! !!