气有浩然 学无止境

短文本相似度算法及改进

简介

短文本相似度即计算两段短文本的相似程度,文本语义越相近,则相似度越高。例如:今天天气很好今天天气晴朗相似度较高,而今天天气很好小明是个三好学生相似度较低。计算文本相似度有多种方法,接下来笔者会分别介绍编辑距离法词向量法以及笔者自己创新改进的文本相似度计算方法

基于编辑距离

所谓编辑距离,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。
该算法较为轻量,实现简单,在Python,PHP,C++,Java等各大主流编程语言中都实现了现成的接口以供调用。该算法仅从字词层面进行文本对比,对语法,语义层面的文本基本没有效果,如:‘金正恩扬言攻击美国’和‘三胖威胁袭击美帝’,这两句话虽然意思一样,但该算法计算出的相似度却很低。尽管如此,该算法依旧在系统中被大规模使用,例如在标题聚类、查重,内容防copy,防重复提交等精度要求较低的场景中,该算法以其轻量,简单,高效的优势大展身手。

基于词向量

词向量是自然语言处理领域最基础的技术之一,不了解相关技术的读者请自行Google,这里不做过多阐述。基于词向量的短文本相似度算法不仅可以计算文本语法层面的相似度,对语义层面的相似度也有很好的兼顾。以‘金正恩扬言攻击美国’和‘三胖威胁袭击美帝’两句为例,最简单的计算方法如下:

  1. 对这两句话进行分词得到:
    金正恩 扬言 攻击 美国
    三胖 威胁 袭击 美帝
  2. 将每个单词向量化
  3. 用第一句中每个词的向量分别和第二句中每个词的向量求向量夹角的cos值(词义相似度)并取最大值的和,然后取平均,最后把两句话颠倒过来重复上述过程求和再次取平均。

    :用金正恩三胖威胁袭击美帝分别求词义相似度,取相似度最高的值,然后再用扬言三胖威胁袭击美帝分别求词义相似度,取相似度最高的值,以此类推,把所有最高相似度求和取平均。然后将两句话调换位置,再次求最高相似度然后取平均,最后将两个平均数相加除以2,则得到两个句子的相似度。

该算法是最基本的基于词向量的文本相似度算法,当然根据不同需求,还可以有其他变种,比如根据词语重要性的不同,可以给每个单词配上权重,然后在进行上述求和。总之,基于词向量的短文本相似度算法因为包含了语义特征,而且实现简单,效果不俗,在自然语言处理领域,该算法已成为了一种最基本的文本处理算法。
然而即便如此,该算法依旧有着比较大的局限性。例如对于:雷神今天打败了钢铁侠钢铁侠今天打败了雷神这种主谓调换的句子,该算法就没法取得比较好的效果。于是笔者对该算法进行了如下改进。

改进版

改进的算法从句法结构(T1表示)和语法结构(T2表示)两个维度,配合词向量及预配置权重对句子的相似度进行计算。具体做法是:

  1. 对两个句子A雷神今天打败了钢铁侠和B钢铁侠今天打败了雷神分别分词
  2. 将分词后的句子分别解析成对应句子语法树(斯坦福,哈工大及中科院皆有开源项目可供参考)
  3. 分别求出AB两个句子出现的句法类型(如:主谓,动宾,动词短语,名词短语)为集合S1,和S2,然后求集合S1和S2的并集,表示为S3。则T1 = (count(S1) + count(S2)) / count(S3) / 2,该公式确保,如果AB两个句子的句法结构越相似,则T1的值越大,当AB句式完全相同时,T1=1。
  4. 利用上述求得的S1和S2,求得S1和S2的并集为S4,然后分别计算S4中,两个句子的对应句式的相似度然后求和取平均。即A句的动词短语和B句的动词短语利用上述介绍的词向量技术求相似度,A句的主语和B句的主语求相似度,以此类推,直到把S4中出现的所有句式的相似度都求出来然后求和取平均,记为T2。
  5. 则最终相似度的计算公式是:R = w T1 + (1 - w) T2,w是权重。
  6. 最后,该算法最强大的地方是:在计算T1和T2的过程中,可以事先给相应的句法类型配置相应的权重。如A句中主语很重要,则事先将主语的权重配置很高,则计算T2时,因为主语权重较高,而AB两个句子的主语雷神钢铁侠不一样,则最终计算出来的相似度则较小,这在相似度精度要求较高的场景中非常有效。
    总之,该算法可实现人工可控的高度定制化,适用精确度要求较高的短文本相似度计算场景中。缺点是计算效率不高,且需要大量的人工配置与调试。

总结

以上三种短文本相似度算法或思路在生产中都有自己的应用场景,本人改进的第三种算法虽然精确度比算法一二要高,但配置复杂,调试困难,需要大量的人工成本,所以可能并不适用一些简单,或者粗粒度的场景中,开发者要根据自己的实际需求合理选择最适合自己的算法。

⬆️