Pengelompokan berdasarkan skor kesamaan

17

Asumsikan bahwa kita memiliki satu set elemen E dan kesamaan ( tidak jarak ) fungsi sim (ei, ej) antara dua elemen ei, ej ∈ E .

Bagaimana kita (secara efisien) mengelompokkan elemen-elemen E , menggunakan sim ?

k -berarti, misalnya, membutuhkan k yang diberikan , Canopy Clustering membutuhkan dua nilai ambang batas. Bagaimana jika kita tidak menginginkan parameter yang sudah ditentukan sebelumnya?

Perhatikan, sim itu tidak selalu berupa metrik (yaitu ketidaksamaan segitiga mungkin, atau mungkin tidak berlaku). Selain itu, tidak masalah jika kluster dipisahkan (partisi E ).

clustering algorithms similarity vefthym
sumber
2
Saya heran mengapa Anda menekankan bahwa Anda tidak memiliki jarak. Saya bukan ahli di sini, tetapi bertanya-tanya apakah seharusnya tidak mungkin mengubah kesamaan seperti itu menjadi jarak, jika diperlukan, pada dasarnya dengan mempertimbangkan kebalikannya. Terlepas dari itu, saya ragu bahwa ada algoritma pengelompokan yang sepenuhnya bebas dari parameter, sehingga beberapa penyetelan kemungkinan besar akan diperlukan dalam semua kasus. Ketika Anda mempertimbangkan k-Means, dapatkah seseorang berasumsi bahwa Anda memiliki properti bernilai nyata (khususnya, bahwa Anda dapat mengambil "mean" dari beberapa elemen)?
Marco13
4
Anda tidak perlu tahu k untuk melakukan k means. Anda dapat mengelompokkan dengan berbagai k dan memeriksa varian kluster untuk menemukan yang optimal. Atau Anda mungkin berpikir tentang pergi untuk model campuran Gaussian atau proses restaraunt lainnya seperti hal-hal untuk membantu Anda berkelompok.
cwharland
2
Saya mengajukan pertanyaan karena alasan tertentu: Jika Anda bisa menerapkan k-Means, tetapi satu-satunya masalah adalah menemukan "k" awal, maka Anda dapat mempertimbangkan en.wikipedia.org/wiki/Self-organizing_map sebagai alternatif. Ini memiliki beberapa properti bagus, dan pada dasarnya berperilaku "mirip" dengan k-Berarti, tetapi tidak memerlukan "k" awal untuk ditetapkan. Ini mungkin bukan solusi out-of-the-box, karena memiliki parameter tuning tambahan (dan pelatihan mungkin mahal secara komputasi), tetapi tetap patut untuk dilihat.
Marco13
2
Pilihan awal k memang memengaruhi hasil pengelompokan tetapi Anda dapat menentukan fungsi kerugian atau lebih tepatnya fungsi akurasi yang memberi tahu Anda untuk setiap nilai k yang Anda gunakan untuk mengelompokkan, kesamaan relatif dari semua subjek dalam kelompok itu. Anda memilih k yang meminimalkan varians dalam kesamaan itu. GMM dan proses dirichlet lainnya menangani masalah yang tidak diketahui dengan baik. Salah satu sumber terbaik yang pernah saya lihat di sini adalah tutorial Edwin Chen .
cwharland
4
Hanya pemikiran: Jika skor kesamaan Anda dinormalisasi menjadi 1 , maka 1-sim(ei, ej) = Distance. Dengan metrik jarak, Anda dapat menerapkan misalnya pengelompokan hierarkis. Turun dari root, Anda akan melihat pada level berapa granularity cluster masuk akal untuk masalah khusus Anda.
Olexandr Isayev

Jawaban:

8

  1. Saya pikir sejumlah algoritma pengelompokan yang biasanya menggunakan metrik, tidak benar-benar mengandalkan properti metrik (selain komutatifitas, tapi saya pikir Anda akan memilikinya di sini). Misalnya, DBSCAN menggunakan lingkungan epsilon di sekitar titik; tidak ada apa pun di sana yang secara khusus mengatakan masalah ketimpangan segitiga. Jadi Anda mungkin dapat menggunakan DBSCAN, meskipun Anda mungkin harus melakukan semacam indeks spasial tidak standar untuk melakukan pencarian efisien dalam kasus Anda. Versi epsilon-neighborhood Anda kemungkinan akan sim> 1 / epsilon daripada sebaliknya. Kisah yang sama dengan k-means dan algoritma terkait.

  2. Bisakah Anda membuat metrik dari kesamaan Anda? Satu kemungkinan: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) untuk semua k ... Atau, dapatkah Anda memberikan batas atas sedemikian rupa sehingga sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, untuk semua k dan beberapa konstanta positif d? Secara intuitif, nilai sim besar berarti lebih dekat bersama: apakah metrik mirip 1 / sim? Bagaimana dengan 1 / (sim + konstan)? Bagaimana dengan min (1 / sim (ei, ek) + 1 / sim (ek, ej)) untuk semua k? (yang terakhir dijamin menjadi metrik, btw)

  3. Konstruksi alternatif dari metrik adalah melakukan penanaman. Sebagai langkah pertama, Anda dapat mencoba memetakan titik Anda ei -> xi, sehingga xi meminimalkan jumlah (abs (sim (ei, ej) - f (dist (xi, xj))), untuk beberapa fungsi yang sesuai f dan metrik Fungsi f mengubah jarak dalam penyematan ke nilai mirip-kesamaan, Anda harus bereksperimen sedikit, tetapi 1 / dist atau exp ^ -dist adalah titik awal yang baik. Anda juga harus bereksperimen pada yang terbaik Dimensi untuk xi. Dari sana, Anda dapat menggunakan pengelompokan konvensional pada xi. Idenya di sini adalah bahwa Anda hampir dapat (dalam arti paling cocok) mengubah jarak Anda dalam penyematan ke nilai-nilai kesamaan, sehingga mereka akan mengelompok dengan benar.

  4. Pada penggunaan parameter yang telah ditentukan, semua algoritma memiliki beberapa penyetelan. DBSCAN dapat menemukan jumlah cluster, tetapi Anda masih perlu memberikan beberapa parameter. Secara umum, penyetelan memerlukan beberapa kali proses algoritme dengan nilai yang berbeda untuk parameter yang dapat disetel, bersama dengan beberapa fungsi yang mengevaluasi good-of-clustering (baik dihitung secara terpisah, disediakan oleh algoritma pengelompokan itu sendiri, atau hanya dilirik :) Jika karakter dari data Anda tidak berubah, Anda dapat menyetel sekali dan kemudian menggunakan parameter tetap itu; jika itu berubah maka Anda harus menyetel untuk setiap menjalankan. Anda dapat menemukannya dengan menyetel untuk setiap pelarian dan kemudian membandingkan seberapa baik parameter dari satu run bekerja pada yang lain, dibandingkan dengan parameter yang secara khusus disetel untuk itu.

Alex I
sumber
7

Alex membuat sejumlah poin bagus, meskipun saya mungkin harus sedikit menekan implikasinya bahwa DBSCAN adalah algoritma pengelompokan terbaik untuk digunakan di sini. Bergantung pada implementasi Anda, dan apakah Anda menggunakan indeks dipercepat atau tidak (banyak implementasi tidak), kompleksitas waktu dan ruang Anda berdua O(n2), yang jauh dari ideal.

Secara pribadi, algoritma pengelompokan go-to saya adalah OpenOrd untuk clustering pemenang-pengambilan-semua dan FLAME untuk pengelompokan fuzzy. Kedua metode tidak peduli apakah metrik yang digunakan adalah kesamaan atau jarak (FLAME pada khususnya hampir identik di kedua konstruksi). Implementasi OpenOrd di Gephi adalah O(nlogn)dan dikenal lebih terukur daripada algoritma pengelompokan lainnya yang ada dalam paket Gephi.

FLAME di sisi lain sangat bagus jika Anda mencari metode pengelompokan fuzzy. Meskipun kompleksitas FLAME sedikit lebih sulit untuk ditentukan karena ini merupakan proses berulang, ia telah terbukti sub-kuadratik, dan serupa dalam kecepatan lari ke knn.

indico
sumber
4

DBSCAN (lihat juga: DBSCAN Umum) tidak memerlukan jarak. Yang dibutuhkan hanyalah keputusan biner . Umumnya, orang akan menggunakan "jarak <epsilon" tetapi tidak ada yang mengatakan Anda tidak dapat menggunakan "kesamaan> epsilon" sebagai gantinya. Ketidaksetaraan segitiga dll tidak diperlukan.

Perbanyakan afinitas, seperti namanya, menggunakan kesamaan.

Pengelompokan hierarki, kecuali mungkin hubungan Ward, tidak membuat asumsi apa pun. Dalam banyak implementasi Anda hanya dapat menggunakan jarak negatif ketika Anda memiliki kesamaan, dan itu akan berfungsi dengan baik. Karena semua yang diperlukan adalah min, maks, dan <.

K-means Kernel dapat bekerja JIKA kesamaan Anda adalah fungsi kernel yang baik. Anggap saja sebagai k-means dalam ruang vektor yang berbeda, di mana jarak Euclidean sesuai dengan fungsi kesamaan Anda. Tetapi Anda perlu tahu k.

PAM (K-medoid) harus bekerja. Tetapkan setiap objek ke medoid yang paling mirip, lalu pilih objek dengan kemiripan rata-rata tertinggi sebagai medoid baru ... tidak diperlukan ketimpangan segitiga.

... dan mungkin masih banyak lagi. Ada ratusan algoritma pengelompokan. Sebagian besar harus bekerja IMHO. Sangat sedikit yang benar-benar membutuhkan properti metrik. K-means mungkin memiliki persyaratan terkuat: ia meminimalkan varians (bukan jarak, atau kesamaan), dan Anda harus dapat menghitung cara.

Anony-Mousse -Reinstate Monica
sumber