Unüberwachtes Clustering mit unbekannter Anzahl von Clustern

Ich habe einen großen Satz von Vektoren in 3 Dimensionen. Ich muss diese basierend auf dem euklidischen Abstand so gruppieren, dass alle Vektoren in einem bestimmten Cluster einen euklidischen Abstand untereinander haben, der kleiner als ein Schwellenwert "T" ist.

Ich weiß nicht, wie viele Cluster existieren. Am Ende können einzelne Vektoren vorhanden sein, die nicht Teil eines Clusters sind, da sein euklidischer Abstand mit keinem der Vektoren im Raum kleiner als "T" ist.

Welche vorhandenen Algorithmen / Ansätze sollten hier verwendet werden?

Sie können hierarchisches Clustering verwenden . Es ist ein ziemlich grundlegender Ansatz, daher stehen viele Implementierungen zur Verfügung. Es ist zum Beispiel in Pythons Scipy enthalten .

Siehe zum Beispiel das folgende Skript:

import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster

# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20

# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")

# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()

Dies führt zu einem ähnlichen Ergebnis wie im folgenden Bild.

Der als Parameter angegebene Schwellenwert ist ein Abstandswert, auf dessen Grundlage entschieden wird, ob Punkte / Cluster zu einem anderen Cluster zusammengeführt werden. Die verwendete Abstandsmetrik kann ebenfalls angegeben werden.

Beachten Sie, dass es verschiedene Methoden gibt, um die Ähnlichkeit zwischen und innerhalb des Clusters zu berechnen, z. B. Abstand zwischen den nächstgelegenen Punkten, Abstand zwischen den am weitesten entfernten Punkten, Abstand zu den Clusterzentren usw. Einige dieser Methoden werden auch vom hierarchischen Clustering-Modul von scipys unterstützt ( einzelne / vollständige / durchschnittliche ... Verknüpfung ). Laut Ihrem Beitrag möchten Sie eine vollständige Verknüpfung verwenden .

Beachten Sie, dass dieser Ansatz auch kleine (Einzelpunkt-) Cluster zulässt, wenn sie das Ähnlichkeitskriterium der anderen Cluster, dh den Abstandsschwellenwert, nicht erfüllen.

Es gibt andere Algorithmen, die eine bessere Leistung erzielen und in Situationen mit vielen Datenpunkten relevant werden. Wie andere Antworten / Kommentare vermuten lassen, sollten Sie sich auch den DBSCAN-Algorithmus ansehen:

• https://en.wikipedia.org/wiki/DBSCAN
• http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html
• http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

Einen guten Überblick über diese und andere Clustering-Algorithmen finden Sie auch auf dieser Demoseite (der Python-Bibliothek zum Scikit-Lernen):

• http://scikit-learn.org/stable/modules/clustering.html

Bild von diesem Ort kopiert:

Wie Sie sehen können, macht jeder Algorithmus einige Annahmen über die Anzahl und Form der Cluster, die berücksichtigt werden müssen. Sei es implizite Annahmen des Algorithmus oder explizite Annahmen der Parametrisierung.

Die Antwort von moooeeeep empfahl die Verwendung von hierarchischem Clustering. Ich wollte erarbeiten , wie zu wählen , die Schwelle des Clustering.

Eine Möglichkeit besteht darin, Cluster basierend auf verschiedenen Schwellenwerten t1 , t2 , t3 , ... zu berechnen und dann eine Metrik für die "Qualität" des Clusters zu berechnen. Die Voraussetzung ist, dass die Qualität eines Clusters mit der optimalen Anzahl von Clustern den Maximalwert der Qualitätsmetrik hat.

Ein Beispiel für eine gute Qualitätsmetrik, die ich in der Vergangenheit verwendet habe, ist Calinski-Harabasz. Kurz gesagt: Sie berechnen die durchschnittlichen Entfernungen zwischen den Clustern und dividieren sie durch die Entfernungen innerhalb der Cluster. Die optimale Clusterzuweisung besteht aus Clustern, die am stärksten voneinander getrennt sind, und Clustern, die "am engsten" sind.

Übrigens müssen Sie kein hierarchisches Clustering verwenden. Sie können auch so etwas wie k- Mittel verwenden, es für jedes k vorberechnen und dann das k auswählen , das die höchste Calinski-Harabasz-Punktzahl aufweist.

Lassen Sie mich wissen, wenn Sie weitere Referenzen benötigen, und ich werde meine Festplatte nach Papieren durchsuchen.

Überprüfen Sie den DBSCAN- Algorithmus. Es gruppiert sich basierend auf der lokalen Dichte von Vektoren, dh sie dürfen nicht mehr als einen Abstand von ε voneinander entfernt sein und kann die Anzahl der Cluster automatisch bestimmen. Ausreißer, dh Punkte mit einer unzureichenden Anzahl von ε- Nachbarn, werden ebenfalls als nicht Teil eines Clusters betrachtet. Die Wikipedia-Seite enthält Links zu einigen Implementierungen.

Verwenden Sie OPTICS , das mit großen Datenmengen gut funktioniert.

OPTIK: Bestellpunkte zur Identifizierung der Clusterstruktur Eng verwandt mit DBSCAN, findet eine Kernprobe mit hoher Dichte und erweitert Cluster daraus 1 . Im Gegensatz zu DBSCAN wird die Clusterhierarchie für einen variablen Nachbarschaftsradius beibehalten. Besser geeignet für die Verwendung in großen Datenmengen als die aktuelle sklearn-Implementierung von DBSCAN

from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)

Feinabstimmung eps, min_samples wie pro Ihre Anforderung.

Möglicherweise haben Sie keine Lösung: Dies ist der Fall, wenn der Abstand zwischen zwei unterschiedlichen Eingabedatenpunkten immer größer als T ist. Wenn Sie die Anzahl der Cluster nur aus den Eingabedaten berechnen möchten, können Sie sich MCG ansehen, ein hierarchisches Clustering Methode mit automatischem Stoppkriterium: Siehe die kostenlose Seminararbeit unter https://hal.archives-ouvertes.fr/hal-02124947/document (enthält bibliografische Verweise).

Ich möchte die Antwort von moooeeeep durch hierarchisches Clustering ergänzen. Diese Lösung funktioniert für mich, obwohl es ziemlich "zufällig" ist, einen Schwellenwert auszuwählen. Durch die Bezugnahme auf eine andere Quelle und den Test selbst habe ich eine bessere Methode erhalten und die Schwelle konnte leicht durch ein Dendrogramm ermittelt werden:

from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method  = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()

Sie werden die Handlung wie folgt sehen, klicken Sie hier . Wenn Sie dann die horizontale Linie zeichnen, beispielsweise bei Abstand = 1, entspricht die Anzahl der Konjunktionen Ihrer gewünschten Anzahl von Clustern. Also wähle ich hier Schwelle = 1 für 4 Cluster.

threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))

Jetzt wird jedem Wert in cluster_list eine zugewiesene Cluster-ID des entsprechenden Punkts in ori_array zugewiesen.