Persyaratan memori berarti pengelompokan

8

Adakah yang bisa memberitahu saya faktor-faktor yang mempengaruhi persyaratan memori berarti pengelompokan dengan sedikit penjelasan?k

clustering k-means Martin
sumber
4
k -berarti NP-keras, jadi ada banyak heuristik yang berbeda secara signifikan, juga dalam konsumsi sumber daya; apakah Anda tertarik pada beberapa algoritma spesifik?
2
Apakah Anda mengacu pada algoritma Lloyd? Jika demikian, saya yakin persyaratan memori untuk implementasi standar adalah O (log k * n) karena Anda harus menyimpan daftar pasangan (titik, gugus) untuk langkah pembaruan. Karena k biasanya kecil, tebakan saya adalah Anda biasanya dapat menyimpan hanya kependekan untuk setiap poin, tetapi saya belum melihat implementasi spesifik.
rm999
Anda hanya benar-benar membutuhkan penyimpanan perantara ukuran , jika Anda bersedia menyimpan data pada disk dan memindai di setiap pass. Tentu saja, ini sangat lambat, sehingga ada pengorbanan yang terlibat. Apa yang Anda cari secara spesifik. k
Suresh Venkatasubramanian

Jawaban:

1

Algoritma seperti Lloyds dapat diimplementasikan dengan hanya menggunakan nilai floating point memori. Algoritma MacQueens k-means seharusnya hanya membutuhkan memori .k⋅(2⋅d+1)k⋅(d+1)

Namun, karena sebagian besar pengguna ingin mengetahui titik mana yang termasuk dalam cluster mana, hampir setiap implementasi yang Anda temukan akan menggunakan memori .HAI(n+k⋅d)

Dengan kata lain, penggunaan memori dengan k-means pada dasarnya adalah ukuran data output .

Memiliki QUIT - Anony-Mousse
sumber
0

Baru-baru ini saya menemukan sebuah catatan implementasi scipy dari algoritma k-means di scipy.cluster.vq.py

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.

sumber