算法：怎样计算文本的相似性【待完善】

By arthur503 -- 14 Oct 2013

文本的相似性的应用很多，比如：网页相似性判断、论文查重、盗版检查、垃圾邮件地址清单检查、新闻相似性度量等等。如果推而广之，甚至不止判断文本的相似性，还可以判断图片、视频（提取关键帧，相当于图片）等的相似性计算，来做盗版检查等（吴军《数学之美》CH16：信息指纹的作用）。

那么，怎样比较两个文本之间的相似性？方法有那些？

一、算法

在德问上有这个帖子，如何设计一个比较两篇文章相似性的算法？，讨论的结果质量很高。此处先摘录，以后慢慢实现再来补充。

1. 关键词匹配

基于统计模型，检查各个词的频度、平均频度、频度方差等，据此计算两篇文章的相似度。

不过，有人评价此方法：

对于@灵剑2012的答案，这种基于统计的方法更多的关注了文章中词频的信息，而对于词本身的信息似乎关注的不够。

2. 根据余弦定理计算文本向量的相似度

这里也是引自吴军的“数学之美系列 12 - 余弦定理和新闻的分类”。这篇文章主要是讲新闻的分类。先找一组数字或向量来描述一篇新闻。比如，词汇表有六万四千个词，则在一篇新闻中，根据这64,000个词的 TF/IDF 值得到一个64,000维的向量。向量可以看做多维空间中的有向线段，夹角越小，表示两个向量越相似。这样，我们可以通过判断两个向量之间的余弦，来计算两条新闻的相似性。

另外，对于使用的余弦定理，在我的博文统计学习方法BR-附录：距离、相似度和熵的度量方法总结中有对距离、相似度和熵的度量方法进行了总结。

对于余弦定理方法，有人评价如下：

梁会的答案看似简单明了，但实现起来效率可能是个问题，因为向量本身很长，有64000维。

使用SimHash计算文本相似性

如果不关注具体的相似片段的话，可以利用hash的办法来解决，如simhash。

我在博文映射的世界之五：特殊哈希算法之相似哈希（SimHash）里，介绍了SimHash的原理。通过相似哈希，可以计算出两个文本之间的相似程度。

神经网络中hebb rule的方法

有人提出来使用神经网络的方法，对神经网络不懂，请参看网页地址。

5. 编辑距离

也叫Levenshtein距离，是测量一个文本通过编辑操作（增加、删除、替换（有的也包括相邻字母交换操作）），得到另一个文本的最小编辑次数。两个文本的编辑距离越小越相似。具体见我的博文：编辑距离：我和你到底有多远？（一）

不过，编辑距离偏重于测量文本的相似性，如果使用同义词、前后文本交换位置则会导致编辑距离增大，但实际内容并无变化。因此，编辑距离可以用于文本的对比、查重，但对主题的相似性的用处貌似有限。

最后有人说：

这是目前研究比较多的领域，目前没有什么理论突破。所有的模型都是基于经典的VSM（（vector space model）的cosine measure计算文章相似度。

http://www2002.org/CDROM/refereed/643/node5.html

基本思想：文章看成一个向量，每个关键词作为一个特征，每个特征的权重基于term frequency和inverse document frequency计算出来。

这样文章的比较抽象成空间2个向量的比较，定义文章的相似度(similarity)为空间这2个向量的余弦值即可。值为1则2片文章完全相似，为0则完全不同。

google的学术论文搜索有无数，有兴趣的同学google，海量论文在此！！

http://scholar.google.com.hk/scholar?q=text+similarity++VSM&btnG=&hl=zh-CN&as_sdt=0&as_vis=1

如果是中文的VSM还需要个特殊的分词操作，把句子分成一个个的汉字单词。这方面有开源的package可以使用，英文因为本来就是单词结构无需这样的操作。

二、总结

我个人的感觉，“关键词匹配”等算法，使用统计方法对词频等信息进行匹配，可以一定程度上反映文本的相似性。由此思想，还可以引出通过计算文本中的单词集合（set）之间的杰卡德相似系数与距离（详见统计学习方法BR-附录：距离、相似度和熵的度量方法总结）等方法。但是，只对词频进行统计对文本信息的缺失太多，无法表征文本中想要表达的主题信息，对于新闻分类这样的情景作用有限。

余弦度量的方法比较好，利用了所有可能的词的词频信息，足以表征一般新闻的主题。缺点是，对于每个新闻都是64,000维的向量（这样才能保证相同主题的维度是一致的），计算量大，效率可能受影响。

使用相似哈希（SimHash）的方法，可以对文本之间的相似性进行判断，主要计算的是使用的单词是否相似。使用SimHash对新闻中IDF较大的TOP K个单词计算（无需计算所有的64,000维文本的哈希值），可以得到一定的主题信息，而且计算量不大。

神经网络方法还不懂，不评价。

编辑距离更倾向于文本的相似性，计算得到的是文本之间的距离而非主题之间的相似性，因此，比较适用于文本查重一类，不适用于新闻分类这样的场景。

最后总结一下，“关键词匹配”和编辑距离更偏向于文本相似性判断，在一定程度上也可以进行主题分类，但感觉效果不佳。余弦度量的主题分类效果好，缺点是计算量大。相似哈希在文本和主题之间折中，计算了信息量大（IDF大）的文本的相似性，反映了一定的主题信息（保存在IDF大的单词中），计算量大大减小。神经网络方法不懂，不评价。

【待完善】

文本的相似性判断，应该包括：文本的相似性判断和主题的相似性判断。例如：新闻查重应该属于典型的主题相似性判断，而论文查重应该更倾向于文本的相似性判断，需要知道文章的具体相似部分、相似片段、相似百分比。对于文本的相似性判断，我们应该更关注文本中的词；而对于主题的相似性判断，应该更关注使用词来表示的文本主题。

这一部分还需要再考虑完善。