高维最近邻搜索与局部敏感哈希

Question

这里是主要问题。我有一个非常大的数据库，大约有25000个48维的向量，每个向量的值范围在0到255之间。具体细节不是特别重要，但我觉得这可以帮助提供一些背景信息。

我不需要找到最近的邻居，所以只要在一定的准确度范围内进行近似邻居搜索就可以了。我一直在尝试使用局部敏感哈希，但我真的很迷茫。

我根据文章中“稳定分布”的描述写了一个哈希函数，尽量做到最好。以下是我的代码。

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

这个哈希函数至少在某种程度上是“有效”的。如果我按照哈希值对一组点进行排序，并计算一个点与它在列表中的邻居之间的平均距离，结果大约是400，而随机选择的两个点之间的平均距离大约是530。

我最大的几个问题是：

A: 有没有建议我可以在哪里找到更多相关的资料？我搜索的结果不多。

B: 这个方法建议输出一个整数值（而我的函数没有做到这一点）。然后你应该尝试找到这个整数值的匹配项，匹配项表示可能的最近邻居。我明白我应该为所有点计算一组哈希值表，然后检查这些表中的哈希匹配，但我返回的值似乎不够精确，导致我根本找不到匹配项。我需要进行更多的测试。

C: 有没有关于如何基于其他哈希方法构建哈希函数的说明？

Answer 1

这里有两个回答：

B: 维基百科页面上提到，应该在 hashVal 上使用 math.floor()：这样你就能得到整数了。

C: 如果你想使用汉明方法，其实可以很简单地实现：每个汉明哈希函数都是由一个坐标（在0到47之间）和一个位数（在0到7之间）来定义的。你可以通过以下方式获取某个特定位 b 的整数值：

bool(i & 2**b)

Answer 2

这可能有点偏题，但你可以试试用PCA（主成分分析）来减少数据集的维度。你可以在这个链接找到更多信息：http://en.wikipedia.org/wiki/Principal_component_analysis。有很多专门为NumPy设计的PCA模块，比如这个：http://folk.uio.no/henninri/pca_module/。这个方法其实很简单，使用现成的模块就能轻松搞定。

简单来说，它的作用是通过在给定的维度中最大化方差，来减少维度的数量（你可以指定想要的维度数量）。