Lakukan pengelompokan K-means (atau kerabat dekatnya) dengan hanya matriks jarak, bukan data poin demi fitur

Saya ingin melakukan pengelompokan K-means pada objek yang saya miliki, tetapi objek tidak digambarkan sebagai titik dalam ruang, yaitu dengan objects x featuresdataset. Namun, saya dapat menghitung jarak antara dua objek (didasarkan pada fungsi kesamaan). Jadi, saya membuang matriks jarak objects x objects.

Saya sudah mengimplementasikan K-means sebelumnya, tapi itu dengan input dataset poin; dan dengan input matriks jarak tidak jelas bagi saya bagaimana memperbarui cluster menjadi "pusat" cluster tanpa representasi titik. Bagaimana ini biasanya dilakukan? Apakah ada versi K-means atau metode yang dekat dengannya, untuk itu?

Jelas, k-means harus dapat menghitung cara .

Namun, ada variasi yang terkenal itu dikenal sebagai k-medoids atau PAM (Partitioning Around Medoids), di mana medoid adalah objek yang sudah ada yang paling sentral ke cluster. K-medoid hanya membutuhkan jarak berpasangan.

Anda persis menggambarkan pengaturan masalah kernel -means; ketika Anda tidak dapat merepresentasikan titik data sebagai vektor Euclidean, tetapi jika Anda masih dapat menghitung (atau mendefinisikan) produk dalam antara dua titik data maka Anda dapat melakukan kernelisasi algoritma. Halaman web berikut menyediakan deskripsi singkat tentang algoritma:$k$

Kernel artinya halaman$k$

Trik kernel ini adalah ide yang sangat populer dan mendasar dalam Statistik dan pembelajaran mesin.

Halaman wiki pada trik kernel

Jika Anda tertarik, buku Learning with Kernels dari oleh Bernhard Schölkopf dan Alexander J. Smola akan menjadi pengantar yang sangat bagus.

Catatan dari Max Welling ini tampaknya sangat bagus; juga, jika Anda menggunakan R Anda bisa melihat pada paket R ini .

MDS mungkin merupakan salah satu cara untuk menyelesaikan masalah Anda, tetapi itu tidak secara langsung menyerang masalah yang ingin Anda selesaikan; sementara kernel k-means tidak.

@ung benar-benar benar menyarankan Anda penskalaan multidimensi (MDS) sebagai alat awal untuk membuat points X dimensions data di luar matriks jarak. Saya menambahkan beberapa stroke. K-means clustering menyiratkan jarak euclidean . MDS akan memberi Anda koordinat titik-dalam-dimensi sehingga menjamin Anda jarak euclidean. Anda harus menggunakan metrik MDS dan meminta jumlah dimensi sebesar mungkin, karena tujuan Anda adalah untuk meminimalkan kesalahan dalam mengekstrak kembali data, bukan untuk memetakannya dalam 2D ​​atau 3D.

Bagaimana jika Anda tidak memiliki perangkat lunak MDS tetapi memiliki beberapa fungsi matriks seperti dekomposisi nilai eigen atau dekomposisi nilai singular? Lalu, Anda bisa melakukan sendiri metrik MDS sederhana - Torgerson MDS, juga dikenal sebagai Analisis Koordinat Utama (PCoA). Itu berjumlah sedikit "memutar" analisis Komponen Utama. Saya tidak akan menjelaskannya di sini, meskipun cukup sederhana. Anda dapat membacanya di banyak tempat, misalnya di sini .

Akhirnya, dimungkinkan untuk memprogram "K-means untuk input matriks jarak" secara langsung - tanpa memanggil atau menulis fungsi yang melakukan PCoA atau metrik MDS lainnya. Kita tahu, bahwa (a) jumlah deviasi kuadrat dari centroid sama dengan jumlah jarak Euclidean kuadrat berpasangan dibagi dengan jumlah titik; dan (b) tahu bagaimana menghitung jarak antara centroid kluster dari matriks jarak ; (c) dan kita lebih lanjut tahu bagaimana jumlah kuadrat saling terkait dalam K-means. Semua itu bersama-sama membuat penulisan algoritma yang Anda inginkan mudah dan tidak rumit. Orang harus ingat bahwa K-means hanya untuk jarak Euclidean / ruang euclidean. Gunakan K-medoid atau metode lain untuk jarak non-euclidean.

Pertanyaan serupa .

Saya tentu tidak tahu bagaimana hal itu "biasanya" dilakukan, dan sebagai catatan, saya tidak tahu banyak tentang analisis cluster. Namun, apakah Anda terbiasa dengan Penskalaan Multidimensi ? ( Berikut referensi lain, wiki , dan Anda dapat mencari CV di bawah tag penskalaan multidimensi .) Penskalaan multidimensi menggunakan matriks jarak berpasangan, yang terdengar seperti situasi Anda. Dari MDS, Anda bisa mendapatkan lokasi objek dalam ruang dimensi terendah yang diperlukan untuk mewakilinya secara memadai. Saya kira Anda bisa menggunakan lokasi tersebut untuk melakukan analisis kluster berikutnya seperti k-means; sebagai alternatif, setelah Anda memiliki output, Anda mungkin tidak lagi membutuhkan CA.

Saya tidak tahu apakah Anda menggunakan R, tetapi di sini adalah tampilan tugas untuk Psychometrics, yang mencakup bagian tentang MDS di R. Semoga itu membantu.

$k$

Dalam kasus Anda, apa yang pada dasarnya perlu Anda lakukan adalah:

1. $D$
2. $D_{ij}$$D_{ji}$
3. $D^c$
4. $S^c = -\frac{1}{2}D^c$
5. $S^c$$S^c$$\tilde S^c$
6. $\tilde S^c = V \Lambda V^\top$
7. $n-1$$X = V\Lambda^{1/2}$

$n$

Data Anda juga dapat dilihat sebagai jaringan, dan Anda dapat menggunakan salah satu dari banyak algoritma pengelompokan jaringan yang tersedia. Untuk ini, Anda mungkin perlu menerapkan ambang pada bobot tepi, dan mengubah jarak ke kesamaan. Ini bukan cara 'statistik' dalam melakukan sesuatu, tetapi analisis cluster adalah masalah yang tidak ditentukan untuk memulai, dan sebagai alat eksplorasi algoritma clustering jaringan berkinerja sangat baik.

Saya tidak tahu mengapa itu sangat tidak biasa dalam literatur, namun solusi yang disarankan oleh @gung dan @ttnphns (pertama memproyeksikan jarak berpasangan Anda ke ruang Euclidean menggunakan Analisis Koordinat Utama, misalnya melalui paket ini jika Anda menggunakan R, dan kemudian melakukan K-means cara biasa) sederhana dan tidak memerlukan algoritma khusus. Saya pribadi menggunakannya di sini tertanam dalam kerangka kerja optimasi dan itu bekerja dengan cukup baik.

Berkenaan dengan clustering dan MDS saya akan menyarankan sumber daya berikut:

• Ekologi Numerik (Pierre Legendre dan Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 atau http://tinyurl.com/cgrdfqk (buku google) - bab tentang 'Kemiripan ekologis'
• Analisis Cluster (Brian S. Everitt, Sabine Landau, Morven Leese, Daniel Stahl): http://tinyurl.com/bld7k8h (buku google) - bab tentang 'Pengukuran kedekatan'
• Kursus 'Biostatistik-II, Metode Multivariat' oleh Prof. Brian C. McCarthy di Ohio University: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

Referensi ini juga mencakup topik kesamaan dan fungsi jarak (pengukuran kedekatan) untuk data biner dan kontinu.