CODE大全
版权声明:本文为博主原创文章,未经博主允许不得转载。

邻快速查找技术,局部敏感哈希(Locality-Sensitive Hashing, LSH)算法

发布时间:『 2017-02-28 16:47』  博客类别:架构设计  阅读(4276) 评论(0)

在检索技术中,索引一直需要研究的核心技术。当下,索引技术主要分为三类:基于树的索引技术(tree-based index)、基于哈希的索引技术(hashing-based index)与基于词的倒排索引(visual words based inverted index)。本文主要对哈希索引技术进行介绍。

在检索中,需要解决的问题是给定一个查询样本query,返回与此query相似的样本,线性搜索耗时耗力,不能承担此等重任,要想快速找到结果,必须有一种方法可以将搜索空间控制到一个可以接受的范围,哈希在检索中就是承担这样的任务,因而,这些哈希方法一般都是局部敏感(Locality-sensitive)的,即样本越相似,经过哈希后的值越有可能一样。所以,本文中介绍的技术都是局部敏感哈希(Locality Sensitive Hashing,LSH),与hashmap、hashtable等数据结构中的哈希函数有所不同。

哈希技术分类

对于哈希技术,可以按照不同的维度对齐进行划分。

按照其在检索技术中的应用方法来划分,可以分为分层法和哈希码法:

  • 分层法即为在数据查询过程中使用哈希技术在中间添加一层,将数据划分到桶中;在查询时,先对query计算桶标号,找到与query处于同一个桶的所有样本,然后按照样本之间的相似度计算方法(比如欧氏距离、余弦距离等)使用原始数据计算相似度,按照相似度的顺序返回结果,在该方法中,通常是一组或一个哈希函数形成一个表,表内有若干个桶,可以使用多个表来提高查询的准确率,但通常这是以时间为代价的。分层法的示意图如图1所示。在图1中,H1、H2等代表哈希表,g1、g2等代表哈希映射函数。

  分层法的代表算法为E2LSH

  • 哈希码法则是使用哈希码来代替原始数据进行存储,在分层法中,原始数据仍然需要以在第二层被用来计算相似度,而哈希码法不需要,它使用LSH函数直接将原始数据转换为哈希码,在计算相似度的时候使用hamming距离来衡量。转换为哈希码之后的相似度计算非常之快,比如,可以使用64bit整数来存储哈希码,计算相似度只要使用同或操作就可以得到。

  哈希码法的代表算法有很多,比如KLSH、Semantic Hashing、KSH等。

以我看来,两者的区别在于如下几点:

  • 在对哈希函数的要求上,哈希码方法对哈希函数的要求更高,因为在分层法中,即便哈希没有计算的精确,后面还有原始数据直接计算相似度来保底,得到的结果总不会太差,而哈希码没有后备保底的,胜则胜败则败。

  • 在查询的时间复杂度上,分层法的时间复杂度主要在找到桶后的样本原始数据之间的相似度计算,而哈希码则主要在query的哈希码与所有样本的哈希码之间的hamming距离的相似计算。哈希码法没有太多其他的需要,但分层法中的各个桶之间相对较均衡方能使复杂度降到最低。按照我的经验,在100W的5000维数据中,KSH比E2LSH要快一个数量级。

  • 在哈希函数的使用上,两者使用的哈希函数往往可以互通,E2LSH使用的p-stable LSH函数可以用到哈希码方法上,而KSH等哈希方法也可以用到分层法上去。

按照哈希函数来划分,可以分为无监督和有监督两种:

  • 无监督,哈希函数是基于某种概率理论的,可以达到局部敏感效果。如E2LSH等。

  • 有监督,哈希函数是从数据中学习出来的,如KSH、Semantic Hashing等。

一般来说,有监督算法比无监督算法更加精确,因而也更常用于哈希码法中。

局部敏感哈希LSH

在很多应用领域中,我们面对和需要处理的数据往往是海量并且具有很高的维度,怎样快速地从海量的高维数据集合中找到与某个数据最相似(距离最近)的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集,我们通过线性查找(Linear Search)就可以容易解决,但如果是对一个海量的高维数据集采用线性查找匹配的话,会非常耗时,因此,为了解决该问题,我们需要采用一些类似索引的技术来加快查找过程,通常这类技术称为最近邻查找(Nearest  Neighbor,AN),例如K-d tree;或近似最近邻查找(Approximate Nearest  Neighbor, ANN),例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH是ANN中的一类方法。


我们知道,通过建立Hash Table的方式我们能够得到O(1)的查找时间性能,其中关键在于选取一个hash function,将原始数据映射到相对应的桶内(bucket, hash bin),例如对数据求模:h = x mod w,w通常为一个素数。在对数据集进行hash 的过程中,会发生不同的数据被映射到了同一个桶中(即发生了冲突collision),这一般通过再次哈希将数据映射到其他空桶内来解决。这是普通Hash方法或者叫传统Hash方法,其与LSH有些不同之处。

20170228163728.png

LSH的基本思想是:将原始数据空间中的两个相邻数据点通过相同的映射或投影变换(projection)后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。也就是说,如果我们对原始数据进行一些hash映射后,我们希望原先相邻的两个数据能够被hash到相同的桶内,具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后,我们就得到了一个hash table,这些原始数据集被分散到了hash table的桶内,每个桶会落入一些原始数据,属于同一个桶内的数据就有很大可能是相邻的,当然也存在不相邻的数据被hash到了同一个桶内。因此,如果我们能够找到这样一些hash functions,使得经过它们的哈希映射变换后,原始空间中相邻的数据落入相同的桶内的话,那么我们在该数据集合中进行近邻查找就变得容易了,我们只需要将查询数据进行哈希映射得到其桶号,然后取出该桶号对应桶内的所有数据,再进行线性匹配即可查找到与查询数据相邻的数据。换句话说,我们通过hash function映射变换操作,将原始数据集合分成了多个子集合,而每个子集合中的数据间是相邻的且该子集合中的元素个数较小,因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。

那具有怎样特点的hash functions才能够使得原本相邻的两个数据点经过hash变换后会落入相同的桶内?这些hash function需要满足以下两个条件:

  • 如果d(x,y) ≤ d1, 则h(x) = h(y)的概率至少为p1;

  • 如果d(x,y) ≥ d2, 则h(x) = h(y)的概率至多为p2;

其中d(x,y)表示x和y之间的距离,d1 < d2, h(x)和h(y)分别表示对x和y进行hash变换。

满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。而通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。


使用LSH进行对海量数据建立索引(Hash table)并通过索引来进行近似最近邻查找的过程如下:

离线建立索引

  • 选取满足(d1,d2,p1,p2)-sensitive的LSH hash functions;

  • 根据对查找结果的准确率(即相邻的数据被查找到的概率)确定hash table的个数L,每个table内的hash functions的个数K,以及跟LSH hash function自身有关的参数;

  • 将所有数据经过LSH hash function哈希到相应的桶内,构成了一个或多个hash table;

在线查找

  • 将查询数据经过LSH hash function哈希得到相应的桶号;

  • 将桶号中对应的数据取出;(为了保证查找速度,通常只需要取出前2L个数据即可);

  • 计算查询数据与这2L个数据之间的相似度或距离,返回最近邻的数据;

LSH的应用

LSH的应用场景很多,凡是需要进行大量数据之间的相似度(或距离)计算的地方都可以使用LSH来加快查找匹配速度,下面列举一些应用:

  • 查找网络上的重复网页

    互联网上由于各式各样的原因(例如转载、抄袭等)会存在很多重复的网页,因此为了提高搜索引擎的检索质量或避免重复建立索引,需要查找出重复的网页,以便进行一些处理。其大致的过程如下:将互联网的文档用一个集合或词袋向量来表征,然后通过一些hash运算来判断两篇文档之间的相似度,常用的有minhash+LSH、simhash。

  • 查找相似新闻网页或文章

    与查找重复网页类似,可以通过hash的方法来判断两篇新闻网页或文章是否相似,只不过在表达新闻网页或文章时利用了它们的特点来建立表征该文档的集合。

  • 图像检索

    在图像检索领域,每张图片可以由一个或多个特征向量来表达,为了检索出与查询图片相似的图片集合,我们可以对图片数据库中的所有特征向量建立LSH索引,然后通过查找LSH索引来加快检索速度。目前图像检索技术在最近几年得到了较大的发展,有兴趣的读者可以查看基于内容的图像检索引擎的相关介绍。

  • 音乐检索

    对于一段音乐或音频信息,我们提取其音频指纹(Audio Fingerprint)来表征该音频片段,采用音频指纹的好处在于其能够保持对音频发生的一些改变的鲁棒性,例如压缩,不同的歌手录制的同一条歌曲等。为了快速检索到与查询音频或歌曲相似的歌曲,我们可以对数据库中的所有歌曲的音频指纹建立LSH索引,然后通过该索引来加快检索速度。

  • 指纹匹配

    一个手指指纹通常由一些细节来表征,通过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相同或相似。类似于图片和音乐检索,我们可以对这些细节特征建立LSH索引,加快指纹的匹配速度。

参考资料


——— 全文完 ———
如有版权问题,请联系532009913@qq.com。
关键字:   局部敏感哈希     LSH     邻快速查找技术     Locality-sensitive-h     E2LSH  
评论信息
暂无评论
发表评论
验证码: 
Powered by CODE大全 | 鄂ICP备14009759号-2 | 网站留言 Copyright © 2014-2016 CODE大全 版权所有