精华内容
下载资源
问答
  • 局部敏感哈希

    千次阅读 2017-12-14 20:37:45
    局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍 本文主要介绍一种用于海量高维数据的近似最近邻快速查找技术——局部敏感哈希(Locality-Sensitive Hashing, LSH),内容包括了LSH的原理、LSH哈希函数集...

    局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍

    本文主要介绍一种用于海量高维数据的近似最近邻快速查找技术——局部敏感哈希(Locality-Sensitive Hashing, LSH),内容包括了LSH的原理、LSH哈希函数集、以及LSH的一些参考资料。


    一、局部敏感哈希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有些不同之处。



    局部敏感哈希示意图(from: Piotr Indyk)


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


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

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

    2)如果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)并通过索引来进行近似最近邻查找的过程如下:

    1. 离线建立索引

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

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

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

    2. 在线查找

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

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

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


    LSH在线查找时间由两个部分组成: (1)通过LSH hash functions计算hash值(桶号)的时间;(2)将查询数据与桶内的数据进行比较计算的时间。因此,LSH的查找时间至少是一个sublinear时间。为什么是“至少”?因为我们可以通过对桶内的属于建立索引来加快匹配速度,这时第(2)部分的耗时就从O(N)变成了O(logN)或O(1)(取决于采用的索引方法)。


    LSH为我们提供了一种在海量的高维数据集中查找与查询数据点(query data point)近似最相邻的某个或某些数据点。需要注意的是,LSH并不能保证一定能够查找到与query data point最相邻的数据,而是减少需要匹配的数据点个数的同时保证查找到最近邻的数据点的概率很大。




    二、LSH的应用


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

    (1)查找网络上的重复网页

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

    (2)查找相似新闻网页或文章

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

    (3)图像检索

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

    (4)音乐检索

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

    (5)指纹匹配

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



    三、LSH family

    我们在第一节介绍了LSH的原理和LSH hash function需要满足的条件,回顾一下:

    满足以下两个条件的hash functions称为(d1,d2,p1,p2)-sensitive:

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

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


    d(x,y)是x和y之间的一个距离度量(distance measure),需要说明的是,并不是所有的距离度量都能够找到满足locality-sensitive的hash functions。


    下面我们介绍一些满足不同距离度量方式下的locality-sensitive的hash functions:

    1. Jaccard distance

    Jaccard distance: (1 - Jaccard similarity),而Jaccard similarity = (A intersection B) / (A union B),Jaccard similarity通常用来判断两个集合的相似性。


    Jaccard distance对应的LSH hash function为:minhash,其是(d1,d2,1-d1,1-d2)-sensitive的。


    2. Hamming distance

    Hamming distance: 两个具有相同长度的向量中对应位置处值不同的次数。


    Hamming distance对应的LSH hash function为:H(V) = 向量V的第i位上的值,其是(d1,d2,1-d1/d,1-d2/d)-sensitive

    的。


    3. Cosine distance 

    Cosine distance:cos(theta) = A·B / |A||B| ,常用来判断两个向量之间的夹角,夹角越小,表示它们越相似。


    Cosine distance对应的LSH hash function为:H(V) = sign(V·R),R是一个随机向量。V·R可以看做是将V向R上进行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitive的。


    理解:利用随机的超平面(random hyperplane)将原始数据空间进行划分,每一个数据被投影后会落入超平面的某一侧,经过多个随机的超平面划分后,原始空间被划分为了很多cell,而位于每个cell内的数据被认为具有很大可能是相邻的(即原始数据之间的cosine distance很小)。


    4. normal Euclidean distance

    Euclidean distance是衡量D维空间中两个点之间的距离的一种距离度量方式


    Euclidean distance对应的LSH hash function为:H(V) = |V·R + b| / a,R是一个随机向量,a是桶宽,b是一个在[0,a]之间均匀分布的随机变量。V·R可以看做是将V向R上进行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的。

    理解:将原始数据空间中的数据投影到一条随机的直线(random line)上,并且该直线由很多长度等于a的线段组成,每一个数据被投影后会落入该直线上的某一个线段上(对应的桶内),将所有数据都投影到直线上后,位于同一个线段内的数据将被认为具有很大可能是相邻的(即原始数据之间的Euclidean distance很小)。



    四、增强LSH(Amplifying LSH


    通过LSH hash functions我们能够得到一个或多个hash table,每个桶内的数据之间是近邻的可能性很大。我们希望原本相邻的数据经过LSH hash后,都能够落入到相同的桶内,而不相邻的数据经过LSH hash后,都能够落入到不同的桶中。如果相邻的数据被投影到了不同的桶内,我们称为false negtive;如果不相邻的数据被投影到了相同的桶内,我们称为false positive。因此,我们在使用LSH中,我们希望能够尽量降低false negtive rate和false positive rate。


    通常,为了能够增强LSH,即使得false negtive rate和/或false positive rate降低,我们有两个途径来实现:1)在一个hash table内使用更多的LSH hash function;2)建立多个hash table。


    下面介绍一些常用的增强LSH的方法:


    1. 使用多个独立的hash table

    每个hash table由k个LSH hash function创建,每次选用k个LSH hash function(同属于一个LSH function family)就得到了一个hash table,重复多次,即可创建多个hash table。多个hash table的好处在于能够降低false positive rate。


    2. AND 与操作

    从同一个LSH function family中挑选出k个LSH function,H(X) = H(Y)有且仅当这k个Hi(X) = Hi(Y)都满足。也就是说只有当两个数据的这k个hash值都对应相同时,才会被投影到相同的桶内,只要有一个不满足就不会被投影到同一个桶内。


    AND与操作能够使得找到近邻数据的p1概率保持高概率的同时降低p2概率,即降低了falsenegtiverate。


    3. OR 或操作

    从同一个LSH function family中挑选出k个LSH function,H(X) = H(Y)有且仅当存在一个以上的Hi(X) = Hi(Y)。也就是说只要两个数据的这k个hash值中有一对以上相同时,就会被投影到相同的桶内,只有当这k个hash值都不相同时才不被投影到同一个桶内。


    OR或操作能够使得找到近邻数据的p1概率变的更大(越接近1)的同时保持p2概率较小,即降低了false positive rate。


    4. AND和OR的级联

    将与操作和或操作级联在一起,产生更多的hahs table,这样的好处在于能够使得p1更接近1,而p2更接近0。



    除了上面介绍的增强LSH的方法外,有时候我们希望将多个LSH hash function得到的hash值组合起来,在此基础上得到新的hash值,这样做的好处在于减少了存储hash table的空间。下面介绍一些常用方法:

    1. 求模运算

    new hash value = old hash value % N


    2. 随机投影

    假设通过k个LSH hash function得到了k个hash值:h1, h2..., hk。那么新的hash值采用如下公式求得:

    new hash value = h1*r1 + h2*r2 + ... + hk*rk,其中r1, r2, ..., rk是一些随机数。


    3. XOR异或

    假设通过k个LSH hash function得到了k个hash值:h1, h2..., hk。那么新的hash值采用如下公式求得:

    new hash value = h1 XOR h2 XOR h3 ... XOR hk




    五、相关参考资料


    Website:

    [1] http://people.csail.mit.edu/indyk/ (LSH原作者)

    [2] http://www.mit.edu/~andoni/LSH/ (E2LSH)


    Paper:

    [1] Approximate nearest neighbor: towards removing the curse of dimensionality

    [2] Similarity search in high dimensions via hashing

    [3] Locality-sensitive hashing scheme based on p-stable distributions 

    [4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search

    [5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

    Tutorial:

    [1] Locality-Sensitive Hashing for Finding Nearest Neighbors

    [2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing

    [3] Similarity Search in High Dimensions


    Book:

    [1] Mining of Massive Datasets
    [2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice


    Cdoe:

    [1] http://sourceforge.net/projects/lshkit/?source=directory

    [2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html 

    [3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm 

    [4] http://code.google.com/p/likelike/ 

    [5] https://github.com/yahoo/Optimal-LSH

    [6] OpenCV LSH(分别位于legacy module和flann module中)

    展开全文
  • 局部敏感哈希算法的代码
  • LSH 局部敏感哈希算法

    2018-01-15 20:28:43
    LSH (Locality-sensitive-hashing)局部敏感哈希算法 matlab实现
  • LSH局部敏感哈希

    2019-12-30 17:11:07
    阅读目录 1. 基本思想 2. 局部敏感哈希LSH 3.... 局部敏感哈希(Locality Sensitive Hashing,LSH)算法是我在前一段时间找工作时接触到...局部敏感哈希是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且...

    原地址:https://www.cnblogs.com/bonelee/p/10943021.html

    阅读目录

      局部敏感哈希(Locality Sensitive Hashing,LSH)算法是我在前一段时间找工作时接触到的一种衡量文本相似度的算法。局部敏感哈希是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现优异。它的主要作用就是从海量的数据中挖掘出相似的数据,可以具体应用到文本相似度检测、网页搜索等领域。

    回到顶部

    1. 基本思想

      局部敏感哈希的基本思想类似于一种空间域转换思想,LSH算法基于一个假设,如果两个文本在原有的数据空间是相似的,那么分别经过哈希函数转换以后的它们也具有很高的相似度;相反,如果它们本身是不相似的,那么经过转换后它们应仍不具有相似性。

      哈希函数,大家一定都很熟悉,那么什么样的哈希函数可以具有上述的功能呢,可以保持数据转化前后的相似性?当然,答案就是局部敏感哈希。

    回到顶部

    2. 局部敏感哈希LSH

      局部敏感哈希的最大特点就在于保持数据的相似性,我们通过一个反例来具体介绍一下。

      假设一个哈希函数为Hash(x) = x%8,那么我们现在有三个数据分别为255、257和1023,我们知道255和257本身在数值上具有很小的差距,也就是说它们在三者中比较相似。我们将上述的三个数据通过Hash函数转换:

      Hash(255) = 255%8 = 7;

      Hash(257) = 257%8 = 1;

      Hash(1023) = 1023%8 = 7;

      我们通过上述的转换结果可以看出,本身很相似的255和257在转换以后变得差距很大,而在数值上差很多的255和1023却对应相同的转换结果。从这个例子我们可以看出,上述的Hash函数从数值相似度角度来看,它不是一个局部敏感哈希,因为经过它转换后的数据的相似性丧失了。

      我们说局部敏感哈希要求能够保持数据的相似性,那么很多人怀疑这样的哈希函数是否真的存在。我们这样去思考这样一个极端的条件,假设一个局部敏感哈希函数具有10个不同的输出值,而现在我们具有11个完全没有相似度的数据,那么它们经过这个哈希函数必然至少存在两个不相似的数据变为了相似数据。从这个假设中,我们应该意识到局部敏感哈希是相对的,而且我们所说的保持数据的相似度不是说保持100%的相似度,而是保持最大可能的相似度

      对于局部敏感哈希“保持最大可能的相似度”的这一点,我们也可以从数据降维的角度去考虑。数据对应的维度越高,信息量也就越大,相反,如果数据进行了降维,那么毫无疑问数据所反映的信息必然会有损失。哈希函数从本质上来看就是一直在扮演数据降维的角色。

    回到顶部

     3. 文档相似度计算

      我们通过利用LSH来实现文档的相似度计算这个实例来介绍一下LSH的具体用法。

      3.1 Shingling

      假设现在有4个网页,我们将它们分别进行Shingling(将待查询的字符串集进行映射,映射到一个集合里,如字符串“abcdeeee", 映射到集合”(a,b,c,d,e)", 注意集合中元素是无重复的,这一步骤就叫做Shingling, 意即构建文档中的短字符串集合,即shingle集合。),得到如下的特征矩阵:

    其中“1”代表对应位置的Shingles在文档中出现过,“0”则代表没有出现过。

      在衡量文档的相似度中,我们有很多的方法去完成,比如利用欧式距离、编辑距离、余弦距离、Jaccard距离等来进行相似度的度量。在这里我们运用Jaccard相似度。接下来我们就要去找一种哈希函数,使得在hash后尽量还能保持这些文档之间的Jaccard相似度,即:

      我们的目标就是找到这样一种哈希函数,如果原来文档的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来文档的Jaccard相似度低,那么它们的hash值不相同的概率高,我们称之为Min-hashing(最小哈希)。

      3.2 Min-hashing

      Min-hashing定义为:特征矩阵按行进行一个随机的排列后,第一个列值为1的行的行号。举例说明如下,假设之前的特征矩阵按行进行的一个随机排列如下:

    元素

    S1

    S2

    S3

    S4

    0

    0

    1

    0

    成功

    0

    0

    1

    1

    1

    0

    0

    0

    减肥

    1

    0

    1

    1

    0

    1

    0

    1

      最小哈希值:h(S1)=3,h(S2)=5,h(S3)=1,h(S4)=2.

      为什么定义最小hash?事实上,两列的最小hash值就是这两列的Jaccard相似度的一个估计,换句话说,两列最小hash值同等的概率与其相似度相等,即P(h(Si)=h(Sj)) = sim(Si,Sj)。为什么会相等?我们考虑Si和Sj这两列,它们所在的行的所有可能结果可以分成如下三类:

      (1)A类:两列的值都为1;

      (2)B类:其中一列的值为0,另一列的值为1;

      (3)C类:两列的值都为0.

      特征矩阵相当稀疏,导致大部分的行都属于C类,但只有A、B类行的决定sim(Si,Sj),假定A类行有a个,B类行有b个,那么sim(si,sj)=a/(a+b)。现在我们只需要证明对矩阵行进行随机排列,两个的最小hash值相等的概率P(h(Si)=h(Sj))=a/(a+b),如果我们把C类行都删掉,那么第一行不是A类行就是B类行,如果第一行是A类行那么h(Si)=h(Sj),因此P(h(Si)=h(Sj))=P(删掉C类行后,第一行为A类)=A类行的数目/所有行的数目=a/(a+b),这就是最小hash的神奇之处。

      Min-hashing的具体做法可以根据如下进行表述:

      返回到我们的实例,我们首先生成一堆随机置换,把特征矩阵的每一行进行置换,然后hash function就定义为把一个列C hash成一个这样的值:就是在置换后的列C上,第一个值为1的行的行号。如下图所示:

      图中展示了三个置换,就是彩色的那三个,我现在解释其中的一个,另外两个同理。比如现在看蓝色的那个置换,置换后的Signature Matrix为:

      然后看第一列的第一个是1的行是第几行,是第2行,同理再看二三四列,分别是1,2,1,因此这四列(四个document)在这个置换下,被哈希成了2,1,2,1,就是右图中的蓝色部分,也就相当于每个document现在是1维。再通过另外两个置换然后再hash,又得到右边的另外两行,于是最终结果是每个document从7维降到了3维。我们来看看降维后的相似度情况,就是右下角那个表,给出了降维后的document两两之间的相似性。可以看出,还是挺准确的,回想一下刚刚说的:希望原来documents的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来documents的Jaccard相似度低,那么它们的hash值不相同的概率高,如何进行概率上的保证?Min-Hashing有个惊人的性质:

      就是说,对于两个document,在Min-Hashing方法中,它们hash值相等的概率等于它们降维前的Jaccard相似度。

      注:在上述例子中,我们还可以采取欧氏距离等相似度量来替代Jaccard相似度,这时候LSH相应的策略也需要进行改变,从而使得最后的hash值等于降为前的相似度。

    展开全文
  • 具有局部敏感哈希的快速kNN图构建
  • 利用局部敏感哈希学习进行跨媒体检索
  • 这个是standford 关于局部敏感哈希的课件。主要就是介绍了什么是局部敏感hash,minhash 的主要思想,以及相应的算法,怎么生成signature matrix 的基本算法,以及相关的运用。
  • 适用于短文本分类,主要是用于Knn算法进行短文本分类利用局部敏感哈希进行相应的操作
  • 局部敏感哈希算法

    2019-09-22 00:54:03
    这篇文章介绍了局部敏感哈希算法,局部敏感哈希是非监督的哈希算法。算法的输入是实数域的特征向量,输出为一个binary vector。利用哈希函数将数据点映射到不同的桶中是一种保形映射,使得数据点i和数据点j在原始...

    这篇文章介绍了局部敏感哈希算法,局部敏感哈希是非监督的哈希算法。 
    算法的输入是实数域的特征向量,输出为一个binary vector。 
    利用哈希函数将数据点映射到不同的桶中是一种保形映射,使得数据点 i 和数据点 j 在原始空间的相似度 s 与映射后的在同一个桶的概率呈现正相关。之所以这么做,主要是避免exhausted search. 如果理想状态,每个桶中的元素数目大致相同,那么查询时的运算量将从原来的数据样本数目m个降低到m/k个,其中k为桶的数目。 
    由于输出是二值向量,设其长度为L,每个哈希值其实对应着一个桶,理想情况下每个桶中都有数据,k=2L。 
    从原理上来说,代码实现是很简单的,matlab的版本的代码可见http://ttic.uchicago.edu/~gregory/download.html 
    这其实是一个比较完整的工具包

    本文主要做关键部分的代码解析。

    入口函数lsh

    T1=lsh('lsh',20,24,size(patches,1),patches,'range',255);

    第一个参数是使用的算法的类型,包括两种类型,分别是lsh和e2lsh 
    生成一个range的参数,得到的[0 0 ,…0; 255 255 ,….,255]这样的形式

    range = processRange(d,range);

    这个函数是用来产生lsh函数的。

    Is = lshfunc(type,l,k,d,varargin{:});

    l表示函数的个数,k表示一个函数中的位数,d表示数据的维度。

       for j=1:l
         % select random dimensions
         I(j).d = include(unidrnd(length(include),1,k)); % 均匀分布的,随机选中k维
         % for each dimension select a threshold
         % hash key = [[ x(:,d)' >= t ]]
         t = unifrnd(0,1,1,k).*(range(2,I(j).d)-range(1,I(j).d)); %每一维都随机选中一个阈值位于0~255之间
         I(j).t = range(1,I(j).d)+t;
         I(j).k = k;
       end

    这里hash函数就是一个简单 阈值函数,将原始的400维的数据,随机选出k=24维,变为0到1,后文会有进一步说明。l为总共生成的哈希函数的数目,这里取值为20。 
    产生Is的变量的内容如下:

     
    这里写图片描述


    d是选择的维度下标,t是维度的阈值。

    T = lshprep(type,Is,b);

     

    T这个变量存储了哈希查找哈希值以及索引信息。

      T(j).type = type;
      T(j).Args = varargin;
      T(j).I = Is(j);
      T(j).B = B;
      T(j).count = 0;
      T(j).buckets = [];
      % prepare T's table
      T(j).Index = {};
      T(j).verbose=1;
    
      % set up secondary hash table for buckets
      % max. index can be obtained by running lshhash on max. bucket
      T(j).bhash = cell(lshhash(ones(1,k)*255),1); % lshhash是一个计算hash值的函数,将24维的二值向量映射为一个哈希值

    随后的函数,将数据放入桶中,对T中变量进行赋值。

      T = lshins(T,x,ind);

    这个函数中有一些关键的处理,其中

      buck = findbucket(T(j).type,x,T(j).I);%这是一个将数据转化为二值向量的函数

     

    它里面的主要采用了矩阵的比较,本质上就是用刚才生成的阈值函数做了一个二值化。 
    其中v是一个59500*24维的二值矩阵,每一行表示一个数据样本。

     v = x(I.d,:)' <= repmat(I.t,size(x,2),1);
     v = uint8(v+128);

    但注意,输出的d维二值向量每一维并不是[0, 1],而在区间[128 129],这可能是要用于后文二次哈希的计算方便。为了后文方便说明,我们用哈希向量来简称这个二值向量。

    这里一个桶buck对应着一个哈希向量,但是桶的数目非常多,直接来进行比较是很费时间的。

      [uniqBuck,ib,bID] = unique(buck,'rows');
      keys = lshhash(uniqBuck);%返回每个桶的哈希key值

     

    例如,对j=1这个哈希函数而言,总共有14615个不同的桶(新分配空间为14615*24),如果要查找一个桶就需要14615次比较非常费时。作者的优化方案是进行二次哈希,让多个哈希向量映射为一个整型的hash-key值,用lshhash函数完成此功能。

      % allocate space for new buckets -- possibly excessive
      T(j).buckets=[T(j).buckets; zeros(length(ib),T(j).I.k,'uint8')];

     

    对每一个单独的哈希key值ib(b)

        % find which data go to bucket uniqBuck(b)
        thisBucket = find(bID==bID(ib(b)));
    
        % find out if this bucket already has anything
        % first, which bucket is it? 该hash函数T(j)下的,对应于哈希key值keys(b)的桶是否已经存在
        ihash = T(j).bhash{keys(b)}; % possible matching buckets
        if (isempty(ihash)) % nothing matches
          isb = [];
        else % may or may not match
          isb = ihash(find(all(bsxfun(@eq,uniqBuck(b,:),T(j).buckets(ihash,:)),2)));
        end

    其中

          isb = ihash(find(all(bsxfun(@eq,uniqBuck(b,:),T(j).buckets(ihash,:)),2)));

     

    是一种非常有效的写法,bsxfun(@eq ,a,b)这种形式会得到两个向量之间的逐位比较,它matlab内部的实现是通过循环来实现的。通过all在水平方向上进行判别,

    就相当于比较两个向量是否相等。这一步是比较在T(j).bhash中存放的哈希向量中是否已经存在当前的获得的哈希向量,即是否已经记录了当前的桶,这样我们就

    可以分情况讨论是往这个桶里添加新的数据,还是要先创建一个桶再添加新的数据。

      if (~isempty(isb)) % 如果isb不为空,那么即该bucket已经存在
          % adding to an existing bucket.
          oldcount=length(T(j).Index{isb}); % # elements in the bucket prior
                                            % to addition 添加前桶中元素的数目,主要是方便统计
          newIndex = [T(j).Index{isb}  ind(thisBucket)];
        else
          % creating new bucket
          newBuckets=newBuckets+1;
          oldcount=0;
          isb = oldBuckets+newBuckets;
          T(j).buckets(isb,:)=uniqBuck(b,:);%为什么用128 129表示
          T(j).bhash{keys(b)} = [T(j).bhash{keys(b)}; isb];%根据hash-key值来映射桶序号
          newIndex = ind(thisBucket);%该桶中存放的元素的下标
        end

    随后完成信息的更新

        % if there is a bound on bucket capacity, and the bucket is full,
        % keep a random subset of B elements (note: we do this rather than
        % simply skip the new elements since that could introduce bias
        % towards older elements.)
        % There is still a bias since older elements have more chances to get
        % thrown out.
        if (length(newIndex) > T(j).B)
          rp=randperm(length(newIndex));
          newIndex = newIndex(rp(1:T(j).B));% 如果超过的了桶的容量限制,那么随机选定T(j).B个数据
        end
        % ready to put this into the table
        T(j).Index{isb}= newIndex;%重新为属于该桶的数据下标赋值
        % update distinct element count
        T(j).count = T(j).count + length(newIndex)-oldcount;
        %新数目减去老数目为改变量,注意如果以前桶中有元素,是通过追加的方式添加上去的,在追加后再与T(j).B进行比较。作者这么做,就是为了保证桶中元素不会因为满了而倾向于保持老元素,新元素就加不进去了,所以先追加后然后再随机选择指定数目保留下来。当然这样做还是会造成桶中旧的元素更容易被扔掉这一情形。

    运行分析

    运行lsh函数会得到:

    Table 5 adding 13852 buckets (now 13852)
    Table 5: 59500 elements
    12619 distinct buckets
    Table 6 adding 12619 buckets (now 12619)
    Table 6: 59500 elements
    11936 distinct buckets
    Table 7 adding 11936 buckets (now 11936)
    Table 7: 59500 elements
    15997 distinct buckets

    参数查看 lshstats

    examine statistics of LSH data structure

    [mi,ma,me]=lshstats(T,B,xref,xtst,minNN)

     

    例如;

    lshstats(T1(1:5),'test',patches,patches(:,1:1000),2);

    输出为 
    Table 1: 59500 in 13404 bkts, med 1, max 4288, avg 813.19 
    Table 2: 59500 in 12661 bkts, med 1, max 2646, avg 544.55 
    Table 3: 59500 in 16147 bkts, med 1, max 4057, avg 751.01 
    Table 4: 59500 in 11627 bkts, med 1, max 4989, avg 864.60 
    Table 5: 59500 in 13630 bkts, med 1, max 3528, avg 601.55

    这表示table1有13404 个桶,平均容量是每个桶1个数据,最大容量为4288,期望容量为813.19

    Running test…10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 
    # of comparisons: mean 980.14, max 8122, failures: 54

    这里使用了5个哈希函数,它的含义是对前1000个样本进行查找,平均每次查找需要比较980个样本,但是同时失败次数为54次

    如果增加哈希函数的数目,会得到不同的结果,根据参考文献中的分析,如果增加哈希函数的数目,那么会需要更长的查找时间,但是同时recall将会增加,例如这里我们用全部的20个哈希函数来做实验。

     lshstats(T1,'test',patches,patches(:,1:1000),2);

    得到结果 
    Running test…10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 
    # of comparisons: mean 2957.24, max 13120, failures: 2 
    可以发现平均查找所需的时间变长了,但是recall相应的变高的(几乎没有错误)。

    lshlookup

    下面是查找第50个样本,在这之前,首先增加二值向量的长度,即引用文献中的b的长度,这会减少平均每个桶中的元素数目

    lshstats(T2(1:10),'test',patches,patches(:,1:1000),2);

    Table 1: 59500 in 33066 bkts, med 1, max 1829, avg 146.51 
    Table 2: 59500 in 34018 bkts, med 1, max 1638, avg 160.95 
    Table 3: 59500 in 34077 bkts, med 1, max 1386, avg 156.09 
    Table 4: 59500 in 35716 bkts, med 1, max 2813, avg 210.50 
    Table 5: 59500 in 34492 bkts, med 1, max 1470, avg 194.75 
    Table 6: 59500 in 34659 bkts, med 1, max 1543, avg 156.86 
    Table 7: 59500 in 33033 bkts, med 1, max 1232, avg 146.30 
    Table 8: 59500 in 33923 bkts, med 1, max 1955, avg 152.32 
    Table 9: 59500 in 34032 bkts, med 1, max 1718, avg 176.25 
    Table 10: 59500 in 32402 bkts, med 1, max 2862, avg 226.41

    注意avg变小了

    tic; [nnlsh,numcand]=lshlookup(patches(:,50),patches,T2,'k',11,'distfun','lpnorm','distargs',{1});toc

    算法运行结果结果实现检索一个数据所需的时间:

    时间已过 0.030697 秒。

    下面来解析这个函数的实现 
    需要完成的任务是找到所有match这个query的tables。 
    步骤1 用哈希函数T(j)获取查询x0的映射的50维(维度为哈希函数中随机选定的位数的长度,即b)二值向量,由于加了128,所以范围是在[128,129]。

      buck = findbucket(T(j).type,x0,T(j).I); 

    步骤2 将该向量转化成哈希key,这一步不是一一映射,而是多对一的映射,主要目的是为了提升向量的检索速度。

     key = lshhash(buck);

    步骤3 根据哈希key值获取所有的哈希向量,一个哈希key值对应着多个bucket

     ihash = T(j).bhash{key}; % possible matching buckets

     

    步骤4 进一步查找到该哈希向量,即找到对应的桶

     if (~isempty(ihash)) % nothing matches
        b = ihash(find(all(bsxfun(@eq,buck,T(j).buckets(ihash,:)),2)));
        if (~isempty(b))
          iNN = [iNN T(j).Index{b}]; %把该桶中的数据union起来,因为不同的哈希函数会有不同的结果
        end
      end

    步骤5 
    去除重复数据

    [iNN,iu]=unique(iNN);
    cand = length(iNN);

    步骤6 
    这一步主要是将相似列表中的数据做个排序返回。用于CBIR检索很合适。

    if (~isempty(iNN))
    
      if (strcmp(sel,'best'))
    
        D=feval(distfun,x0,Xsel(x,iNN),distargs{:});% 即比较这些桶中的最近邻数据和query的距离
        [dist,sortind]=sort(D);
        ind = find(dist(1:min(k,length(dist)))<=r);%返回小于指定距离的下标,基于iNN
        iNN=iNN(sortind(ind));% 返回相似数据,这就完成了检索
    
      else % random
    
        rp=randperm(cand);
        choose=[];
        for i=1:length(rp)
          d = feval(distfun,x0,Xsel(x,iNN(rp(i))),distargs{:});
          if (d <= r) 
        choose = [choose iNN(rp(i))];
        if (length(choose) == k)
          break;
        end
          end
        end
        iNN = choose;
      end
    
    end

    转载于:https://www.cnblogs.com/wt869054461/p/5754888.html

    展开全文
  • 主要是讲LSH的第二部分,这一章节主要是讲局部敏感哈希的主要运用。
  • 局部敏感哈希LSH

    2017-03-13 09:42:34
     局部敏感哈希(Locality Sensitive Hashing,LSH)算法是我在前一段时间找工作时接触到的一种衡量文本相似度的算法。局部敏感哈希是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现...
    
    

      局部敏感哈希(Locality Sensitive Hashing,LSH)算法是我在前一段时间找工作时接触到的一种衡量文本相似度的算法。局部敏感哈希是近似最近邻搜索算法中最流行的一种,它有坚实的理论依据并且在高维数据空间中表现优异。它的主要作用就是从海量的数据中挖掘出相似的数据,可以具体应用到文本相似度检测、网页搜索等领域。

    1. 基本思想

      局部敏感哈希的基本思想类似于一种空间域转换思想,LSH算法基于一个假设,如果两个文本在原有的数据空间是相似的,那么分别经过哈希函数转换以后的它们也具有很高的相似度;相反,如果它们本身是不相似的,那么经过转换后它们应仍不具有相似性。

      哈希函数,大家一定都很熟悉,那么什么样的哈希函数可以具有上述的功能呢,可以保持数据转化前后的相似性?当然,答案就是局部敏感哈希。

    2. 局部敏感哈希LSH

      局部敏感哈希的最大特点就在于保持数据的相似性,我们通过一个反例来具体介绍一下。

      假设一个哈希函数为Hash(x) = x%8,那么我们现在有三个数据分别为255、257和1023,我们知道255和257本身在数值上具有很小的差距,也就是说它们在三者中比较相似。我们将上述的三个数据通过Hash函数转换:

      Hash(255) = 255%8 = 7;

      Hash(257) = 257%8 = 1;

      Hash(1023) = 1023%8 = 7;

      我们通过上述的转换结果可以看出,本身很相似的255和257在转换以后变得差距很大,而在数值上差很多的255和1023却对应相同的转换结果。从这个例子我们可以看出,上述的Hash函数从数值相似度角度来看,它不是一个局部敏感哈希,因为经过它转换后的数据的相似性丧失了。

      我们说局部敏感哈希要求能够保持数据的相似性,那么很多人怀疑这样的哈希函数是否真的存在。我们这样去思考这样一个极端的条件,假设一个局部敏感哈希函数具有10个不同的输出值,而现在我们具有11个完全没有相似度的数据,那么它们经过这个哈希函数必然至少存在两个不相似的数据变为了相似数据。从这个假设中,我们应该意识到局部敏感哈希是相对的,而且我们所说的保持数据的相似度不是说保持100%的相似度,而是保持最大可能的相似度

      对于局部敏感哈希“保持最大可能的相似度”的这一点,我们也可以从数据降维的角度去考虑。数据对应的维度越高,信息量也就越大,相反,如果数据进行了降维,那么毫无疑问数据所反映的信息必然会有损失。哈希函数从本质上来看就是一直在扮演数据降维的角色。

     3. 文档相似度计算

      我们通过利用LSH来实现文档的相似度计算这个实例来介绍一下LSH的具体用法。

      3.1 Shingling

      假设现在有4个网页,我们将它们分别进行Shingling(将待查询的字符串集进行映射,映射到一个集合里,如字符串“abcdeeee", 映射到集合”(a,b,c,d,e)", 注意集合中元素是无重复的,这一步骤就叫做Shingling, 意即构建文档中的短字符串集合,即shingle集合。),得到如下的特征矩阵:

    其中“1”代表对应位置的Shingles在文档中出现过,“0”则代表没有出现过。

      在衡量文档的相似度中,我们有很多的方法去完成,比如利用欧式距离、编辑距离、余弦距离、Jaccard距离等来进行相似度的度量。在这里我们运用Jaccard相似度。接下来我们就要去找一种哈希函数,使得在hash后尽量还能保持这些文档之间的Jaccard相似度,即:

      我们的目标就是找到这样一种哈希函数,如果原来文档的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来文档的Jaccard相似度低,那么它们的hash值不相同的概率高,我们称之为Min-hashing(最小哈希)。

      3.2 Min-hashing

      Min-hashing定义为:特征矩阵按行进行一个随机的排列后,第一个列值为1的行的行号。举例说明如下,假设之前的特征矩阵按行进行的一个随机排列如下:

    元素

    S1

    S2

    S3

    S4

    0

    0

    1

    0

    成功

    0

    0

    1

    1

    1

    0

    0

    0

    减肥

    1

    0

    1

    1

    0

    1

    0

    1

      最小哈希值:h(S1)=3,h(S2)=5,h(S3)=1,h(S4)=2.

      为什么定义最小hash?事实上,两列的最小hash值就是这两列的Jaccard相似度的一个估计,换句话说,两列最小hash值同等的概率与其相似度相等,即P(h(Si)=h(Sj)) = sim(Si,Sj)。为什么会相等?我们考虑Si和Sj这两列,它们所在的行的所有可能结果可以分成如下三类:

      (1)A类:两列的值都为1;

      (2)B类:其中一列的值为0,另一列的值为1;

      (3)C类:两列的值都为0.

      特征矩阵相当稀疏,导致大部分的行都属于C类,但只有A、B类行的决定sim(Si,Sj),假定A类行有a个,B类行有b个,那么sim(si,sj)=a/(a+b)。现在我们只需要证明对矩阵行进行随机排列,两个的最小hash值相等的概率P(h(Si)=h(Sj))=a/(a+b),如果我们把C类行都删掉,那么第一行不是A类行就是B类行,如果第一行是A类行那么h(Si)=h(Sj),因此P(h(Si)=h(Sj))=P(删掉C类行后,第一行为A类)=A类行的数目/所有行的数目=a/(a+b),这就是最小hash的神奇之处。

      Min-hashing的具体做法可以根据如下进行表述:

      返回到我们的实例,我们首先生成一堆随机置换,把特征矩阵的每一行进行置换,然后hash function就定义为把一个列C hash成一个这样的值:就是在置换后的列C上,第一个值为1的行的行号。如下图所示:

      图中展示了三个置换,就是彩色的那三个,我现在解释其中的一个,另外两个同理。比如现在看蓝色的那个置换,置换后的Signature Matrix为:
      然后看第一列的第一个是1的行是第几行,是第2行,同理再看二三四列,分别是1,2,1,因此这四列(四个document)在这个置换下,被哈希成了2,1,2,1,就是右图中的蓝色部分,也就相当于每个document现在是1维。再通过另外两个置换然后再hash,又得到右边的另外两行,于是最终结果是每个document从7维降到了3维。我们来看看降维后的相似度情况,就是右下角那个表,给出了降维后的document两两之间的相似性。可以看出,还是挺准确的,回想一下刚刚说的:希望原来documents的Jaccard相似度高,那么它们的hash值相同的概率高,如果原来documents的Jaccard相似度低,那么它们的hash值不相同的概率高,如何进行概率上的保证?Min-Hashing有个惊人的性质:
      就是说,对于两个document,在Min-Hashing方法中,它们hash值相等的概率等于它们降维前的Jaccard相似度。
      注:在上述例子中,我们还可以采取欧氏距离等相似度量来替代Jaccard相似度,这时候LSH相应的策略也需要进行改变,从而使得最后的hash值等于降为前的相似度。
    展开全文
  • 局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介绍 本文主要介绍一种用于海量高维数据的近似最近邻快速查找技术——局部敏感哈希(Locality-Sensitive Hashing, LSH),内容包括了LSH的原理、LSH哈希函数集、...
  • 针对这些问题,提出一种基于位置信息熵的局部敏感哈希聚类方法。通过对生物序列使用 K 词计算其标准熵,将标准熵作为局部敏感哈希函数簇的特征向量,计算特征矩阵并应用于生物序列聚类。实验结果表明,该算法能够...
  • 局部敏感哈希(LSH)

    2020-08-06 23:49:35
    局部敏感哈希,英文locality-sensetive hashing,常简称为LSH。局部敏感哈希在部分中文文献中也会被称做位置敏感哈希。LSH是一种哈希算法,最早在1998年由Indyk在上提出。不同于我们在数据结构教材中对哈希算法的...
  • 基于局部敏感哈希算法和神经网络学习的跨媒体检索方法
  • k均值LSH 使用局部敏感哈希的k均值实现。
  • LSH(局部敏感哈希

    2015-07-03 12:13:28
    是课程结课作业,简单的介绍了LSH(局部敏感哈希) 主要分以下几部分内容 1.Nearest Neighbor Search (Retrieval) 2.Two Stages of Hash Function Learning 3.Hash Fuction 4.LSH 5.Application 6.Evaluation
  • 针对能耗社区的特点和其面临的问题,提出一个基于局部敏感哈希技术的能耗社区实时推荐系统.该推荐系统主要包括两个功能模块:1)离线数据处理模块,该模块采用局部敏感哈希技术对整个话题和资源集进行离线聚类处理;2)...
  • 欧氏距离局部敏感哈希,每次描述资源都不知道说啥,还得凑够50个字,打了这么多字,想收一个积分了。没得编了,给出文章的链接吧。https://blog.csdn.net/Wolf_xujie/article/details/103847577
  • LSHBOX,用于大规模图像检索的 C 工具箱,提供了几种局部敏感哈希(LSH)算法,还支持 Python 和 MATLAB。局部敏感哈希(LSH)是用于大规模图像检索的有效方法,并且其在最近邻域搜索算法中实现了极好的性能。LSHBOX...
  • 局部敏感哈希(LSH)是一种解决近似最近邻问题的流行算法,被证明是解决NNS的一种有效方法。高维和大规模数据库中的问题。 在p稳定LSH方案的基础上,提出了一种基于p稳定LSH的改进算法,称为基于随机性的局部敏感...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 439
精华内容 175
关键字:

局部敏感哈希