न्यूनतम हैश के साथ लोकैलिटी-सेंसिटिव हैशिंग

Question

मैंने मिन हैश के साथ एलएसएच (स्थानीय रूप से संवेदनशील हैशिंग) को लागू करने के बारे में बहुत सारे ट्यूटोरियल, दस्तावेज और कोड पढ़े हैं।

एलएसएच हैशिंग यादृच्छिक सबसेट द्वारा दो सेटों के जैककार्ड गुणांक को खोजने और उन पर बढ़ने की कोशिश करता है। मैंने code.google.com में कार्यान्वयन को देखा है लेकिन उनकी विधि को भी समझने में सक्षम नहीं था। मैं पेपर Google news personalization: scalable online collaborative filtering समझता हूं, लेकिन मैं वहां से किसी भी कार्यान्वयन को समझने में असफल रहा हूं।

क्या कोई मुझे सरल शब्दों में बता सकता है कि मिनीशैश के साथ एलएसएच को कैसे कार्यान्वित किया जाए?

Answer 1

उल्लिखित पेपर का एक लिंक गुम है।

आप मिनी-हैश एल्गोरिदम लागू करना चाहते हैं लेकिन एलएसएच प्रति से। मिन-हैशिंग एक एलएसएच तकनीक है। इस प्रकार, सामान्य रूप से एलएसएच जैककार्ड गुणांक का अनुमान नहीं लगाता है, मिन-हैशिंग की विशेष विधि करता है।

एक परिचय Mining of Massive Datasets, Chapter 3 by Anand Rajaraman and Jeff Ullman में दिया गया है।

Answer 2

एक सेट के न्यूनतम-हैश प्रतिनिधित्व Jaccard समानता, दो मिनट हैश सेट के बीच साझा हैश की सापेक्ष संख्या के रूप में दिया का आकलन करने के लिए एक कुशल साधन है:

import random 



def minhash(): 
    d1 = set(random.randint(0, 2000) for _ in range(1000)) 
    d2 = set(random.randint(0, 2000) for _ in range(1000)) 
    jacc_sim = len(d1.intersection(d2))/len(d1.union(d2)) 
    print("jaccard similarity: {}".format(jacc_sim)) 

    N_HASHES = 200 
    hash_funcs = [] 
    for i in range(N_HASHES): 
     hash_funcs.append(universal_hashing()) 

    m1 = [min([h(e) for e in d1]) for h in hash_funcs] 
    m2 = [min([h(e) for e in d2]) for h in hash_funcs] 
    minhash_sim = sum(int(m1[i] == m2[i]) for i in range(N_HASHES))/N_HASHES 
    print("min-hash similarity: {}".format(minhash_sim)) 



def universal_hashing(): 
    def rand_prime(): 
     while True: 
      p = random.randrange(2 ** 32, 2 ** 34, 2) 
      if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)): 
       return p 
    m = 2 ** 32 - 1 
    p = rand_prime() 
    a = random.randint(0, p) 
    if a % 2 == 0: 
     a += 1 
    b = random.randint(0, p) 
    def h(x): 
     return ((a * x + b) % p) % m 
    return h 




if __name__ == "__main__": 
    minhash()