[PYTHON] Implementierung und Experiment der konvexen Clustering-Methode

Code, den ich geschrieben habe

Es ist ein kindisches Ergebnis, aber ich habe Code auf Github veröffentlichen durchgeführt.

Verweise

• [1] Fortsetzung / leicht verständliche Mustererkennung - Einführung in das Lernen ohne Lehrer - (Sehr leicht verständliches Buch!)
• [2] D. Lashkari und P. Golland: Konvexes Clustering mit exemplarischen Modellen (Originalarbeit der konvexen Clustering-Methode)

Mein grobes Verständnis

Die konvexe Clustermethode ist eine Clustermethode, bei der die Anzahl der Klassen basierend auf der Parameterschätzung der gemischten Normalverteilung unbekannt ist.

Der Unterschied zur Parameterschätzung der gemischten Normalverteilung (im Folgenden als weiches K-Mittel bezeichnet) durch den üblichen EM-Algorithmus liegt in den Parametern, denen Anfangswerte zugewiesen werden müssen.

Daher hat es den Vorteil, weniger vom Anfangswert der Lösung abhängig zu sein als weiche K-Mittel.

Die Wahrscheinlichkeit der von jedem Schwerpunkt gebildeten Normalverteilung wird berechnet, indem alle beobachteten Daten als Schwerpunkte betrachtet werden. Die Wahrscheinlichkeitsberechnung ist nur einmalig und nur die vorherige Wahrscheinlichkeit wird aktualisiert. Mit der Aktualisierung nähert sich die vorherige Wahrscheinlichkeit von Zentroiden, bei denen es schwierig ist, eine Verteilung zu bilden, Null. Selbst wenn es eine bestimmte Vorwahrscheinlichkeit gibt, ist die Anzahl der verbleibenden Zentroide die endgültige Anzahl der Klassen.

Motivation zur Umsetzung

Ich war interessiert, weil es in der Literatur eingeführt wurde [1]. Es ist attraktiv, dass es einfach zu implementieren scheint und weniger vom Anfangswert abhängig zu sein scheint. Als Ansatz zur Herstellung von Spielzeug für mein Hobby erwartete ich, dass es einfacher zu verwenden sein würde als nicht parametrische Buchten.

Implementierung

Implementiert in Python + Numpy. Es wird nur der Implementierungsteil der Parameteraktualisierung der konvexen Clustering-Methode angezeigt.

convex_clustering.py

def calculateLikelihoodCombination(x, sigma, gaussianFunc):
    likelihood = np.empty(0)
    for i1 in x:
        likelihood = np.append(likelihood, gaussianFunc(x, i1, sigma))
    samples = len(x)
    return np.reshape(likelihood, (samples, samples))


def calculatePrior(prePrior, likelihood):
    samples = len(prePrior)
    molecule = (prePrior*likelihood.T).T
    denomin = np.sum(molecule, axis=0) + 1e-10
    return np.sum(molecule/denomin, axis=1)/samples


def runConvexClustering(x, hyperSigma, gaussian, plotter):
    # Pre-calculation of likelihood
    likelihood = calculateLikelihoodCombination(x, hyperSigma, gaussian)
    # Initialize prior probability.
    classNum = len(x)  # Number of samples is used as number of classes.
    firstPrior = 1.0/classNum  # Set non zero value.
    prior = np.repeat(firstPrior, classNum)

    # Update parameters.
    for dummy in range(1000):
        prior = calculatePrior(prior, likelihood)

Es ist so einfach, dass Sie nur Dutzende von Zeilen benötigen. Ich denke, es ist kürzer als der weiche K-Mittel-Code, den ich in der Vergangenheit lokal geschrieben habe.

Experimentelle Bedingungen

Die Gesamtzahl der Proben in einem Experiment beträgt 4 * 100 = 400 Punkte. Die mit der Größe der Anfangswertdispersion verbundene Vergrößerung ist die Vergrößerung von der Standardabweichung der für die Probenahme verwendeten Normalverteilung.

Ergebnis

Die folgende Tabelle zeigt den Status des Clusters. Die vertikale Achse der Tabelle sind die Daten, und die horizontale Achse ist die Größe der Anfangswertstreuung.

	gewöhnlich	Groß	Sehr groß
\mathbb{R}^{1}
\mathbb{R}^{2}

Blau ist die Probe und Grün ist die Form der konvexen Bindung der Normalverteilung, die aus dem Schwerpunkt der Klasse erzeugt wird, der durch das konvexe Clustering-Verfahren erhalten wird.

Darüber hinaus ist die Anzahl der nach dem Schnitt verbleibenden Klassen wie folgt. In ähnlicher Weise ist die vertikale Achse der Tabelle die Daten, und die horizontale Achse ist die Größe der Streuung der Anfangswerte.

Erwägung

Wenn die Verteilung des Anfangswertes [normal, groß] ist, scheint es, dass er ziemlich gut geclustert ist. Ich bin der Meinung, dass Clustering korrekter ist, wenn es [groß] ist. Bei der Anwendung auf ein echtes Problem ist es möglicherweise besser, eine etwas größere Verteilung als erwartet zu verwenden. Wenn die Varianz des Anfangswertes [sehr groß] ist, werden vier Verteilungen als eine Verteilung zusammengefasst. Dies ist jedoch ein ziemlich selbsterklärendes Ergebnis.

Die Anzahl der Schwerpunkte in den Sekundärdaten liegt näher an der Anzahl der Normalverteilungen (= 4), die zur Erzeugung der Stichprobe verwendet wurden, als in den Primärdaten. Dies wird auch in Lit. [2] erwähnt. Je breiter der zu durchsuchende Raum ist, desto geringer ist die Abhängigkeit vom Anfangswert der konvexen Clustering-Methode. Ich mache mir jedoch ein wenig Sorgen, dass die Anzahl der Zentroide nicht nahe genug an 4 heranreicht, wie in der Literatur [1] [2]. \ # Ich hoffe aufrichtig, dass es kein Fehler in der Implementierung ist.

Zusammenfassung

Was ich über die konvexe Clustering-Methode durch Implementierung und Experimentieren empfunden habe, ist, dass "die Implementierung sehr einfach ist, aber es scheint einige Tricks zu geben, um sie auf tatsächliche Probleme anzuwenden". In der Literatur [1] [2] werden die Vor- und Nachteile in der Diskussion angegeben, und es scheint schwierig zu sein, sie in Abhängigkeit von dem zu behandelnden Problem zu verwenden. Ich denke, es ist eine kostengünstige Clustering-Methode, aber ich möchte genauer prüfen, ob sie als Ansatz für das Problem, das ich lösen möchte, geeignet ist.