1、文本相似度：

1) 语义相似、但字面不相似

2) 字面相似、但是语义不相似

2、方案：

1) 语义相似：依靠用户行为，最基本的方法：（1）基于共点击的行为（协同过滤），（2）借助回归算法

2) 字面相似：(1) LCS最大公共子序列 (2) 利用中文分词

3 字面相似的问题解决：
       余弦相似度 cosine
                    举例：A(1,2,3)，B(2,3,4)
                    cosine(A,B) = 分子 / 分母
                    分子：A*B = 1*2+2*3+3*4 = 20

                    |A| = sqrt(1*1+2*2+3*3) = 3.74
                    |B| = sqrt(2*2+3*3+4*4) = 5.38
                    分母：|A|*|B| = 20.12

4 tfidf：

1) TF：词频
            
                    关键词：在当前文章出现较多，但在其他文章中出现较少
            
2) IDF：反文档频率
                                    
score = TF * IDF

5、自动摘要:

1) 确定关键词集合（两种方法（a）top-10 （b）阈值截断 > 0.8 ）
2）哪些句子包含关键词，把这些句子取出来
3)  对关键词排序，对句子做等级划分
4）把等级高的句子取出来，就是摘要

6.实践：

1.idf实践：

一共508篇文章

（1）数据预处理：把所有文章的内容，全部收集到一个文件中

]# python convert.py input_tfidf_dir/ > idf_input.data

（2）计算IDF：通过mr批量计算IDF

         计算方法：文档总数/包含该词的文档数

代码：

convert.py:

import os

import sys

file_path_dir = sys.argv[1]

def read_file_handler(f):
    fd = open(f, 'r')
    return fd

file_name = 0
for fd in os.listdir(file_path_dir):
    file_path = file_path_dir + '/' + fd

    content_list = []

    file_fd = read_file_handler(file_path)
    for line in file_fd:
        content_list.append(line.strip())

    print '\t'.join([str(file_name), ' '.join(content_list)])

    file_name += 1

map.py:

import sys

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    file_name, file_content = ss
    word_list = file_content.strip().split(' ')

    word_set = set(word_list)

    for word in word_set:
        print '\t'.join([word, '1'])

red.py:

import sys
import math

current_word = None
sum = 0

docs_cnt = 508

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    word, val = ss
    if current_word == None:
        current_word = word
    if current_word != word:
        idf = math.log(float(docs_cnt) / (float(sum) + 1.0))
        print '\t'.join([current_word, str(idf)])
        current_word = word
        sum = 0

    sum += int(val)

idf = math.log(float(docs_cnt) / (float(sum) + 1.0))
print '\t'.join([current_word, str(idf)])

编写run.sh脚本运行MapReduce：

7.LCS（最长公共子序列）解决方案：

动态规划解决：

LCSpython实践：

1.数据：

2.python代码：

map.py:

# -*- coding: utf-8 -*-
#!/usr/bin/python

import sys

def cal_lcs_sim(first_str, second_str):
    len_vv = [[0] * 50] * 50

    first_str = unicode(first_str, "utf-8", errors='ignore')
    second_str = unicode(second_str, "utf-8", errors='ignore')

    len_1 = len(first_str.strip())
    len_2 = len(second_str.strip())

    for i in range(1, len_1 + 1):
        for j in range(1, len_2 + 1):
            if first_str[i - 1] == second_str[j - 1]:
                len_vv[i][j] = 1 + len_vv[i - 1][j - 1]
            else:
                len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])

    return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2))

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    first_str = ss[0].strip()
    second_str = ss[1].strip()

    sim_score = cal_lcs_sim(first_str, second_str)
    print '\t'.join([first_str, second_str, str(sim_score)])

执行脚本run.sh

执行：

结果：

 

shell终端做快速计算：
            ]# echo $[60000*2/16]
            ]# echo $((60000*2/16))

前言

  在自然语言处理的学习和研究中，有好多问题涉及到如何检测两个文本的相似度问题，尤其是在度量句子或者短语之间的相似度。测算度量文本相似度的方法大体有三种：基于关键词匹配的传统方法、基于向量空间的方法和利用深度学习进行文本相似度检测的方法。随着近些年深度学习学科的发展，文本相似度的方法逐渐从基于关键词匹配的传统方法转变为深度学习，且结合向量空间和深度学习进行文本相似度检测。

文本相似度算法

基于关键词匹配

  基于关键词匹配方法具有代表性的有：N-gram 相似度与Jaccard 相似度

N-Gram相似度

  使用N-Gram相似度进行文本相似度匹配是一种模糊匹配方式，关键在于通过两个长的很像的句子之间的差异来度量相似度。
  N-Gram相似度计算具体指假设有一个字符串，那么字符串的N-Gram表示为按照长度N切分这个字符串原句得到词段（词段即原句中所有长度为N的子串）。设想如果有两个字符串，然后分别求它们的N-Gram，那么就可以从它们的共有子串的数量这个角度去定义两个字符串间的N-Gram距离。通过N-Gram距离来判断这两个句子的相似程度。即：$$Similarity=|G_N(S)|+|G_N(T)|-2\times |G_N(S)\cap G_N(T)|$$  其中，$G_N(S)$和$G_N(T)$ 分别表示字符串S和T的N-Gram集合，当 $Similarity$ 值越低时，两字符串越相似。
  N-Gram忽略了两个字符串长度差异可能导致的问题。比如字符串 girl 和 girlfriend，二者所拥有的公共子串数量显然与 girl 和其自身所拥有的公共子串数量相等，但是并不能据此认为 girl 和girlfriend 是两个等同的匹配。

Jaccard相似度

  jaccard index又称为jaccard similarity coefficient。主要用于比较有限样本集之间的相似性和差异性。
  原理：计算两个句子之间词集合的交集和并集的比值。该值越大，表示两个句子越相似，在涉及大规模并行运算的时候，该方法在效率上有一定的优势，公式如下：$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|}0⩽J(A,B)⩽1$$ jaccard值越大说明相似度越高
  Jaccard不相似度：与jaccard 系数相关的指标是jaccard距离用于描述不相似度，公式如下：$$d_j(A,B)=1-J(A,B)=\frac{|A\cup B|-|A\cap B|}{|A\cup B|}=\frac{A\Delta B}{|A\cup B|}$$
  jaccard相似度的缺点是只适用于二元数据集合。

基于向量空间

Word2vec

  word2vec核心思想是认为词的意思可以从它频繁出现的上下文信息中体现。分为两种结构，一种是Skip-gram，利用中心词预测窗口内的上下文；另一种是CBOW，利用窗口内的上下文预测中心词。
  以CBOW为例，CBOW是一种基于窗口的语言模型。一个窗口指的是句子中的一个固定长度的片段，窗口中间的词语称为中心词，窗口其他词语称为中心词的上下文。CBOW模型通过三层神经网络接受上下文的特征向量，预测中心词是什么。

图1：Word2vec模型结构示意图

TF-IDF

  TF-IDF的核心思想是：在一篇文章中，某个词语的重要性与该词语在这篇文章中出现的次数成正相关，同时与整个语料库中出现该词语的文章数成负相关.
　　TF(term frequency)：词频，某一个给定的词语在该文件中出现的频率，表示一个词语与该文章的相关性。这个数字是对词数（term count）的归一化，以防止它偏向长的文件。
　　IDF(inverse document frequency)：逆向文件词频，表示一个词语出现的普遍程度。某一特定词语的idf，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取以10为底的对数得到。
　　一篇文章中某个词语的重要程度，可以标记为词频和逆向文件词频的乘积.$$tfidf=tf\ast idf$$   通过计算出文档中每个词的TF-IDF值，然后结合相似度计算方法（一般采用余弦相似度）就可以计算两个文档的相似度。

向量空间与相似度计算

  假设有两个对象 $X,Y$，这两个对象都包括N维特征$X=(x_1,x_2,...,x_n)$，$Y=(y_1,y_2,...,y_n)$，常用的计算$X$和$Y$相似性的方法有：欧氏距离、曼哈顿距离、余弦相似度等。
    欧氏距离：最常用的距离计算公式，以多维空间各个点的绝对距离做衡量。适用于数据稠密且连续的情况。拿两个文档所有的词（不重复）在A文档的词频作为x，在B文档的作为y进行计算。$$d=\sqrt{\sum _{t=1}^n(x_i-y_i{)}^2}$$    例如：A=你是个坏人、B=小明是个坏人 ，词频分别为A={1 0 1 1} 、B={0 1 1 1}。则距离为$\sqrt{2}\approx 1.414$，再通过$1÷(1+欧几里德距离)$得到相似度。

    曼哈顿距离：使用在几何度量空间的几何学用语，用以标明两个点上在标准坐标系上的绝对轴距总和。与欧氏距离有点像，即：$$d=\sum _{i=1}^n|x_i-y_i|$$    同理$x_n$和$y_n$分别代表两个文档所有的词（不重复）在$A$和$B$的词频。
    余弦相似度：余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。$$\cos \theta =\frac{{\sum }_{i=1}^n{x}_i\times y_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2{\sum }_{i=1}^n{y}_i^2}}$$    例如：判断两句话

     A=你是个坏人 B=小明是个坏人
     (1)进行分词
     A=你 / 是 / 个 / 坏人 B=小明 / 是 / 个 / 坏人
     (2) 列出所有的词
      { 你 小明 是 个 坏人 }
     (3)计算词频（出现次数）
      A={1 0 1 1} (每个数字对应上面的字) B={0 1 1 1}
     (4)后把词频带入公式
      $\cos \theta =0.667$
    余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫余弦相似度。

基于深度学习

卷积神经网络（CNN）

  CNN通过设计卷积神经网络，结合不同规格的卷积神经网络的差异性度量句子的相似程度。

图2：CNN判断句子相似度结构图   如上图所示，分别对两个句子建模，然后利用一个句子相似度测量层计算句子相似度，最后通过一个全连接层输出相似度得分。

文章参考以下博客及书籍：
Vico_Men_浅析文本相似度
lbky_文本相似度
何晗_《自然语言处理入门》

1. 背景介绍

CSDN 及各类技术博客上有很多文本相似度方面的文章，但它们的侧重点是代码，目标受众是开发人员，代码基础薄弱的话看起来会比较吃力。

本文侧重讲述逻辑和使用场景，尝试将算法通俗化，尽量多举例，降低理解门槛。希望读完本文，大家可以对文本相似度有一个完整而深刻的理解，最好能在非代码维度上超过开发人员（达到了这种水平，输出的需求自然会得到开发同学最大的尊重和认同）。

文本相似度，顾名思义是指两个文本（文章）之间的相似度，在搜索引擎、推荐系统、论文鉴定、机器翻译、自动应答、命名实体识别、拼写纠错等领域有广泛的应用。

总的来说，文本相似度是自然语言处理（NLP）中必不可少的重要环节，几乎所有 NLP 的领域都会涉及到！

与之相对应的，还有一个概念——文本距离——指的是两个文本之间的距离。文本距离和文本相似度是负相关的——距离小，“离得近”，相似度高；距离大，“离得远”，相似度低。业务上不会对这两个概念进行严格区分，有时用文本距离，有时则会用文本相似度。

 

2. 各类算法

2.1 欧氏距离

数学中的一个非常经典的距离，公式如下：

例 1：计算 “产品经理” 和“产业经理是什么”之间的欧氏距离

过程如下：

• 文本向量 A=（产，品，经，理），即 x1 = 产，x2 = 品，x3 = 经，x4 = 理，x5、x6、x7 均为空；
• 文本向量 B=（产，业，经，理，是，什，么），即 y1 = 产，y2 = 业，y3 = 经，y4 = 理，y5 = 是，y6 = 什，y7 = 么。

这里规定，若 xi=yi，则 xi-yi=0；若 xi≠yi，|xi-yi|=1。

所以，欧氏距离d是 2

（1）适用场景

编码检测等类似领域。两串编码必须完全一致，才能通过检测，这时一个移位或者一个错字，可能会造成非常严重的后果。比如下图第一个二维码是 “这是一篇文本相似度的文章”，第二个是 “这是一篇文本相似度文章”。从人的理解来看，这两句话相似度非常高，但是生成的二维码却千差万别。

（2）不适用场景

文本相似度，意味着要能区分相似 / 差异的程度，而欧氏距离更多的只能区分出是否完全一样。而且，欧氏距离对位置、顺序非常敏感，比如 “我的名字是孙行者” 和“孙行者是我的名字”，在人看来，相似度非常高，但是用欧氏距离计算，两个文本向量每个位置的值都不同，即完全不匹配。

 

2.2 曼哈顿距离

和欧氏距离非常相似（把平方换成了绝对值，拿掉了根号），公式如下：

适用场景同欧氏距离。

 

2.3 编辑距离（Levenshtein 距离、莱文斯坦距离）

编辑距离(Edit Distance) 一文读懂：https://blog.csdn.net/sinat_26811377/article/details/102652547

 

顾名思义，编辑距离指的是将文本 A 编辑成文本 B 需要的最少变动次数（每次只能增加、删除或修改一个字）。

例 2：计算 “椰子” 和“椰子树”之间的编辑距离。

因为将 “椰子” 转化成 “椰子树”，至少需要且只需要 1 次改动（反过来，将“椰子树” 转化成“椰子”，也至少需要 1 次改动，如下图），所以它们的编辑距离是 1。

因此，编辑距离是对称的，即将 A 转化成 B 的最小变动次数和将 B 转化成 A 的最小变动次数是相等的。

同时，编辑距离与文本的顺序有关。

比如，“椰子”和 “子椰”，虽然都是由“椰”“子” 组成，但因为顺序变了，编辑距离是 2（如下图），而不是 0。

（1）适用场景

编辑距离算出来很小，文本相似度肯定很高。如果用算法语言来说的话，就是准确率很高（即虽然会漏掉一些好的 case，但可以确保选出来的 case 一定非常好）。

（2）不适用场景

反过来说，虽然准确率很高，但召回率不高。在某些业务场景中，漏掉的 case 会引起严重后果，比如 “批发零售” 和“零售批发”，人的理解应该非常相似，可编辑距离却是 4，相当于完全不匹配，这显然不符合预期。

 

2.4 Jaccard 相似度（杰卡德相似度）

杰卡德相似度，指的是文本 A 与文本 B 中交集的字数除以并集的字数，公式非常简单：

如果要计算 Jaccard 距离，公式稍作变更即可：

例 3：计算 “荒野求生” 和“绝地求生”的杰卡德相似度。

因为它们交集是 {求，生}，并集是 {荒，野，求，生，绝，地}，所以它们的杰卡德相似度 = 2/6=1/3。

杰卡德相似度与文本的位置、顺序均无关。比如 “王者荣耀” 和“荣耀王者”的相似度是 100%。无论 “王者荣耀” 这 4 个字怎么排列，最终相似度都是 100%。

在某些情况下，会先将文本分词，再以词为单位计算相似度。比如将 “王者荣耀” 切分成 “王者 / 荣耀”，将“荣耀王者” 切分成“荣耀 / 王者”，那么交集就是{王者，荣耀}，并集也是{王者，荣耀}，相似度恰好仍是 100%。

（1）适用场景

• 对字 / 词的顺序不敏感的文本，比如前述的 “零售批发” 和“批发零售”，可以很好地兼容。
• 长文本，比如一篇论文，甚至一本书。如果两篇论文相似度较高，说明交集比较大，很多用词是重复的，存在抄袭嫌疑。

（2）不适用场景

• 重复字符较多的文本，比如 “这是是是是是是一个文本” 和“这是一个文文文文文文本”，这两个文本有很多字不一样，直观感受相似度不会太高，但计算出来的相似度却是 100%（交集 = 并集）。
• 对文字顺序很敏感的场景，比如 “一九三八年” 和“一八三九年”，杰卡德相似度是 100%，意思却完全不同。

 

2.5 余弦相似度

余弦相似度的灵感来自于数学中的余弦定理，这里对数学内容不做过多解释，直接上公式：

其中，A、B 分别是文本一、文本二对应的 n 维向量。取值方式用语言比较难描述，直接看例子吧：

 

例 4：文本一是 “一个雨伞”，文本二是 “下雨了开雨伞”，计算它们的余弦相似度。

它们的并集是 {一，个，雨，伞，下，了，开}，共 7 个字。

• 若并集中的第 1 个字符在文本一中出现了 n 次，则 A1=n（n=0，1，2……）。
• 若并集中的第 2 个字符在文本一中出现了 n 次，则 A2=n（n=0，1，2……）。

依此类推，算出 A3、A4、……、A7，B1、B2、……、B7，最终得到：

• A=（1，1，1，1，0，0，0）。
• B=（0，0，2，1，1，1，1）。

将 A、B 代入计算公式，得到

（1）适用场景

余弦相似度和杰卡德相似度虽然计算方式差异较大，但性质上很类似（与文本的交集高度相关），所以适用场景也非常类似。

余弦相似度相比杰卡德相似度最大的不同在于它考虑到了文本的频次，比如上面例子出现了 2 次 “雨”，和只出现 1 次“雨”，相似度是不同的；再比如“这是是是是是是一个文本” 和“这是一个文文文文文文本”，余弦相似度是 39%，整体上符合 “相同的内容少于一半，但超过 1/3” 的观感（仅从文本来看，不考虑语义）。

（2）不适用场景

向量之间方向相同，但大小不同的情况（这种情况下余弦相似度是 100%）。

比如 “太棒了” 和“太棒了太棒了太棒了”，向量分别是（1，1，1）和（3，3，3），计算出的相似度是 100%。

这时候要根据业务场景进行取舍，有些场景下我们认为它们意思差不多，只是语气程度不一样，这时候余弦相似度是很给力的；有些场景下我们认为它们差异很大，哪怕意思差不多，但从文本的角度来看相似度并不高（最直白的，一个 3 个字，一个 9 个字），这时候余弦相似度就爱莫能助了。

 

2.6 Jaro 相似度

Jaro 相似度据说是用来判定健康记录上两个名字是否相同，公式如下：

其中，m 是两个字符串中相互匹配的字符数量；|s1 | 和 | s2 | 表示两个字符串的长度（字符数量）；t 是换位数量。

这里着重说一下 “匹配” 和 “换位” 的概念，先列一个公式，我称之为 “匹配阈值”：

当 s1 中某字符与 s2 中某字符相同，且它们的位置相距小于等于 k 时，就说它们是匹配的。

比如 “我明白了” 和“快一点告诉我”，按公式算出 k=2。虽然两个字符串中都有 “我” 字，但一个在第 1 位，另一个在第 6 位，相距为 5，大于 k 值，所以这两个字符串没有任何一个字符是匹配的。

再比如 “我明白了” 和“明白了我”，k=1，所以这两个字符串的 “明”“白”“了” 是匹配的，但是 “我” 是不匹配的，所以它们有 3 个字符是匹配的。

换位的意思，是将 s1 和 s2 匹配的字符依次抽出来，看它们顺序不一样的字符有多少个，这个数就是换位数量。

例 5：计算 “我表白了一个女孩” 和“近几天我白表了一次情”的 Jaro 相似度。

|s1|=8，|s2|=10，k=4，匹配的字符有 5 个，即 m=5，分别是 “我”“表”“白”“了”“一”。

将 s1 中的匹配字符依次抽出来，得到一个向量 r1=（我，表，白，了，一）。

将 s2 中的匹配字符依次抽出来，得到一个向量 r2=（我，白，表，了，一）。

比对 r1 和 r2，发现有 2 个位置的值不一样（第 2 位和第 3 位），所以换位数 t=2。

于是，d=1/3[5/8+5/10+(5-2)/5]=57.5%。

（1）适用场景

对位置、顺序敏感的文本。文本位置的偏移，很容易使匹配字符数 m 变少；文本顺序的变换，会使换位数量 t 增大。它们都会使 Jaro 相似度减小。换句话说，如果某业务场景下需要考虑文本位置偏移、顺序变换的影响，既不希望位置或顺序变了相似度却保持不变，又不希望直接一刀切将相似度变为 0，那 Jaro 距离是十分合适的。

（2）不适用场景

未知（什么！作者这么任性的吗？）。

其实，我自己确实没想清楚，也没有在实践中使用过这个算法。

整体来说，Jaro 距离是比较综合的文本相似度算法，从换位字符数来看，有点像编辑距离；从匹配字符的抽取来看，又有点像 “交集”。

最后，对例 5 做个横向对比：“我表白了一个女孩” 和“近几天我白表了一次情”

• 方法3的编辑距离算出来是 8，s1 长度是 8，s2 长度是 10，编辑距离等于 8，从数据上看非常不相似，与人的感官差异很大。
• 方法4的杰卡德相似度算出来是 38.5%，数值比较低，和人的感官差异较大。
• 方法5的余弦相似度算出来是 55.9%，和 Jaro 距离算出来差不多，都是 50%+，比较符合人的感官——超过一半的内容是相同的，同时有将近一半内容是不同的。
• 如果在此例中，调整字符顺序，让换位数量 t 变大，匹配数量 m 变小，余弦相似度不变，Jaro 相似度会降低。

 

3. 拓展阅读

3.1 名词解释

算法中的重要概念（指标）——准确率、精确率、召回率。其中准确率和精确率很容易混淆，详细差别可以点开以下链接：http://t.cn/R6y8ay9

3.2 贝叶斯公式

NLP 领域，我个人认为有两个非常重要的、频繁出现的基本公式，一个是前述的文本相似度，另一个就是贝叶斯公式了。对这块有兴趣的同学，可以阅读下文：http://t.cn/haY0x

作者写的非常易于理解——我在《深度学习》这本书里看 NLP 相关内容时，有几个公式怎么都理解不了，看这篇文章简直是秒懂。

3.3 代码

编辑距离的代码见百度百科最底部，有兴趣的同学可以扩展阅读：http://t.cn/R850kBe

余弦相似度的代码见这篇 CSDN 博客 ，写的比较详细：http://t.cn/R850ru8

切记，一定要在电脑上打开链接查看代码（别问我怎么知道的）。

PS. 代码这一块我就意思一下，不是重点，不再每个算法都一一列举了。