高维最近邻搜索与局部敏感散列

Question

这是主要问题。我有一个非常大的数据库（25000个左右），有48个维向量，每个向量的值都在0-255之间。具体情况并不那么重要，但我认为这可能有助于提供背景。在

我不需要一个最近的邻居，所以在一定程度的准确度内的近似邻居搜索是可以接受的。我一直在玩弄Locality Sensitivity Hashing，但我非常迷茫。在

我已经尽我所能编写了一个hash函数，如文章“稳定分布”中所述。这是密码。在

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：Wikipedia页面指出math.floor()应该用于hashVal：这就是获取整数的方法。在

C：如果你想使用Hamming方法，你可以很简单地实现它：每个Hamming散列函数都是由一个坐标（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/）。 这个方法相当简单，有了一个随时可用的模块，它将非常简单。在

基本上，它的作用是通过在给定的维度数量内最大化方差来减少维度的数量（您应该能够指定所需的数量）。在