NLP系列文章（四）——文本的相似性度量_最长公共子序列的文本相似度

文本相似一般是指的，某一文本 $doc1$与另一文本 $doc2$的相似程度。一般可以从两个方面去考察两个文本之间的相似程度：形似（字面相似）和神似（语义相似）。当然这两种相似性也不能够完全割裂开来，只不过可以认为字面相似的文本不一定语义相似，语义相似的文本不一定用词相似。

为了考察文本的相似性，同样需要对文本进行相应的表示，表示的方法在上一部分进行说明，本部分不再进行阐述。所以文本的相似性度量，可以认为是文本表示的下游任务。

字面相似

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

编辑距离

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

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

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

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

Jaccard（杰卡德）相似度

Jaccard相似度的计算用到了集合论中的交集并集的相关概念，可以认为Jaccard相似度可以计算两个集合的相似程度，当然在文本中也适用，用一个例子来说明：

		今天天气很好==>今天/天气/很好
		今天天气不好==>今天/天气/不好
1
2

所有词汇的集合:
word_set = {今天，天气，很好，不好}
两个句子中相同的词汇集合：
same_set = {今天，天气}
$$Jaccard\_similarity=\frac{len(same\_set)}{len(word\_set)}=\frac{2}{4}=0.5$$

把这个问题抽象出来可以给出Jaccard相似度的定义：

	给定两个集合A，B，Jaccard系数（相似度）定义为A与B交集大小与并集大小的比值，公式如下：
1

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|}$$
Jaccard值越大说明相似度越高。

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
2

具体的计算公式如下：
$$Euclidean\_Distance(vec1,vec2)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$

$$cosine\_similarity(vec1,vec2)=\frac{vec1\cdot vec2}{|vec1|\times |vec2|}=\frac{{\sum }_{i=1}^n(x_i\times y_i)}{{\sum }_{i=1}^n{x}_i\times {\sum }_{i=1}^n{y}_i}$$

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

词移距离（WMD）

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

计算两篇文档的词移距离，需要将两篇文档的所有词向量准备出来。
其中利用$doc1$和$doc2$代表两篇文档，$wor{d}_{1i}$和$wor{d}_{2j}$分别代表文档1和文档2中的词汇。

计算的方法如下：
$$WMD(doc1,doc2)=\sum _{i,j=0}^{n,m}{T}_{ij}\times euclidean\_distance(wor{d}_{1i},wor{d}_{2j})$$

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

DSSM

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

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

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

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

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