NLP从零开始------9文本进阶处理之文本相似度计算

1.文本相似度计算简介

在自然语言处理中，经常会涉及度量两个文本相似度的问题。在诸如对话系统和信息减速等中，度量句子或短语之间的相似度尤为重要。在新闻学传媒中应用文本相似度可以帮助读者快速检索到想要了解的报道。

文本相似度的定义式如下所示：

$Sim(A,B)=\frac{\lg P(common(A,B))}{\lg P(description(A,B))}$

其中，common(A,B)和A和B的共性信息，description(A,B)是描述A和B的全部信息，上式表达出相似度与文本共性成正相关。由于没有限制应用领域，由此此定义被广泛采用。

相似度一般可用[0,1]中的实数表示，该实数可通过语义距离计算获得。相似度与语义距离呈负相关。语义距离较小，相似度越高；语义距离越大则相似度越低。通常用下式表示相似度与语义距离的关系。

$Sim(S_{A},S_{B})=\frac{a}{Dis(S_{A},S_{B})+a}$

其中， $Dis(S_{A},S_{B})$ 表示文本 $S_{A}$ 、 $S_{B}$ 之间的非负语义距离，a为调节因子，保证当语义距离为0时上式具有意义。

2.文本的表示

文本相似度的计算原理中还有一个重要概念是文本的表示，代表对文本的基本处理方法，目的是将半结构化或非半结构化的文本转换为计算机可读形式。不同的文本相似度计算方法的本质是文本表示方法的不同，文本的表示方式包括3种：一是基于关键词匹配的传统方法，如n-gram相似度等；二是基于向量空间的方法，这种方法将文本映射到向量空间，再利用余弦相似度等方法计算相似度；三是基于深度学习的方法，如基于用户点击数据的深度语义模型（DSSM）、基于卷积神经网路(CNN)的ConvNet，以及Siamese LSTM，Transformers模型（BERT、GPT等)等方法。随着深度学习的发展，计算文本相似度的主流方法已经逐渐不在是基于关键词匹配的传统方法，而是基于深度学习的方法。

2.1 基于关键词匹配的文本表示的方达

2.1.1 n-gram相似度

基于n-gram模型定义文本（字符串）相似度是一种模糊匹配方式，即通过两个长得很像的文本间的“差异”来衡量相似度。n-gram相似度的计算按长度N切分原句得到词段，也就是原句中所有长度为N的子字符串。对于两个字符串S和T，则可以根据共有子字符串的数量定义两个字符串的相似度，如下式。

$Similarity=\left | G_{N}(S)) \right |+\left | G_{N}(T)) \right |-2\left | G_{N}(S))\cap G_{N}(T)) \right |$

其中， $G_{N}(S)$ 、 $G_{N}(T)$ 分别表示字符串S和T中n-gram的集合，N一般取2或3。字符串距离越近，他们越相似。当两个字符串完全相等时，距离为0。

2.1.2 杰卡德相似度

杰卡德相似度的计算相对简单，原理也容易理解，就是计算两个文本之间词集合的交集字数和并集字数的比值，如下式所示。该值越大，表示两个文本越相似。在涉及大规模并行运算的时候，该方法的效率上有一定优势。

$J(A,B)=\frac{\left [ A\cap B \right ]}{\left [ A\cup B \right ]}$

其中0<=J（A,B）<=1

关于杰卡德相似度更详细的内容在后面进行讲解。

2.2 基于向量空间的文本表示方法

基于向量空间的文本表示方法目前有3种方法，第1种是词网(WordNet)，它可提供一种词的分类资源，但是无法体现词与词之间的细微区别，同时它也很难计算词与词之间的相似度；第2种是离散表示，如独热表示，它的向量长度和字典的长度相同，因此向量长度可能十分长，同时由于向量之间正交，因此无法计算词之间的相似度；第3种是分布式表示，其基本思想是将每个词映射为一个固定长度的短向量(相对独热表示而言)，这些词构成一个词向量空间，每一个向量视为空间中的一个点，在这个空间引入“距离”，即可根据词之间的距离来判断它们之间的相似性，代表方法如 Word2Vec、LDA等。

2.3 基于深度学习的文本表示方法

深度学习在图像和语音识别领域中取得了不错的进展，近些年深度学习也开始应用于自然语言处理。语义相似性匹配已经逐渐从人工设计特征转向分布式表示和神经网络结构相结合的方式。常见的基于深度学习的文本表示方法有DSSM、ConvNet、Skip-Thoughts、Tree-LSTM 和 Siamese Network。　

(1)DSSM 在检索场景下，利用用户的点击数据来训练语义层次的匹配。DSSM 利用点击率来代替相关性，点击数据中包含大量的用户问句和对应的点击文档，这些点击数据将用户的问题和匹配的文档连接起来。DSSM的优点在于直接利用用户的点击数据，得到的结果可以直接排序，但是缺点在于没有利用上下文信息。DSSM的扩展还包括CDSSM、DSSM-LSTM 等。其中CDSSM能在一定程度上弥补上下文缺失的缺陷，在结构上将DNN 替换成CNN; DSSM-LSTM使用长短期记忆(Long Short-Term Memory, LSTM)记录上下文。　　

(2)ConvNet通过精心设计CNN，结合不同规格的CNN的差异性度量句子的相似度。在实际应用中，可采用“Siamese”(孪生) CNN结构，分别对两个句子建模，然后利用一个句子相似度测量层计算句子相似度，最后通过一个全连接层输出 softmax相似度得分。一个句子首先被转化为嵌入矩阵(Embedding Matrix)，然后输入卷积-池化层得到处理后的句子向量。为更好地计算句子之间的相似度，该模型分别对不同的输出结果计算其相似性，最终将相似度向量输入全连接层得到相似性分数，将其与标签值相比较。总体来看，这个模型的复杂度还是很高的，而且对卷积核在垂直方向的计算也没有特别直观的解释。　　

(3) Skip-Thoughts 的核心思想是将 Word2Vec 中的 Skip-Gram模型从词的层面扩展到句子的层面，利用 seq2seq 模型预测输入语句的上下句。在之前的各类监督方法中，模型通过确定的标签作为优化目标更新参数虽然取得了不错的效果，但是只能适用于不同的任务。模型在一个连续的文本语料(小说)上进行训练，通过 Encoder 端将词转化为句子向量量，然后在 Decoder 端结合 Encoder 端的句子向量生成上下文语句。对于这样一个模型，最大的问题在于如何把有限的词扩展到任意的词或句子。针对这个问题可以采用的方法是学习一种映射，将一个模型中的词表示映射到另外一个模型中。具体的操作是把CBOW中预训练得到的词向量映射到 Encoder 端的词空间，最终将词汇量扩展。训练好的Skip-Thoughts模型会将Encoder端作为特征提取器,对所有的句子提取Skip-Thoughts向量, 得到的这些向量表示可以用在不同的任务(如语义相似度计算)中。　　 (4) Tree-LSTM的核心思想是将对语序敏感的标准LSTM 序列，推广为树状结构的网络拓扑图。标准LSTM 仅考虑句子的序列信息，但是在自然语言中句法结构能够自然地将词结合成短语或句子,因此可利用句法结构信息生成LSTM 扩展结构: Child-Sum Tree-LSTM和N-ary Tree-LSTM。　　 (5) Siamese Network用来度量数据之间的相似性。将两组数据(文本、图像等)同时输入一个神经网络中，并经由这个神经网络转化为N×1 维的向量，此后会通过一个数值(如余弦相似度)函数计算这两个向量的距离，通过得到的距离来度量原始输入数据的相似性。在标准的Siamese Network中，两侧的神经网络需要使用相同的网络结构和参数；同时在进行梯度更新前，需要先对两侧的梯度平均。

关于Siamese Network模型有以下两点值得注意。　　

一是在 Siamese Network 中采用孪生 LSTM, 是因为 LSTM 能够解决循环神经网络(Recurrent Neural Network, RNN) 的长期依赖问题, 通过使用记忆单元(Memory Cell),LSTM 能够储存更长输入序列的信息。当然对特别长的句子而言，标准的LSTM 能力也是有限的。对于长度超过30个字符的长句子，通过模型得到的最终隐藏层状态，占据比重较大的还是后面的词，前面的词基本“消失”，因此需要用到注意力机制。　　

二是在度量相似性的时候，采用曼哈顿距离而不是欧氏距离。根据目前的主流观点，一方面用Word2Vec训练出来的词，存在大量欧氏距离相等的情况，如果用L2范数去衡量，存在语义丢失的情况，而余弦相似度适合向量维数特别大的情况，因此采用曼哈顿距离最合适；另一方面，采用L2范数会存在梯度消失的问题，在训练的早期 L2范数会错误地认为两个语义不相关的句子相似(因为采用欧氏距离时的梯度消失问题)。

3.常用文本相似度算法

在文本相似度的计算中，根据需求选择合适的算法尤为重要。比如在论文查重的时候依据杰卡德相似度寻找相似的文章，再使用欧氏距离精确查找重复段落。

3.1 欧式算法

1.欧氏距离欧氏距离公式是数学中的一个非常经典的距离公式，如下式所示。

$d=\sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2} }$

上式中 d 表示欧氏距离， $x_{i}$ 和 $y_{i}$ 分别表示需要计算相似度的2个文本向量中应位置的元素。

例如，计算“产品经理”和“产业经理是什么”之间的欧氏距离，具体计算过程如下。
文本向量A = ( 产 ,品，经，理），即 $x _ { 1 }$ = 产， $x _ { 2}$ = 品， $x _ { 3 }$ = 经, $x _ { 4 }$ = 理， $x _ { 5}$ 、 $x _ { 6 }$ 、 $x _ { 7 }$ 均为空；

文本向量B=（产，业，经，理，是，什，么），即 $x _ { 1 }$ = 产， $x _ { 2}$ = 业， $x _ { 3 }$ = 经, $x _ { 4 }$ = 理， $x _ { 5}$ =是、 $x _ { 6 }$ =什、 $x _ { 7 }$ =么；
规定若 $x _ { i }$ = $y _ { i }$ ，则 $x _ { 1 } - y _ { 1 } = 0$ ；若 $x _ { i } \neq y _ { i } and x _ { 1 } - y _ { 1 } = 10$
可以得到文本向量A和B的欧氏距离d，如下式所示。

$d = \sqrt { 0 ^ { 2 } + 1 ^ { 2 } + 0 ^ { 2 } + 0 ^ { 2 } + 1 ^ { 2 } + 1 ^ { 2 } + 1 ^ { 2 } } = 2$
该相似度算法主要适用场景为编码检测等。两串编码必须完全一致，才能通过检测，如果编码中有一个移位或一个错字，可能会造成较大的差异。例如，有两个二维码，一个二维码的内容是“这是一篇文本相似度的文章”，另一个二维码的内容是“这是一篇文本相似度文章”，从人的理解角度来看，这两句话相似度非常高，但是实际上这两句话生成的二维码却千差万别。文本相似度，意味着要能区分相似或差异的程度，而欧氏距离只能区分出文本中的元素是否完全一样，并且欧氏距离对文本的位置和顺序非常敏感。如“我的名字是孙行者”和“孙行者是我的名字”，从人的角度看这两段文本的相似度非常高，但如果用欧氏距离计算两段文本的相似度，那么会发现两个文本向量每个位置的值都不同，即完全不匹配。

3.2 曼哈顿距离

曼哈顿距离的计算公式与欧氏距离的计算公式非常相似。相较于欧氏距离，曼哈顿距离的计算公式将求平方换成了求绝对值，并去除了根号，如下式所示。
$d = \sum _ { i = 1 } ^ { n } \vert x _ { i } - y _ { i } \vert$
曼哈顿距离的适用场景与欧氏距离的适用场景类似。

3.3 编辑距离

        编辑距离又称莱文斯坦（Levenshtein）距离，指的是将文本A编辑成文本B需要的最少变动次数（每次只能增加、删除或修改一个字）。
        例如，计算“椰子”和“椰子树”之间的编辑距离。
        因为将“椰子”转化成“椰子树”，至少需要且只需要1次改动，如“椰子”→增加“树”→“椰子树”；反过来，将“椰子树”转化成“椰子”，也至少需要1次改动，如“椰子树”→删除“树”→“椰子”，所以“椰子”和“椰子树”的编辑距离是1。
        因此可以看出编辑距离是对称的，即将A转化成B的最小变动次数和将B转化成A的最小变动次数是相等的。
        同时，编辑距离与文本的顺序有关。例如，“椰子”和“子椰”，虽然都是由“椰”“子”组成的，但因为组词顺序变了，所以其编辑距离是2，而不是0，具体计算过程如下。
        “椰子”→删除“子”→“椰”→增加“子”→“子椰”

“椰子”→删除“椰”→“子”→增加“椰”→“子椰”

“椰子”→“子”变“椰”→“椰椰”→“椰”变“子”→“子椰”

“椰子”→“椰”变“子”→“子子”→“子”变“椰”→“子椰”
如果文本的编辑距离很小，则文本相似度肯定很高。虽然据此会漏判一些高相似度的文本，但可以确保通过编辑距离筛选的文本相似度一定很高。但在某些业务场景中，漏判会引起严重后果，例如“批发零售”和“零售批发”，从人的角度理解这两段文本应该高度相似，可编辑距离却是4，相当于完全不匹配，这显然不符合预期。

3.4 杰卡德相似度

        杰卡德相似度指的是文本A与文本B中交集的字数除以并集的字数，如下式所示。
                                                         $J ( A , B ) = \frac { \vert A \cap B \vert } { \vert A \cup B \vert }$
        如果要计算文本的杰卡德距离，将式（4-8）稍做改变即可，如上式所示。
                                                      $d _ { j } ( A , B ) = 1 - \frac { \vert A \cap B \vert } { \vert A \cup B \vert }$
        计算“目不转睛”和“目不暇接”的杰卡德相似度示例如下。
        这两段文本的交集为｛目，不｝，并集为｛目，不，转，睛，暇，接｝，所以杰卡德相似度 $J ( A , B ) = \frac { 2 } { 6 } = \frac { 1 } { 3 }$ 。
        杰卡德相似度与文本的位置、顺序均无关。例如，“王者荣耀”和“荣耀王者”的相似度是100％，无论“王者荣耀”这4个字怎么排列，最终相似度都是100％。
        在某些情况下，会先将文本分词，再以词为单位计算相似度。例如将“王者荣耀”切分成“王者／荣耀”，将“荣耀王者”切分成“荣耀／王者”，那么交集就是｛王者，荣耀｝，并集也是｛王者，荣耀｝，相似度仍是100％。
        该算法主要适用于对字／词的顺序不敏感的文本，如“零售批发”；和“批发零售”可以很好地兼容，以及长文本（如一篇论文，甚至一本书）。如果两篇论文相似度较高，说明交集比较大，很多用词是重复的，存在抄袭嫌疑。
        该算法不太适用于两种情况。一是重复字符较多的文本，例如，“这是是是是是是一个文本”和“这是一个文文文文文文本”，这两个文本有很多字不一样，但计算得到的杰卡德相似度却是100％（交集＝并集）；二是对文字顺序很敏感的场景，例如，“一九三八年”和“一八三九年”，计算得到的杰卡德相似度是100％，实际上两段文本代表的意思却完全不同。

3.5 余弦相似度

余弦相似度的“灵感”来自数学中的余弦定理，计算公式如下所示。

$\cos \theta = \frac{\sum_{i=1}^{n} (A_i \times B_i)}{\sqrt{\sum_{i=1}^{n} (A_i)^2} \times \sqrt{\sum_{i=1}^{n} (B_i)^2}}$

        在上式中，A、B分别是两段文本对应的n维向量。例如，文本一是“一把雨伞”，文本二是“下雨了开雨伞”，计算这两段文本的余弦相似度。可以看出这两段文本的并集为｛一，把，雨，伞，下，了，开｝，共7个字。
        若并集中的第1个字在文本一中出现了n次，则 $A _ { 1 } = n ( n = 0 , 1 , 2 , \cdots )$ 。
        若并集中的第2个字在文本一中出现了n次，则 $A _ { 2 } = n ( n = 0 , 1 , 2 , \cdots )$
        以此类推，算出 $A _ { 3 }$ , $A _ { 4 }$ , $\cdots$ , $A _ { 7 }$ 及 $B _ { 1 }$ , $B _ { 2 }$ , $\cdots$ , $B _ { 7 }$ ，最终可以得到 $A = ( 1 , 1 , 1 , 1 , 0 , 0 , 0 )$ , $B = ( 0 , 0 , 2 , 1 , 1 , 1 )$ 。
        将A、B代入式中，得到的结果如下式所示

                                 $\cos \theta = \frac { 0 + 0 + 2 + 1 + 0 + 0 + 0 } { \sqrt { 1 + 1 + 1 + 1 + 0 + 0 + 0 } \times \sqrt { 0 + 0 + 2 ^ { 2 } + 1 + 1 + 1 + 1 } } \approx 0 . 5 3$
        余弦相似度和杰卡德相似度虽然计算方式差异较大，但性质很类似，都与文本的交集高度相关，所以它们的适用场景也非常类似。余弦相似度相比杰卡德相似度最大的不同在于它考虑到了文本的频次，例如“下雨了开雨伞”中出现了2次“雨”，“一把雨伞”只出现1次“雨”，计算得到的余弦相似度是不同的。例如“这是是是是是是一个文本”和“这是一个文文文文文文本”，余弦相似度是39％，在不考虑语义的前提下，整体上符合“相同的内容少于一半，但超过1／3”的观感。
        余弦相似度不太适用于向量之间方向相同但大小不同的情况，通常这种情况下余弦相似度是100％。例如“太棒了”和“太棒了太棒了太棒了”，向量分别是（1,1,1）和（3,3,3），计算出的相似度是100％。可根据业务场景进行取舍，在有些场景下认为两者意思差不多，只是语气程度不一样，此时可认为使用余弦相似度计算出的文本相似度是可靠的；在有些场景下认为两者差异很大，哪怕两段文本所表达的意思差不多，但纯粹从文本的角度来看相似度并不高，因为前者为3个字、后者为9个字，在这种场景下使用余弦相似度计算出的文本相似度是不理想的。

3.6 哈罗距离

        哈罗（Jaro）距离是指对两个字符串的相似度进行衡量，以得出两个字符串的相似程度，如式下所示。
                                                 $d = \frac { 1 } { 3 } ( \frac { m } { \vert s _ { 1 } \vert } + \frac { m } { \vert s _ { 2 } \vert } + \frac { m - t } { m } )$
        其中，m是两个字符串中相互匹配的字符数量； $\vert s _ { 1 } \vert$ 和 $\vert s _ { 2 } \vert$ 表示两个字符串的长度（字符数量）；t是换位数量。
        用于字符串匹配的阈值如下式所示。

                                                      $k = [ \frac { \max ( \vert s _ { 1 } \vert , \vert s _ { 2 } \vert ) } { 2 } - 1 ]$
        当字符串 $s_{1}$ 中某字符与字符串 $s _ { 2 }$ 中某字符相同，且这些相同字符的位置相距小于等于k时，则认为这两个字符串是匹配的。
        例如，“我明白了”和“快一点告诉我”，按上式算出k = 2。虽然两个字符串中都有“我”字，但一个在第1位，另一个在第6位，相距为5，大于k值，所以这两个字符串没有任何一个字符是匹配的。再例如，“我明白了”和“明白了我”，k = 1，所以这两.个字符串的“明”“白”“了”是匹配的，但是“我”是不匹配的，所以两者有3个字符是匹配的。将 $s _ { 1 }$ 和 $s _ { 2 }$ 匹配的字符依次抽出来，其中顺序不一样的字符即为换位数量。
        例如，计算“我表白了一个女孩”和“近几天我白表了一次情”的哈罗距离示意如下。
   $\vert s _ { 1 } \vert = 8,\vert s _ { 2 } \vert = 1 0 ,k = 4$ ，匹配的字符有5个，即m = 5，分别是“我”“表”“白”“了”,“一”。
        将 $s _ { 1 }$ 中的匹配字符依次抽出来，得到一个向量 $r _ { 1 }$ = (我，表，白，了，一）。
        将 $s _ { 2 }$ 中的匹配字符依次抽出来，得到一个向量 $r_{2}$ ＝（我，白，表，了，一）。
        比对 $r _ { 1 }$ 和 $r _ { 2 }$ 发现有2个位置的值不一样，即第2位和第3位，所以换位数t = 2 。
        代入上式中可以得到哈罗距离 $d = \frac { 1 } { 3 } [ \frac { 5 } { 8 } + \frac { 5 } { 1 0 } + \frac { ( 5 - 2 ) } { 5 } ] = 0 . 5 7 5$ 。

        该算法主要适用于对位置、顺序敏感的文本。文本位置的偏移，很容易使匹配字符数m变少；文本顺序的变换，会使换位数量t增大。它们都会使哈罗距离减小。如果某业务场景下需要考虑文本位置偏移、顺序变换的影响，既不希望位置或顺序变了相似度却保持不变，又不希望直接“一刀切”，将相似度变为0，那么此时使用哈罗距离计算文本相似度是十分合适的。
        哈罗距离从换位字符数的角度看与编辑距离类似，从匹配字符的抽取角度看又与“交集”类似。
        最后使用一个例子对本节中的相似度算法进行横向对比，计算“我表白了一个女孩”和“近几天我白表了一次情”的文本相似度。

使用编辑距离计算文本相似度，其中 $S _ { 1 }$ 长度是8， $S _ { 2 }$ 长度是10，因此得到编辑距离等于8，从数据上看文本非常不相似，与人的感官预期差异很大。使用杰卡德相似度算出来是38.5％，相似度比较低，和人的感官预期差异较大。使用余弦相似度算出来是55,9％，和哈罗距离计算得到的结果相近，都是50％以上，比较符合人的感官预期，即超过一半的内容是相同的，同时有将近一半内容是不同的。如果在此例中，调整字符顺序，让换位数量t变大，让匹配数量m变小，则得到余弦相似度不变，而哈罗距离会减小。