MinHashing vs SimHashing

Misalkan saya memiliki lima set yang ingin saya klaster. Saya mengerti bahwa teknik SimHashing dijelaskan di sini:

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

dapat menghasilkan tiga cluster ( {A}, {B,C,D}dan {E}), misalnya, jika hasilnya adalah:

A -> h01
B -> h02
C -> h02
D -> h02
E -> h03

Demikian pula, teknik MinHashing yang dijelaskan dalam Bab 3 buku MMDS:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

juga dapat menghasilkan tiga kelompok yang sama jika hasilnya adalah:

A -> h01 - h02 - h03

B -> h04 - h05 - h06
      |
C -> h04 - h07 - h08
                  |
D -> h09 - h10 - h08

E -> h11 - h12 - h13

(Setiap set sesuai dengan tanda tangan MH yang terdiri dari tiga "band", dan dua set dikelompokkan jika setidaknya satu dari band tanda tangan mereka cocok. Lebih banyak band berarti lebih banyak peluang yang cocok.)

Namun saya memiliki beberapa pertanyaan terkait:

(1) Dapatkah SH dipahami sebagai versi pita tunggal MH?

(2) Apakah MH harus menyiratkan penggunaan struktur data seperti Union-Find untuk membangun cluster?

(3) Apakah saya benar dalam berpikir bahwa cluster, dalam kedua teknik, sebenarnya "pra-cluster", dalam arti bahwa mereka hanya set "pasangan calon"?

$O(n^2)$

Seperti yang ditunjukkan dengan tepat di atas, MinHash dan SimHash keduanya milik Locality Sensitive Hashing. Referensi: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Perbedaan utama antara keduanya adalah cara penanganan tabrakan,

1. SimHash, menggunakan kesamaan cosinus
2. MinHash, gunakan Jaccard Index.

Jawaban untuk pertanyaan Anda:

1. Tidak. Mereka menggunakan teknik penanganan tabrakan yang berbeda untuk memvalidasi kesamaan. Juga ada varian pada Fungsi Hash tunggal untuk Min Hash tetapi berfungsi berbeda. Untuk detail lebih lanjut, periksa referensi berikut, https://en.wikipedia.org/wiki/MinHash (Varian dengan fungsi hash tunggal)
2. Ya, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
3. $O(n \log n)$