本帖最后由 Gass_314 于 2012-6-18 11:56 编辑 本人认为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>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的优化算法。 |
[技术| 编程·课件·Linux] 写点以前看过的东西,也为论文练下笔(simhash与lsh)
Gass_314
· 发布于 2012-06-18 11:40
· 2250 次阅读
转载文章时务必注明原作者及原始链接,并注明「发表于 软院网 RuanYuan.Net 」,并不得对作品进行修改。