高维最近邻搜索和局部灵敏度散列

这是主要问题。我有非常大的数据库（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：有关如何基于其他哈希方法构建哈希函数的说明？

来源

2010-07-16 Piper Merriam

Maby这是一个小题目，但您可以尝试使用PCA http://en.wikipedia.org/wiki/Principal_component_analysis来降低数据集的维度。应该有大量专为numPy设计的PCA模块（例如：http://folk.uio.no/henninri/pca_module/）。该方法相当简单，并且随时可以使用模块，这将是一个快捷方式。

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

来源

2010-07-16 07:17:05

我结束了使用MTP工具包蟒蛇对我的数据进行PCA：你可以在给定的位b与得到一个整数值。非常非常有效，并且正是我一直在努力做的事情。 – 2010-07-21 23:00:09

MTP？你的意思是MDP，http://mdp-toolkit.sourceforge.net？ – denis 2010-08-25 16:10:39

这里有两个答案：

乙：维基百科页面表明math.floor()应该hashVal使用：你这是怎么获得的整数。如果你想使用汉明方法，你可以很简单地实现它：每个汉明哈希函数只是由一个坐标（0到47之间）和一个位数（0到7之间）来定义的，。

bool(i & 2**b)

来源

2010-07-16 07:51:57 EOL

高维最近邻搜索和局部灵敏度散列

回答

相关问题