Speicherbedarf von bedeutet Clustering

8

Kann mir jemand die Faktoren, die den Speicherbedarf von Means-Clustering beeinflussen, mit ein wenig Erklärung erklären?k

clustering k-means Martin
quelle
4
k Mittel sind NP-hart, daher gibt es viele Heuristiken, die sich auch im Ressourcenverbrauch erheblich unterscheiden. Interessieren Sie sich für einen bestimmten Algorithmus?
2
Beziehen Sie sich auf den Lloyd's-Algorithmus? In diesem Fall wäre der Speicherbedarf für eine Standardimplementierung meines Erachtens O (log k * n), da Sie für den Aktualisierungsschritt eine Liste von (Punkt-, Cluster-) Paaren speichern müssten. Da k normalerweise klein ist, könnte man davon ausgehen, dass man normalerweise nur einen kurzen Punkt für jeden Punkt speichert, aber ich habe mir keine spezifischen Implementierungen angesehen.
rm999
Sie benötigen wirklich nur einen Zwischenspeicher der Größe , wenn Sie bereit sind, die Daten auf der Festplatte zu speichern und sie in jedem Durchgang zu scannen. Dies ist natürlich sehr langsam, und daher gibt es Kompromisse. Was genau haben Sie gesucht? k
Suresh Venkatasubramanian

Antworten:

1

Algorithmen wie Lloyds können nur mit Gleitkommawerten implementiert werden . Der MacQueens k-means-Algorithmus sollte nur Speicher benötigen .k ≤ ( d + 1 )k⋅(2⋅d+1)k⋅(d+1)

Da die meisten Benutzer jedoch wissen möchten, welcher Punkt zu welchem ​​Cluster gehört, verwendet fast jede Implementierung, die Sie finden, -Speicher.O(n+k⋅d)

Mit anderen Worten ist der durch k-Mittel verwendete Speicher im Wesentlichen die Ausgangsdatengröße .

Hat aufgehört - Anony-Mousse
quelle
0

Ich bin kürzlich auf eine scipy-Implementierung des k-means-Algorithmus in scipy.cluster.vq.py gestoßen

Notes
-----
This could be faster when number of codebooks is small, but it
becomes a real memory hog when codebook is large. It requires
N by M by O storage where N=number of obs, M = number of
features, and O = number of codes.

quelle