Menginisialisasi pusat K-means dengan cara subsampel acak dari dataset?

Jika saya memiliki dataset tertentu, seberapa pintarkah untuk menginisialisasi pusat cluster dengan menggunakan sampel acak dari dataset tersebut?

Misalnya, saya ingin 5 clusters. Saya 5 random sampleskatakan, size=20%dari dataset asli. Bisakah saya mengambil rata-rata dari masing-masing 5 sampel acak ini dan menggunakan rata-rata tersebut sebagai 5 pusat klaster awal saya? Saya tidak tahu di mana saya membaca ini tetapi saya ingin tahu apa yang kalian pikirkan tentang ide itu.

UPDATE: Silakan lihat utas ini Menginisialisasi K-means clustering: apa metode yang ada? untuk diskusi umum tentang berbagai metode inisialisasi.

Jika kamu secara acak membagi sampel menjadi 5 subsamples, berarti 5 Anda hampir akan bertepatan. Apa arti dari membuat titik-titik dekat seperti itu menjadi pusat-pusat cluster awal?

Dalam banyak implementasi K-means, pemilihan default pusat cluster awal didasarkan pada ide yang berlawanan: untuk menemukan 5 poin yang paling berjauhan dan menjadikannya pusat awal. Anda mungkin bertanya apa yang mungkin menjadi cara untuk menemukan titik-titik yang jauh itu? Inilah yang dilakukan K-means SPSS untuk itu:

Ambil k case (titik) dari dataset sebagai pusat awal. Semua kasus lainnya sedang diperiksa kemampuannya untuk menggantikan mereka sebagai pusat awal, dengan ketentuan sebagai berikut:

• a) Jika kasing jauh dari pusat terdekat dengan jarak antara dua paling dekat satu sama lain, kasing menggantikan pusat dua yang terakhir yang lebih dekat.
• b) Jika kasing jauh dari pusat 2 yang paling dekat dengan jarak dari pusat ke terdekat dan pusat paling dekat dengan yang terakhir ini, kasing ini menggantikan pusat terdekat dengan itu.

Jika kondisi (a) tidak terpenuhi, kondisi (b) diperiksa; jika tidak puas maka kasing tidak menjadi pusat. Sebagai hasil dari run through cases tersebut kami mendapatkan k maksimal case di cloud yang menjadi pusat awal. Hasil algo ini, meskipun cukup kuat, tidak sepenuhnya tidak sensitif terhadap pilihan mulai dari "setiap k kasus" dan untuk urutan kasus dalam dataset; jadi, beberapa upaya awal acak masih diterima, karena selalu demikian halnya dengan K-means.

Lihat jawaban saya dengan daftar metode inisialisasi populer untuk k-means. Metode pemisahan menjadi subsampel acak (dikritik di sini oleh saya dan orang lain) serta metode yang dijelaskan yang digunakan oleh SPSS - termasuk dalam daftar juga.

Berarti akan terlalu mirip. Anda bisa juga menemukan mean kumpulan data, dan kemudian menempatkan centroid awal dalam lingkaran kecil / bola di sekitar mean ini.

Jika Anda ingin melihat beberapa skema inisialisasi suara untuk k-means, lihatlah k-means ++. Mereka telah menemukan metode yang cukup pintar untuk menabur k-means.

• Arthur, D. dan Vassilvitskii, S. (2007).
  k-means ++: keuntungan dari penyemaian yang hati-hati ".
  Prosiding simposium tahunan ACM-SIAM kedelapan belas pada algoritma Discrete

Slide penulis: http://www.ima.umn.edu/~iwen/REU/BATS-Means.pdf

Menggunakan alat sampel acak akan memberi Anda kebalikan dari yang Anda butuhkan, seperti yang ditunjukkan ttnphns dalam komentarnya. Apa yang kita butuhkan adalah cara untuk menemukan titik data yang cukup jauh satu sama lain.

Idealnya, Anda bisa beralih di semua titik, menemukan jarak di antara mereka, menentukan di mana jarak adalah yang terbesar ...

Bukan untuk menghindari niat OP, tapi saya pikir "solusi" dibangun ke dalam algoritma k-means. Kami melakukan beberapa iterasi dan menghitung ulang centroid cluster berdasarkan iterasi sebelumnya. Kami juga biasanya menjalankan algoritma kmeans beberapa kali (dengan nilai awal acak), dan membandingkan hasilnya.

Jika seseorang memiliki pengetahuan apriori , pengetahuan domain, maka itu dapat mengarah pada metode yang lebih baik untuk mengidentifikasi di mana pusat-pusat cluster awal seharusnya. Jika tidak, itu mungkin masalah memilih titik data acak sebagai nilai awal dan kemudian menggunakan beberapa proses dan beberapa iterasi per proses.

$k$