Saya memiliki sekelompok set n yang saya butuhkan untuk menghitung semacam nilai "keunikan" atau "kesamaan". Saya telah menetapkan indeks Jaccard sebagai metrik yang cocok. Sayangnya, indeks Jaccard hanya beroperasi pada dua set sekaligus. Untuk menghitung kesamaan antara semua set , itu akan membutuhkan dalam urutan n 2 perhitungan Jaccard.
(Jika itu membantu, biasanya antara 10 dan 10.000, dan setiap set berisi rata-rata 500 elemen. Juga, pada akhirnya, saya tidak peduli seberapa mirip dua set tertentu - agak, saya hanya peduli apa kesamaan internal dari seluruh kelompok set adalah (Dengan kata lain, rata-rata (atau setidaknya perkiraan rata-rata yang cukup akurat) dari semua indeks Jaccard dalam grup)
Dua pertanyaan:
- Apakah ada cara untuk tetap menggunakan indeks Jaccard tanpa kompleksitas?
- Apakah ada cara yang lebih baik untuk menghitung kemiripan / keunikan himpunan di seluruh kelompok himpunan daripada cara yang saya sarankan di atas?
algorithms
time-complexity
rinogo
sumber
sumber
Jawaban:
Pilihannya adalah menggunakan Skema Tanda Tangan [1], penyaringan berbasis ukuran : skema yang menggunakan informasi ukuran untuk mengurangi jumlah pasangan yang ditetapkan yang perlu dipertimbangkan.
Mereka juga bereksperimen dengan bentuk tertimbang; di mana bobot berbasis IDF.
[1] Arasu, Arvind, Venkatesh Ganti, dan Raghav Kaushik. "Set Persamaan Efisien yang Tepat Bergabung." Dalam Prosiding Konferensi Internasional ke-32 tentang Pangkalan Data yang Sangat Besar, 918–929. VLDB '06. VLDB Endowment, 2006
sumber
Pilihan lain adalah menggunakan tautan wiki hashing sensitivitas lokal . Saya telah melihatnya digunakan dalam deteksi kemiripan komunitas oleh Wu dan Zou ( Metode pendeteksian komunitas tambahan untuk sistem penandaan sosial menggunakan hashing yang sensitif terhadap lokalitas , Neural Networks 58: 14–28; ACM DL ) yang pada dasarnya mendeteksi kemiripan antara integer atau set string.
sumber