Episode
Bibit yang Cepat dan Bagus untuk k-Means
dengan Olivier Bachem
Penyemaian - tugas menemukan pusat kluster awal - sangat penting dalam mendapatkan pengklusteran berkualitas tinggi untuk k-Means. Namun, seeding k-means++, status algoritma seni, tidak menskalakan dengan baik ke himpunan data besar karena secara inheren berurutan dan membutuhkan k melewati data secara penuh. Baru-baru ini ditunjukkan bahwa pengambilan sampel Monte Carlo rantai Markov dapat digunakan untuk secara efisien memperkirakan langkah penyemaian k-means++. Namun, hasil ini memerlukan asumsi pada distribusi yang menghasilkan data. Kami mengusulkan algoritma penyemaian sederhana namun cepat yang menghasilkan pengklusteran yang sangat baik bahkan tanpa asumsi pada data. Analisis kami menunjukkan bahwa algoritma memungkinkan trade-off yang menguntungkan antara kualitas solusi dan biaya komputasi, mempercepat penyemaian k-means++ hingga beberapa urutan besarnya. Kami memvalidasi hasil teoritis kami dalam eksperimen ekstensif pada berbagai himpunan data dunia nyata.
Penyemaian - tugas menemukan pusat kluster awal - sangat penting dalam mendapatkan pengklusteran berkualitas tinggi untuk k-Means. Namun, seeding k-means++, status algoritma seni, tidak menskalakan dengan baik ke himpunan data besar karena secara inheren berurutan dan membutuhkan k melewati data secara penuh. Baru-baru ini ditunjukkan bahwa pengambilan sampel Monte Carlo rantai Markov dapat digunakan untuk secara efisien memperkirakan langkah penyemaian k-means++. Namun, hasil ini memerlukan asumsi pada distribusi yang menghasilkan data. Kami mengusulkan algoritma penyemaian sederhana namun cepat yang menghasilkan pengklusteran yang sangat baik bahkan tanpa asumsi pada data. Analisis kami menunjukkan bahwa algoritma memungkinkan trade-off yang menguntungkan antara kualitas solusi dan biaya komputasi, mempercepat penyemaian k-means++ hingga beberapa urutan besarnya. Kami memvalidasi hasil teoritis kami dalam eksperimen ekstensif pada berbagai himpunan data dunia nyata.
Memiliki umpan balik? Kirimkan masalah di sini.