局部敏感哈希python实现_局部敏感哈希（LSH）
⼀. 近邻搜索
局部敏感哈希，英⽂locality-sensetive hashing，常简称为LSH。局部敏感哈希在部分中⽂⽂献中也会被称做位置敏感哈希。LSH是⼀种哈希算法，最早在1998年由Indyk在上提出。不同于我们在数据结构教材中对哈希算法的认识，哈希最开始是为了减少冲突⽅便快速增删改查，在这⾥LSH恰恰相反，它利⽤的正式哈希冲突加速检索，并且效果极其明显。
LSH主要运⽤到⾼维海量数据的快速近似查。近似查便是⽐较数据点之间的距离或者是相似度。因此，很明显，LSH是向量空间模型下的东西。⼀切数据都是以点或者说以向量的形式表现出来的。在细说LSH之前必须先提⼀下K最近邻查 (kNN，k-Nearest Neighbor)与c 最近邻查 (cNN，c-Nearest Neighbor )。      kNN问题就不多说了，这个⼤家应该都清楚，在⼀个点集中寻距离⽬标点最近的K个点。我们主要提⼀下cNN问题。⾸先给出最近邻查(NN，Nearest Neighbor)的定义。
python教材下载
定义 1： 给定⼀拥有n个点的点P，在此集合中寻距离q 点最近的⼀个点。
这个定义很容易被理解，需要说明的是这个距离是个⼴义的概念，并没有说⼀定是欧式距离。随着需求的不同可以是不同的距离度量⼿段。那么接下来给出cNN问题的定义。  　
z型钢性心定义 2： 给定⼀拥有n个点的点集P，在点集中寻点 这个 满⾜ 其中d 是P中 距离古点最近⼀点到的的距离。
cNN不同于kNN，cNN和距离的联系更加紧密。LSH本⾝设计出来是专门针对解决cNN问题，⽽不是kNN问题，但是很多时候kNN与cNN 有着相似的解集。因此LSH也可以运⽤在kNN问题上。这些问题若使⽤⼀⼀匹配的暴⼒搜索⽅式会消耗⼤量的时间，即使这个时间复杂度是线性的。
也许⼀次两次遍历整个数据集不会消耗很多时间，但是如果是以⽤户检索访问的形式表现出来可以发现查询的⽤户多了，每个⽤户都需要消耗掉⼀些资源，服务器往往会承受巨⼤负荷。那么即使是线性的复杂度也是不可以忍受的。早期为了解决这类问题涌现出了许多基于树形结构的搜索⽅案，如KD树，SR树。但是这些⽅法只适⽤于低维数据。⾃从LSH的出现，⾼维数据的近似查便得到了⼀定的解决。
⼆. LSH的定义
LSH不像树形结构的⽅法可以得到精确的结果，LSH所得到的是⼀个近似的结果，因为在很多领域中并不需⾮常⾼的精确度。即使是近似解，但有时候这个近似程度⼏乎和精准解⼀致。    LSH的主要思想是，⾼维空间的两点若距离很近，那么设计⼀种哈希函数对这两点进⾏哈希值计算，使得他们哈希值有很⼤的概率是⼀样的。同时若两点之间的距离较远，他们哈希值相同的概率会很⼩。给出LSH的
定义如下：
定义3： 给定⼀族哈希函数H，H是⼀个从欧式空间S到哈希编码空间U的映射。如果以下两个条件都满⾜, 则称此 哈希函数满⾜性。
若则若则
定义3中B表⽰的是以q为中⼼， 或 为半径的空间。其实还有个版本的定义, ⽤的是距离的⽅式, 其实都是⼀样的。(⾄于说为什么是同时时出现，如果要严密的说这确实是个问题，但是⼈家⼤⽜的论⽂下的定义, 不要在意这些细节 我绘制了⼀幅图来说明⼀下这个定义。
三. 曼哈顿距离转换成汉明距离
从理论讲解的逻辑顺序上来说，现在还没到⾮要讲具体哈希函数的时候，但是为了⽅便理解，必须要举⼀个实例来讲解会好⼀些。那么就以曼哈顿距离下(其实⽤的是汉明距离的特性)的LSH哈希函数族作为⼀个参考的例⼦讲解。  　曼哈顿距离⼜称L1L1范数距离。其具体定义如下：
定义 4： 在n维欧式空间 中任意两点 他们之间的买哈顿距离为:
其实曼哈顿距离我们应该并不陌⽣。他与欧式距离(L2范数距离)的差别就像直⾓三⾓形两边之和与斜
边的差别。其实在这篇论⽂发表的时候欧式距离的哈希函数还没有被探究出来，原本LSH的设计其实是想解决欧式距离度量下的近似搜索。所以当时这个事情搞得就很尴尬，然后我们的⼤⽜Indyk等⼈就强⾏解释，⼤致意思是：不要在意这些细节，曼哈顿和欧式距离差不多。他在⽂章中提出了两个关键的问题。  　
1.使⽤L1范数距离进⾏度量。
2.所有坐标全部被正整数化。  　对于第⼀条他解释说L1范数距离与L2范数距离在进⾏近似查时得到的结果⾮常相似。对于第⼆条，整数化是为了⽅便进⾏01编码。
对数据集 所有的点, 令C作为所有点中坐标的最⼤值m, 也就是上限。下限是0，这个很明显。然后就可以把 嵌⼊汉明空间 其中 此处 是数据点在原来欧式空间的维度。对于 个点 如果⽤ '空间的坐标表⽰就是:
Unary_ 是⼀串长度为 ⼆进制的汉明码，其意思是前 位为1 后 位为0。举个例⼦, C若为5 x 为3，则 Unary=11100 。 是多个 Unary 拼接⽽成。此时可以发现对于两点 他们之间的曼哈顿距离和通过变换坐标后的汉明距 离是⼀样的。到此处, 我们可以针对汉明距离来定义⼀族哈希函数。
##四. 汉明距离下的LSH哈希函数
办公软件2003
五. LSH的重要参数
当基本哈希函数确定, 理论上讲只要 通过改变 l都可以将 时的哈希概率差距拉的很⼤。代价是要 ⾜够⼤的 这也是LSH⼀个致命的弊病。 说了这么多我们来举⼀个实例帮助理解。
例1：数据点集合P由以下6个点构成:
可知坐标出现的最⼤值是4，则 维度为2, 则 显然n 。我们进⾏8位汉明码编码。
若我我们现在采⽤k = 2, l = 3⽣成哈希函数。 由 构成。每个 由它对应的 构成
假设有如下结果。 分别抽取第2，4位。 分别抽取第1，6位。 分别抽取第3，8位。 哈希表的分布如下图所⽰。
可以计算出 。则分别取出表1,2，3的11，11，11号哈希桶的数据点与q⽐较。依次是C,D,E,F。算出距离q最近的点为F。当然这个例⼦可能效果不是很明显。原始搜索空间为6个点, 现在搜索空间为4个点。对于刚接触LSH的⼈会有个疑问。如果不同哈希表的数据点重复了 怎么办, 会不会增加搜索空间的⼤⼩。
⾸先要说的是这个概率很⼩, 为什么呢。试想假设两个不同哈希表的哈希桶对 查询有相同点, 这意味着
在两张哈希表中这个点与q都有相同哈希值。如果使⽤单个哈希函数q和此点被哈希到⼀起的概率 为 则刚才那个事件发⽣的概率为 这个概率是很⼩的。当然也有很多办法可以解决这个问题。这不是⼀个⼤问 题。
我在实际运⽤时k⼤概总是取10-20之间的数, l⼤致20-100左右。每次对 q进⾏候选点匹配时, 候选的样本点数量已 经是P的⼗分之⼀到百分之⼀了。就好⽐P有10000个数据点, 使⽤暴⼒匹配要遍历整个数据集, 使⽤LSH可能只要匹配1 00到1000个点就可以了。⽽且往往我都能到最近点。即使不到最近的，总体成功率也在90%-98%左右。
之前讲解的是⼀个⼤致思想，有很多细节没有说明⽩。 ⽐如哈希表和哈希桶的具体表现形式。就好⽐我给出的是个逻辑结构, 并没有说清楚它的物理结构。现在说说通常是怎么 具体实施的。其实我想说的是物理结构这个东西每个⼈都可以设计⼀个⾃⼰习惯的，不⼀定⾮要按某个标准来。⾞要的是 思想。 当k的数值很⼤时, 对于拥有⼤量数据点的 产⽣不同的哈希值会很多。这种⼆进制的编码的哈希值最多可以有2种。这样⼀来可能会产⽣⼤量哈希桶, 于是平我们可以采⽤⼀种⽅法, 叫⼆级哈希。⾸先我们可以将数据点p哈希到编码 为 的哈希桶。
然后我们可以⽤⼀个普通的哈希将哈希桶 哈希到⼀张⼤⼩为M 的哈希表中。注意这⾥的 是针对 哈希桶的数⽬⽽不是针对点的数量。⾄于第⼆个哈希具体这么做, 我想学过数据结构的同学都应该知道。对
于哈希桶⽽ ⾔，我们限制它的⼤⼩为 也就是说它最多可以放下 个点。当它的点数量达到B时, 原本我们可以重新开辟⼀段空间 放多余的点, 但是我不放⼊, 舍弃它。
假设点集P有n个点, M与B有如下关系：
是内存利⽤率。对查询q的近邻点时，我们要搜索所有哈希表⾄少 个点。因此磁盘的访问是有上界的，上界便是l。 我们现在来分析下l，k 的取值问题。⾸先我们列出两个事件。 假如我们的哈希函数是满⾜ 性的。
P1：如果存在⼀个点 ⾄少存在⼀个 满⾜
P2： q通过 哈希到的块中仅包含 以外的点的块数⼩于cl。
定理 则P1,P2可以保证⾄少 的概率。其中
总结:
以上便是LSH的基本理论, 我总结⼀下。对于LSH算的主要流程分为两个部分，⼀个是建⽴哈希结构，另⼀个便是检 索。在知道具体度量⽅式的情况下，利⽤该度量下的LSH哈希函数，建⽴哈希结构。⾸先选取合适的k，l参数，然后建⽴ l张哈希表，每张哈希表⽤k个独⽴抽取的基本哈希函数联合判断，
建⽴哈希表的内部结构。哈希值相同的点放在⼀起，哈 希值不同的放在不同的地⽅。⾄于查询，当q成为我们的查询点, ⾸先计算q在每张哈希表的哈希值，取出对应哈希值的哈 希桶内所有点，与q做距离计算。到满⾜我们条件的点作为查询结果。
六、局部敏感哈希规整
说到Hash，⼤家都很熟悉，是⼀种典型的Key-Value结构，最常见的算法莫过于MD5。其设计思想是使Key集合中的任意关键字能够尽可能均匀的变换到Value空间中，不同的Key对应不同的Value，即使Key值只有轻微变化，Value值也会发⽣很⼤地变化。这样特性可以作为⽂件的唯⼀标识，在做下载校验时我们就使⽤了这个特性。但是有没有这样⼀种Hash呢？他能够使相似Key值计算出的Value值相同或在某种度量下相近呢？甚⾄得到的Value值能够保留原始⽂件的信息，这样相同或相近的⽂件能够以Hash的⽅式被快速检索出来，或⽤作快速的相似性⽐对。位置敏感哈希(Local Sensitive Hashing, LSH)正好满⾜了这种需求，在⼤规模数据处理中应⽤⾮常⼴泛，例如已下场景：
1. 近似检测(Near-duplicate detection)：通常运⽤在⽹页去重⽅⾯。在搜索中往往会遇到内容相似的重复页⾯，它们中⼤多是由于⽹站
之间转载造成的。可以对页⾯计算LSH，通过查相等或相近的LSH值到Near-duplicate。
2. 图像、⾳频检索：通常图像、⾳频⽂件都⽐较⼤，并且⽐较起来相对⿇烦，我们可以事先对其计算LSH，⽤作信息指纹，这样可以给
定⼀个⽂件的LSH值，快速到与其相等或相近的图像和⽂件。
3. 聚类：将LSH值作为样本特征，将相同或相近的LSH值的样本合并在⼀起作为⼀个类别。
LSH(Location Sensitive Hash)，即位置敏感哈希函数。与⼀般哈希函数不同的是位置敏感性，也就是散列前的相似点经过哈希之后，也能够在⼀定程度上相似，并且具有⼀定的概率保证。 LSH的形式化定义可参见前⾯部分。
如下图，空间上的点经位置敏感哈希函数散列之后，对于q，其rNN有可能散列到同⼀个桶(如第⼀个桶)，即散列到第⼀个桶的概率较⼤，会⼤于某⼀个概率阈值p1;⽽其(1+emxilong)rNN之外的对象则不太可能散列到第⼀个桶，即散列到第⼀个桶的概率很⼩，会⼩于某个阈值webservice接口地址格式
p2.
LSH的作⽤:
◆⾼维下近似查询 相似性检索在各种领域特别是在视频、⾳频、图像、⽂本等含有丰富特征信息领域
中的应⽤变得越来越重要。丰富的特征信息⼀般⽤⾼维向量表⽰，由此相似性检索⼀般通过K近邻或近似近邻查询来实现。⼀个理想的相似性检索⼀般需要满⾜以下四个条件[4]：
1. ⾼准确性。即返回的结果和线性查的结果接近。
2. 空间复杂度低。即占⽤内存空间少。理想状态下，空间复杂度随数据集呈线性增长，但不会远⼤于数据集的⼤⼩。
3. 时间复杂度低。检索的时间复杂度最好为O(1)或O(logN)。
4. ⽀持⾼维度。能够较灵活地⽀持⾼维数据的检索。
此外, 检索模式应能快速地构造索引数据结构, 并且可以完成插⼊、删除等操作。
传统主要⽅法是基于空间划分的算法——tree类似算法，如R-tree，Kd-tree，SR-tree。这种算法返回的结果是精确的，但是这种算法在⾼维数据集上的时间效率并不⾼。实验[5]指出维度⾼于10之后，基于空间划分的算法时间复杂度反⽽不如线性查。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.
mockingbird钢琴谱进⼊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距离搜索问题.
4, Kernel LSH
gzip头中的幻数不正确前⾯讲了三种LSH算法，基本可以解决⼀般情况下的问题，不过对于某些特定情况还是不⾏：⽐如输⼊的key值不是均匀分布在整个空间中，可能只是集中在某个⼩区域内，需要在这个区域内放⼤距离尺度。⼜⽐如我们采⽤直⽅图作为特征，往往会dense⼀些，向量只分布在⼤于0的区域中，不适合采⽤cosine距离，⽽stable Distribution投影⽅法参数太过敏感，实际设计起来较为困难和易错，不免让我们联想，是否有RBF kernel这样的东西能够⽅便的缩放距离尺度呢？或是我们想得到别的相似度表⽰⽅式。这⾥就需要更加fancy的kernel LSH了。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。