向量相似度计算.doc

向量相似度测量  2013-02-2319:36:21|  分类:默认分类|字号 订阅相似度,可以完全转化为两个向量之间的相似度。而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算。事实上,这种表示方法压缩了字符串,用每个字符出现的次数代替了字符串本身,损失了字符出现的位置信息。因此,对于同一个消息,如果只调换了字符顺序的话,通过这种方式计算出的消息指纹不变。但实际情况中,这种情况往往出现较少。(一个极端的例子。是“喜欢”和“欢喜”)。对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作。两个字符串的最短编辑距离是指把一个字符串变为另外一个字符串需要的最少操作次数。求解最小编辑距离是一个可以用动态规划方法解决的经典问题。,曼哈顿距离度量下,任意两点之间的距离是其坐标的绝对差异的总和。。这个距离测量的名字来源于曼哈顿的街道网格布局。任何一个新的纽约客知道,你不能从第二大道的第二街直通建筑物步行到第六大道的第六街。真正的步行距离会比4*4块多,在数学上,两个n维向量的曼哈顿距离公式如下:在数据分析和数据挖掘的过程中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如K最近邻(KNN)和K均值(K-Means)。当然衡量个体差异的方法有很多,最近查阅了相关的资料,这里整理罗列下。为了方便下面的解释和举例,先设定我们要比较X个体和Y个体间的差异,它们都包含了N个维的特征,即X=(x1,x2,x3,…xn),Y=(y1,y2,y3,…yn)。下面来看看主要可以用哪些方法来衡量两者的差异,主要分为距离度量和相似度度量。距离度量距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大。欧几里得距离(EuclideanDistance) 欧氏距离是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离。公式如下: 因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高(cm)和体重(kg)两个单位不同的指标使用欧式距离可能使结果失效。明可夫斯基距离(MinkowskiDistance) 明氏距离是欧氏距离的推广,是对多个距离度量公式的概括性的表述。公式如下: 这里的p值是一个变量,当p=2的时候就得到了上面的欧氏距离。曼哈顿距离(ManhattanDistance) 曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,即当上面的明氏距离中p=1时得到的距离度量公式,如下:相似度度量相似度度量(Similarity),即计算个体间的相似程度,与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大。向量空间余弦相似度(CosineSimilarity) 余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量,余弦相似度更加注重两个向量