k-means implementasi dengan custom distance matrix dalam input

14

Adakah yang bisa menunjukkan saya implementasi k-means (akan lebih baik jika di matlab) yang dapat mengambil matriks jarak dalam input? Implementasi matlab standar membutuhkan matriks observasi dalam input dan tidak mungkin mengubah ukuran kesamaan secara kustom.

clustering matlab k-means Eugenio
sumber
2
Anda bisa mencoba menghasilkan data mentah yang sesuai dengan matriks jarak euclidean Anda dan memasukkannya ke K-Means. Alternatif pendekatan mudah bisa menggunakan metode Ward dari hierarchical clustering of the matrix: K-Means dan Ward berbagi ideologi serupa tentang apa itu cluster.
ttnphns
selain ttnphns dan Bukan Durrett Anda mungkin menemukan Apakah boleh menggunakan jarak Manhattan dengan tautan antar-klaster Ward dalam pengelompokan hierarkis? menarik
steffen
Bukan Matlab, tetapi halaman python di bawah ini-itu-mungkin-untuk-menentukan-Anda-sendiri-jarak-fungsi-menggunakan-scikits-learn-k-means dapat menggunakan salah satu dari 20 metrik aneh di scipy.spatial. jarak.
denis

Jawaban:

13

Karena k-means perlu dapat menemukan sarana dari himpunan bagian yang berbeda dari poin yang ingin Anda klaster, itu tidak benar-benar masuk akal untuk meminta versi k-means yang mengambil matriks jarak sebagai input.

Anda bisa mencoba k-medoid sebagai gantinya. Ada beberapa implementasi matlab yang tersedia.

NF
sumber
1
Hai, terima kasih atas jawabannya; alih-alih langsung memberikan matriks jarak, mungkinkah memberikan metrik jarak khusus sebagai input? Intinya adalah bahwa saya harus membandingkan dua metode pengelompokan dan, karena yang kedua saya menggunakan matriks kesamaan kesamaan, saya ingin menggunakan pendekatan yang sama dengan kmeans untuk mendapatkan perbandingan yang adil.
Eugenio
2
ELKI memungkinkan Anda untuk menggunakan fungsi jarak arbitrer dengan k-means. Perhatikan bahwa algoritme mungkin gagal menyatu. K-means benar-benar dirancang untuk jarak euclidean kuadrat (jumlah kuadrat). Dengan jarak lain, rerata mungkin tidak lagi optimal, dan boom, algoritma pada akhirnya tidak akan bertemu. Serius, pertimbangkan untuk menggunakan k-medoid. Ini sebenarnya ditulis untuk memungkinkan penggunaan ide k-means dengan jarak arbirary .
Memiliki QUIT - Anony-Mousse
Ada juga pyclustering pustaka python / C ++ yang memungkinkan Anda menyediakan fungsi metrik khusus: github.com/annoviko/pyclustering/issues/417
CpILL
7

Anda bisa mengubah matriks jarak menjadi data mentah dan memasukkannya ke pengelompokan K-Means. Langkah-langkahnya adalah sebagai berikut:

1) Jarak antara titik N Anda harus kuadratkan dengan euclidean. Melakukan " double centering " dari matriks: Mengurangi mean baris dari setiap elemen; dalam hasilnya, rata-rata kolom pengurangan dari setiap elemen; dalam hasilnya, tambahkan mean matriks ke setiap elemen; bagi dengan minus 2. Matriks yang Anda miliki sekarang adalah matriks SSCP (jumlah-kuadrat-dan-silang) antara titik-titik Anda di mana titik asal diletakkan di pusat geometris awan titik N. (Baca penjelasan tentang pemusatan ganda di sini .)

2) Lakukan PCA (Analisis komponen utama) pada matriks itu dan dapatkan matriks pemuatan komponen NxN . Beberapa kolom terakhir cenderung berjumlah 0, - jadi potong saja. Yang Anda pertahankan sekarang sebenarnya adalah skor komponen utama, koordinat titik N Anda ke komponen utama yang lulus, sebagai sumbu, melalui cloud Anda. Data ini dapat diperlakukan sebagai data mentah yang cocok untuk input K-Means.

PS Jika jarak Anda tidak benar secara geometris kuadrat euclidean Anda mungkin mengalami masalah: matriks SSCP mungkin tidak positif (semi) pasti. Masalah ini dapat diatasi dengan beberapa cara tetapi dengan kehilangan presisi.

ttnphns
sumber
Terima kasih atas jawaban anda! Sebenarnya saya tidak memiliki matriks jarak nyata tetapi matriks kesamaan (0 ... 1) di antara objek, dan kesamaan tidak dihitung persis menggunakan jarak euclidian tetapi dengan algoritma kustom yang mempertimbangkan data mentah tetapi tidak dalam cara standar. Saya kira dalam hal ini saya tidak dapat menerapkan prosedur Anda, apakah saya benar?
Eugenio
Anda masih bisa, setelah mengkonversi kesamaan ke jarak. Yang terakhir mungkin tidak benar euclidean (dan SSCP akan memiliki beberapa nilai eigen negatif); kemudian coba tambahkan konstanta kecil ke jarak sampai SSCP kehilangan neg. eig. Ada juga cara lain untuk mengatasi masalah tersebut. Dan harap diingat bahwa Anda menggandakan pusat matriks dari jarak kuadrat .
ttnphns
PS Dan omong-omong. Jika matriks Anda adalah persamaan, maka, yah, itu bahkan lebih baik. Anda hanya memperlakukannya sebagai matriks SSCP yang saya bicarakan dan lakukan PCA dengannya. Namun, masalah kemungkinan nilai eigen negatif masih ada.
ttnphns
@ttnphns, maaf saya hilang penjelasan Anda untuk langkah 1. Matriks jarak X(katakanlah N * N) akan menjadi simetris, sehingga colMeans(X) =rowMeans(X) dan setelah Anda mengurangi baris atau col berarti: Y=X-rowMeans(X), mean(Y)0
Zhubarb
1
@ Zhubarb, ketika saya katakan You could turn your matrix of distances into raw data(poin 1 dan 2) saya merujuk, pada dasarnya, untuk penskalaan multidimensi Torgerson (MDS) , di mana pemusatan ganda adalah langkah awal. Silakan cari situs ini (dan Google juga) tentang prosedur itu. "Double centering" adalah konversi jarak (kuadrat) ke dalam matriks produk skalar yang sesuai yang ditentukan pada titik asal dimasukkan ke dalam pusat massa awan titik.
ttnphns
3

Silakan lihat artikel ini, yang ditulis oleh salah satu kenalan saya;)

http://arxiv.org/abs/1304.6899

Ini adalah tentang implementasi k-means umum, yang mengambil matriks jarak sewenang-wenang sebagai input. Ini bisa berupa matriks nonnegatif simetris dengan nol diagonal. Perhatikan bahwa itu mungkin tidak memberikan hasil yang masuk akal untuk matriks jarak aneh. Program ini ditulis dalam C #.

Kode sumber dapat diperoleh dengan mengunjungi tautan di atas, lalu mengklik Format Lain, lalu mengklik Sumber Unduh. Maka Anda akan mendapatkan .tar.gz yang berisi Program.cs. Atau, kode sumber juga dapat disalin dari PDF.

szali
sumber
3

Anda bisa menggunakan Java Machine Learning Library. Mereka memiliki implementasi K-Means. Salah satu konstruktor menerima tiga argumen

  1. Nilai K.
  2. Objek itu adalah turunan dari Kelas DistanceMeasure .
  3. Jumlah iterasi.

Seseorang dapat dengan mudah memperluas kelas DistanceMeasure untuk mencapai hasil yang diinginkan. Idenya adalah untuk mengembalikan nilai dari matriks jarak kustom dalam metode ukuran (Instance x, Instance y) dari kelas ini.

K-Means ditandai untuk konvergen dengan asumsi sifat-sifat tertentu dari metrik jarak. Jarak Euclidean, jarak Manhattan atau metrik standar lainnya memenuhi asumsi ini. Karena metrik jarak khusus mungkin tidak memenuhi asumsi ini, konstruktor memiliki parameter ketiga yang menentukan jumlah iterasi yang akan dijalankan untuk membangun clusterer.

Chaitanya Shivade
sumber