Связь между (1) хеш-функцией, (2) длиной подписи и (3) сходством Жаккара?

Я пытаюсь понять/реализовать сходство jaccard на основе minHash в python. Основная цель — использовать его в MapReduce. Однако мне не ясно, как выбор хэш-функции и длины подписи влияет на частоту ошибок при вычислении подобия Жаккара. Из википедии я обнаружил, что в целом длина подписи (K) и ошибка (e), связанные с вычисленным сходством жаккара, составляют k = O (1/e ^ 2). Я попытался реализовать minHash в python:

import random
import sys

#ERROR_THRESHOLD = 0.05
#SIG_LENGTH = int(1/(ERROR_THRESHOLD**2))
_memomask = {}

def hash_values(n, x):
    """Compute n different hash values"""
    values = []
    for i in range(n):
        mask = _memomask.get(i)
        if mask is None:
            random.seed(i)
            mask = _memomask[i] = random.getrandbits(32)
        values.append((hash(str(x)) % mask))
    return values


def compare_signatures(x, y):
    """Compare MinHash Signatures"""
    size = len(x)

    if size != len(y): raise Exception("Different signature length")
    if size == 0: raise Exception("signature length is zero")

    counter = 0
    for i in range(size): counter += int(x[i] == y[i])
    return counter/float(size)

items = [['A',3], ['A',6], ['A',9], ['B',2], ['B',4], ['B',6], ['B',8]]

for SIG_LENGTH in [1, 10, 100, 400, 1000]:
    #Step 1: Compute Hash Signature for each token
    data = []
    for item in items:
        values = hash_values(SIG_LENGTH, item[1])
        key = item[0]    
        data.append((key, values))

    #Step 2: Group by Key and compute MinHash for each index
    signatures = {}
    for item in data:
        key = item[0]
        values = item[1]
        if key not in signatures: signatures[key] = [-1.0]*SIG_LENGTH
        cur_signature = signatures[key]   

        signatures[key] = [(values[i] if cur_signature[i] == -1.0 else min(values[i], cur_signature[i])) for i in range(SIG_LENGTH)]

    #Step 3: Compute Probability of minHash signature to be same
    keys = signatures.keys()
    key_length = len(keys)
    print "Jaccard Similarity based on signature of length {0}".format(SIG_LENGTH)
    for i in range(key_length):
        x_key = keys[i]
        x_sig = signatures[x_key]
        for j in range(i+1,key_length):
            y_key = keys[j]
            y_sig = signatures[y_key]
            print "J({0},{1}) = {2}".format(x_key, y_key, compare_signatures(x_sig, y_sig))

В моем тесте я обнаружил, что точность увеличивается по мере увеличения длины подписи, но затем она начинает уменьшаться (или остается стабильной). Мне интересно, это из-за выбора хэш-функции. Если да, может ли кто-нибудь предложить хорошую хеш-функцию для использования.

Я нашел связанный пост, но до сих пор не ясно: ">Сколько хеш-функций требуется для алгоритма minhash


python hash-function minhash
person user3142979    schedule 29.12.2013    source источник
comment
Я переместил код в строку. Если он слишком большой, вам следует уменьшить его, а не ссылаться на копию в другом месте. В этом случае размер в порядке, и вы все равно не можете его сильно уменьшить.   -  person Marcelo Cantos    schedule 29.12.2013

Ответы (3)


arrow_upward
1
arrow_downward

md5 и sha работают очень хорошо:

import random
import hashlib
import sys

k = int(sys.argv[1])
salts = [random.getrandbits(32) for i in range(k)]

def h(value, salt):
    m = hashlib.md5() #or hashlib.sha1()
    m.update(str(value))
    m.update(str(salt))
    return m.digest()

def get_signatures(A):
    return [min([h(x, salt) for x in A]) for salt in salts]

def compare_signatures(A, B):
    """Compare MinHash Signatures"""
    sigA = get_signatures(A)
    sigB = get_signatures(B)
    return sum(map(lambda x: int(sigA[x] == sigB[x]), range(k)))/float(k)

A = [3,6,9]
B = [2,4,6,8]

print compare_signatures(A, B)

и несколько тестов:

$ for((i=10;i<2000;i*=10)); do python minhash.py $i; done
0.2
0.14
0.163
person Marat    schedule 02.02.2014

arrow_upward
0
arrow_downward

Один из способов сгенерировать большое количество хэш-функций — использовать разные начальные значения. Как в createHashFunctions здесь.

person jaguarpaw    schedule 20.02.2014

arrow_upward
0
arrow_downward

Вы спросили: 1) каково оптимальное количество хэшей для алгоритма minhash и 2) используете ли вы правильную хеш-функцию.

1) Вы упомянули: k = O(1/e^2). Это правильно, если e относится к ошибке. Вы также можете выразить это как ожидаемую ошибку (эпсилон) порядка (1/k**0,5). Помните, что это средняя ожидаемая ошибка, при которой этот алгоритм будет сходиться, а не обязательно ожидаемая ошибка для конкретного сравнения.

2) Вы можете использовать любую случайную хэш-функцию, если каждый хэш имеет разную соль. 64-битные хэши, вероятно, самые маленькие, которые я бы рекомендовал. Я бы не стал использовать MD5 или SHA, поскольку здесь вам не нужны эти накладные расходы. Обязательно возьмите модуль хеша по размеру вашей операционной системы, например. sys.maxsize() в Python. Если вы этого не сделаете, вы столкнетесь с тем, что алгоритм работает неправильно.

person apublius    schedule 13.01.2015