局部敏感哈希 - 寻找R的概率和值

Question

感谢那些回答了我的之前的问题并让我走到了现在这一步。

我有一个包含大约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 值？ (http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions)

C: 关于我之前的问题（B）。我发现在我的哈希函数中使用更高的R值会将我的向量映射到一个较小范围的哈希值。有没有一种优化R值的方法。

D: 大约需要使用多少张表？

- Piper Merriam

Answer 1

对于那些感兴趣的人。我找到了这份文档(http://web.mit.edu/andoni/www/papers/cSquared.pdf)，其中详细而复杂地解释了如何使用LSH来处理高维空间。

- Piper Merriam

Answer 2

你可能想要查看"MetaOptimize"--类似于机器学习的Stack Overflow。

http://metaoptimize.com/qa

你的问题并不是一个Python或编程问题，那个社区可能能够提供更多帮助。

- Jon