ps: 文章翻译与 Mining of Massive Datasets
场景：在一堆非常多的文档中，找到相似的文档，或者对文档间的相似性进行评估。
当应用于此类目的的时候，我们最常用的用来表示一篇文档的方法是：shingling。
1. k-shingles
可以把一篇文档看成一个字符串。那么一篇文档的k-shingle就是在这篇文档中出过现的任何长度为k的字符串。k-shingles就是改篇文档所有k-shingle的集合。 （那么k的大小决定于什么因素呢？ 与文档的长度和所有的字符个数有关。k的取值一般要满足一个规则：k的取值应该能够满足，任何一个给定的shingle出现在任何给定的文档中的概率都非常低。） （一般对于邮件类的文档，k取值为5是最为合适的。假设在邮件中一般只会出现字母字符和空格字符。那么将会有27^5=14,348,907个可能的shingles。而一般的Email的字符长度会远小于14million。而在实际的测试中k=5也确实是表现的非常好。而对于长文档，如研究论文等k取9是一个安全的取值。）
2. Hashing Shingles
我们可以选择一个hash函数来将k-shingle映射成为数值，这样对文档的表示形式就是一群整数的集合。
3. 对于单词建立shingles
除了将文档看成字符串，我们也可以以单词为个体建立shingle。对于新闻类的文档，建立单词的shingle是非常有效的。（对于新闻类的文档，会出现非常多的停用词，停用词一般不能告诉我们文档的重要信息，所以一般会先去掉停用词）
（然而，对于在新闻类文档中找到两个类似的文档问题，研究发现，对于这样的shingle：‘一个停用词后边紧跟着两个词，不管后边的两个词是不是停用词’ 能够形成非常有用的shingles集合。它的好处在于，可以让新闻类文档形成的shingles集合中，与webPage本身有关的多于与周围环境有关的
<原因未知，书中也没有更多的说明>
。这样非常合适这样的目的：在一大堆网页中，找出网页中文章是相关的，而不管文章周围的内容。）
<原因未知，书中也没有更多的说明>
。这样非常合适这样的目的：在一大堆网页中，找出网页中文章是相关的，而不管文章周围的内容。）
4. 保持相似度的集合摘要（MinHashing）
可以发现，文档的shingles集合是非常大的，尽管我们用hash将其映射为4byte或者更大的整数。假设我们有上百万的文档，那么内存中就会放不下这些shingles的集合。
我们的目标就是把大数据量的shingles集合变换为非常小的代表（称之为签名）。而且这样的签名应该有这样的性质： 能够很容易的对两个签名集合进行比较，并且能够较简单的计算两个签名集合的jaccard距离；而且，签名集合计算出来的的相似度（jaccard距离）应该和实际的相差不大，签名集合越大，越能接近准确值。
MinHashing就是具有这些性质的获取签名的一种有效方法。 签名一般大概会取几百个左右，每一个值都是原代表集合的一个不同的MinHash值。
那么如何计算一个集合的minhash值呢？ 首先，对集合的表示方法进行改变，假设现在三篇文档，我们用下面的方式来表示，称之为characteristic matrix; 左边的一列是所有出现过的元素。这样每一篇文档被表示为0,1集合。
| element | s1 | s2 | s3 |
| a | 1 | 0 | 0 |
| b | 0 | 0 | 1 |
| c | 0 | 1 | 0 |
| d | 1 | 0 | 1 |
| e | 0 | 0 | 1 |
若要求一个文档的minhash值，首先对每一列的元素进行同样的重新排列，相当于把最左侧的element的顺序进行重排；然后，每一个文档的一个minhash值就是该列元素中第一’1‘所在位置的元素；（假设上表中就是已经重排后的矩阵，那么s1的该minhash值就是a， s2是c； s3是b；）
同上，我们取几百个不同的minhash函数对矩阵进行不同的重排，就可以得到每个文档的签名（元素数目和所取得函数数目相同）
分析上边的计算过程，我们可以发现，在实际计算中，我们可以不用真的对所有元素进行重排（对于大数据量文档来说这是一个非常不现实的过程），因为我们只要找到第一个不元素1所在的位置就行了，所需要的只是按照minhash函数的规定一次遍历元素集直到知道元素1为止。
5. 如何计算MinHash 签名
书上给出的是这样的方法： 由于对characteristic matrix的行（一般是百万甚至十亿级别的数量）进行重排是非常耗时的。所以我们通过hash函数来模拟重排过程，利用hash函数将行号映射到与行数相同的buckets中；hash的过程可能会有冲突，不过当k非常大而且冲突并不是非常多的时候区别并不是很大。
首先随机选取n个hansh函数；h1,h2…..hn;
| row | s1 | s2 | s3 | s4 | h1= x+1 mod 5 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 2 |
| 2 | 0 | 1 | 0 | 1 | 3 |
| 3 | 1 | 0 | 1 | 1 | 4 |
| 4 | 0 | 0 | 1 | 0 | 0 |
我们用SIG(i,c)用来存储第i个hash函数和第c列数据（文档c的变换表示）的签名值，并且初始化为无穷大。
其次没我们对每一行r进行如下处理：
1. 计算 h1(r),h2(r)….hn(r);
2. 对每一列c进行： 如果 c列r行的数值是0，什么也不做； 否则， 对每一个i=1,2,….n 设置SIG(i,c) = min(SIG(i,c), hi(r))；也就是设置为当前的SIG(i,c)值和hi(r)的最小值。 (过程相当于在计算的过程中，不断用重排后位置最靠前且数值为1的行号放在相应的SIG中，从而达到前文所述的求签名值得目的)
通过上面的方法就可以求得一篇文档的minhan签名。但是尽管我们通过minhash将文档压缩为小的签名值，并且能保证相互间相似度的计算；我们仍不能很有效的找到相似度最高的文档对，因为要比较的文档数目可能非常大。这时候，如果我们的目标找到相似度在一定阈值以上的文档对，或者最相似的文档对；而不是计算所有的文档对的相似度，那么我们就可以采用图像处理经常使用的LSH技术来简化计算。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/209407.html原文链接：https://javaforall.net
