江苏龙网

  1. 主页 > 生活百科 > >

LSH 局部敏感哈希( 四 )

局部敏感哈希


现有的很多检索算法并不能同时满足以上的所有性质 。以前主要采用基于空间划分的算法–tree 算法, 例如: R-tree[6], Kd-tree[7],SR-tree 。这些算法返回的结果都是精确的, 然而它们在高维数据集上时间效率并不高 。文献[5]的试验指出在维度高于10之后, 基于空间划分的算法的时间复杂度反而不如线性查找 。
1998年, P.Indy和R.Motwani提出了LSH算法的理论基础 。1999 年Gionis A,P.Indy和R.Motwani使用哈希的办法解决高维数据的快速检索问题, 这也是Basic LSH算法的雏形 。2004 年, P.Indy 提出了LSH 算法在欧几里德空间(2-范数)下的具体解决办法 。同年, 在自然语言处理领域中, Deepak Ravichandran使用二进制向量和快速检索算法改进了Basic LSH 算法, 并将其应用到大规模的名词聚类中, 但改进后的算法时间效率并不理想 。
2005 年, Mayank Bawa, Tyson Condie 和Prasanna Ganesan 提出了LSH Forest算法, 该算法使用树形结构代替哈希表, 具有自我校正参数的能力 。2006 年, R. Panigrahy用产生近邻查询点的方法提高LSH 空间效率, 但却降低了算法的空间效率 。2007年,William Josephson 和Zhe Wang使用多重探测的方法改进了欧几里德空间(2-范数)下的LSH 算法, 同时提高了算法的时间效率和空间效率 。
◆分类和聚类 根据LSH的特性 ， 即可将相近（相似）的对象散列到同一个桶之中 ， 则可以对图像、音视频、文本等丰富的高维数据进行分类或聚类 。
◆数据压缩 。如广泛地应用于信号处理及数据压缩等领域的Vector Quantization量子化技术 。总而言之 ， 哪儿需要近似kNN查询 ， 哪儿都能用上LSH.
进入LSH实现部分 ， 将按LSH的发展顺序介绍几种应用广泛的LSH算法 。1, 基于Stable Distribution投影方法 2, 基于随机超平面投影的方法; 3, SimHash; 4, Kernel LSH
1, 基于Stable Distribution投影方法
2008年IEEE Signal Process上有一篇文章Locality-Sensitive Hashing for Finding Nearest Neighbors是一篇较为容易理解的基于Stable Dsitrubution的投影方法的Tutorial, 有兴趣的可以看一下. 其思想在于高维空间中相近的物体 ， 投影（降维）后也相近 。基于Stable Distribution的投影LSH ， 就是产生满足Stable Distribution的分布进行投影 ， 最后将量化后的投影值作为value输出. 更详细的介绍在Alexandr Andoni维护的LSH主页中 ， 理论看起来比较复杂 ， 不过这就是LSH方法的鼻祖啦 ， 缺点显而易见：你需要同时选择两个参数 ， 并且量化后的哈希值是一个整数而不是bit形式的0和1 ， 你还需要再变换一次 。如果要应用到实际中 ， 简直让你抓狂 。
2, 基于随机超平面投影的方法
大神Charikar改进了上种方法的缺点 ， 提出了一种随机超平面投影LSH. 这种方法的最大优点在于：
1),不需要参数设定
2),是两个向量间的cosine距离 ， 非常适合于文本度量
3),计算后的value值是比特形式的1和0 ， 免去了前面算法的再次变化
3, SimHash
前面介绍的LSH算法 ， 都需要首先将样本特征映射为特征向量的形式 ， 使得我们需要额外存储一个映射字典 ， 难免麻烦 ， 大神Charikar又提出了大名鼎鼎的SimHash算法 ， 在满足随机超平面投影LSH特性的同时避免了额外的映射开销 ， 非常适合于token形式的特征 。首先来看SimHash的计算过程： a ， 将一个f维的向量V初始化为0；f位的二进制数S初始化为0； b ， 对每一个特征：用传统的hash算法（究竟是哪种算法并不重要 ， 只要均匀就可以）对该特征产生一个f位的签名b 。对i=1到f： 如果b的第i位为1 ， 则V的第i个元素加上该特征的权重； 否则 ， V的第i个元素减去该特征的权重 。c ， 如果V的第i个元素大于0 ， 则S的第i位为1 ， 否则为0； d ， 输出S作为签名 。
大家引用SimHash的文章通常都标为2002年这篇Similarity Estimation Techniques from Rounding Algorithms, 而这篇文章里实际是讨论了两种metric的hash. 作者猜测, SimHash应该是随机超平面投影LSH ， 而不是后来的token形式的SimHash. 其实只是概念的归属问题, 已经无关紧要了
我想很多人引用上篇文章也有部分原因是因为07年google研究院的Gurmeet Singh Manku在WWW上的这篇paper: Detecting Near-Duplicates for Web Crawling, 文中给出了simhash在网络爬虫去重工作的应用 ， 并利用编码的重排列方式解决快速Hamming距离搜索问题.


推荐阅读


上一篇：喝茶拉肚子是在排毒吗,五种养生茶是首选

下一篇：桔子茶的做法,水果茶的做法和配方