Clustering-Algorithmus für nicht dimensionale Daten

12

Ich habe einen Datensatz mit Tausenden von Punkten und ein Mittel zum Messen des Abstands zwischen zwei beliebigen Punkten, aber die Datenpunkte haben keine Dimensionalität. Ich möchte, dass ein Algorithmus Cluster-Zentren in diesem Datensatz findet. Ich stelle mir vor, dass ein Clusterzentrum aus mehreren Datenpunkten und einer Toleranz besteht, da die Daten keine Dimensionen haben. Die Zugehörigkeit zum Cluster wird möglicherweise durch den Durchschnitt der Entfernung eines Datenpunkts zu jedem Datenpunkt im Clusterzentrum bestimmt.

bitte verzeihen sie mir, wenn diese frage eine bekannte lösung hat, ich weiß sehr wenig über diese art von problem! Meine (sehr begrenzte) Forschung hat nur Clustering-Algorithmen für dimensionale Daten ergeben, aber ich entschuldige mich im Voraus, wenn ich etwas Offensichtliches verpasst habe.

Danke!

Lackdose
quelle
Warum macht Nichtdimensionalität dieses Problem besonders?
Raphael
1
Einige Algorithmen, die ich für das Clustering gesehen habe (eigentlich nur k-means), erfordern die Erzeugung von zufälligen Datenpunkten als Seeds, was mit dimensionslosen Daten nicht möglich ist. Die besondere Anforderung besteht also darin, dass die Cluster-Zentren durch einen Satz vorhandener Datenpunkte (möglicherweise gewichtet) dargestellt werden müssen.
Paintcan

Antworten:

15

Wenn es sich bei der Abstandsfunktion um eine Metrik handelt, können Sie entweder Mittelwert-Clustering (bei dem der maximale Radius eines Balls minimiert wird) oder k- Mittelwert-Clustering (bei dem die Summe der Abstände zu den Mittelwerten des Clusters minimiert wird) verwenden. Das Clustering von k- Zentren ist einfach: Wählen Sie einfach die k-am weitesten entfernten Punkte aus, und Sie erhalten garantiert eine 2-Approximation über Dreiecksungleichung (dies ist ein altes Ergebnis, das Gonzalez zu verdanken hat).kkkk

Für median Clustering gab es eine Menge Arbeit, zu viel, um sie hier zu wiederholen. Michael Shindler von der UCLA hat einen guten Überblick über die wichtigsten Ideen.k

Beide Probleme sind im Allgemeinen NP-schwer und können nur schwer auf einen beliebigen Faktor angenähert werden. Beachten Sie, dass sich die Annäherbarkeit erheblich verschlechtert, wenn Sie die Bedingung fallen lassen, dass es sich um eine Metrik handelt.

Ein weiterer heuristischer Ansatz, der für Ihre Anwendung in Frage kommt, ist die Verwendung einer Technik wie MDS (Multidimensional Scaling), um Ihre Distanzmatrix in einen euklidischen Raum einzubetten, und dann eine der vielen verschiedenen euklidischen Clustermethoden (oder sogar Mittel-Clustering) ). Wenn Sie sicher sind, dass Ihre Distanzfunktion eine Metrik ist, können Sie eine etwas intelligentere Einbettung in den euklidischen Raum vornehmen und eine nachweisbare (wenn auch schwache) Garantie für die Qualität Ihrer Antwort erhalten.k

Wie bei den meisten Clustering-Problemen hängt Ihre endgültige Auswahl letztendlich von der Anwendung, Ihrer Datengröße usw. ab.

Suresh Venkat
quelle
3
Vielen Dank für den schnellen und übersichtlichen Überblick. Ich benötige mindestens ein paar Tage, um festzustellen, ob Sie meine Frage beantwortet haben. Es scheint, dass ich eine Menge lernen muss, bevor ich mein Problem ausreichend verstehe :)
paintcan
5

Es gibt auch Korrelationscluster , die als Eingabeinformation für jedes Elementpaar angeben, ob sie zu demselben Cluster oder zu verschiedenen Clustern gehören.

Warren Schudy
quelle
Ja, das ist ein weiteres gutes Beispiel. Und natürlich ist Warren ein Experte dafür! Ich weiß nicht, ob der OP-Eingang +/- war oder über die Schwellenwertberechnung konvertiert werden konnte. Wenn ja, ist dies definitiv eine praktikable Option.
Suresh Venkat
5

Wenn Sie nur nach einer guten empirischen Leistung suchen, funktioniert der Affinitätsausbreitungsalgorithmus normalerweise besser als k-Mediane. Es gibt Code in mehreren Sprachen und Veröffentlichungen, die den Algorithmus detaillierter beschreiben, finden Sie hier: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

ichs(ich,cich)

scichcichs(ich,ich)

dan_x
quelle
5

Ihre Frage scheint zu implizieren, dass Sie nach einem Algorithmus mit angemessener Rechenzeit suchen. Angesichts der Größe Ihrer Scheitelpunkte (oder Punkte) müsste eine gewichtete Diagrammdarstellung Ihrer Daten erstellt und das Diagramm mithilfe des Markov-Cluster-Algorithmus (MCL) geclustert werden.

http://www.micans.org/mcl/

MCL basiert auf zufälligen Schritten durch gewichtete und ungewichtete Graphen, um dichte Untergraphen zu finden. Es ist in der Lage, große Diagramme zu verarbeiten und wurde in vielen bekannten, häufig verwendeten bioinformatischen Programmen (wie BLAST) verwendet. -Boucher

Christina Boucher
quelle
1

Man betrachte den Algorithmus für den nächsten Nachbarn .

Raphael
quelle
Raphael, der k-NN-Algorithmus ist eigentlich kein Clustering-Algorithmus, oder? es sei denn, Sie ziehen wiederholt die k Nachbarn eines Knotens heraus?
Suresh Venkat
k