Deteksi Duplikat Mirip dengan Kemiripan Jaccard dan MinHash

Menemukan dokumen mirip: Kemiripan Jaccard dan MinHash

• Definisi masalah
  • Membahas cara mengidentifikasi dokumen yang mirip dalam koleksi dokumen berskala besar
  • Sebagai contoh, saat mengambil halaman yang sama beberapa kali melalui web crawling, kita bisa memiliki beberapa versi dengan sedikit perbedaan metadata atau hasil edit kecil
  • Artikel ini mengeksplorasi metode deduplikasi aproksimasi menggunakan kemiripan Jaccard dan MinHash

Kemiripan

• Definisi kemiripan
  • Mendefinisikan kemiripan antara dua dokumen, dan cara menemukan pasangan dengan nilai kemiripan di atas ambang tertentu
  • Mendefinisikan fungsi kemiripan S:U×U→[0,1], dan jika S(A,B)≥S_crit maka dua dokumen dianggap sebagai duplikat aproksimasi

Kemiripan Jaccard

• Kemiripan Jaccard
  • Fungsi yang menyatakan kemiripan dua himpunan berhingga sebagai rasio antara irisan dan gabungannya
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Semakin mirip dua himpunan, semakin banyak elemen yang sama

Perluasan kemiripan Jaccard

• Metode perluasan
  • Mengubah dokumen menjadi himpunan fitur, lalu mencari himpunan dengan kemiripan Jaccard tinggi
  • Pada korpus kecil, metode ini dapat diterapkan secara langsung, tetapi pada korpus besar menjadi tidak efisien

Aproksimasi kemiripan Jaccard

• Tanda tangan MinHash
  • Menggunakan sampling untuk mengaproksimasi kemiripan Jaccard
  • Dengan menghitung terlebih dahulu tanda tangan berukuran tetap untuk tiap dokumen, kemiripan dapat diestimasi secara efisien

Menggunakan lebih banyak fungsi hash

• Banyak fungsi hash
  • Menggunakan beberapa fungsi hash untuk merangkum tiap dokumen sebagai vektor berisi k elemen
  • Dengan menghitung jumlah hash yang cocok di antara dua tanda tangan, kemiripan Jaccard dapat didekati

Membandingkan semua dokumen

• Pengelompokan dokumen
  • Mengelompokkan dokumen agar hanya dokumen yang mirip saja yang dibandingkan
  • Menggunakan nilai MinHash sebagai kunci pengelompokan untuk menemukan duplikat aproksimasi secara efisien

Deteksi duplikat yang lebih fleksibel

• Menggunakan banyak kunci
  • Menggunakan beberapa kunci untuk menempatkan dokumen ke beberapa bucket, lalu membandingkannya di dalam tiap bucket
  • Duplikat tetap bisa dideteksi bahkan pada nilai kemiripan yang lebih rendah

Kesimpulan

• Kesimpulan
  • Algoritme seperti MinHash memungkinkan pencarian dokumen mirip secara efisien
  • Diharapkan artikel ini dapat memperkenalkan algoritme semacam ini kepada lebih banyak engineer dan membantu pemahamannya

Lampiran: merepresentasikan dokumen sebagai himpunan

• n-gram

  • Merepresentasikan dokumen sebagai n-gram untuk dibandingkan
  • Tingkat presisi perbandingan berubah tergantung nilai n

• Segmentasi kata

  • Memecah dokumen menjadi kata atau token untuk digunakan sebagai fitur
  • Tokenizer yang lebih canggih juga dapat digunakan

Opini GN⁺

• Pentingnya deteksi dokumen mirip

  • Menghapus duplikasi dalam dataset besar penting untuk meningkatkan kualitas data dan menghemat ruang penyimpanan
  • Ini sangat penting terutama dalam proses web crawling atau pengumpulan data

• Kelebihan MinHash

  • MinHash dapat mendeteksi dokumen mirip dengan cara yang efisien dan scalable
  • Lebih fleksibel dibanding metode deduplikasi berbasis hash tradisional

• Teknik serupa lainnya

  • Algoritme sketch lain seperti HyperLogLog juga dapat digunakan untuk menyelesaikan masalah serupa
  • Menggabungkan kedua algoritme tersebut dapat menghasilkan solusi yang lebih kuat

• Hal yang perlu dipertimbangkan saat penerapan nyata

  • Pentingnya pemilihan fungsi hash: pemilihan fungsi hash sangat memengaruhi akurasi hasil
  • Keseimbangan antara performa dan akurasi: semakin banyak fungsi hash yang digunakan, semakin tinggi akurasinya, tetapi biaya performanya juga meningkat

• Teknologi yang direkomendasikan

  • Dapat diterapkan dengan mudah menggunakan alat seperti implementasi MinHashLSH milik Spark
  • Disarankan untuk memanfaatkan teknik ini secara aktif demi deduplikasi yang efisien pada dataset berskala besar

[GN⁺]

Opini Hacker News

• Kemiripan Jaccard dan skor F1 juga dapat digunakan dengan cara yang sama pada himpunan fuzzy

  • Pada himpunan fuzzy, perlu memilih pasangan T-Norm/T-Conorm yang sesuai
  • Metode ini berguna untuk validasi segmentasi citra medis
  • Kebanyakan orang menetapkan ambang di 0.5 dan menggunakan himpunan biner
  • Ini sangat menurunkan presisi operator validasi

• Pernah mengimplementasikan deduplikasi database pemerintah Prancis dengan Python

  • Saat ini merekomendasikan datasketch
  • Ada juga alat baru bernama rensa
  • rensa adalah versi yang lebih cepat yang ditulis dalam Rust

• Ini adalah teknik yang dikembangkan pada masa awal Google untuk deduplikasi

  • Dijelaskan secara rinci dalam "Mining Massive Datasets" karya Jeffrey Ullman
  • Teknik ini pertama kali dikembangkan di AltaVista

• Pernah mengimplementasikan sistem Minhash

  • Menyelesaikan masalah mencari invers (atau hampir invers) dari submatriks dalam matriks besar
  • Menggunakan Minhashing untuk menemukan matriks yang serupa
  • Menyesuaikan selektivitas pencarian dengan menggunakan hash multi-resolusi

• Sedang mengembangkan alat visualisasi karena Minhash dan variannya sulit dipahami

  • Rencananya akan mencakup perhitungan kemiripan Jaccard

• Lebih mudah memahami teknik ini melalui contoh kode

  • Mempelajari teknik ini dari Douglas Eck di Google
  • Digunakan untuk clustering lagu

• Tim NVIDIA merilis algoritme deduplikasi fuzzy yang dipercepat GPU

  • Menyediakan repositori GitHub dan dokumentasi
  • Contoh Python juga disertakan

• Strategi deduplikasi yang menggabungkan hashing atau jaringan saraf kecil dengan mesin pencarian vektor adalah hal yang umum

  • Ada model RETSim dari Google dan proyek mesin USearch

• Menunjukkan typo kepada penulis

  • Seharusnya S(A,C), bukan S(A,B)

• Sedang menyelesaikan masalah menggabungkan item berita serupa menjadi satu di Postgres

  • Ada 600.000 item feed
  • Konten dan ringkasannya sangat mirip