闲来无事写点东西（lsh与simhash）

热度 7已有 2282 次阅读2012-6-17 15:52 |个人分类:算法技术| hash

本人hash算法的本质就是以小的东西代替大的东西，并满足代替之前的某种关联，从而达到简化运算，进而提高性能的目的。

simhash的输入是一个向量，输出是一个f位的签名值。方便起见，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如文档的特征为n维，每一个特征向量对应一个f位的签名b（这个可以做传统的hash算法产生），那么即产生了b1，b2，b3，....等签名。备注：每一个特征的权重分别为w1,w2,w3，，，，那么：

向量V(f维)<----0, S(f位的二进制数)<------0：

for i<--1 to f

if b[i](b的第i位)==1

v[i]+w (其中b为特征向量，v[i]为v的第i维，w为b的权重)
else

v[i]-w

for i<---1 to f

if v[i]>0

S[i]=1
else

S[i]=0

return S

这个算法实际上很简单，根据最开始的前面b1，b2，，，，等，V=w1b1+w2b2+....+wnbn,所以v的每一位都是w的代数差，非0加运算，零为减运算，最后得到一个f维的v向量，再做0-1标准化，即v[i]>0置为1，其他的置为0，得S=(0,1,0,0,....,1)

lsh算法即为位置敏感hash，与一般的hash函数不同的是具有位置敏感性，也就是散列前的相似点经过hash后，也能够在一定程度上相似，并且具有一定的概率保证。这个特性非常重要，应用的地方非常多。例如图像搜索，信息检索中，在这些应用中，我们首先需要对数据进行预处理，处理出来的数据往往都是高维向量，而我们想要的搜索也好检索也好，无非是根据一个向量找一个或者多个相似的向量，这种相似性很多地方体现为距离的接近性，也就是两个高维向量的距离。因此，lsh算法的关键在于两个函数，一个是距离函数，一个是hash函数，距离可以是欧式空间距离也可以是其他度量空间的距离，距离函数选取的好坏直接影响到hash前后的敏感性。hash的选取是一个难点，除了已知的几种方法本人感觉还没有什么好的办法，这种可能主要是通过实验来测定，诸位有什么想法也可以和我互相交流。

上面提到的lsh的应用实际就是knn邻近查询，传统的knn查询中的算法主要是基于空间树的界分法，比如kd-tree,vp-tree，这种方法对于低维度的数据来说具有很大的优势，处理迅速方便，通过三角形原理能够减少一半的搜索量，搜索结果也很精确，但是一旦数据超过某个维度，这种方法反而不如线性搜索来的快，因为分支的交集太多了。

lsh的算法原理是如维度无关的，所以不会出现上面的问题，唯一的就是索引结构可能臃肿了，目前有很多人专注提出基于lsh的优化算法。