Местность Чувствительное Хеширование - нахождение вероятностей и значений для R

Благодаря тем, кто ответил на мои предыдущие вопросы и получил меня настолько далеко.

У меня есть таблица приблизительно 25 000 векторов, каждого с 48 размерами, со значениями в пределах от 0-255.

Я пытаюсь разработать Местность Чувствительный Хеш (http://en.wikipedia.org/wiki/Locality-sensitive_hashing) алгоритм для нахождения, что близкий соседний или самый близкий сосед указывает.

Моя текущая функция LSH - это:

def lsh(vector, r = 1.0, a = None, b = None):
    if not a:
        a = [normalvariate(10, 4) for i in range(48)]
    if not b:
        b = uniform(0, r)
    hashVal = floor((sum([a[i]*vector[i] for i in range(48)]) + b)/r)
    return int(hashVal)

Мои вопросы в этой точке:

A: Есть ли оптимальные значения для "normalvariate (10, 4)" часть моего кода. Это - Python, созданные в random.normalvariate (http://docs.python.org/library/random.html#random.normalvariate) функция, которую я использую для создания "d размерный вектор с записями, выбранными независимо из стабильного распределения". От моего экспериментирования значения, кажется, не имеют значения слишком много.

B: Наверху статьи Википедии это указывает:

если d (p, q) <= R, то h (p) = h (q) с вероятностью, по крайней мере, P1

если d (p, q)> = cR, то h (p) = h (q) с вероятностью в большей части P2

Значение R, упомянутое здесь также значение R, упомянутое под разделом Stable Distributions. (http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions)

C: Связанный с моим предыдущим вопросом (B). Я обнаружил, что использование более высоких значений R в моей функции издевательства отображает мои векторы в меньший диапазон значений хэш-функции. Есть ли способ оптимизировать мое значение R.

D: Приблизительно, сколько таблиц можно было бы использовать?

5
задан Piper Merriam 16 July 2010 в 16:59
поделиться

1 ответ

Тем, кому интересно. Я нашел этот документ ( http://web.mit.edu/andoni/www/papers/cSquared.pdf , в котором есть очень подробное, хотя и сложное объяснение того, как использовать LSH для многомерных пространств. .

2
ответ дан 15 December 2019 в 00:48
поделиться
Другие вопросы по тегам:

Похожие вопросы: