Saya tahu k-means biasanya dioptimalkan menggunakan Expectation Maximization . Namun kami dapat mengoptimalkan fungsi kerugiannya dengan cara yang sama kami mengoptimalkan lainnya!
Saya menemukan beberapa makalah yang benar-benar menggunakan keturunan gradien stokastik untuk k-means skala besar, tapi saya tidak bisa menjawab pertanyaan saya.
Jadi, ada yang tahu kenapa begitu? Apakah karena Maksimisasi Ekspektasi lebih cepat bertemu ? Apakah ada jaminan khusus? Atau apakah itu alasan historis ?
Jawaban:
Seperti yang disebutkan OP, mungkin untuk menyelesaikan k-means menggunakan gradient descent, dan ini mungkin berguna dalam kasus masalah skala besar.
Tentu saja ada alasan historis untuk prevalensi algoritma gaya EM untuk menyelesaikan k-means (yaitu algoritma Lloyd). Algoritma Lloyd sangat populer sehingga orang kadang-kadang menyebutnya "algoritma k-means", dan bahkan mungkin tidak menyadari bahwa ada pendekatan lain. Tapi, popularitas ini bukan tidak pantas.
Bottou dan Bengio (1995) menunjukkan bahwa algoritma Lloyd setara dengan mengoptimalkan fungsi biaya k-means menggunakan metode Newton. Dalam masalah optimisasi umum, metode urutan kedua seperti metode Newton dapat konvergen lebih cepat daripada metode urutan pertama seperti gradient descent karena mereka mengeksploitasi informasi tentang kelengkungan fungsi tujuan (dan metode urutan pertama tidak). Dalam percobaan pada dataset Iris yang terkenal, mereka menunjukkan bahwa algoritma Lloyd memang konvergen lebih cepat daripada gradient descent. Akan menarik untuk melihat perbandingan ini pada berbagai dataset yang lebih luas.
Referensi:
Bottou dan Bengio (1995) . Properti konvergensi dari algoritma k-means.
sumber
K-means clustering adalah tanpa pengawasan, dan teknik tanpa pengawasan terdekat yang menggunakan EM adalah model-based clustering (Gaussian campuran model, GMM). Masalah yang mengganggu dengan pengelompokan berbasis model GMM terjadi ketika banyak fitur berkorelasi, yang menyebabkan singularitas hampir sama dalam matriks kovarians (korelasi) berbasis fitur. Dalam situasi ini, fungsi kemungkinan menjadi tidak stabil, dengan indeks kondisi mencapai tak terbatas, menyebabkan GMM rusak sepenuhnya.
Jadi, hilangkan ide EM dan kNN - karena didasarkan pada matriks kovarians (korelasi) untuk analisis tanpa pengawasan. Pertanyaan Anda tentang pengoptimalan sangat mirip dengan pemetaan Sammon, dan penskalaan multidimensi metrik dan non-metrik klasik. Pemetaan Sammon berbasis derivatif-iteratif, sementara berbagai bentuk MDS umumnya merupakan komposisi eigend iteratif atau satu langkah, yang tetap dapat dioptimalkan selama operasi matriks satu langkah.
Melihat kembali permintaan Anda: jawabannya adalah: sudah dilakukan dalam pemetaan Sammon.
sumber