学习 Local Sensitive Hash

1. 最近邻法的应用

1.1 Jaccard 相似集

如何定义相似：即相关属性交集的大小，越大则越相似。我们给相似一个数学上的定义：Jaccard 相似集。

集合 \(S\) 与集合 \(T\) 的 Jaccard 集合被定义为 \(|S \cap T|/|S \cup T|\)，即它们交集与并集的大小之比。我们简单地定义为\(SIM(S,T)\)


1.2 文件的相似度

大范围内搜索内容相似的文本是相似度分析的一个非常重要的应用：

1. 查找剽窃，即相似度查询
2. 网站针对不同主机的镜像页面维护
3. 查找同源但经过修改的文章

2. Shingling of Documents

介绍一种文本相似度检测的常用方法。

2.1 k-Shingles

任何文本都是一个由符号组成的字符串，定义 k-Shingles 为任意文本内长度为 k 的子字符串。
假设我们有文本 \(\mathcal{D}=abcdabd\)，我们取 \(k=2\)，则 \(\mathcal{D}\) 的 2-shingles 为 {\(ab, bc, cd, da, bd\)}。

2.2 choosing the shingle size

• k 应当选择一个足够大的值使得任意文本中任意 shingle 出现的概率都足够低。

举例来说对于所有ASCII字符组成的文本，选用 \(k=5\) 可以得知一共将会有 \(27^5=14,348,907\) 种不同的组合。因为普通的邮件很难有这么长的文本，所以我们估计 \(k=5\) 是一个很好的选择。然而又因为各个字母的出现频率不同，使得计算更加复杂。一般取概率 \(20^{k}\)，研究表明 \(k=9\) 是一个比较安全的设定。

2.3 Hashing Shingles

为了方便使用，我们设定一个hash函数将所有长度为k的子字符串映射到一个个编号桶中并用桶号来标记shingle。

3. Similarity-Preserving Summaries of Sets

3.1 集合的矩阵表示

行表示所有元素，列表示子集合：

本例子中，总集合为 {\(a,b,c,d,e\)}，子集合 \(S_{1}=\{a,d\}\),\(S_{2}=\{c\}\),\(S_{3}=\{b,d,e\}\),\(S_{4}=\{a,c,d\}\).
矩阵十分适合表示子集合，但是因为它总是稀疏的，所以并不适合来储存子集合。

3.2 最小哈希

如何计算出一个最小的哈希值来表示子集合们呢？我们以行为参照，遇到的第一个数字就是它的分类，这样做显然不总是能够成功分类，这时我们需要调整行的顺序，尽可能的达到分类的目的。
这里给出一个例子：

延续上图，最小哈希函数 \(h\) 映射集合到行上：
子集合 \(h(S_{1})=\{a\}\), \(h(S_{2})=\{c\}\), \(h(S_{3})=\{b\}\), \(h(S_{4}=\{a\}\).

3.3 最小哈希和 Jaccard 相似的关系

• 给出一个随机的元素排列，最小哈希函数给两个子集合同样赋值的概率等于这两个值的Jaccard 相似。

3.4 最小哈希签名

给定总矩阵 \(M\)，我们从中随机的抽取 \(n\) 种，给定子集合集合 \(S\)，我们得到 \([h_1(S), h_2(S), ..., h_n{S}]\)，这样我们从矩阵 \(M\) 得到了一个一个签名矩阵，签名矩阵一般都比 \(M\) 小很多。（列数不变，行数减少）

3.5 计算哈希最小签名

为了方便计算，我们使用一个随机哈希函数来模拟元素的随机行排列，这个哈希函数映射行数到等数量的捅中。下面是一个例子：

在获得了这些hash函数后，我们开始计算hash最小签名：
1. 定义 \(SIG(i,c)\) 为签名矩阵中第 \(i\) 个哈希第 \(c\) 列的元素。
2. 初始化置所有 \(SIG(i,c)\) 为正无穷。
3. 对每一个row \(r\) 进行计算，首先是 h_{i}({r}), 然后对每一列 \(c\)，做：

• 如果 \(c\) 在行 \(r\) 为 0， 什么也不做。
• 如果 \(c\) 在行 \(r\) 为 1， 对所有 \(i = 1,2,...,n\), 置 \(SIG(i,c)=min(SIG(i,c), h_i({r}))\)。

举例：
初始化后如下：

检测行row 0，发现 \(h_1(0)=h_2(0)=1\), 且 这一行在 \(S_1\) 与 \(S_4\) 上面为1. 所以我们改动这两列为：

之后移动到 row 1，可以发现只用改动 \(S_3\):

再之后是 row 2，只用改动 \(S_2\):

在下来是 row 3，发现 \(S_1, S_2, S_3\)都需要更改, 因为要取较小的那个值，所以 \(h_1(3)=4\) 不予赋值：

之后是 row 4，改变之后得到：


最后我们来检查这个签名表的功能。
唯一的误差来自\(SIG(S_1,S_4)\) 注意计算方式

4. Locality-Sensitive Hashing for Documents

仅仅只用最小哈希是不足以面对高维度数据的。

4.1 LSH for Minhash Signatures

LSH的基本思路是对一个项目进行多次哈希操作，经过多次哈希操作后，相似的项目更加可能被哈希操作归类到一个bin中去。这时我们仅仅考虑那些落于一个桶中的项目就可以，这大大减少了计算量。
我们希望不相似的项目永远不要被分入同一个桶中，而相似的项目也永远不要被误分到不同的桶中。

• 我们定义分到桶中的不相似项目为 false positive
• 我们定义分到桶外的相似项目为 false negative

我们使用一个高效率的方法来应用 minhash signatures：我们将整个签名矩阵的行均分为 b 个 band，每个 band 有 r 个行，总行数(哈希函数数量 \(=b\times r\)). 每一个 band 我们都设立一个同样的哈希函数去转换 r-vector.

即对哈希签名矩阵再进行哈希操作，如图中的第一个 band，其第二和第四项都是 \([0;2;1]\) 故他们被同一个哈希操作分给同一个桶的概率是 \(100\%\)。这时候不考虑其他band的情况，这两项就一定会被列为可能相似对候选。

在一个 band 里没有被哈希到一个桶里的配对，还有可能成为候选，只要在其他band里面成功配对就可以。

4.2 band 的分析

若两个文本在任何一个具体的行上被赋予同样hash值的概率为 \(s\)，则其成为候选配对项目的概率为：
本band内所有row都有同样hash的概率：\(s^r\)
本band内至少有一个row拥有不同hash：\(1-s^r\)
所有band里面hash都不完全相同的概率：\((1-s^r)^b\)
至少一个band里面hash完全相同的概率：\(1-(1-s^r)^b\)

如何计算s是一个遗留问题

4.3 Combining the Techniques

1. 选择合适的 \(k\) 值去构建 \(k\)-shingles. 可选：对 \(k\)-shingles 进行哈希操作。
2. 对 document-shingle pairs 进行排序。
3. 选择一个长度 \(n\)， 构建最小哈希签名矩阵。
4. 选择 threshold \(t\) 决定相似项目的选择标准。选择相应的 \(k\) 和 \(r\) 满足 \(n=k \times r\). 且 \(t\) 约满足 \(t=(\frac{1}{b})^{{\frac{1}{r}}}\)
5. 使用LSH去选择候选对儿
6. 检查所有的候选对，确保签名相似度都在 \(t\) 以上。

5. 距离测量

5.1 距离的定义

距离需要满足：


5.2 欧氏距离

n-维欧氏距离定义为：

注意这里使用的是 \(L_2\) 范数，其 \(L_r\) 范数下的形态为：

当 \(r=1\) 时我们得到 曼哈顿距离
另一个有趣的是 \(r\) 趋于无穷大的时候，这时候所求的是 \(|x_i-y_i|\) 的最大值在所有维度\(i\)上。

5.3 Jaccard距离

Jaccard距离定义为 \(d(x,y)=1-SIM(x,y)\)

5.4 Cosine 距离

The cosine distance between two points is the angle that the vectors to those points make
Cosine 距离测量的是两个向量之间的夹角。

5.5 Edit 距离

用来测定经过多少步的插入和删除，从 x 到 y：


5.6 Hamming 距离

两个向量的汉明距离是他们不相同部分的数量。比如 10101 和 11110 的汉明距离是 3.

6. The Theory of Locality-Sensitive Functions

第四节仅仅介绍了一种可以跟band方法合并的LSH函数 (minhash function)，这一节我们将介绍更多。

所有LSH函数需要满足：
1. 越靠近的点对越可能成为候选
2. 统计上不相关
3. 既提升速度又能够比较好的避免误分

6.1 Locality-Sensitive Functions

定义：
\(f(x)=f(y)\) x, y 作为候选对
\(f(x)\neq f(y)\) x, y 不作为候选对
所有的函数 \(f\) 组成了一个函数族。定义 \(d_1 < d_2\) 为两个在某一距离度量下的距离，我们定义一个函数族 \(\mathbb{F}\) 为 \((d_1,d_2,p_1,p_2)\) 敏感当其中任何的函数 \(f\) 满足：
* 当 \(d(x,y) \le d_1\), \(f(x)=f(y)\) 的概率至少为 \(p_1\)
* * 当 \(d(x,y) \ge d_1\), \(f(x) = f(y)\) 的概率至多为 \(p_2\)
* 

6.2 Locality-Sensitive Families for Jaccard Distance

截止目前为止，我们只有一种办法可以找到LSH函数：使用最小哈希函数并假设距离度量是 Jaccard 距离。
* 最小哈希函数是 \(((d_1,d_2,1-d_1,1-d_2))\) 敏感的。这很显然符合我的之前的标准。
举例，设定 \(d_1=0.3, d_2=0.6\)，则最小哈希函数满足 \(((0.3,0.6,0.7,0.4))\) 敏感。即，当两个项目的 Jaccard 距离至多为 0.3，也就是他们的相似度大于 0.7 的时候，有至少七成的可能将他们选择成为候选对。当他们相似度小于 0.4 时，至多只有四成可能将他们算作同一类。

6.3 扩大 Locality-Sensitive Families

应用LSH

这里我翻译了Indyk et al 的LSH matlab 代码文档

代码下载地址：http://ttic.uchicago.edu/~gregory/download.html

• 主要函数

lsh.m 在输入的数据集合上构建LSH数据结构
lshprep.m 设定并启动hash函数
lshfunc.m 设定并启动基于hash函数的hash表
lshins.m 向hash表内插入数据
lshlookup.m 使用LSH进行NNS搜索
lshstats.m 对生成的LSH数据结构进行检查

在独立的文件夹lshtst/中包含了一个简单的例子：
patches.mat - 59500 个 20x20 灰度图片片段 (转换为59500*400的矩阵)

首先载入数据集合：

>> load patches;

之后我们开始建立第一个LSH数据结构，我们建立一个拥有 20 个哈希表，使用 24-bit key 且使用简易LSH构架的LSH数据结构：

>> T1=lsh('lsh',20,24,size(patches,1),patches,'range',255);
 BUNLIMITED 24 keys 20 tables 13598 distinct buckets
Table 1 adding 13598 buckets (now 13598)
Table 1: 59500 elements 11540 distinct buckets
Table 2 adding 11540 buckets (now 11540)
Table 2: 59500 elements 11303 distinct buckets
Table 3 adding 11303 buckets (now 11303)
Table 3: 59500 elements 12046 distinct buckets
Table 4 adding 12046 buckets (now 12046)
Table 4: 59500 elements 12011 distinct buckets
Table 5 adding 12011 buckets (now 12011)
Table 5: 59500 elements 10218 distinct buckets
... ... ... ...
Table 20 adding 15435 buckets (now 15435)
Table 20: 59500 elements

lsh() 函数的输入参数依次为 1. 使用构架 2. hash 表数量 3. hash key的位数 4. 数据长度 5. 数据 6. 设定范围(?)

我们可以依次看到总共 59500 个数据在每一个hash表内的表现。例如在第一个表中，所有的数据被分在了 13598 个桶中。第二行显示了总共多少个原始数据被分类，假如我们保持桶的大小为无穷的话，这个数字永远和数据长度相当。

我们用 lshstats() 来检查学习得到的LSH数据结构的统计数据：

>> lshstats(T1);
20 tables, 24 keys
Table 1: 59500 in 13598 bkts, med 1, max 2687, avg 520.01
Table 2: 59500 in 11540 bkts, med 1, max 3605, avg 626.10
Table 3: 59500 in 11303 bkts, med 1, max 4685, avg 912.04
Table 4: 59500 in 12046 bkts, med 1, max 3385, avg 652.34
Table 5: 59500 in 12011 bkts, med 1, max 2393, avg 510.91
Table 6: 59500 in 10218 bkts, med 1, max 2645, avg 618.73
Table 7: 59500 in 11632 bkts, med 1, max 3472, avg 779.28
Table 8: 59500 in 16140 bkts, med 1, max 5474, avg 828.26
Table 9: 59500 in 13289 bkts, med 1, max 3300, avg 543.68
Table 10: 59500 in 13905 bkts, med 1, max 3087, avg 671.83
Table 11: 59500 in 13165 bkts, med 1, max 3914, avg 714.18
Table 12: 59500 in 12855 bkts, med 1, max 4510, avg 759.96
Table 13: 59500 in 15263 bkts, med 1, max 3414, avg 641.39
Table 14: 59500 in 12601 bkts, med 1, max 3228, avg 707.47
Table 15: 59500 in 14790 bkts, med 1, max 4412, avg 725.62
Table 16: 59500 in 11448 bkts, med 1, max 4144, avg 696.01
Table 17: 59500 in 17118 bkts, med 1, max 6394, avg 901.37
Table 18: 59500 in 15205 bkts, med 1, max 2971, avg 566.43
Table 19: 59500 in 11527 bkts, med 1, max 2901, avg 609.99
Table 20: 59500 in 15435 bkts, med 1, max 6199, avg 931.30
Total 59500 elements

依次显示了数据大小，桶数量，最小(?)/最大/平均数量数据在某一桶中。
通过命令 lshstats(T1,100) 可以获得更多信息：

>> lshstats(T1,100);
20 tables, 24 keys
Table 1: 59500 in 13598 bkts, med 1, max 2687, avg 520.01, 49 (25458)> 100
Table 2: 59500 in 11540 bkts, med 1, max 3605, avg 626.10, 56 (28790)> 100
Table 3: 59500 in 11303 bkts, med 1, max 4685, avg 912.04, 60 (31263)> 100
Table 4: 59500 in 12046 bkts, med 1, max 3385, avg 652.34, 54 (28664)> 100
Table 5: 59500 in 12011 bkts, med 1, max 2393, avg 510.91, 64 (27325)> 100
Table 6: 59500 in 10218 bkts, med 1, max 2645, avg 618.73, 59 (31034)> 100
Table 7: 59500 in 11632 bkts, med 1, max 3472, avg 779.28, 52 (30374)> 100
Table 8: 59500 in 16140 bkts, med 1, max 5474, avg 828.26, 51 (24696)> 100
Table 9: 59500 in 13289 bkts, med 1, max 3300, avg 543.68, 54 (27940)> 100
Table 10: 59500 in 13905 bkts, med 1, max 3087, avg 671.83, 55 (26870)> 100
Table 11: 59500 in 13165 bkts, med 1, max 3914, avg 714.18, 56 (26659)> 100
Table 12: 59500 in 12855 bkts, med 1, max 4510, avg 759.96, 59 (26986)> 100
Table 13: 59500 in 15263 bkts, med 1, max 3414, avg 641.39, 56 (25801)> 100
Table 14: 59500 in 12601 bkts, med 1, max 3228, avg 707.47, 60 (28723)> 100
Table 15: 59500 in 14790 bkts, med 1, max 4412, avg 725.62, 49 (25435)> 100
Table 16: 59500 in 11448 bkts, med 1, max 4144, avg 696.01, 66 (30972)> 100
Table 17: 59500 in 17118 bkts, med 1, max 6394, avg 901.37, 53 (24456)> 100
Table 18: 59500 in 15205 bkts, med 1, max 2971, avg 566.43, 54 (25890)> 100
Table 19: 59500 in 11527 bkts, med 1, max 2901, avg 609.99, 57 (31533)> 100
Table 20: 59500 in 15435 bkts, med 1, max 6199, avg 931.30, 49 (25821)> 100
Total 59500 elements

49 (25821)> 100 表示在该哈希表中，有 49个桶中含有超过100个数据，总共饱含了 25831 个数据。

我们还可以做测试来验LSH的表现：其中第三项是被LSH学习标记过的原始数据，第四项是我们要查找的数据，第五项是NNS的范围

>>lshstats(T1,'test',patches,patches(:,1:1000),2);
... ... ... ...
 >>Running test...10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
 # of comparisons: mean 2809.38, max 10795, failures: 4

在总共59500个数据中，我们平均对比2809.38次，最多对比10795次，失败查找4次。

当我们减少哈希表的数量时(切割使用T1的前五个)：

>>lshstats(T1(1:5),'test',patches,patches(:,1:1000),2);
Running test...10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
# of comparisons: mean 1071.22, max 8239, failures: 36

平均和最大对比数都显著下降，但是相对的失败查找增多

如果使用前十个：

>>lshstats(T1(1:10),'test',patches,patches(:,1:1000),2);
Running test...10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
# of comparisons: mean 1728.92, max 9379, failures: 11

可见hash表的数量是一个关于对比数还有失败率的tradeoff。

接下来我们研究key位数的关系并且测试

>> T2=lsh('lsh',20,50,size(patches,1),patches,'range',255);
>> lshstats(T2,'test',patches,patches(:,1:1000),2);
  Running test...10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
   # of comparisons: mean 629.64, max 5716, failures: 401

我们发现对比数进一步减少了但是失败率飙升。我们再增加20个hash表并测试：

>> T2(21:40) = lsh('lsh',20,50,size(patches,1),patches,'range',255);
>> lshstats(T2,'test',patches,patches(:,1:1000),2);
  Running test...10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
  # of comparisons: mean 832.36, max 5934, failures: 320

帮助似乎也不是很大

接下来我们看一下怎么使用lookup功能。这是我们的目标图片：

>> figure(1);imagesc(reshape(patches(:,50),20,20));colormap gray;axis image



我们来查找一下它的10个最近邻居(参数我们选用11因为它肯定能找到它自己)，并且显示：

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

>> figure(2);clf;
>> for k=1:10, subplot(2,5,k);imagesc(reshape(patches(:,nnlsh(k+1)),20,20)); colormap gray;axis image; end



使用遍历查找的方式：

tic;d=sum(abs(bsxfun(@minus,patches(:,50),patches)));
[ignore,ind]=sort(d);toc;
Elapsed time is 0.220885 seconds.



结果有着轻微的不同但是还可以啦。

如果想要使用 e2lsh scheme

>> Te=lsh('e2lsh',50,30,size(patches,1),patches,'range',255,'w',-4);

注意 -4 是间隔参数。50个函数，每个函数使用30个映射。