Bukti konvergensi k-means

20

Untuk suatu tugas, saya diminta untuk memberikan bukti bahwa k-means menyatu dalam sejumlah langkah yang terbatas.

Inilah yang saya tulis:

$C$
$E (C) = \sum_{x} {min}_{i = 1}^{k} {‖ x - c_{i} ‖}^{2}$ $E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$ $E(C)$

Langkah 2 mengacu pada langkah yang memberi label setiap titik data dengan pusat klaster terdekat, dan langkah 3 adalah langkah di mana pusat diperbarui dengan mengambil rata-rata.

Ini tidak cukup untuk membuktikan konvergensi dalam sejumlah langkah terbatas. Energi dapat terus semakin kecil tetapi tidak mengesampingkan kemungkinan bahwa titik-titik pusat dapat melompat tanpa banyak mengubah energi. Dengan kata lain mungkin ada beberapa energi minimum dan algoritme dapat melompat di antara mereka, bukan?

mathematical-statistics k-means jkabrg
sumber

5

Petunjuk: ada berapa banyak kemungkinan pengumpulan titik pusat?

whuber

34

Pertama, paling banyak ada cara untuk mempartisi poin data menjadi cluster; setiap partisi dapat disebut "clustering". Ini adalah angka yang besar tetapi terbatas. Untuk setiap iterasi algoritma, kami menghasilkan pengelompokan baru hanya berdasarkan pengelompokan yang lama. Perhatikan itu $k^N$ $N$ $k$

jika pengelompokan yang lama sama dengan yang baru, maka pengelompokan berikutnya akan kembali sama.
Jika pengelompokan baru berbeda dari yang lama maka yang baru memiliki biaya lebih rendah

Karena algoritma ini mengulangi fungsi yang domainnya adalah himpunan berhingga, iterasi akhirnya harus memasuki siklus. Siklus tidak dapat memiliki panjang lebih besar dari karena jika tidak dengan (2) Anda akan memiliki beberapa pengelompokan yang memiliki biaya lebih rendah daripada itu sendiri yang tidak mungkin. Karenanya siklus harus memiliki panjang tepat . Karenanya k-means bertemu dalam jumlah iterasi yang terbatas. $1$ $1$

jkabrg
sumber

Mengapa pesanan itu penting? Artinya, mengapa kita tidak memiliki

memilih

clustering?

N

$N$

k

$k$

rrrrr

@rrrrr Formula yang benar adalah

mana

{\binom{n}{k}}

$\lbrace{n\atop k}\rbrace$

adalahangka Stirling dari jenis kedua. Tidak masalah karena saya mengatakanpaling

.

{\binom{n}{k}}

$\lbrace{n\atop k}\rbrace$

k^{N}

$k^N$

jkabrg

6

Untuk menambahkan sesuatu: Apakah algoritme konvergen atau tidak juga tergantung pada kriteria stop Anda. Jika Anda menghentikan algoritme setelah penetapan cluster tidak berubah lagi, maka Anda dapat benar-benar membuktikan bahwa algoritma tersebut tidak perlu konvergen (asalkan penetapan cluster tidak memiliki pemutus pengikat deterministik jika beberapa centroid memiliki jarak yang sama).

Di sini Anda memiliki 8 titik data (titik) dan dua centroid (garis merah). Sekarang titik hijau-data memiliki jarak yang sama ke pusat massa kiri dan kanan. Hal yang sama berlaku untuk titik data biru. Mari kita asumsikan bahwa fungsi penugasan tidak deterministik dalam kasus ini. Lebih lanjut kita mengasumsikan bahwa pada iterasi 1 titik-titik hijau ditugaskan ke cluster kiri dan titik-titik biru ditugaskan ke cluster kanan. Lalu kami memperbarui centroid. Ternyata mereka sebenarnya tetap di tempat yang sama. (Ini adalah perhitungan yang mudah. Untuk centroid kiri Anda rata-rata koordinat dari dua titik hitam kiri dan dua titik hijau -> (0, 0,5). Sama untuk centroid kanan).

Kemudian pada iterasi 2 situasinya terlihat sama lagi, tetapi sekarang kita mengasumsikan bahwa fungsi penugasan non-deterministik kita memberikan titik-titik hijau ke cluster kanan dan titik-titik biru ke cluster kiri. Sekali lagi centroid tidak akan berubah.

Iterasi 3 lagi sama dengan iterasi 1. Dengan demikian kami memiliki kasus di mana penugasan gugusan terus berubah dan algoritme (dengan kriteria stop ini) tidak bertemu.

$\leq$ $\lt$

Rauwuckl
sumber

Bukti konvergensi k-means

Jawaban: