Ich habe eine Liste von undurchsichtigen Objekten. Ich kann nur den Abstand zwischen ihnen berechnen (nicht wahr, nur die Bedingungen für das Problem festlegen):
%Vor%Ich möchte diese Objekte gruppieren. Ich möchte die Anzahl der Cluster steuern und möchte, dass sich "close" -Objekte im selben Cluster befinden:
%Vor%Kann jemand einige Clustering-Algorithmen (je einfacher, desto besser!) oder Bibliotheken, die mir helfen können, vorschlagen (und verlinken?)?
Erläuterung Die meisten Clustering-Algorithmen erfordern, dass die Objekte in einem N-dimensionalen Raum angeordnet werden. Dieser Raum wird verwendet, um "Zentroide" von Clustern zu finden. In meinem Fall weiß ich weder, was N ist, noch weiß ich, wie man ein Koordinatensystem aus den Objekten extrahiert. Ich weiß nur, wie weit 2 Objekte entfernt sind. Ich würde gerne einen guten Cluster-Algorithmus finden, der nur diese Informationen verwendet.
Stellen Sie sich vor, Sie gruppieren sich basierend auf dem "Geruch" eines Objekts. Sie wissen nicht, wie Sie auf einer 2D-Ebene "riechen", aber Sie wissen, ob zwei Gerüche ähnlich sind oder nicht.Ich glaube, Sie suchen K-Medoids . Es ist wie K-bedeutet, dass Sie die Anzahl der Cluster, K , im Voraus angeben, aber es ist nicht erforderlich, dass Sie die Objekte, die Sie gruppieren, wie K- bedeutet das.
Stattdessen hat jeder Cluster ein repräsentatives Medoid , das das Mitglied des Clusters ist, das der Mitte am nächsten ist. Man könnte es sich als eine Version von K vorstellen, die "Mediane" statt "Mittel" findet. Alles, was Sie brauchen, ist eine Entfernungsmetrik, um Dinge zusammenzufassen, und ich habe diese in einigen meiner eigenen Arbeiten aus genau den gleichen Gründen verwendet, die Sie angeben.
Naive K-medoids ist nicht der schnellste Algorithmus, aber es gibt schnelle Varianten, die wahrscheinlich gut genug für Ihre Zwecke sind. Hier sind Beschreibungen der Algorithmen und Links zur Dokumentation ihrer Implementierungen in R :
Wenn Sie weitere Informationen benötigen, hier ist ein Papier , das einen Überblick über diese und andere gibt K-Medoids Methoden.
Hier ist ein Überblick für einen Clustering-Algorithmus, der nicht die K-means-Anforderung zum Auffinden eines Schwerpunkts hat.
Dieser Algorithmus wird die Objekte sicher gruppieren. Aber seine Laufzeit ist O (n ^ 2) . Außerdem wird es von diesen ersten n Punkten ausgewählt.
Kann jemand dies verbessern (bessere Laufzeitperfektion, weniger abhängig von anfänglichen Entscheidungen)? Ich würde gerne deine Ideen sehen.
Hier ist ein schneller Algorithmus.
%Vor%Alternativ lesen Sie die Wikipedia-Seite . K-Means-Clustering ist eine gute Wahl:
Der K-Means-Algorithmus weist jeden Punkt dem Cluster zu, dessen Zentrum (auch Centroid genannt) am nächsten ist. Das Zentrum ist der Durchschnitt aller Punkte im Cluster - das heißt, seine Koordinaten sind das arithmetische Mittel für jede Dimension getrennt über alle Punkte im Cluster.
Die Algorithmusschritte sind:
%Vor%Die Hauptvorteile dieses Algorithmus sind seine Einfachheit und Geschwindigkeit welche erlaubt es, auf großen Datensätzen zu laufen. Sein Nachteil ist, dass es nicht so ist das gleiche Ergebnis mit jedem Lauf erzielen, da die resultierenden Cluster davon abhängen die anfänglichen zufälligen Zuordnungen. Es minimiert die Varianz innerhalb des Clusters, aber stellt nicht sicher, dass das Ergebnis a hat globales Minimum der Varianz. Ein weiterer Nachteil ist die Forderung nach das Konzept eines Mittelwerts, um definierbar zu sein was nicht immer der Fall ist. Für solch Datasets die K-Medoids-Variante ist angebracht.
Wie wäre es mit diesem Ansatz:
Ich denke, dass dieser Algorithmus Ihnen ein ziemlich gutes Clustering geben sollte, obwohl die Effizienz ziemlich schlecht sein könnte. Um die Effizienz zu verbessern, können Sie Schritt 3 so ändern, dass Sie den Mindestabstand zu dem ursprünglichen Objekt, das den Cluster gestartet hat, und nicht den durchschnittlichen Abstand zu allen bereits im Cluster vorhandenen Objekten finden.
Bei der phylogenetischen DNA-Sequenzanalyse wird regelmäßig hierarchisches Clustering auf Textstrings mit [Ausrichtungs] -Abstandsmatrizen verwendet. Hier ist ein nettes R-Tutorial zum Clustering:
(Verknüpfung: Gehen Sie direkt zum Abschnitt "Hierarchische Agglomeration" ...)
Hier sind einige andere [Sprach-] Bibliotheken:
Dieser Ansatz könnte helfen zu bestimmen, wie viele [k] "natürliche" Cluster es gibt und welche Objekte als Wurzeln für die k-means verwendet werden.
Tags und Links algorithm language-agnostic cluster-analysis