k-means || alias Scalable K-Means ++

12

Bahman Bahmani et al. memperkenalkan k-means ||, yang merupakan versi lebih cepat dari k-means ++.

Inisialisasi k-means ||

Algoritma ini diambil dari halaman 4 makalah mereka , Bahmani, B., Moseley, B., Vattani, A., Kumar, R., & Vassilvitskii, S. (2012). K-means yang dapat diskalakan ++. Prosiding Endowment VLDB , 5 (7), 622-633.

Sayangnya saya tidak mengerti huruf-huruf Yunani yang mewah itu, jadi saya perlu bantuan untuk memahami bagaimana ini bekerja. Sejauh yang saya pahami, algoritma ini adalah versi perbaikan dari k-means ++, dan menggunakan oversampling, untuk mengurangi jumlah iterasi: k-means ++ harus mengulangi kali, di mana adalah jumlah cluster yang diinginkan.kkk

Saya mendapat penjelasan yang sangat bagus melalui contoh konkret tentang cara kerja k-means ++, jadi saya akan menggunakan contoh yang sama lagi.

Contoh

Saya memiliki dataset berikut:

(7,1), (3,4), (1,5), (5,8), (1,3), (7,8), (8,2), (5,9), (8) , 0)

k=3 (jumlah cluster yang diinginkan)

=2 (faktor oversampling)

Contoh data yang ditetapkan untuk k-means ||

Saya mulai menghitungnya, tetapi saya tidak yakin apakah saya melakukannya dengan benar, dan tidak tahu tentang Langkah 2, 4, atau 5.

  • Langkah 1: sampel secara seragam secara acak dariXCX

    Katakanlah centroid pertama adalah (sama seperti dalam k-means ++)(8,0)

  • Langkah 2:ψϕX(C)

    tidak ada ide

  • Langkah 3:

    • d2(x,C)=[2,41,74,73,58,65,4,90]

      Kami menghitung jarak kuadrat ke pusat terdekat ke setiap titik. Dalam hal ini kami hanya memiliki satu pusat sejauh ini .(8,0)

    • d2(x,C)=[4,81,148,146,116,130,8,180]

      (Karena dalam hal ini.)=2

    • cumulative d2(x,C)=[4,85,233,379,495,625,633,813]

      Pilih angka acak dalam interval . Katakanlah Anda memilih dan . Mereka berada dalam kisaran dan yang masing-masing sesuai dengan item ke-4 dan ke-8.[ 0 , 813 ) 246.90 659.42 [ 379 , 495 ) [ 633 , 813 )=2[0,813)246.90659.42[379,495)[633,813)

    • Ulangi kali, tetapi apa itu (dihitung pada Langkah 2) dalam kasus ini? ψO(logψ)ψ

  • Langkah 4: Untuk , atur menjadi jumlah poin di lebih dekat ke daripada titik lain di .w x X x CxCwxXxC
  • Langkah 5: Sertakan poin-poin tertimbang dalam ke dalam cluster. kCk

Bantuan apa pun secara umum atau dalam contoh khusus ini akan bagus.

pengguna1930254
sumber

Jawaban:

10

poin data: (7,1), (3,4), (1,5), (5,8), (1,3), (7,8), (8,2), (5,9) , (8,0)

l = 2 // faktor oversampling

k = 3 // tidak. cluster yang diinginkan

Langkah 1:

Misalkan centroid pertama adalah adalah . { c 1 } = { ( 8 , 0 ) } X = { x 1C{c1}={(8,0)}X={x1,x2,x3,x4,x5,x6,x7,x8}={(7,1),(3,4),(1,5),(5,8),(1,3),(7,8),(8,2),(5,9)}

Langkah 2:

ϕX(C) adalah jumlah dari semua jarak 2-norma terkecil (jarak euclidean) dari semua titik dari himpunan ke semua titik dari . Dengan kata lain, untuk setiap titik di menemukan jarak ke titik terdekat di , di menghitung akhirnya jumlah dari semua jarak minimal, satu untuk setiap titik di .XCXCX

Ditunjukkan dengan sebagai jarak dari ke titik terdekat di . Kami kemudian memiliki .dC2(xi)xiCψ=i=1ndC2(xi)

Pada langkah 2, berisi elemen tunggal (lihat langkah 1), dan adalah himpunan semua elemen. Jadi pada langkah ini, hanyalah jarak antara titik dalam dan . Dengan demikian . X d 2 C (CXdC2(xi)Cxiϕ=i=1n||xic||2

ψ=i=1nd2(xi,c1)=1.41+6.4+8.6+8.54+7.61+8.06+2+9.4=52.128 log(ψ)=log(52.128)=3.95=4(rounded)

Perhatikan bahwa pada langkah 3, rumus umum diterapkan karena akan berisi lebih dari satu titik.C

Langkah 3:

The untuk loop dieksekusi untuk yang sebelumnya dihitung.log(ψ)

Gambar tidak seperti yang Anda mengerti. Gambar-gambar yang independen, yang berarti Anda akan mengeksekusi hasil seri untuk setiap titik di . Jadi, untuk setiap titik dalam , dilambangkan sebagai , hitung probabilitas dari . Di sini Anda memiliki faktor diberikan sebagai parameter, adalah jarak ke pusat terdekat, dan dijelaskan pada langkah 2.X x i p x = l d 2XXxipx=ld2(x,C)/ϕX(C)ld2(x,C)ϕX(C)

Algoritma ini sederhana:

  • iterate di untuk menemukan semuaXxi
  • untuk setiap hitungxipxi
  • menghasilkan angka yang seragam dalam , jika lebih kecil dari pilih untuk membentuk[0,1]pxiC
  • setelah Anda selesai menggambar semua termasuk poin yang dipilih dari keCC

Perhatikan bahwa pada setiap langkah 3 dieksekusi dalam iterasi (baris 3 dari algoritma asli) Anda berharap untuk memilih poin dari (ini dengan mudah ditampilkan menulis langsung rumus untuk harapan).lX

for(int i=0; i<4; i++) {

  // compute d2 for each x_i
  int[] psi = new int[X.size()];
  for(int i=0; i<X.size(); i++) {
    double min = Double.POSITIVE_INFINITY;
    for(int j=0; j<C.size(); j++) {
      if(min>d2(x[i],c[j])) min = norm2(x[i],c[j]);
    }
    psi[i]=min;
  }

  // compute psi
  double phi_c = 0;
  for(int i=0; i<X.size(); i++) phi_c += psi[i];

  // do the drawings
  for(int i=0; i<X.size(); i++) {
    double p_x = l*psi[i]/phi;
    if(p_x >= Random.nextDouble()) {
      C.add(x[i]);
      X.remove(x[i]);
    }
  }
}
// in the end we have C with all centroid candidates
return C;

Langkah 4:

Sebuah algoritma sederhana untuk itu adalah untuk menciptakan vektor ukuran sama dengan jumlah elemen dalam , dan menginisialisasi semua nilai dengan . Sekarang iterasi di (elemen tidak dipilih sebagai centroid), dan untuk setiap , cari indeks dari centroid terdekat (elemen dari ) dan kenaikan dengan . Pada akhirnya Anda akan memiliki vektor dihitung dengan benar.C 0 X x iX j C w [ j ] 1 wwC0XxiXjCw[j]1w

double[] w = new double[C.size()]; // by default all are zero
for(int i=0; i<X.size(); i++) {
  double min = norm2(X[i], C[0]);
  double index = 0;
  for(int j=1; j<C.size(); j++) {
    if(min>norm2(X[i],C[j])) {
      min = norm2(X[i],C[j]);
      index = j;
    }
  }
  // we found the minimum index, so we increment corresp. weight
  w[index]++;
}

Langkah 5:

Mengingat bobot dihitung pada langkah sebelumnya, Anda mengikuti algoritma kmeans ++ untuk memilih hanya poin sebagai awal centroid. Dengan demikian, Anda akan mengeksekusi untuk loop, pada setiap loop memilih elemen tunggal, yang diambil secara acak dengan probabilitas untuk setiap elemen menjadi . Pada setiap langkah Anda memilih satu elemen, dan menghapusnya dari kandidat, juga menghapus bobot yang sesuai.k k p ( i ) = w ( i ) / m j = 1 w jwkkp(i)=w(i)/j=1mwj

for(int k=0; k<K; k++) {
  // select one centroid from candidates, randomly, 
  // weighted by w
  // see kmeans++ and you first idea (which is wrong for step 3)
  ... 
}  

Semua langkah sebelumnya berlanjut, seperti dalam kasus kmeans ++, dengan aliran normal dari algoritma clustering

Saya harap lebih jelas sekarang.

[Nanti, edit nanti]

Saya juga menemukan presentasi yang dibuat oleh penulis, di mana Anda tidak dapat dengan jelas bahwa pada setiap iterasi beberapa poin mungkin dipilih. Presentasinya ada di sini .

[Kemudian edit masalah @ pera]

Jelas bahwa tergantung pada data dan masalah yang Anda ajukan akan menjadi masalah nyata jika algoritme akan dieksekusi pada satu host / mesin / komputer. Namun Anda harus perhatikan bahwa varian kmanans clustering ini didedikasikan untuk masalah besar, dan untuk berjalan pada sistem terdistribusi. Terlebih lagi, para penulis, dalam paragraf berikut di atas deskripsi algoritma menyatakan sebagai berikut:log(ψ)

Perhatikan bahwa ukuran secara signifikan lebih kecil dari ukuran input; Oleh karena itu reclustering dapat dilakukan dengan cepat. Misalnya, di MapReduce, karena jumlah pusat kecil, mereka semua dapat ditugaskan ke satu mesin dan algoritma aproksimasi yang dapat dibuktikan (seperti k-means ++) dapat digunakan untuk mengelompokkan titik-titik untuk mendapatkan pusat k. Implementasi MapReduce dari Algoritma 2 dibahas dalam Bagian 3.5. Meskipun algoritma kami sangat sederhana dan cocok untuk implementasi paralel alami (dalam ), bagian yang menantang adalah untuk menunjukkan bahwa ia memiliki jaminan yang dapat dibuktikan.l o g ( ψ )Clog(ψ)

Hal lain yang perlu diperhatikan adalah catatan berikut pada halaman yang sama yang menyatakan:

Dalam praktiknya, hasil percobaan kami di Bagian 5 menunjukkan bahwa hanya beberapa putaran yang cukup untuk mencapai solusi yang baik.

Yang berarti Anda dapat menjalankan algoritme bukan untuk waktu , tetapi untuk waktu konstan yang diberikan.log(ψ)

rapaio
sumber
dapatkah Anda memperpanjang jawaban Anda dengan perhitungan sebagai contoh saya?
user1930254
Saya seorang programmer, saya pikir saya bisa menulis dalam kode lebih cepat daripada mengetik di sini :). Semoga itu menjelaskan algo.
rapaio
Bisakah Anda jelaskan apa idenya dengan nomor iterasi log (Ksi)? Saya tidak mengerti ide di bawahnya, sepertinya jumlah iterasi akan tergantung pada rentang nilai objek, yang sepertinya tidak masuk akal. Misalnya, jika objek memiliki nilai atribut sekitar 1000, itu bisa, misalnya, menghasilkan kesalahan sekitar 1000, yang berarti akan ada 3 iterasi. Di sisi lain, jika nilai berada dalam kisaran 10 yang dapat mengakibatkan kesalahan sekitar 10 yang menghasilkan 1 iterasi. Bukankah jumlah iterasi tergantung pada jumlah objek?
Marko
@pera Saya memperbarui jawaban untuk mengklarifikasi masalah yang Anda ajukan
rapaio
@rapaio Terima kasih atas jawaban Anda, saya sudah mencari solusi yang akan menentukan jumlah iterasi berdasarkan jumlah medoids. Di mana x dapat ditingkatkan untuk mendapatkan inisialisasi yang lebih baik dengan biaya beberapa iterasi lebih banyak. Apakah Anda baik-baik saja, berdasarkan bagian kedua yang Anda berikan? Terima kasih lagi.
Marko