向量相似度计算.docx

相似度，可以完全转化为两个向量之 间的相似度。而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算。 事实上，这种表示方法压缩了字符串，用每个字符出现的次数代替了字符串本身，损失了字符出现的位置信息。因此，对于同一个消息，如果只调换了字符顺序的 话，通过这种方式计算出的消息指纹不变。但实际情况中，这种情况往往出现较少。 （一个极端的例子 。是“喜欢”和“欢喜”）3.3.2 最短编辑距离 最短编辑距离是一个经典的概念。对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作。两个字符串的最短编辑距离是指把一个字符 串变为另外一个字符串需要的最少操作次数。 求解最小编辑距离是一个可以用动态规划方法解决的经典问题。

7.4.3 曼哈顿距离度量

不 同于欧几里得距离，曼哈顿距离度量下，任意两点之间的距离是其坐标的绝对差异的总和。图7.6比较在XY平面上的两个点之间的欧氏距离和曼哈顿距离。这个 距离测量的名字来源于曼哈顿的街道网格布局。任何一个新的纽约客知道，你不能从第二大道的第二街直通建筑物步行到第六大道的第六街。真正的步行距离会比 4*4块多，在数学上，两个n维向量的曼哈顿距离公式如下:

在数据分析和数 据挖掘的过程中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分 类和聚类算法，如K最近邻（KNN）和K均值（K-Means）。当然衡量个体差异的方法有很多，最近查阅了相关的资料，这里整理罗列下。

为了方便下面的解释和举例，先设定我们要比较X个体和Y个体间的差异，它们都包含了N个维的特征，即X=（x1, x2, x3, xn），Y=（y1, y2, y3, yn）。下面来看看主要可以用哪些方法来衡量两者的差异，主要分为距离度量和相似度度量。

距离度量

距离度量（Distance）用于衡量个体在空间上存在的距离，距离越远说明个体间的差异越大。

欧几里得距离(Euclidean Distance)

欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下：

因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。

明可夫斯基距离(Minkowski Distance)

第1页