Auswählen einer Clustering-Methode

Wenn Sie die Clusteranalyse für einen Datensatz verwenden, um ähnliche Fälle zu gruppieren, müssen Sie aus einer Vielzahl von Clustermethoden und Entfernungsmaßen auswählen. Manchmal kann eine Wahl die andere beeinflussen, aber es gibt viele mögliche Kombinationen von Methoden.

Hat jemand irgendwelche Empfehlungen, wie man unter den verschiedenen Clustering-Algorithmen / Methoden und Distanzmaßen wählt ? In welcher Beziehung steht dies zur Art der Variablen (z. B. kategorial oder numerisch) und zum Clustering-Problem? Gibt es eine optimale Technik?

Es gibt keine definitive Antwort auf Ihre Frage, da die Wahl der Entfernung zur Darstellung der (Dis-) Ähnlichkeit von Individuen auch innerhalb derselben Methode zu unterschiedlichen Ergebnissen führen kann, z. Als weiteres Beispiel für Binärdaten können Sie den Jaccard-Index als Maß für die Ähnlichkeit auswählen und mit der klassischen hierarchischen Gruppierung fortfahren. es gibt aber alternative Ansätze wie die Mona ( Monothetic Analysis) Algorithmus, der jeweils nur eine Variable berücksichtigt, während andere hierarchische Ansätze (z. B. klassische HC, Agnes, Diana) bei jedem Schritt alle Variablen verwenden. Der k-means-Ansatz wurde auf verschiedene Weise erweitert, einschließlich der Aufteilung um Medoide (PAM) oder repräsentative Objekte anstelle von Zentroiden (Kaufman und Rousseuw, 1990) oder Fuzzy-Clustering (Chung und Lee, 1992). Zum Beispiel besteht der Hauptunterschied zwischen dem k-Mittelwert und dem PAM darin, dass der PAM eine Summe von Unähnlichkeiten eher als eine Summe von euklidischen Quadratabständen minimiert; Fuzzy-Clustering ermöglicht die Berücksichtigung einer "Teilmitgliedschaft" (wir ordnen jeder Beobachtung eine Gewichtung zu, die die Klassenzugehörigkeit widerspiegelt). Und für Methoden, die sich auf ein probabilistisches Framework oder ein sogenanntes modellbasiertes Clustering (oder eine latente Profilanalyse) stützenFür die Psychometriker gibt es ein tolles Paket: Mclust . Daher müssen Sie sich überlegen, wie Sie die Ähnlichkeit von Personen sowie die Methode zum Verbinden von Personen definieren (rekursives oder iteratives Clustering, strikte oder unscharfe Klassenzugehörigkeit, unbeaufsichtigter oder halbüberwachter Ansatz usw.).

In der Regel ist es zur Beurteilung der Clusterstabilität interessant, mehrere Algorithmen zu vergleichen, die im Grunde genommen Ähnlichkeiten aufweisen (z. B. k-Mittelwerte und hierarchische Cluster, da für beide euklidische Abstände gelten). Zur Beurteilung der Konkordanz zwischen zwei Clusterlösungen wurden einige Hinweise als Antwort auf die Frage vorgeschlagen, wo ein Dendrogramm geschnitten werden soll. (Siehe auch die Querverweise für andere Links auf dieser Website). Wenn Sie R verwenden, werden Sie feststellen, dass in der Task-Ansicht der Clusteranalyse bereits mehrere Pakete verfügbar sind und dass einige Pakete Vignetten enthalten, die bestimmte Methoden erläutern oder Fallstudien enthalten.

Clusteranalyse: Grundlegende Konzepte und Algorithmen bieten einen guten Überblick über verschiedene in der Clusteranalyse verwendete Techniken. Für ein gutes Buch mit R-Abbildungen aus jüngster Zeit empfehle ich Kapitel 12 von Izenman, Modern Multivariate Statistical Techniques (Springer, 2008). Ein paar andere Standardreferenzen sind unten angegeben:

• Cormack, R., 1971. Eine Überprüfung der Klassifizierung. Zeitschrift der Royal Statistical Society, A 134, 321–367.
• Everitt, B., 1974. Clusteranalyse . London: Heinemann Educ. Bücher.
• Gordon, A., 1987. Eine Überprüfung der hierarchischen Klassifikation. Zeitschrift der Royal Statistical Society, A 150, 119–137.
• Gordon, A., 1999. Classification , 2nd Edition. Chapman und Hall.
• Kaufman, L., Rousseuw, P., 1990. Auffinden von Gruppen in Daten: Eine Einführung in die Clusteranalyse . New York, Wiley.

Ein Zitat von Hastie, Tibshirani und Friedman, Elemente des statistischen Lernens , p. 506

"Ein geeignetes Maß für die Unähnlichkeit ist für den Erfolg des Clusters weitaus wichtiger als die Wahl des Clustering-Algorithmus. Dieser Aspekt des Problems ... hängt von domänenspezifischem Wissen ab und ist für allgemeine Forschung weniger zugänglich."

(Das heißt, wäre es nicht schön, wenn (wibni) es eine Site gäbe, auf der die Schüler ein paar Algorithmen und Metriken für ein paar kleine Standarddatensätze ausprobieren könnten?)

Sie können nicht im Voraus wissen, welcher Cluster-Algorithmus besser ist, aber es gibt einige Hinweise, zum Beispiel, wenn Sie Bilder gruppieren möchten, sollten Sie zuerst bestimmte Algorithmen wie Fuzzy Art ausprobieren, oder wenn Sie Gesichter gruppieren möchten, sollten Sie beginnen mit (GGCI) globalem geometrischem Clustering für das Bild.

Auf jeden Fall garantiert dies nicht das beste Ergebnis. Daher würde ich ein Programm verwenden, mit dem Sie verschiedene Cluster-Algorithmen wie weka, RapidMiner oder sogar R (das nicht visuell ist) methodisch ausführen können. Dort werde ich das Programm einstellen auf Starten Sie all die verschiedenen Cluster-Algorithmen, die ich mit all den möglichen unterschiedlichen Entfernungen verwenden kann, und experimentieren Sie, wenn sie Parameter benötigen, mit einer Vielzahl unterschiedlicher Parameterwerte (außer wenn ich die Anzahl der Cluster nicht kenne, führen Sie jeden mit einer Vielzahl aus von Zahlen davon). Wenn Sie das Experiment abgeschlossen haben, lassen Sie es laufen, aber denken Sie daran, die Ergebnisse der einzelnen Clustering-Läufe irgendwo zu speichern.

Vergleichen Sie anschließend die Ergebnisse, um die bestmögliche Clusterbildung zu erzielen. Dies ist schwierig, da Sie mehrere Metriken vergleichen können und nicht alle von jedem Algorithmus bereitgestellt werden. Zum Beispiel haben Fuzzy-Clustering-Algorithmen andere Metriken als Nicht-Fuzzy, aber sie können trotzdem verglichen werden, indem die resultierenden Fuzzy-Gruppen als Nicht-Fuzzy betrachtet werden. Ich werde mich für den Vergleich mit den klassischen Metriken wie den folgenden entscheiden:

• SSE: Summe der quadratischen Fehler aus den Elementen jedes Clusters.

• Abstand zwischen Clustern: Summe der quadratischen Entfernung zwischen den einzelnen Cluster-Schwerpunkten.

• Intra-Cluster-Abstand für jeden Cluster: Summe der quadratischen Entfernung zwischen den Elementen jedes Clusters und seinem Schwerpunkt.

• Maximaler Radius: größte Entfernung von einer Instanz zu ihrem Cluster-Schwerpunkt.

• Durchschnittlicher Radius: Summe der größten Entfernung von einer Instanz zu ihrem Cluster-Schwerpunkt geteilt durch die Anzahl der Cluster.

Die Wahl der richtigen Entfernung ist keine elementare Aufgabe. Wenn wir eine Cluster-Analyse für einen Datensatz durchführen möchten, können unterschiedliche Ergebnisse mit unterschiedlichen Entfernungen angezeigt werden. Daher ist es sehr wichtig, die richtige Entfernung zu wählen, da wir ein falsches gutes Artefakt erstellen können, das die Variabilität gut erfasst, aber tatsächlich ohne Sinn in unserem Problem.

Der euklidische Abstand ist angemessen, wenn ich stetige numerische Variablen habe und absolute Abstände widerspiegeln möchte. Dieser Abstand berücksichtigt jede Variable und entfernt keine Redundanzen. Wenn ich also drei Variablen hätte, die dasselbe erklären (korrelieren), würde ich diesen Effekt mit drei gewichten. Darüber hinaus ist dieser Abstand nicht skalierungsinvariant, so dass ich im Allgemeinen vorher skalieren muss, um den Abstand zu verwenden.
Beispiel Ökologie: Wir haben unterschiedliche Beobachtungen von vielen Orten, von denen die Experten Proben einiger mikrobiologischer, physikalischer und chemischer Faktoren entnommen haben. Wir wollen Muster in Ökosystemen finden. Diese Faktoren haben eine hohe Korrelation, aber wir wissen, dass jeder relevant ist, daher möchten wir diese Redundanzen nicht beseitigen. Wir verwenden den euklidischen Abstand mit skalierten Daten, um den Effekt von Einheiten zu vermeiden.

Die Mahalanobis-Distanz ist angemessen, wenn ich kontinuierliche numerische Variablen habe und absolute Distanzen widerspiegeln möchte, aber wir Redundanzen entfernen möchten. Wenn wir Variablen wiederholen, verschwindet ihr sich wiederholender Effekt.

Die Familien Hellinger , Species Profile und Chord distance eignen sich, wenn wir Unterschiede zwischen Variablen hervorheben wollen, wenn wir Profile unterscheiden wollen. Diese Abstände werden nach Gesamtgrößen jeder Beobachtung gewichtet, so dass die Abstände klein sind, wenn sie variabel sind, die Individuen ähnlicher sind, obwohl sie in absoluten Größen sehr unterschiedlich waren. Achtung! Diese Abstände spiegeln den Unterschied zwischen den Profilen sehr gut wider, verlieren jedoch den Größeneffekt. Sie können sehr nützlich sein, wenn wir unterschiedliche Stichprobengrößen haben. Beispiel Ökologie: Wir wollen die Fauna vieler Länder untersuchen und haben eine Datenmatrix eines Inventars der Gastropoden (Probenahmestellen in Zeilen und Artennamen in Spalten). Die Matrix ist dadurch gekennzeichnet, dass sie viele Nullen und unterschiedliche Größen aufweist, da einige Orte einige Arten und andere andere Arten aufweisen. Wir könnten die Hellinger-Distanz nutzen.

Bray-Curtis ist ziemlich ähnlich, aber es ist angemessener, wenn wir Profile unterscheiden und auch relative Größen berücksichtigen möchten.

Was mich betrifft, wenn Sie eine sichere Wahl treffen möchten, haben spektrale Clustering- Methoden in den letzten Jahren die höchsten Genauigkeitsraten erzielt - zumindest bei Bildclustern.

Die Entfernungsmetrik hängt stark davon ab, wie Ihre Daten organisiert sind. Die sichere Wahl ist die einfache euklidische Distanz. Wenn Sie jedoch wissen, dass Ihre Daten Mannigfaltigkeiten enthalten, sollten Sie die Punkte mit Hilfe von Kernelmethoden abbilden.

PS: Sie beziehen sich alle auf numerische Werte, nicht auf kategoriale. Ich bin mir nicht sicher, wie man kategoriale Daten gruppiert.

Hier finden Sie eine Zusammenfassung mehrerer Clustering-Algorithmen, mit deren Hilfe die Frage beantwortet werden kann

"Welche Clustertechnik sollte ich verwenden?"

Es gibt keine objektiv „richtigen“ Clustering - Algorithmus Ref

Clustering-Algorithmen können anhand ihres "Cluster-Modells" kategorisiert werden. Ein Algorithmus, der für eine bestimmte Art von Modell entwickelt wurde, schlägt in der Regel bei einer anderen Art von Modell fehl. Zum Beispiel kann k-means keine nicht konvexen Cluster finden, sondern nur kreisförmige Cluster.

Daher wird das Verständnis dieser "Cluster-Modelle" der Schlüssel zum Verständnis der Auswahl zwischen den verschiedenen Cluster-Algorithmen / Methoden. Typische Cluster-Modelle umfassen:

[1] Konnektivitätsmodelle: Erstellt Modelle, die auf der Distanzkonnektivität basieren. ZB hierarchisches Clustering. Wird verwendet, wenn wir unterschiedliche Partitionen basierend auf der Schnitthöhe des Baums benötigen. R-Funktion: hclust im Statistikpaket.

[2] Schwerpunktmodelle: Erstellt Modelle, indem jeder Cluster durch einen einzelnen Mittelwertvektor dargestellt wird. Wird verwendet, wenn eine klare Partitionierung erforderlich ist (im Gegensatz zum später beschriebenen Fuzzy-Clustering). R-Funktion: km bedeutet im Statistikpaket.

[3] Verteilungsmodelle: Erstellt Modelle, die auf statistischen Verteilungen basieren, z. B. multivariate Normalverteilungen, die vom Erwartungsmaximierungsalgorithmus verwendet werden. Wird verwendet, wenn Clusterformen willkürlich sein können, im Gegensatz zu k-means, das kreisförmige Cluster annimmt. R-Funktion: Emcluster im Emcluster-Paket.

[4] Dichtemodelle: Erstellt Modelle basierend auf Clustern als verbundene dichte Regionen im Datenraum. ZB DBSCAN und OPTICS. Wird verwendet, wenn Clusterformen beliebig sein können, im Gegensatz zu k-means, das kreisförmige Cluster annimmt. R-Funktion dbscan im Paket dbscan.

[5] Subraummodelle: Erstellt Modelle, die sowohl auf Clustermitgliedern als auch auf relevanten Attributen basieren. ZB Biklustering (auch als Co-Clustering oder Two-Mode-Clustering bezeichnet). Wird verwendet, wenn gleichzeitiges Zeilen- und Spaltenclustering erforderlich ist. R-Funktion Biclust im Biclust-Paket.

[6] Gruppenmodelle: Erstellt Modelle basierend auf den Gruppierungsinformationen. ZB kollaboratives Filtern (Recommender-Algorithmus). R-Funktion Recommender im recommenderlab-Paket.

[7] Graphbasierte Modelle: Erstellt Modelle basierend auf Clique. Community-Strukturerkennungsalgorithmen versuchen, dichte Untergraphen in gerichteten oder ungerichteten Graphen zu finden. ZB R-Funktion cluster_walktrap im igraph-Paket.

[8] Kohonen Self-Organizing Feature Map: Erstellt Modelle basierend auf einem neuronalen Netzwerk. R-Funktion som im kohonen-Paket.

[9] Spectral Clustering: Erstellt Modelle auf der Grundlage einer nicht konvexen Clusterstruktur oder wenn eine Messung des Zentrums keine geeignete Beschreibung des gesamten Clusters darstellt. R-Funktion specc im Kernlab-Paket.

[10] Subraum-Clustering: Bei hochdimensionalen Daten können Distanzfunktionen problematisch sein. Cluster-Modelle enthalten die relevanten Attribute für den Cluster. ZB HDDC-Funktion im R-Paket HDclassif.

[11] Sequenz-Clustering: Gruppieren Sie verwandte Sequenzen. rBlast-Paket.

[12] Affinitätsausbreitung: Erstellt Modelle auf der Grundlage der Nachrichtenübermittlung zwischen Datenpunkten. Es ist nicht erforderlich, die Anzahl der Cluster zu bestimmen, bevor der Algorithmus ausgeführt wird. Es ist besser für bestimmte Computer Vision- und computerbiologische Aufgaben, z. B. das Zusammenfügen von Bildern menschlicher Gesichter und das Identifizieren regulierter Transkripte, als k-means, Ref Rpackage APCluster.

[13] Stream-Clustering: Erstellt Modelle auf der Grundlage von Daten, die kontinuierlich eingehen, wie Telefonaufzeichnungen, Finanztransaktionen usw. ZB R-Paket BIRCH [ https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Dokument-Clustering (oder Text-Clustering): Erstellt Modelle auf Basis von SVD. Es wurde in der Themenextraktion verwendet. Beispiel: Carrot [ http://search.carrot2.org] ist eine Open-Source-Suchergebnissen-Clustering-Engine, mit der Dokumente in thematische Kategorien gruppiert werden können.

[15] Latentes Klassenmodell: Es verknüpft eine Menge beobachteter multivariater Variablen mit einer Menge latenter Variablen. Ökobilanzen können bei der kollaborativen Filterung verwendet werden. R function Recommender im recommenderlab-Paket verfügt über eine kollaborative Filterfunktion.

[16] Biclustering: Wird verwendet, um Zeilen und Spalten von Zwei-Modus-Daten gleichzeitig zu gruppieren. ZB R-Funktion Biclust im Paket Biclust.

[17] Soft Clustering (Fuzzy Clustering): Jedes Objekt gehört zu einem bestimmten Grad zu jedem Cluster. ZB R Fclust-Funktion im fclust-Paket.