相似文档 Shingling, Minhashing, Locality-sensitive hashing

伪代码和图片出自MOOC Mining Massive Datasets

本节关心的问题:找出内容近似的文档。

三个主要技术:

  1. Shingling(N-gram)
  2. Minhashing
  3. Locality-sensitive hashing

流程:

文档->[Shingling]->k-shingles集合(Boolean Matrix)->[Minhashing]->signature矩阵->[LSH]->候补的近似文档对

1 Shingling

文档中的k-shingle是文档中k个连续的字符:

若k较大,可考虑用token 的方式减小shingles。

将文档用shingles,或shingles的token表示后,可以用 杰卡德相似系数(Jaccard similarity)来计算两个文档的相似程度:

QQ截图20150212140657

用boolean matrix来表示若干文档及其相应的shingles,矩阵每一列对应于一篇文档,每一列对应一个shingles,M_{ij}=1表示文档j中包含第i个shingles。

假设总共有6个shingles,文档1有第2,3,5个shingles,文档2有第1,3,5,6个shingles,求对应的布尔矩阵:

矩阵中两列的相似度即为两篇文档的杰卡德相似系数。

即两篇文档的杰卡德相似系数为0.4

2 Minhashing

Minhashing的作用是从boolean矩阵生成signature矩阵。

假设将boolean矩阵里的行重新随机排列一下,对每一列c而言,minhash函数h(c)的作用是在重新排列的boolean矩阵里,第c列中在从上往下数第几行里出现元素1

考虑如下boolean矩阵,左边彩色的格子表示的是三种对矩阵不同的随机排列,紫色的1对应于原布尔矩阵的第5行,表示按照紫色的排列重新排列后,原本矩阵的第5行被调换为新矩阵的第1行。右边的signature矩阵中,紫色的一行表示按照紫色的排列顺序重新排列的矩阵中,各列中首次出现1的行数。

QQ截图20150212130427

一个重要的属性:进行多次的重新排列和minhashing,两列C_1,C_2出现h(C_1)=h(C_2)的概率等于两列的杰卡德相似系数。上面代码中是指定了重新排列的顺序,下面改为随机生成。

因此,不再需要比较两个布尔矩阵两列的相似度,可以根据signature矩阵中列的相似度来近似获对应文档的相似度。

根据signature矩阵的计算结果表示第1,3两列相似度为0.78,第2,4两列的相似度为0.74

如果从布尔矩阵计算,则1,3两列相似度为0.75,第2,4两列的相似度为0.75。

实践中,如果布尔矩阵行数非常大,那么,存储行的随机排列,以及从原矩阵中依据排列顺序选出一行一行会非常麻烦。因此做如下近似:

随机选若干哈希函数(例如100)个,初始化一个空的矩阵M,行数等于哈希函数的数量,列数等于文档数(即等于布尔矩阵列数),做如下操作:

QQ截图20150212133146

 

得到的矩阵M是signature矩阵的一个近似。

例子:

QQ截图20150212133257

上例中还是指定了哈希函数,哈希函数也可以使用随机生成的哈希函数。

再次考虑这个例子,不重新排列行再用minhash,而是使用100个随机生成的哈希函数,获得近似的signature矩阵。

QQ截图20150212130427

即,在近似signature矩阵中,文档对1,3,以及文档对2,4的相似度分别为0.77和0.79

3 Locality-Sensitive Hashing

例如上面获得的近似signature矩阵,仍然有100行,如果生成的signature矩阵,仍然行数庞大,比较各个文档对O(n^2)仍然是较大的工程。局部敏感哈希的目的是避免这样庞大的运算。

如果将signature矩阵分为若干(b)段,然后对每一段的rtimes n的小矩阵,用一个哈希函数对各列进行哈希,那么在这一段小矩阵内近似的列会被哈希到一起。如此循环,对所有b段都进行同样的操作。

bands

之后将至少在一段中被哈希到一起的列对,作为候选相似列对,输出出来。

仍是上面的例子,通过20段的LSH获得的候补相似文档对为1,3和2,4。

假设我们有100000篇文档,通过shingles和minhashing获得了一个100times 100000的signature矩阵,对所有文档对进行比较会非常费时。

若将矩阵划分为5行一段,共20段。假设两篇文档C_1,C_2的相似度为80%,则两篇文章在1个5行的矩阵段中相同的概率为0.8^5=0.328,因而两篇文章的20段均不相同的概率为:(1-0.328)^20=0.00035

QQ截图20150212140007

上图表明,通过调整段数b和每段行数r的关系,可以尽可能地过滤掉不相似文档对,获得非常相似的文档对的候补。

Leave a Reply

Your email address will not be published. Required fields are marked *