algoritma pengelompokan untuk data non-dimensi

Saya memiliki dataset ribuan titik dan alat untuk mengukur jarak antara dua titik, tetapi titik data tidak memiliki dimensi. saya ingin algoritma untuk menemukan pusat cluster di dataset ini. Saya membayangkan bahwa karena data tidak memiliki dimensi, pusat cluster mungkin terdiri dari beberapa titik data dan toleransi, dan keanggotaan dalam cluster dapat ditentukan oleh rata-rata jarak titik data ke setiap titik data di pusat cluster.

tolong maafkan saya jika pertanyaan ini memiliki solusi terkenal, saya tahu sedikit tentang masalah seperti ini! penelitian saya (sangat terbatas) hanya muncul algoritma clustering untuk data dimensi, tetapi saya minta maaf sebelumnya jika saya telah melewatkan sesuatu yang jelas.

Terima kasih!

Jika fungsi jarak adalah metrik, maka Anda bisa menggunakan pusat clustering (di mana jari-jari maksimum bola diminimalkan) atau median clustering (yang meminimalkan jumlah jarak ke pusat-pusat cluster). -pusat pengelompokan mudah: hanya mengambil titik- terjauh, dan Anda dijamin untuk mendapatkan 2-perkiraan melalui ketimpangan segitiga (ini adalah hasil lama karena Gonzalez).k k $k$$k$$k$$k$

Untuk pengelompokan median, ada banyak pekerjaan, terlalu banyak untuk ditinjau di sini. Michael Shindler di UCLA memiliki survei yang bagus tentang ide-ide utama.$k$

Kedua masalah ini NP-hard secara umum, dan sulit diperkirakan dalam faktor arbitrer. Perhatikan bahwa jika Anda menjatuhkan syarat menjadi metrik, segalanya menjadi jauh lebih buruk dalam hal perkiraan.

Pendekatan lain, lebih heuristik yang mungkin ok untuk aplikasi Anda adalah dengan menggunakan teknik seperti MDS (penskalaan multidimensi) untuk menanamkan matriks jarak Anda dalam ruang Euclidean, dan kemudian menggunakan salah satu dari banyak metode pengelompokan Euclidean yang berbeda (atau bahkan pengelompokan berarti ). Jika Anda yakin bahwa fungsi jarak Anda adalah metrik, maka Anda dapat melakukan penanaman yang sedikit lebih cerdas ke dalam ruang Euclidean dan mendapatkan jaminan yang dapat dibuktikan (meskipun lemah) pada kualitas jawaban Anda.$k$

Pada akhirnya, seperti kebanyakan masalah pengelompokan, pilihan akhir Anda bergantung pada aplikasi, ukuran data Anda, dan sebagainya.

Ada juga pengelompokan korelasi , yang memiliki informasi input untuk setiap pasangan item yang menunjukkan apakah mereka termasuk dalam cluster yang sama atau cluster yang berbeda.

Jika Anda hanya mencari kinerja empiris yang baik, algoritma propagasi afinitas biasanya bekerja lebih baik daripada k-median. Ada kode yang tersedia dalam beberapa bahasa dan publikasi yang menjelaskan algoritma secara lebih rinci ada di sini: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

Tujuan yang ingin dimaksimalkan adalah:

di mana adalah ukuran kesamaan yang didefinisikan antara pasangan titik (misalnya, jarak negatif), dan memberikan kluster tempat berada. Ada satu parameter tambahan yang diberikan dalam yang mengontrol apakah Anda lebih suka cluster besar atau kecil.c i ∈ c i s ( i , i $s$$c_i \in \mathbf{c}$$i$$s(i, i)$

Pertanyaan Anda tampaknya menyiratkan bahwa Anda mencari algoritma dengan waktu komputasi yang layak. Mengingat ukuran simpul Anda (atau titik) akan membuat representasi grafik tertimbang data Anda dan menggunakan Markov Cluster Algorithm (MCL) untuk mengelompokkan grafik.

http://www.micans.org/mcl/

MCL didasarkan pada jalan acak melalui grafik tertimbang dan tidak berbobot untuk menemukan subgraph padat. Ia mampu menangani grafik besar dan telah digunakan di banyak program bioinformatik yang terkenal (seperti BLAST). -Boucher

Pertimbangkan algoritma tetangga k-terdekat .