k-means vs k-median?

14

Saya tahu ada algoritma pengelompokan k-means dan k-median. Satu yang menggunakan mean sebagai pusat cluster dan yang lainnya menggunakan median. Pertanyaan saya adalah: kapan / di mana menggunakannya?

clustering k-means Jack Twain
sumber
Anda harus menentukan median (dan mungkin menghitungnya) jika Anda memiliki lebih dari satu dimensi; jika Anda hanya mengambil median di setiap nilai maka Anda kehilangan properti rotasi. Kemungkinan selanjutnya adalah k -medoids
Henry

Jawaban:

14

k-means meminimalkan varians dalam-kluster, yang sama dengan jarak Euclidean kuadrat.

Secara umum, rata - rata aritmatika melakukan ini. Itu tidak mengoptimalkan jarak, tetapi kuadrat penyimpangan dari mean.

k-median meminimalkan penyimpangan absolut, yang sama dengan jarak Manhattan.

Secara umum, median per-sumbu harus melakukan ini. Ini adalah penaksir yang bagus untuk mean, jika Anda ingin meminimalkan jumlah penyimpangan absolut (yaitu sum_i abs (x_i-y_i)), bukan yang kuadrat.

Ini bukan pertanyaan tentang akurasi. Ini pertanyaan tentang kebenaran. ;-)

Jadi, inilah pohon keputusan Anda:

  • Jika jarak Anda adalah jarak Euclidean kuadrat , gunakan k-means
  • Jika jarak Anda adalah metrik Taxicab , gunakan k-median
  • Jika Anda memiliki jarak lain , gunakan k-medoid

Beberapa pengecualian: sejauh yang saya tahu, memaksimalkan persamaan cosinus terkait dengan meminimalkan jarak Euclidean kuadrat pada data yang dinormalkan L2. Jadi jika data Anda L2 dinormalisasi; dan Anda l2-menormalkan berarti Anda setiap iterasi, maka Anda dapat menggunakan k-means lagi.

Memiliki QUIT - Anony-Mousse
sumber
Saya agak mempermasalahkan pernyataan bahwa median meminimalkan jarak manhattan, karena tidak ada kesepakatan unik tentang konsep median untuk data multidimensi. Itu tidak salah, tetapi saya menemukan pernyataan yang menyesatkan untuk dibuat dalam konteks multidimensi. Ada beberapa generalisasi multidimensi dari median, banyak di antaranya tidak memiliki koneksi untuk meminimalkan jarak manhattan.
Tim Seguine
1
Saya mengubahnya ke median per sumbu. Saya harap kamu lebih bahagia sekarang.
Memiliki QUIT - Anony-Mousse
2

Jika Anda ingin membuat analisis bukan tentang kemungkinan dampak dari nilai ekstrem gunakan k berarti tetapi jika Anda ingin menjadi lebih akurat gunakan k median

Raf
sumber
5
Bisakah Anda mendukung dan / atau menjelaskan pernyataan ini dengan cara apa pun?
jona
Ya, bisakah Anda menjelaskan lebih lanjut? dengan contoh?
Jack Twain
2
Saya pikir itu karena "Median" dapat mentolerir outlier tetapi "Mean" benar-benar terpengaruh oleh mereka. Sebagai contoh: jika kita memiliki poin data {1,2,3,5,78} jelas bahwa 78 outlier. Median dari data ini adalah 3 dan rata-rata adalah 17.8. Jadi median adalah cara terbaik untuk meringkas data ini.
Fadwa