python - 高维最近邻搜索和局部敏感性哈希

Question

这是主要问题。我有一个非常大的数据库(25,000 个左右)，包含 48 个维度向量，每个向量都填充了 0-255 之间的值。具体细节不是那么重要，但我认为它可能有助于提供上下文。

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

我已经尽我所能按照“稳定分布”一文中的描述编写了一个哈希函数。这是代码。

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。

我最大的问题是这些。

答:关于我在哪里可以阅读更多相关信息的任何建议。我的搜索没有产生很多结果。

B: 该方法建议它输出一个整数值(我的没有)。然后你应该尝试找到这个整数值的匹配项，匹配项表示可能是最近的邻居。我知道我应该为我的所有点计算一些散列值表，然后检查所述表的散列匹配，但我返回的值似乎不够好，我最终会得到完全匹配。我需要进行更多测试。

C:如何根据其他哈希方法构造哈希函数的说明？

Answer 1

也许这有点离题，但您可以尝试使用 PCA http://en.wikipedia.org/wiki/Principal_component_analysis用于降低数据集的维度。应该有很多为 numPy 设计的 PCA 模块(例如:http://folk.uio.no/henninri/pca_module/)。 该方法相当简单，并且使用现成的模块将非常容易。

基本上它所做的是通过在给定维数内最大化方差来减少维数(您应该能够指定所需的数字)。