K-means cepat seperti algoritma untuk 10 ^ 10 poin?

14

Saya mencari untuk melakukan k-means pengelompokan pada set poin 10-dimensi. Tangkapan: ada 10 ^ 10 poin .

Saya hanya mencari pusat dan ukuran cluster terbesar (misalkan 10 hingga 100 cluster); Saya tidak peduli tentang tujuan dari setiap titik. Menggunakan k-means secara spesifik tidak penting; Saya hanya mencari efek yang sama, setiap perkiraan k-means atau algoritma terkait akan bagus (minibatch-SGD berarti, ...). Karena GMM dalam arti masalah yang sama dengan k-means, melakukan GMM pada data ukuran yang sama juga menarik.

Pada skala ini, melakukan subsampling data mungkin tidak mengubah hasilnya secara signifikan: kemungkinan menemukan 10 klaster teratas yang sama dengan menggunakan sampel 1/1000 data sangat baik. Tetapi bahkan kemudian, itu adalah masalah 10 ^ 6 poin yang berada di / di luar batas penurut.

clustering k-means Alex I
sumber
1
Beberapa algoritma dijelaskan dalam buku "Mining of Massive Datasets", yang dapat Anda unduh secara gratis di sini . Baca Bab 7 "Clustering".
lanenok

Jawaban:

12

k-means didasarkan pada rata-rata .

Ini memodelkan cluster menggunakan cara, dan dengan demikian peningkatan dengan menambahkan lebih banyak data adalah marjinal. Kesalahan estimasi rata-rata berkurang dengan 1 / sqrt (n); jadi menambahkan lebih banyak data terbayar semakin sedikit ...

Strategi untuk data sebesar itu selalu berputar di sekitar pengambilan sampel:

Jika Anda ingin runtime sublinear, Anda harus melakukan sampling!

Bahkan, Mini-Batch-Kmeans dll melakukan hal ini: sampel berulang kali dari kumpulan data.

Namun, pengambilan sampel (khususnya pengambilan sampel yang tidak bias) juga tidak gratis ... biasanya, Anda harus membaca data Anda secara linear untuk sampel, karena Anda tidak mendapatkan akses acak ke catatan individual.

Saya akan menggunakan algoritma MacQueen. Ini online; secara default ia melakukan satu kali melewati data Anda (meskipun populer untuk iterate ini). Ini tidak mudah untuk didistribusikan, tetapi saya kira Anda mampu membaca data Anda secara linear sebanyak 10 kali dari SSD?

Memiliki QUIT - Anony-Mousse
sumber
Saya tidak tahu tentang algoritma online MacQueen! Apakah biasanya mendapatkan hasil yang sama dengan K-means "klasik"? Bagaimana dengan menggunakan sampling reservoir sebagai gantinya? Dengan cara itu OP memiliki sampel untuk menjalankan kembali K-means jika beberapa nilai K harus diuji.
Victor Ma
6

Sebagai catatan samping perhatikan bahwa menggunakan K-means untuk data 10D mungkin berakhir di tempat sesuai dengan kutukan dimensi. Tentu saja itu sedikit berbeda sesuai dengan sifat data tetapi ketika saya mencoba untuk menentukan ambang batas di mana K-Means mulai berperilaku aneh mengenai dimensi, saya mendapat sesuatu seperti 7D. Setelah 7 dimensi mulai kehilangan cluster yang benar (data saya secara manual dihasilkan sesuai dengan 4 distribusi Gaussian yang terpisah dan saya menggunakan fungsi kmlan MATLAB untuk percobaan kecil saya).

Kasra Manshaei
sumber
Ini mungkin dan, tentu saja, selalu bergantung pada data. Namun, mengingat bahwa poster memiliki 10 ^ 10 (mungkin independen) sampel, tampaknya 10 dimensi tidak akan menjadi masalah besar di sini.
Ryan J. Smith
2
Terima kasih atas komentar Anda @ RyanJ.Smith. komentar Anda persis di arah yang sama dengan saya. Saya hanya tidak melihat apa pun mengenai masalah ini di pos. Dan tentang nr sampel; namun dia memiliki banyak titik sampel yang mungkin masih terjebak dalam masalah dimensionalitas. Saya pikir Anda memperdebatkan sisi berlawanan dari Masalah Ukuran Sampel Rendah yang menurut saya tidak valid. Jika dia memiliki data dimensi tinggi, ukuran sampel yang rendah akan menjadi masalah tetapi saya pikir sejumlah besar data tidak berarti apa-apa.
Kasra Manshaei
10 dimensi belum banyak.
Memiliki QUIT - Anony-Mousse
1
Bagaimana Anda menentukan teman saya? apa yang saya katakan adalah hasil percobaan yang dirancang untuk menjawab pertanyaan seperti itu namun TIDAK BISA dijawab secara umum! Apa sebenarnya "banyak" dalam komentar Anda? itu tergantung pada banyak keadaan seperti yang saya sebutkan dalam jawaban saya. dalam beberapa situasi 10D bisa bermasalah.
Kasra Manshaei