Rechenkomplexität von Clustering-Algorithmen

8

Mein Wunsch ist es, die zeitliche Komplexität mehrerer Clustering-Ansätze zu beschreiben. Angenommen, wir haben Datenpunkte im dimensionalen Raum. $n$ $m$

Nehmen wir weiter an, dass die paarweise Unähnlichkeitsmatrix von Dimensionen bereits berechnet wurde und dass wir bereits Schritte ausgegeben haben . Was ist dann die zeitliche Komplexität gerade von $\Delta$ $n\times n$ $O(m\cdot n^2)$

hierarchisches Clustering (HC) unter Verwendung der Ward-Verknüpfung
HC mit vollständiger Verknüpfung
HC unter Verwendung einer durchschnittlichen Verknüpfung
HC mit einfacher Verknüpfung
$k$ medoid Ansatz
$k$ bedeutet Ansatz

Gibt es einen Vorteil, wenn die Unähnlichkeitsmatrix noch nicht berechnet wurde? Soweit ich weiß, ist es für den HC- und Medoid-Ansatz notwendig, aber nicht für Mittel? $\Delta$ $k$ $k$

Danke für deine Hilfe!

lg.learning clustering Lan
quelle

Dies ist eine CS-Frage, keine Frage zur statistischen Analyse. Es wäre perfekt für die SE-Site mit Algorithmen geeignet, die sich derzeit in der Vorschlagsphase unter area51.stackexchange.com/proposals/5120/… befinden .

Whuber

Sie können die Distanzmatrix auch in ein kantengewichtetes Diagramm umwandeln und Diagrammclustermethoden anwenden (z. B. den Markov CLustering-Algorithmus von van Dongen oder meinen Clustering-Algorithmus für die Suche nach eingeschränkten Nachbarschaften). Dies ist jedoch eher eine ODER-Frage als eine einfache Algorithmusfrage (nicht zu Erwähnen Sie, dass Graph-Clustering-Algorithmen im Allgemeinen für dichte Graphen ungeeignet sind, was den Zweck, die Distanzmatrix in einen Graphen

Andrew D. King

7

Single Linkage Clustering entspricht fast dem Minimum von Spanning Tree in vollständigen Diagrammen, einfache O (n ^ 2) -Zeit. Informationen zur O (n ^ 2) -Zeit für andere agglomerative Clustering-Methoden (einschließlich der ziemlich sicheren und vollständigen Verknüpfung) finden Sie in meinem Artikel "Schnelles hierarchisches Clustering und andere Anwendungen dynamischer engster Paare", SODA '98 und JEA '00.

David Eppstein
quelle

6

$k$ $O(kn)$ $k$ $k$

$k$ $k$

Suresh Venkat
quelle

3

Warum ist es "nicht sinnvoll"? Es gibt mehrere neuere Arbeiten zur Anzahl der Iterationen, bis k-means konvergiert (was bedeutet, dass eine Iteration die Clusterbildung unverändert lässt) oder bis sie ein gewünschtes Approximationsverhältnis erreicht.

Jeffs

Sie nehmen jedoch entweder eine Eigenschaft der Daten oder eine bestimmte Variante des Algorithmus an (wie die k-means ++ - Methode oder die geglättete Variante). Die Frage, wie ich sie las, schien sich eher auf generische Varianten zu beziehen. Ihr Punkt ist jedoch gut aufgenommen.

Suresh Venkat

Rechenkomplexität von Clustering-Algorithmen

Antworten: