LSH 局部敏感哈希( 二 ) _局部敏感哈希

对数据集所有的点, 令C作为所有点中坐标的最大值m, 也就是上限。下限是0 ，这个很明显。然后就可以把嵌入汉明空间其中此处是数据点在原来欧式空间的维度。对于个点如果用 '空间的坐标表示就是:
Unary_ 是一串长度为二进制的汉明码，其意思是前位为1 后位为0 。举个例子, C若为5 x 为3 ，则 Unary=11100。是多个 Unary 拼接而成。此时可以发现对于两点他们之间的曼哈顿距离和通过变换坐标后的汉明距离是一样的。到此处, 我们可以针对汉明距离来定义一族哈希函数。
##四. 汉明距离下的LSH哈希函数

文章插图

文章插图

五. LSH的重要参数

文章插图

文章插图

【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的取值问题。首先我们列出两个事件。假如我们的哈希函数是满足性的。