Memperkuat Hash Sensitifitas Lokalitas

Saya mencoba membangun hash sensitif lokalitas kosinus sehingga saya dapat menemukan kandidat pasangan barang yang serupa tanpa harus membandingkan setiap pasangan yang memungkinkan. Saya memilikinya pada dasarnya bekerja, tetapi sebagian besar pasangan dalam data saya tampaknya memiliki kesamaan cosinus dalam kisaran -0,2 hingga +0,2 jadi saya mencoba untuk memotongnya dengan sangat halus dan memilih hal-hal dengan kesamaan cosinus 0,1 ke atas.

Saya telah membaca Mining Dataset Masif Bab 3. Ini berbicara tentang meningkatkan akurasi pemilihan pasangan kandidat dengan Memperkuat Keluarga Lokal-Sensitif. Saya pikir saya baru saja memahami penjelasan matematis, tetapi saya berjuang untuk melihat bagaimana saya menerapkannya secara praktis.

Apa yang saya miliki sejauh ini adalah sebagai berikut

1. Saya telah mengatakan 1000 film masing-masing dengan peringkat dari beberapa pilihan pengguna 1M. Setiap film diwakili oleh vektor tipis skor pengguna (nomor baris = ID pengguna, nilai = skor pengguna)
2. Saya membangun N vektor acak. Panjang vektor cocok dengan panjang vektor film (yaitu jumlah pengguna). Nilai vektor adalah +1 atau -1. Saya sebenarnya menyandikan vektor-vektor ini sebagai biner untuk menghemat ruang, dengan +1 dipetakan ke 1 dan -1 dipetakan ke 0
3. Saya membuat vektor sketsa untuk setiap film dengan mengambil produk titik film dan masing-masing vektor acak N (atau lebih tepatnya, jika saya membuat matriks R dengan meletakkan vektor acak N secara horizontal dan meletakannya di atas satu sama lain maka sketsa untuk film m adalah R * m), lalu mengambil tanda setiap elemen dalam vektor yang dihasilkan, jadi saya akhiri dengan vektor sketsa untuk setiap film +1 dan -1, yang lagi-lagi saya encode sebagai biner. Setiap vektor berukuran panjang N bit.
4. Selanjutnya saya mencari sketsa serupa dengan melakukan hal berikut
   1. Saya membagi vektor sketsa menjadi b band r bit
   2. Setiap band r bit adalah angka. Saya menggabungkan nomor itu dengan nomor band dan menambahkan film ke ember hash di bawah nomor itu. Setiap film dapat ditambahkan ke lebih dari satu ember.
   3. Saya kemudian mencari di setiap ember. Setiap film yang berada di ember yang sama adalah pasangan kandidat.

Membandingkan ini dengan 3.6.3 mmds, langkah AND saya adalah ketika saya melihat band r bit - sepasang film melewati langkah AND jika r bit memiliki nilai yang sama. Langkah ATAU saya terjadi di kotak: film adalah pasangan calon jika keduanya berada di salah satu kotak.

Buku ini menyarankan saya untuk "memperkuat" hasil saya dengan menambahkan lebih banyak langkah AND dan ATAU, tetapi saya bingung bagaimana melakukan ini secara praktis karena penjelasan proses konstruksi untuk lapisan selanjutnya adalah dalam hal memeriksa kesetaraan berpasangan daripada memeriksa datang dengan nomor ember.

Adakah yang bisa membantu saya memahami bagaimana melakukan ini?

Saya pikir saya sudah melakukan sesuatu. Pada dasarnya saya mencari pendekatan yang bekerja di lingkungan tipe peta / pengurangan dan saya pikir pendekatan ini melakukannya.

Begitu,

• misalkan saya memiliki b band r rows dan saya ingin menambahkan tahap AND lainnya, ucapkan c AND lainnya.
• jadi alih-alih b * r bit saya perlu hash b * r * c bit
• dan saya menjalankan prosedur saya sebelumnya c kali, setiap kali pada b * r bits
• Jika x dan y ditemukan sebagai pasangan kandidat oleh salah satu dari prosedur ini, ia memancarkan pasangan nilai kunci ((x, y), 1), dengan tupel ID (x, y) sebagai kunci dan nilai 1
• Pada akhir prosedur c saya mengelompokkan pasangan ini dengan kunci dan jumlah
• Setiap pasangan (x, y) dengan jumlah yang sama dengan c adalah pasangan calon di setiap putaran c, dan demikian pula pasangan calon dari seluruh prosedur.

Jadi sekarang saya punya solusi yang bisa diterapkan, dan semua yang perlu saya lakukan adalah mencari tahu apakah menggunakan 3 langkah seperti ini benar-benar akan membantu saya mendapatkan hasil yang lebih baik dengan lebih sedikit bit hash atau kinerja keseluruhan yang lebih baik ...

$$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$$ $v$$h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$$h''(x,j) =f(h'(x,rj),j)$ $$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$$ $h''(x,y)$$\hat{h}:S\to S'$$S'$, tetapi hal itu juga kemungkinan akan memperkenalkan positif palsu dan / atau negatif. Satu ide untuk hash adalah minimum untuk semua (atau minimum di semua dan semua yang terkait langsung dan tidak langsung ). Keduanya jelas akan menimbulkan bias. Saya mungkin mencoba salah satunya, meskipun saya tidak yakin hash dari satu acak DAN / ATAU akan bermakna pada waktu berikutnya. Tetapi mempertimbangkan distribusi seragam dari acak dan sejumlah besar replikasi, mungkin?$h''(x,j)$$j$$j$$y$$v$