Menggunakan k-means dengan metrik lainnya

8

Jadi saya menyadari ini telah ditanyakan sebelumnya: misalnya Apa kasus penggunaan terkait dengan analisis cluster metrik jarak yang berbeda? tetapi saya telah menemukan jawaban yang agak kontradiktif dengan apa yang disarankan harus dimungkinkan dalam literatur.

Baru-baru ini saya telah membaca dua makalah yang menyebutkan menggunakan algoritma kmeans dengan metrik lain, misalnya mengedit jarak antara string dan "Jarak Penggerak Bumi" antara distribusi. Mengingat bahwa makalah ini menyebutkan menggunakan kmeans dengan metrik lain tanpa menentukan bagaimana , terutama ketika datang untuk menghitung rata-rata set poin, menunjukkan kepada saya bahwa mungkin ada beberapa metode "standar" untuk menangani ini yang saya tidak memilih di atas.

Ambil contoh makalah ini , yang memberikan implementasi lebih cepat dari algoritma k-means. Mengutip dari paragraf 4 dalam pengantar, penulis mengatakan algoritmenya "dapat digunakan dengan metrik jarak kotak hitam", dan pada paragraf berikutnya ia menyebutkan edit jarak sebagai contoh spesifik. Namun algoritma-nya masih menghitung rata-rata sekumpulan poin dan tidak menyebutkan bagaimana hal ini dapat memengaruhi hasil dengan metrik lain (saya terutama bingung bagaimana cara kerja rata-rata dengan mengedit jarak).

Makalah lain ini menjelaskan menggunakan k-means untuk mengelompokkan tangan poker untuk abstraksi hold-em texas. Jika Anda melompat ke halaman 2 di bawah kolom kiri penulis menulis "dan kemudian k-means digunakan untuk menghitung abstraksi dengan jumlah cluster yang diinginkan menggunakan Earth Mover Distance antara setiap pasangan histogram sebagai metrik jarak".

Saya tidak benar-benar mencari seseorang untuk menjelaskan makalah ini kepada saya, tetapi apakah saya kehilangan beberapa metode standar untuk menggunakan k-means dengan metrik lainnya? Rata-rata standar dengan jarak penggerak bumi sepertinya bisa bekerja secara heuristik, tetapi jarak edit tampaknya tidak sesuai dengan cetakan sama sekali. Saya menghargai wawasan yang bisa diberikan seseorang.

(sunting) : Saya maju dan mencoba k-means pada histogram distribusi menggunakan jarak penggerak bumi (mirip dengan apa yang ada di kertas poker) dan tampaknya berfungsi dengan baik, kluster yang dihasilkannya terlihat cukup bagus untuk kasus penggunaan saya. Untuk rata-rata saya hanya memperlakukan histogram sebagai vektor dan dirata-rata dengan cara normal. Satu hal yang saya perhatikan adalah jumlah semua titik jarak ke sarana tidak selalu menurun secara monoton. Namun dalam praktiknya, itu akan menentukan min lokal dalam 10 iterasi meskipun ada masalah monoton. Saya akan berasumsi bahwa ini adalah apa yang mereka lakukan di makalah kedua, satu-satunya pertanyaan yang tersisa kemudian adalah, bagaimana sih yang akan Anda rata-rata ketika menggunakan sesuatu seperti mengedit jarak?

ScoobySnacks
sumber
Tautan ke-2 menduplikasi tautan ke-1.
ttnphns
Scooby Terima kasih atas tautan yang menarik. Makalah pertama (yang baru saja saya bahas dengan cepat) menjelaskan metode / algoritma pengelompokan (yang seharusnya) baru yang didasarkan pada gagasan ketidaksetaraan segitiga metrik. Hal ini bukan apa yang orang berarti dalam istilah k-Means metode / algoritma. Jadi judul artikelnya agak menyesatkan, bagi saya. Usulan metode pengelompokan "ketimpangan segitiga", ketika diterapkan pada metrik jarak Euclidean, harus memberikan hasil yang identik dengan apa yang akan diberikan oleh metode "K-means", seperti yang diklaim penulis.
ttnphns
Dalam arti yang ketat, prosedur K-means menyiratkan (1) objek dengan (numerik) fitur matriks input; (2) penugasan berulang objek ke cluster dengan menghitung jarak Euclidean antara objek dan pusat-pusat cluster (yang berarti cluster ). Segala sesuatu di atas atau di atas itu - misalnya menganalisis matriks jarak berpasangan atau menggunakan metrik lain selain Euclidean atau menghitung bentuk lain dari pusat dari rata-rata, dll. - meluas atau memodifikasi K-sarana sehingga menjadi bukan k-sarana dalam pengertian asli.
ttnphns
1
@ttnphns Saya tidak setuju dengan (2). Itu adalah algoritma Lloyds, bukan k-means generik. K-means secara umum berarti meminimalkan tujuan jumlah-kuadrat-partisi. Apa yang Anda gambarkan adalah pola generik mengharapkan-memaksimalkan (EM); dan Lloyds adalah pola EM untuk model kuadrat-terkecil.
Memiliki QUIT - Anony-Mousse

Jawaban:

4

Bukan berarti k-means akan meledak dan gagal jika Anda menggunakan metrik yang berbeda.

Dalam banyak kasus ini akan mengembalikan beberapa hasil . Hanya saja tidak dijamin akan menemukan centroid atau partisi optimal dengan metrik lain, karena rata - rata mungkin tidak cocok untuk meminimalkan jarak.

Pertimbangkan jarak penggerak Bumi. Diberikan tiga vektor

3 0 0 0 0
0 0 3 0 0
0 0 0 0 3

Mean aritmatika adalah

1 0 1 0 1

yang memiliki jarak EMD 6, 4, 6 (total 16). Jika algoritma digunakan sebagai gantinya

0 0 3 0 0

jarak EMD akan menjadi 6, 0, 6; yaitu lebih baik (total 12).

Rata-rata aritmatika tidak meminimalkan EMD, dan hasil penggunaan k-rata-rata (dengan rata-rata artihmatika) tidak akan menghasilkan perwakilan yang optimal.

Hal serupa akan berlaku untuk jarak edit.

Memiliki QUIT - Anony-Mousse
sumber
Saya tidak yakin apakah saya mengikuti cara Anda menghitung jarak EMD. Menurut pemahaman saya, Anda memerlukan matriks transisi dengan bobot untuk berpindah dari satu fitur ke fitur lainnya.
sffc
1
Pilih matriks seperti kanonik, dari motivasi asli: bergerak bumi, dengan biaya = jarak.
Memiliki QUIT - Anony-Mousse
2

K-means sesuai untuk digunakan dalam kombinasi dengan jarak Euclidean karena tujuan utama k-means adalah untuk meminimalkan jumlah varians dalam-cluster , dan varians dalam-cluster dihitung dengan cara yang persis sama dengan jumlah Euclidean jarak antara semua titik di cluster ke cluster centroid. Sebagai jawaban lain menunjukkan , algoritma ini hanya dijamin untuk menyatu (bahkan jika minimum lokal) jika kedua langkah pembaruan sentroid dan langkah pengalihan poin data dilakukan dalam ruang Euclidean n-dimensi yang sama .

Juga, telah ditunjukkan (dan saya meletakkan tautan di sini karena saya sendiri tidak dapat menjelaskan ini) bahwa mean adalah penaksir terbaik untuk digunakan ketika seseorang perlu meminimalkan varians total . Jadi k-means mengikat ke jarak Euclidean adalah dua kali lipat: algoritma harus memiliki beberapa cara untuk menghitung rata-rata satu set titik data (maka nama k- berarti ), tetapi ini berarti hanya masuk akal dan menjamin konvergensi dari proses pengelompokan jika jarak Euclidean digunakan untuk menetapkan kembali titik data ke centroid terdekat.

Anda masih dapat menggunakan k-means dengan langkah-langkah jarak lainnya, seperti dalam makalah ini , di mana penulis menggunakan algoritma dengan jarak Minkowski, yang merupakan generalisasi dari jarak Manhattan, Euclidean, dan Chebyshev. Namun, dalam kasus ini, konvergensi tidak dijamin dan, sebagai konsekuensinya, Anda mungkin berharap bahwa iterasi algoritma di masa depan benar-benar akan memiliki total varians lebih besar daripada iterasi sebelumnya.

Meski begitu, seperti yang ditunjukkan dalam makalah di atas, bahkan tanpa jaminan konvergensi, k-means dapat mencapai hasil pengelompokan yang lebih baik dalam beberapa skenario dengan menggunakan ukuran jarak lainnya. Jika Anda mengambil norma , misalnya, dan mengetahui bahwa jarak Euclidean adalah norma dan bahwa jarak Manhattan adalah norma , telah ditunjukkan bahwa, untuk matriks jarak jarang, k-means digunakan bersama dengan norma dengan mencapai akurasi pengelompokan yang lebih besar daripada saat menggunakan jarak Euclidean.LpL2L1Lp0<p1

Terakhir, saya pikir itu menarik untuk menunjukkan bahwa ada beberapa langkah-langkah kesamaan yang dalam beberapa cara dapat dikonversi ke jarak Euclidean, sedemikian rupa sehingga jika Anda menggunakan ukuran kesamaan tersebut dalam hubungannya dengan k-means, Anda harus mendapatkan hasil serupa. Contohnya adalah kesamaan cosinus .

Douglas De Rizzo Meneghetti
sumber
1
Lp untuk p <1 bukan norma.
Memiliki QUIT - Anony-Mousse
1

Saya tidak tahu apakah ini yang dilakukan oleh makalah terkait, tetapi dimungkinkan untuk melakukan k-means dengan fungsi jarak non-Euclidean menggunakan trik kernel . Yaitu, kami secara implisit memetakan input ke ruang dimensi tinggi (seringkali dimensi tak terbatas) di mana jarak Euclidean sesuai dengan fungsi jarak yang ingin kami gunakan, dan menjalankan algoritme di sana. Khususnya untuk algoritma k-means Lloyd, kita dapat menetapkan titik ke klusternya dengan mudah, tetapi kami mewakili pusat kluster secara implisit dan menemukan perwakilan mereka di ruang input akan membutuhkan menemukan rata-rata Fréchet . Makalah berikut membahas algoritma dan mengaitkannya dengan pengelompokan spektral:

I. Dhillon, Y. Guan, dan B. Kulis. K-means Kernel, Clustering Spectral, dan Pemotongan Normal. KDD 2005.

Ada kernel berdasarkan jarak sunting dan berdasarkan jarak penggerak bumi .

Dougal
sumber