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 .d2C(xi)xiCψ=∑ni=1d2C(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 (CXd2C(xi)Cxiϕ=∑ni=1||xi−c||2
ψ=∑ni=1d2(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 keC′C
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 i ∈ X j C w [ j ] 1 wwC0Xxi∈XjCw[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)/∑mj=1wj
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(ψ)