文本相似度计算

---

1.为什么要计算文本相似度

给定两个串$S_1,S_2$,计算出它们的相似度，取值范围为$[0,1]$。这种计算在很多领域都很有价值：

• 论文查重检测
• 多个新闻合并

如果是人来阅读文章判断是否相似，通常会按照三个标准进行：

• 完全抄袭 使用了相同词语和句子，有大段的相同；
• 部分抄袭 结构**如果句子意思一致，但词语顺序和结构发生了变化，
• 观点抄袭 可能两篇文章没有任何相同的词，但它们表达的意思是一致的，这就是一种观点的复制。

对计算机来说，第一种是比较容易判断的。使用文本对齐算法（一种动态规划），能够将绝大多数段落一一对应。
第二种则相对困难一些，但也有章可循，我们将在下一节进行分析。第三种最为复杂，看如何使用语义来求解。

2.文章向量相似度

对于第二个问题，从最直观的想法，就是将词汇看成一个个的语义单位，看相同的词有多少个。

1. 第一步：我们将两篇文章进行分词，去掉没有用的停用词，如"的","是"等。
2. 对每个词计算在其文章中出现的词频TF，其中：
   $$TF= \frac{词w在文章d_i中出现的次数}{d_i中所有词的总数量}$$
   之所以有分母，是为了避免长文章带来的干扰。

3. “原子能的应用”也许原子能和应用两个词，在同一篇文章中出现的次数一样，因此TF一致，但明显原子能更能体现出文章的意思。因此我们引入了IDF(逆文本频率指数):
   

   $$IDF= {log(\frac{所有文章的数量}{有多少篇文章包含词w})}$$
   因此，一个词在该文章的重要性可以描述为：$TF*IDF$。

4. 那么，我们总可以计算出每个词的TFIDF，值越高，那么它对文章的贡献越大。经过排序后，可以挑选出TFIDF值最大的前n个词。

5. 将两篇文章表示为两个向量，向量的每一个分量对应于一个词的TFIDF，且两个向量之间一一对应。
6. 计算向量的余弦相似度。即可得到文章的相似关系。

这是非常常规的做法，但实际应用中，必须进行优化。下面是一些优化点：
- 倒排索引(搜索引擎的一般步骤)，每个词的TFIDF都能计算并存储起来。这样就不需重复计算了
- 向量应当提前归一化，从而避免计算余弦相似度时，分母平方和的计算复杂度。

不仅如此，如果求解与一篇文章d最相似的前20篇文章，如果文章的数量非常多，那么一次查询，就要让文章d和所有其他文章计算相似度，这个复杂度非常可观。而缓存结果，则需要存储巨大的矩阵，这不现实，怎么优化？

• 文章求相似度时，前面的分量和大于指定阈值时，后面的向量就不用算了。
• 使用并行算法？
• 进一步根据领域压缩向量长度？
• 还需要进一步思考

但是，最困难的问题是第三种情况。如果两篇文章，没有一个词相同，但表达的意思很相似，这种问题如何处理？

3.基于语义的相似度计算

既然词是基本单位，我们简化一下问题：假设有一种技术，能直接告诉我们两个词之间的相似度，范围也是[0,1]，那怎么处理？

思路1: 对词进行聚类并替换

既然词和词之间的关系可以求得。我们想想人是如何处理本问题的。在人的概念中，词和词是能实现分组的。相同组的词，其概念接近。

1. 对所有词进行聚类，聚类的类数可设置为某经验值（2000个基本词元）
2. 将文章进行分词，去掉停用词后，将每个词替换为该词的聚类ID
3. 将聚类ID看成独立的词，再次计算TFIDF,并通过余弦相似度求解。

由于对词聚类只需一次离线计算，因此能够接受较大的计算时间。考虑到语料库的词一定非常多，不需要对所有的词都进行聚类，筛选应当按照如下方法：
应当挑选出平均TFIDF较高的词（该词在每篇文章的TFIDF的平均值），这样既可省略大量的常用词和语气助词和极少数偏僻词，从而极大地减少了计算量。
聚类时，可以考虑层次聚类，形成多个层次的词关系树，那么在替换时，可以将词按照需求，替换为不同层级的树的节点ID，从而实现粗细粒度的调整。

思路2： 使用矩阵来表述关系

对两篇文章$d_1$和$d_2$ 为了减少计算量，我们分别从两篇文章中提取TFIDF值高的词，词数分别为m和n，两两计算关系，会获得m*n的一个矩阵，因为词关系是对称的，所以这一定是个对称矩阵，存储上三角即可。

有了这个矩阵，如何计算相似度？
由于已经有两个TFIDF向量，每个词在矩阵中，对相似度计算的贡献是不同的。较高TFIDF的词，在矩阵中体现的作用应当更高：
因此，对矩阵中的每个元素：

$$m_{i,j}= (1+ar_{i})(1+ar_{j})*m_{i,j}$$
其中，$ar_{i}$表示一个句子的tfidf数组的第i个元素。
对该矩阵重新计算后，其结果是整合TFIDF权重的相似度矩阵。

1.将所有的矩阵元素求和
但是，这种方法有很多缺点，它不能描述相似的分布：一个在某些区域内特别高的矩阵，代表了文章中的少数词关系特别接近。而几乎均匀分布的矩阵，则证明词和词都有弱关系。可能它们的矩阵元素和一样，但这明显情况不同。
除此之外，

2.对矩阵进行降维操作
考虑a,b两个词的相似度很高，那么一般认为，另外一个词c如果和a的相似度较高，那么和b相似度也很高。
这导致了矩阵中存在一定冗余，如果对矩阵进行PCA降维操作，则能一定程度上去掉这种冗余。

3：使用SVD矩阵分解

思路3：二部图算法**

考虑两篇文章A和B，那么词和文章的关系构成了二部图，图中只展示了三个词a,b,c。（此处忽略证明其为二部图的步骤）。

那么可以使用simrank算法，simrank的基本思想是，如果两个实体相似，那么跟它们相关的实体应该也相似。比如在上图中如果a和c相似，那么A和B应该也相似，因为A和a相关，而B和c相关。

$$s(a,b)=\frac{C}{|I(a)||I(b)|}\sum_{i=1}^{|I(a)|}\sum_{j=1}^{|I(b)|}s(I_i(a),I_j(b))$$

其中：s(a,b)是节点a和b的相似度，当a=b时，s(a,b)=1。
简单解释，A和B的相似度，等于out-neighbor(a,b,c)相似度的平均值，再乘以阻尼系数C。
这个有点类似于思路1的矩阵元素求和。

(等待补充)

思路4：使用LDA算法

在研究生期间，我们就讨论过这个问题，其中一位同学使用了LDA算法，由于这块我没有负责，当时就没有特别在意。经过查找，这算是一种很有效的解法。
(等待补充)