高维最近邻搜索和局部灵敏度散列
这是主要的问题。 我有非常大的数据库(25,000左右)的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。
我最大的问题是这些。
答:关于在哪里可以阅读更多关于此的任何建议。 我的搜索没有产生很多结果。
B:该方法建议它输出一个整数值(我不这么做)。 然后你应该尝试为这个整数值找到匹配,而匹配表示一个可能的最近邻居。 我知道我应该为我所有的点计算一些哈希值表,然后检查表中的哈希匹配,但是我返回的值似乎不够好,我最终会完全匹配。 我需要更多的测试。
C:关于如何基于其他哈希方法构建哈希函数的说明?
Maby这有点偏离主题,但您可以尝试使用PCA http://en.wikipedia.org/wiki/Principal_component_analysis降低数据集的维度。 应该有很多为numPy设计的PCA模块(例如:http://folk.uio.no/henninri/pca_module/)。 该方法相当简单,并且随时可以使用模块,这将是一个简单的方法。
基本上它是通过在给定数量的维度内最大化方差来减少维度的数量(您应该能够指定期望的数量)。
这里有两个答案:
B :维基百科页面指出应该在hashVal
上使用math.floor()
:这就是你如何获得整数。
C :如果你想使用Hamming方法,你可以很简单地实现它:每个Hamming哈希函数只是由一个坐标(0到47之间)和一个位数(0到7之间)来定义。 您可以通过以下方式获得给定位b
的整数值:
bool(i & 2**b)
链接地址: http://www.djcxy.com/p/46893.html
上一篇: High Dimension Nearest Neighbor Search and Locality Sensitivity Hashing