7

min-hashを使用してLSH（局所性鋭敏型ハッシュ）を実装する多くのチュートリアル、ドキュメント、およびコードを読みました。

LSHは、ランダムなサブセットをハッシュし、それらを集計することにより、2つのセットのJaccard係数を見つけようとします。code.google.comで実装を見てきましたが、その方法も理解できませんでした。私は紙のGoogleニュースのパーソナライズ：スケーラブルなオンライン協調フィルタリングを理解していますが、そこにある実装のいずれも理解できていません。

MinHashでLSHを実装する方法を簡単な言葉で説明してもらえますか？

4

2 に答える 2

7

min-hashアルゴリズムを実装したいが、LSH自体は実装したくない。最小ハッシュはLSH手法です。したがって、LSHは一般に、Jaccard係数を近似しませんが、最小ハッシュの特定の方法は近似します。

紹介は、AnandRajaramanとJeffUllmanによる「大量のデータセットのマイニング」の第3章に記載されています。

于 2013-02-28T13:46:38.857 に答える
1

セットの最小ハッシュ表現は、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()
于 2018-01-25T04:43:46.837 に答える