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

Question

这是主要问题.我有48个维向量的非常大的数据库(25,000左右),每个向量的值都在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/）。该方法相当简单，有了现成的模块，一切都会变得轻而易举。

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