Bersepeda dalam algoritma k-means

9

Menurut wiki kriteria konvergensi yang paling banyak digunakan adalah "tugas belum berubah". Saya bertanya-tanya apakah bersepeda dapat terjadi jika kita menggunakan kriteria konvergensi? Saya akan senang jika ada orang yang menunjuk referensi ke artikel yang memberikan contoh bersepeda atau membuktikan bahwa ini tidak mungkin.

clustering algorithms k-means Tomek Tarczynski
sumber
2
Biarkan saya tekankan (karena ini sering diabaikan) bahwa bukti konvergensi memerlukan (kuadrat) jarak euclidean , sehingga fungsi jarak dan fungsi rata - rata mengoptimalkan kriteria yang sama. Jika Anda menggunakan jarak yang berbeda (sebenarnya, Anda seharusnya tidak menggunakan jarak, tetapi "jumlah kuadrat terkecil") Anda mungkin kehilangan konvergensi dalam k-means.
Memiliki QUIT - Anony-Mousse

Jawaban:

7

Makalah ini tampaknya membuktikan konvergensi dalam sejumlah langkah terbatas.

Simon Byrne
sumber
1
Persis apa yang saya cari!
Tomek Tarczynski
4

kkk

Suresh Venkatasubramanian
sumber
Terima kasih, itu intuitif bahwa fungsi objektif menurun, tetapi saya tidak yakin bahwa itu menurun dengan ketat. Saya ingin memastikan bahwa tidak ada kasus patologis seperti dalam pemrograman linier
Tomek Tarczynski
Ya dan tidak. Sementara konvergen, itu bisa memakan waktu eksponensial, sebanyak bagaimana simpleks tidak. Selain itu, untuk kedua masalah, Anda dapat menunjukkan bahwa varian "smoothed" menyatu dalam waktu polinomial
Suresh Venkatasubramanian
2

Dalam ketepatan yang terbatas , bersepeda mungkin muncul.

Bersepeda sering dalam presisi tunggal, luar biasa dalam presisi ganda.

Ketika mendekati minimum lokal, fungsi objektif kadang-kadang mungkin sedikit meningkat karena kesalahan pembulatan. Ini sering tidak berbahaya karena fungsi algoritma menurun lagi dan akhirnya mencapai minimum lokal. Tetapi kadang-kadang, algoritma tersebut melangkah pada tugas yang sebelumnya dikunjungi, dan mulai bersepeda.

Sangat mudah dan aman untuk menonton siklus dalam penerapan kriteria berhenti dunia nyata.

François Pays
sumber