欧几里德距离和曼哈顿距离本文由云 + 社区发表
作者：netkiddy
AI 在 2018 年应该是互联网界最火的名词，没有之一。时间来到了 9102 年，也是项目相关，涉及到了一些 AI 写作相关的功能，为客户生成一些素材文章。但是，AI 并不一定最懂你，客户对于 AI 写出来的文章，多少是会做些修改的。为了更好的衡量出 AI 文章的可用度，在这儿就会需要存有一个反馈的环节，来看看用户润色后的文章与原始 AI 文章之间的区别是多大，AI 写出来的文章可用性是否足够。由于目前还没精力细究 AI 写作其中的细节，为了更好地计算每次成文与原文的区分，便花了点小时间看了看文本相似度的知识点，记录于此。
本文将从预备知识的概念开始介绍，从距离名词，到文本分词，相似度算法，并将这些概念融合、统一的介绍 NLP 中文本相似度的知识，期望通过本文，大家可以与我一样，对这些知识有个基本的了解。
在介绍更多的内容之前，我们需要了解文本距离的概念，这些距离是我们在后文比较文本相似度的基础，所以下面将首先形象的为大家介绍几个重要且基础的距离含义。
Euclidean Distance，是最直白的、最容易直观理解的距离度量方法，在二维空间来看，用一句几乎耳熟能详的话来解释就是：两点之间直线最短。这句话中说到的「直线距离」就是欧几里德距离。我们来看下相关数学公式定义。
二维的公式：
p = sqrt( (x1-y1)2+(x2-y2)2 )
三维的公式：
p = sqrt( (x1-y1)2+(x2-y2)2+(x3-y3)2 )
当然，毕竟不是存活于刘慈溪的三体世界之下，我们在小学或者日常所能感知到的多是，二维或者三维空间的距离，当大于 3 维，从数学理论上的 n 维空间的公式，在欧几里德空间中，点x =(x*1,...,*xn) 和 y =(y*1,...,*yn) 之间的欧氏距离为：
p = sqrt( (x1-y1)2+(x2-y2)2+(x3-y3)2+ ... +(xn-yn)2 )
Manhattan Distance 的命名原因，是从规划为方型建筑区块的城市（如曼哈顿）间，最短的出租车从一个点 A 到另一个点 B 的行车路径距离，任何往东三区块、往北六区块的的路径一定最少要走九区块（出租车当然不能穿插过街区），没有其他捷径。抽象到数学角度，从点 A(x1, y1) 到点 B(x2, y2) 的曼哈顿距离为两个点上在标准坐标系上的绝对轴距之总和：
p = |x1-x2| + |y1-y2|
那么，曼哈顿距离和欧几里得距离的区别是什么呢？我们从维基百科拉过来一张图，就可以很直白的看到这二者的区别，假设在下方棋盘一样的图示中，白色方块表示为建筑物，灰色线条表示为道路，那么其中绿色线路表示为黑色两点之间的欧几里德距离（两点之间直线最短），而剩下的红蓝黄三色线路表示的均为为曼哈顿距离：
欧几里德距离和曼哈顿距离
Chebyshev distance 得名自俄罗斯数学家切比雪夫。大家对切比雪夫应该多少是觉得有印象的，没错，切比雪夫更被我们熟悉的是中学时候学过的关于他的切比雪夫多项式吧。所谓切比雪夫距离，是将两点之间的距离定义为其各座标数值差的最大值。如果我们以二维空间中两点 A(x1,y1) 和 B(x2,y2) 二点为例，其切比雪夫距离：
p = max(|x2-x1|, |y2-y1|)
更形象的来介绍，切比雪夫距离在二维空间有着一个应用场景：国际象棋中「国王」的行走距离。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子，我们将国际象棋的棋盘映射到二维直角座标系中，格子的边长定义为 1，座标的 x 轴及 y 轴和棋盘方格平行，原点恰落在某一格的中心点，则「国王」从一个位置走到其他位置需要的步数恰为这两个位置的切比雪夫距离。下图是棋盘上所有位置距 f6 位置的切比雪夫距离。
国际象棋的国王
Cosine distance 使用两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比于欧几里德距离，余弦距离更加注重的是两个向量在方向上的差异。首先我们来看一下数学中余弦定理的定义：
余弦定理公式
关于余弦定理，这儿我们简单来复习下这个初中概念。前几年曾经有过一个地方的高考题出过余弦定理的证明，当时也有人通过向量的方法来证明，两行就得出了答案（其实这儿有点疑问，因为课本中对向量内积是通过余弦定理来证明的，所以从个人来看通过向量内积来证明余弦定理是有些逻辑问题的），那么具体应该如何证明呢？其实很简单，通过一张图就可以证明：
余弦定理的证明
结合这张图，花 2 分钟应该就可以得到余弦定理的结论了，其中需要了解的一点事对于 b*sin(θ) 的定义，是直接使用了毕氏定理。
数学家已经证明，余弦的这种计算方法对 n 维向量也成立。假定 A 和 B 是两个 n 维向量，A 是 [A1, A2, ..., An] ，B 是 [B1, B2, ..., Bn] ，则 A 与 B 的夹角θ的余弦等于：
余弦定理的向量计算公式
使用这个公式，我们会可以更方便的计算余弦距离。
回到余弦距离上来，它与我们上面说的欧几里得距离的区别是什么呢？我们引用一张网上的图片来形象的了解下余弦距离的含义：
余弦距离和欧几里得距离
在上图中，欧几里德距离 dist(A, B) 衡量的是空间中两点的绝对距离，跟各个点所在的位置坐标是直接相关的；而余弦距离衡量的是空间向量的夹角，更加体现在方向上的差异，而不是位置。如果我们保持 A 点位置不变，B 点朝原方向远离坐标轴原点，那么这个时候余弦距离是保持不变的（因为夹角没有发生变化），而 A、B 两点的欧几里德距离显然在发生改变，这就是两者之间的不同之处。
关于余弦距离和欧几里得距离在现实场景中的区别，我们可以通过下面这个例子来形象的了解。现在有用户 A 和用户 B 分别对外卖骑手员工 X 和员工 Y 进行了评分。用户 A 对员工 X 的评分为 2，对员工 Y 的评分为 3，表示到坐标系中为坐标点 AB(2, 3)；同样用户 B 对员工 X、Y 的评分表示为坐标点 B(4, 6)，因此他们之间的欧几里德距离为：
p = sqrt((2 - 4)2 + (3- 6)2) = 3.6
而他们的余弦距离为：
p = (2 * 4 + 3 * 6) / ( sqrt( 22 + 32 ) * sqrt( 42 + 62 ) ) = 1
结合图示如下，其中，点 A 与点 B 之间的之间距离为红色线段所示，也就是上述的欧几里得距离。同时，线段 0A 和线段 0B 由于斜度相等，也就是夹角为 0 度，反映出的余弦距离就是 cos(0) = 1，说明二者完全相似。
用户评分距离图示
欧几里得距离和余弦距离各自有不同的计算方式和衡量特征，因此它们适用于不同的数据分析模型：前者能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。后者则倾向于是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦距离对绝对数值不敏感）。
Hamming distance 在信息论中，表示为两个「等长」字符串之间对应位置的不同字符的个数。换句话说，汉明距离就是将一个字符串变换成另外一个字符串所需要「替换」的字符个数。如下图所示：
汉明距离图示
在了解了上述一系列的距离含义之后，我们已经基本了解了衡量相似度的一个判定方法，但是对于一段文本内容来说，我们对什么来计算距离呢？这就涉及到了第二个基础知识：分词。
为了实现对文本相似度的比较，我们需要分析文本的内容，也就必然会涉及到对文本进行分词处理。而说到分词，其中涉及的内容不比任何一个其他知识点要少，考虑到不是本文重点讲述，此处仅仅简单的列举了下当前分词算法的几种方向，有兴趣的同学可以就此列表再去细细琢磨
从工程角度来看，目前分词已经有了十分成熟工程实现了，如 IK，ansj 等，列出一些比较常用的中文分词方案，以供大家学习使用：
在介绍完距离和分词之后，接下来，我们就需要来关注计算文本相似度的算法了。总的来说，计算文本相似度的算法共分为 4 类：
结合我们上文的几种距离，其中欧几里德距离、曼哈顿距离和余弦距离等适合应用于词向量，汉明距离应属于基于字符的文本相似度的度量方法。本文接下来将重点介绍基于余弦复杂度的文本相似度比较算法，和适用于海量数据的 simhash 文本相似度算法，并给予一定的工程实现方案。
对于多个不同的文本或者短文本对话消息要来计算他们之间的相似度如何，一个好的做法就是将这些文本中词语，映射到向量空间，形成文本中文字和向量数据的映射关系，再通过计算几个或者多个不同的向量的差异的大小，来计算文本的相似度。下面介绍一个详细成熟的向量空间余弦相似度方法计算相似度算法。
枯燥的原理不如示例来的简单明了，我们将以一个简单的示例来介绍余弦复杂度的原理。现在有下面这样的两句话，从我们直觉感官来看，说的是一模一样的内容，那么我们通过计算其余弦距离来看看其相似度究竟为多少。
S1: "为什么我的眼里常含泪水，因为我对这片土地爱得深沉"
S2: "我深沉的爱着这片土地，所以我的眼里常含泪水"
第一步，分词：
我们对上述两段话分词分词并得到下面的词向量：
S1: [为什么 我 的 眼里 常含 泪水 因为 我 对 这片 土地 爱得 深沉 ，]
S2: [我 深沉 的 爱 着 这片 土地 所以 我 的 眼里 常含 泪水 ，]
第二步，统计所有词组：
将 S1 和 S2 中出现的所有不同词组融合起来，并得到一个词向量超集，如下：
[眼里 这片 为什么 我 的 常含 因为 对 所以 爱得 深沉 爱 着 ， 泪水 土地]
第三步，获取词频：
对应上述的超级词向量，我们分别就 S1 的分词和 S2 的分词计算其出现频次，并记录：
S1: [1 1 1 2 1 1 1 1 0 1 1 0 0 1 1 1]
S2: [1 1 0 2 2 1 0 0 1 0 1 1 1 1 1 1]
第四步，复杂度计算：
通过上述的准备工作，现在我们可以想象在空间中存在着两条线段：SA 和 SB，二者均从原点（[0, 0, ...]）出发，指向不同的方向，并分别终结于点 A [1 1 1 2 1 1 1 1 0 1 1 0 0 1 1 1] 和点 B[1 1 0 2 2 1 0 0 1 0 1 1 1 1 1 1]，其中点 A 和点 B 的坐标与我们上述的词频一致。到了这一步，我们可以发现，对于句子 S1 和 S2 的相似度问题，已经被我们抽象到如何计算上述两个向量的相似问题了。
通过上文介绍的余弦定理，我们知道当两条线段之间形成一个夹角，如果夹角为 0 度，意味着方向相同、线段重合，我们就认定这是表示两个向量代表的文本完全相等；如果夹角为 90 度，意味着形成直角，方向完全不相似。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。
那么对于上述给定的两个属性向量A 和B，其余弦相似性θ由点积和向量长度给出，其余弦相似度的计算如下所示：
余弦相似度计算公式
下面我们将通过 golang 来实现一个简单的余弦相似度算法。
func CosineSimilar(srcWords, dstWords []string) float64 {
// get all words
allWordsMap := make(map[string]int, 0)
for _, word := range srcWords {
if _, found := allWordsMap[word]; !found {
allWordsMap[word] = 1
} else {
allWordsMap[word] += 1
}
}
for _, word := range dstWords {
if _, found := allWordsMap[word]; !found {
allWordsMap[word] = 1
} else {
allWordsMap[word] += 1
}
}
// stable the sort
allWordsSlice := make([]string, 0)
for word, _ := range allWordsMap {
allWordsSlice = append(allWordsSlice, word)
}
// assemble vector
srcVector := make([]int, len(allWordsSlice))
dstVector := make([]int, len(allWordsSlice))
for _, word := range srcWords {
if index := indexOfSclie(allWordsSlice, word); index != -1 {
srcVector[index] += 1
}
}
for _, word := range dstWords {
if index := indexOfSclie(allWordsSlice, word); index != -1 {
dstVector[index] += 1
}
}
// calc cos
numerator := float64(0)
srcSq := 0
dstSq := 0
for i, srcCount := range srcVector {
dstCount := dstVector[i]
numerator += float64(srcCount * dstCount)
srcSq += srcCount * srcCount
dstSq += dstCount * dstCount
}
denominator := math.Sqrt(float64(srcSq * dstSq))
return numerator / denominator
}
--- PASS: TestCosineSimilar (0.84s)
similarity_test.go:23: CosineSimilar score: 0.7660323462854266
我们看到，对于上述两句话，在经过余弦计算后，得到的相似度为 0.766（其夹角大概是 40 度），还是比较接近于 1，所以，上面的句子 S1 和句子 S2 是基本相似的。由此，我们就得到了文本相似度计算的处理流程是:
基于余弦复杂度，通过两两比较文本向量来得到两个文本的相似程度是一个非常简单的算法。然而两两比较也就说明了时间复杂度是 O(n2)，那么在面对互联网海量信息时，考虑到一个文章的特征向量词可能特别多导致整个向量维度很高，使得计算的代价太大，就有些力不从心了。因此，为了在爬取网页时用于快速去重，Google 发明了一种快速衡量两个文本集相似度的算法：simhash。
简单来说，simhash 中使用了一种局部敏感型的 hash 算法。所谓局部敏感性 hash，与传统 hash 算法不同的是（如 MD5，当原始文本越是相似，其 hash 数值差异越大），simhash 中的 hash 对于越是相似的内容产生的签名越相近。
simhash 的主要思想是降维，将文本分词结果从一个高维向量映射成一个 0 和 1 组成的 bit 指纹 (fingerprint)，然后通过比较这个二进制数字串的差异进而来表示原始文本内容的差异。下面我们通过图文方式来解释下这个降维和差异计算的过程。
simhash 算法流程实例
在 simhash 中处理一个文本的步骤如下：
第一步，分词：
对文本进行分词操作，同时需要我们同时返回当前词组在文本内容中的权重（这基本上是目前所有分词工具都支持的功能）。
第二步，计算 hash：
对于每一个得到的词组做 hash，将词语表示为到 01 表示的 bit 位，需要保证每个 hash 结果的位数相同，如图中所示，使用的是 8bit。
第三步，加权
根据每个词组对应的权重，对 hash 值做加权计算（bit 为 1 则取为 1 做乘积，bit 为 0 则取为-1 做乘积），如上图中，
第三步，纵向相加：
将上述得到的加权向量结果，进行纵向相加实现降维，如上述所示，得到 [-3 3 -7 -3 7 -3 7 7]。
第四步，归一化：
将最终降维向量，对于每一位大于 0 则取为 1，否则取为 0，这样就能得到最终的 simhash 的指纹签名 [0 1 0 0 1 0 1 1]
第五步，相似度比较：
通过上面的步骤，我们可以利用 SimHash 算法为每一个网页生成一个向量指纹，在 simhash 中，判断 2 篇文本的相似性使用的是海明距离。什么是汉明距离？前文已经介绍过了。在在经验数据上，我们多认为两个文本的汉明距离<=3 的话则认定是相似的。
完整代码见Github
func SimHashSimilar(srcWordWeighs, dstWordWeights []WordWeight) (distance int, err error) {
srcFingerPrint, err := simhashFingerPrint(srcWordWeighs)
if err != nil {
return
}
fmt.Println("srcFingerPrint: ", srcFingerPrint)
dstFingerPrint, err := simhashFingerPrint(dstWordWeights)
if err != nil {
return
}
fmt.Println("dstFingerPrint: ", dstFingerPrint)
distance = hammingDistance(srcFingerPrint, dstFingerPrint)
return
}
func simhashFingerPrint(wordWeights []WordWeight) (fingerPrint []string, err error) {
binaryWeights := make([]float64, 32)
for _, ww := range wordWeights {
bitHash := strHashBitCode(ww.Word)
weights := calcWithWeight(bitHash, ww.Weight) //binary每个元素与weight的乘积结果数组
binaryWeights, err = sliceInnerPlus(binaryWeights, weights)
//fmt.Printf("ww.Word:%v, bitHash:%v, ww.Weight:%v, binaryWeights: %v\n", ww.Word,bitHash, ww.Weight, binaryWeights)
if err != nil {
return
}
}
fingerPrint = make([]string, 0)
for _, b := range binaryWeights {
if b > 0 { // bit 1
fingerPrint = append(fingerPrint, "1")
} else { // bit 0
fingerPrint = append(fingerPrint, "0")
}
}
return
}
func calcWithWeight(bitHash string, weight float64) []float64 {
bitHashs := strings.Split(bitHash, "")
binarys := make([]float64, 0)
for _, bit := range bitHashs {
if bit == "0" {
binarys = append(binarys, float64(-1)*weight)
} else {
binarys = append(binarys, float64(weight))
}
}
return binarys
}
我们使用了调换一段长本文的语序来测试 simhash 的效果：
文本1：
"沉默螺旋模式中呈现出民意动力的来源在于人类有害怕孤立的弱点，但光害怕孤立不至于影响民意的形成，" +
"主要是当个人觉察到自己对某论题的意见与环境中的强势意见一致（或不一致时），害怕孤立这个变项才会产生作用。 " +
"从心理学的范畴来看，社会中的强势意见越来越强，甚至比实际情形还强，弱势意见越来越弱，甚至比实际情形还弱，这种动力运作的过程成–螺旋状"
文本2：
"从心理学的范畴来看，害怕孤立这个变项才会产生作用。社会中的强势意见越来越强，甚至比实际情形还强，弱势意见越来越弱，" +
"主要是当个人觉察到自己对某论题的意见与环境中的强势意见一致（或不一致时），甚至比实际情形还弱，这种动力运作的过程成–螺旋状 " +
"但光害怕孤立不至于影响民意的形成，沉默螺旋模式中呈现出民意动力的来源在于人类有害怕孤立的弱点"
通过计算，结果得到二者的指纹是一模一样，其汉明距离为 0.
srcFingerPrint: [1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0]
dstFingerPrint: [1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0]
--- PASS: TestSimHashSimilar (0.85s)
similarity_test.go:57: SimHashSimilar distance: 0
PASS
注意一：
我们再来看一个文章主旨类似，但是内容相关性较低的文本比较示例：
文本1：
"关于区块链和数字货币的关系，很多人或多或少都存在疑惑。简单来说，区块链是比特币的底层运用，而比特币只是区块链的一个小应用而已。" +
"数字货币即虚拟货币，最早的数字货币诞生于2009年，其发明者中本聪为了应对经济危机对于实体货币经济的冲击。比特币是最早的数字货币，后来出现了以太币、火币以及莱特币等虚拟货币，这些虚拟货币是不能用来交易的。" +
"狭义来讲，区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构， 并以密码学方式保证的不可篡改和不可伪造的分布式账本。" +
"广义来讲，区块链技术是利用块链式数据结构来验证与存储数据、利用分布式节点共识算法来生成和更新数据、利用密码学的方式保证数据传输和访问的安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算方式。"
文本2：
"区块链技术为我们的信息防伪与数据追踪提供了革新手段。区块链中的数据区块顺序相连构成了一个不可篡改的数据链条，时间戳为所有的交易行为贴上了一套不讲课伪造的真是标签，这对于人们在现实生活中打击假冒伪劣产品大有裨益； " +
"市场分析指出，整体而言，区块链技术目前在十大金融领域显示出应用前景，分别是资产证券化、保险、供应链金融、场外市场、资产托管、大宗商品交易、风险信息共享机制、贸易融资、银团贷款、股权交易交割。" +
"这些金融场景有三大共性：参与节点多、验真成本高、交易流程长，而区块链的分布式记账、不可篡改、内置合约等特性可以为这些金融业务中的痛点提供解决方案。" +
"传统的工业互联网模式是由一个中心化的机构收集和管理所有的数据信息，容易产生因设备生命周期和安全等方面的缺陷引起的数据丢失、篡改等问题。区块链技术可以在无需任何信任单个节点的同时构建整个网络的信任共识，从而很好的解决目前工业互联网技术领域的一些缺陷，让物与物之间能够实现更好的连接。"
通过计算，当我们选择前 top10 高频词作为衡量时，结果得到二者的指纹是如下，其汉明距离为 4：
srcFingerPrint: [1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1]
dstFingerPrint: [1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1]
--- PASS: TestSimHashSimilar (0.84s)
similarity_test.go:58: SimHashSimilar distance: 4
PASS
当我们选择前 top50 高频词作为衡量时，结果得到二者的指纹是如下，其汉明距离为 9：
srcFingerPrint: [1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1]
dstFingerPrint: [1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1]
--- PASS: TestSimHashSimilar (0.83s)
similarity_test.go:58: SimHashSimilar distance: 9
PASS
所以我们发现了一个对结果判定很重要的参数：分词数量。在上面的示例中，当我们选择 10 个分词时，其汉明距离仅为 4，几乎符合了我们对文本相似（汉明距离 3）的判断。而随着 topN 数量的增加，引入了更多的词组，其汉明距离越来越大，这也说明了，当大文本内容出现时，选择合适的 topN 分词数量进行比较对结果的影响是十分大的。
注意二：
另外一点需要需要注意的是，simhash 的优点是适用于高维度的海量数据处理，当维度降低，如短文本的相似度比较，simhash 并不合适，以我们计算余弦相似度的文本为例，
S1: "为什么我的眼里常含泪水，因为我对这片土地爱得深沉"
S2: "我深沉的爱着这片土地，所以我的眼里常含泪水"
得到的结果如下：
srcFingerPrint: [1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0]
dstFingerPrint: [1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0]
--- PASS: TestSimHashSimilar (0.86s)
similarity_test.go:53: SimHashSimilar distance: 12
PASS
也就是结果的汉明距离为 12，远远大于我们预定的汉明距离 3，这样的结果跟我们通过预先相似度计算出来的 0.76 分（相比于 1 分）相差很远，可见 simhash 对于短文本的相似度比较还是存在一些偏差的。
http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/33026.pdf
https://lujiaying.github.io/posts/2018/01/Chinese-word-segmentation/
https://www.zhihu.com/question/19578687
此文已由腾讯云 + 社区在各渠道发布
获取更多新鲜技术干货，可以关注我们腾讯云技术社区 - 云加社区官方号及知乎机构号
