从100万篇文档中找出相似度较高的文档对
- WBOYOriginal
- 2016-06-07 15:56:401518browse
当我们想从100万篇文档中找出相项较高的文档对，就需要两两相互比较，一共是5千亿次，如果每次比较花费1微秒，那一共需要6天才能计算完，这肯定是不行的。 问题应用： 1、论文查重，读过大学的就都听过这个词，让无数人崩溃的查重，就是本题的一种应用，只是
当我们想从100万篇文档中找出相似项较高的文档对，就需要两两相互比较，一共是5千亿次，如果每次比较花费1微秒，那一共需要6天才能计算完，这肯定是不行的。
问题应用：
1、论文查重，读过大学的就都听过这个词，让无数人崩溃的查重，就是本题的一种应用，只是将一篇和上千万篇比较，但原理是一样的。
2、同源文档。我们再网站百度一些东西时，点开几个页面，可能发现很多页面及其相似，内容甚至重复，比如CSDN上的博客就有很多是从别的地方复制过来的，各个网站上的新闻等也有时候会相同或相似。如果一个网站汇总每天的新闻，那肯定是要能识别内容相似的两篇文章，选一个即可。
相似度定义：
Jaccard相似度：集合S和T的交集与集合并集大小的比率。加入S文档有三个字母A，B，C，T文档有5个字母B,C,D,E，F，那么S和T的相似度就是2除以6，三分之一。
问题处理
1、单个文档处理
步骤1——Shingling
文档一般都很长，总不能一个字符一个字符的比较，最有效的解决方法就是把整个文档拆分成短字符集合（长度为k），这样处理后如果集合中相同元素越多，那么相似度也就越高，同时还能忽略句子顺序（很多人抄论文时就经常改句子顺序）。
例：文档为abcdabd，选择k=2，那字符集合就是{ab，bc，cd，da，bd}。
当然k=2肯定是不行的，这样集合最大才是26^2，估计任何两个长文档都会认为相似。
具体k应该为多少呢？如果文档是邮件，那么k=5就够了，如果像论文这样大文档，一般k=9.
此外，文档中有很多次被称作停用词，像the，and，to等，一般是忽略这些词，因为对文章主题无作用。
步骤2——哈希
如果k=9，那么集合最大为26^9，每个元素需要9个字节来表示，而实际的集合大小是文档长度*9，现在我想把这多么元素哈希到2^32个桶中，这样每个元素就可以用4个字节来表示，这种做法的效果要比直接另k=4要好。原因是k=4时，实际集合中的元素最多为26^4，而且通常是20^4，因为像字母z，j的频率出现的次数是很低的。而9个字节的集合大小最大能达到26^9
感谢哈希算法一次。
步骤3——最小哈希
即使用4个字节的shingle，那么每篇文档难道要保存4倍的文档大小的信息？本步骤的目标就是将大集合替换成小很多的“签名”，通过计算签名集合的相似度来估计原始集合的相似的，当用50Kb的文档shingle到200Kb，而最后的签名集合只有1Kb时，最终差异值可能在几个百分点之内。
假设有M个文档集合，一共有N元素（所有集合中元素的并集，N很大），那么集合可以用一个N行M列来表示，当这个集合含这个元素时，对应位置为1，否则为0.
我们随机选择n（通常为几百）为签名大小，可以构建集合S的最小哈希签名向量[h1(r)，h2(r)...hn(r)]。
步骤如下：
初始矩阵SIG（大小n*M）都为正无穷，对每行r如下处理：
（1）随机选择n个哈希函数，计算出h1(r)...hn(r).
（2）如果原N*M矩阵对应位置为0，什么都不做，如果为1，那么将SIG中新的值变为hi(r)和SIG中原值的最小值。
也就是通过N步迭代，把原来的N*M大小矩阵，变成n*M大小的矩阵（对于一个文档来说，就是N变成了n）。
这种方法能估计准确有一定的理论依据，概括为：两个集合的两个最小哈希值相等的概率等于这连个几个的相似度。
再次感谢哈希算法。