NLTK 相似性度量

文本相似
字面相似
- 编辑距离
- 2、最长公共子序列和最长公共子串
SimHash
语义相似
欧式距离和余弦相似度
词移距离（WMD）
DSSM
拼写纠错
相关资料

文本相似

文本相似：一般是指的，某一文本 doc1与另一文本 doc2的相似程度。
一般可以从两个方面去考察两个文本之间的相似程度：形似（字面相似）和神似（语义相似）。当然这两种相似性也不能够完全割裂开来，只不过可以认为字面相似的文本不一定语义相似，语义相似的文本不一定用词相似。
为了考察文本的相似性，同样需要对文本进行相应的表示，表示的方法在上一部分进行说明，本部分不再进行阐述。所以文本的相似性度量，可以认为是文本表示的下游任务。

字面相似

字面相似是从文本的字词本身是否相似而考量，希望达到的效果是：两个文本“长得”越像，其本身含义也相近的效果。其中包含有编辑距离，最长公共子序列、最长公共子串，Jaccard（杰卡德）相似度和SimHash算法等。

编辑距离

编辑距离是一个经典的字符串动态规划算法，用于计算两个字符串（A和B），由A变动到B的最小的操作次数，其中每一次的插入、替换和删除都算作一次操作。可以直观的理解编辑距离就是字符串A变为字符串B最少的编辑次数。
当然将字符串A与B视为文本doc1和doc2，就能够刻画两个文本之间的相似程度。

nltk中的metrics模块中提供了各种评估或相似性度量的方法：
1、编辑距离 edit-distance

from nltk.metrics import edit_distance 

edit_distance('rain', 'shine') # 3
edit_distance('test', 'text')   # 1

2、最长公共子序列和最长公共子串

这两个算法类似，但是有一个区别之处在于：子串与子序列的定义不同。
用例子说明如下：
abcdefg是原本的字符串，abc是子串也是子序列，aeg是子序列但不是子串。
从例子中我们可知，子串必是子序列，子序列不一定是子串。唯一的区分点就在于：是否连续。

如何求解最长公共子串和最长公共子序列同样也是较为经典的字符串动态规划算法。通过求解的结果，就可以依据最长公共子串（子序列）的长度越长，就表明两个文本更相似。

3、Jaccard 杰卡德相似系数

计算公式：

$ frac{两个集合的并集长度-两个集合的交集长度}{两个集合的并集长度} $

# Jaccard系数执行相似性度量
from nltk.metrics import jaccard_distance
a = set([1, 2, 3, 4])
b = set([1, 2, 5, 6])

# 参数必须是两个集合（6-2）/6
print(jaccard_distance(b, a)) 
# 0.6666666666666666

a = set([1, 3, 5, 7])
b = set([1, 2, 4, 8])

# (7-1）/7
print(jaccard_distance(b, a))  
# 0.8571428571428571

SimHash

SimHash采用局部哈希的思想来实现，最初由谷歌提出来用于网页去重。之后发展为利用这个算法去，评价文本是否存在抄袭，以及文本的相似性度量。

SimHash算法可以划分为五个步骤：分词、对词Hash、对词加权、合并和降维。
整个过程如下如所示：

分词：顾名思义就是将文本分为词的序列。
Hash：是对词做hash，将每个词Hash利用32位甚至是64的二进制数值来代替，长度可以自由选择。
加权：是针对每个词汇有一个权重，对hash码中为1的数值则置为对应的权重，为0的数值则置为权重的负值。
合并：就是将文本中的所有的词汇进行对位相加。
降维：将文本合并后的结果，大于0的置为1，小于0的置为0。

最终会得到两个表示文本的向量，计算这两个向量的海明距离就可以得到两个文本的相似性度量值。

海明距离越大表示越不相似，海明距离越小表示越相似。

语义相似

语义相似度与字面相似度不同，在设计的最初就是考虑如何利用具有语义的文本表示方法进行语义相似度的计算。所以在文本表示的时候，选择含有词向量的表示方法，可以包括文本的语义信息。

欧式距离和余弦相似度

欧氏距离可以理解为在欧式空间中两个点之间连线的距离，而余弦相似度代表两个向量趋势的一致性程度。
两个向量作为例子进行具体的阐述：

	vec1=[x1,x2,x3...xn]
	vec2=[y1,y2,y3...yn]

具体的计算公式如下：

利用两个文本向量计算上述的两个值，就可以利用结果反映相似性程度。
欧氏距离越小则说明两个文本的差异越小，余弦相似度越接近1则说明两个文本的差异越小；反之则相反。

词移距离（WMD）

词移距离（Word Mover‘s Distance，WMD）可以从名称上了解到就是词汇移动的距离，与各种距离一样，当距离越大时，表示两个文本的相似度越小。

计算两篇文档的词移距离，需要将两篇文档的所有词向量准备出来。
其中利用d o c 1 doc1doc1和d o c 2 doc2doc2代表两篇文档，w o r d 1 i word_{1i}word1i和w o r d 2 j word_{2j}word2j分别代表文档1和文档2中的词汇。

计算的方法如下：

其中 (T_{ij})代表 $ word_{1i} $ 和 $ word_{2j}$ 计算的距离权重，其中 $ euclidean_distance(word_{1i}, word_{2j})$ 代表计算两个词汇的欧式距离，采用欧氏距离是由于其本身就可以代表空间中的移动距离。

DSSM

DSSM（Deep Structured Semmantic Models）是文本相似度计算的一种监督学习方法，利用已有的标注数据可以训练语义相似度模型。这个模型可以预测两个句子的语义相似度，同时也可生成副产物句子的低维语义向量的表达。

DSSM的模型结构示意图如下，从下往上分别是，输入层、表示层，匹配层和输出层。整个过程是由两个文本输入到模型中，经过一系列的处理最终产生这两个文本的相似性的分数。

在这里插入图片描述

输入层可以将文本的字词做Hash处理（可以理解为制作文本的词向量），然后相加生成文本的向量。经过表示层的特征提取和转换表达形成文本最终的语义向量。匹配层通过求解两个文本向量的余弦相似度，并利用余弦相似度得分构造损失函数。通过优化模型参数在输出层的到最后的匹配结果。

由于DSSM是有监督的方法，所以在有标注语料和领域相关化的任务中表现比起无监督的方法较好。但是由于DNN作为DSSM的基础网络并且对于文本的表示采用的是词袋模型的思想，所以对于文本的表达损失了词序信息。CNN-DSSM和LSTM-DSSM的出现一定程度上改进与缓解了这个问题。

文本相似在NLP领域作为一个基础性任务，解决的方法有很多，除了上述的字面相似度和语义相似度，以及各类的无监督方法和监督方法。现在有一些更大更强的模型比如：ELMo、BERT和GPT等，它们可以更好的表达文本本身的含义，对于相似性的度量直接或间接的起到了正向作用。

拼写纠错

部分情况下会用到拼写检查器 spellchecker。
可以用纯字典查找的方式来创建一个非常基本的拼写检查器；也有业界专门开发的 增强型字符串算法，用于模糊的字符串匹配，其中最常用的是 edit-distance 算法。
nltk 为我们提供了多种内置 edit-distance 算法的度量模块