【机器学习】机器学习中的各种相似性、距离度量
【机器学习】机器学习中的各种相似性、距离度量标签(空格分隔): 【机器学习】 声明:引用请注明出处http://blog.csdn.net/lg1259156776/ 说明:主要参考了博文《漫谈机器学习中的距离和相似性度量方法》。具体的计算方法可以参看我的上一篇博文《【Matlab开发】matlab中bar绘图设置与各种距离度量》。本文主要关注点在于各个距离、相似度之间的优缺点,及使用时候的注意事项。 1. 闵可夫斯基距离基本认识该距离最常用的 p 是 2 和 1,前者是欧几里得距离(Euclidean distance),后者是曼哈顿距离(Manhattan distance)。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点,白色表示高楼大厦,灰色表示街道:
当 p 趋近于无穷大时,闵可夫斯基距离转化成切比雪夫距离(Chebyshev distance) 我们知道平面上到原点欧几里得距离(p = 2)为 1 的点所组成的形状是一个圆,当 p 取其他数值的时候呢? 注意,当 p < 1 时,闵可夫斯基距离不再符合三角形法则,举个例子:当 p < 1,(0,0) 到 (1,1) 的距离等于
优缺点及注意事项闵可夫斯基距离比较直观,但是它与数据的分布无关,具有一定的局限性,如果 x 方向的幅值远远大于 y 方向的值,这个距离公式就会过度放大 x 维度的作用。所以,在计算距离之前,我们可能还需要对数据进行 z-transform 处理,即减去均值,除以标准差 可以看到,上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关(例如:身高较高的信息很有可能会带来体重较重的信息,因为两者是有关联的),这时候就要用到马氏距离(Mahalanobis distance)了。 2. 马氏距离考虑下面这张图,椭圆表示等高线,从欧几里得的距离来算,绿黑距离大于红黑距离,但是从马氏距离,结果恰好相反: 马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。假设样本点(列向量)之间的协方差对称矩阵是 下图蓝色表示原样本点的分布,两颗红星坐标分别是(3,3),(2,-2): 由于 x, y 方向的尺度不同,不能单纯用欧几里得的方法测量它们到原点的距离。并且,由于 x 和 y 是相关的(大致可以看出斜向右上),也不能简单地在 x 和 y 方向上分别减去均值,除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换,即求马氏距离(可以看到,右边的红星离原点较近): 将上面两个图的绘制代码和求马氏距离的代码贴在这里,以备以后查阅: # -*- coding=utf-8 -*- # code related at: http://www.cnblogs.com/daniel-D/ import numpy as np import pylab as pl import scipy.spatial.distance as dist def plotSamples(x,y,z=None): stars = np.matrix([[3.,-2.,0.],[3.,2.,0.]]) if z is not None: x,y = z * np.matrix([x,y]) stars = z * stars pl.scatter(x,s=10) # 画 gaussian 随机点 pl.scatter(np.array(stars[0]),np.array(stars[1]),s=200,marker='*',color='r') # 画三个指定点 pl.axhline(linewidth=2,color='g') # 画 x 轴 pl.axvline(linewidth=2,color='g') # 画 y 轴 pl.axis('equal') pl.axis([-5,5,-5,5]) pl.show() # 产生高斯分布的随机点 mean = [0,0] # 平均值 cov = [[2,1],[1,2]] # 协方差 x,y = np.random.multivariate_normal(mean,cov,1000).T plotSamples(x,y) covMat = np.matrix(np.cov(x,y)) # 求 x 与 y 的协方差矩阵 Z = np.linalg.cholesky(covMat).I # 仿射矩阵 plotSamples(x,Z) # 求马氏距离 print 'n到原点的马氏距离分别是:' print dist.mahalanobis([0,0],[3,3],covMat.I),dist.mahalanobis([0,[-2,2],covMat.I) # 求变换后的欧几里得距离 dots = (Z * np.matrix([[3,-2,2,0]])).T print 'n变换后到原点的欧几里得距离分别是:' print dist.minkowski([0,np.array(dots[0]),2),dist.minkowski([0,np.array(dots[1]),2) 马氏距离的变换和 PCA 分解的白化处理颇 有异曲同工之妙,不同之处在于:就二维来看,PCA 是将数据主成分旋转到 x 轴(正交矩阵的酉变换),再在尺度上缩放(对角矩阵),实现尺度相同。而马氏距离的 L逆矩阵是一个下三角,先在 x 和 y 方向进行缩放,再在 y 方向进行错切(想象矩形变平行四边形),总体来说是一个没有旋转的仿射变换。 3. 向量内积、余弦相似度和皮尔逊相关系数向量内积是线性代数里最为常见的计算,实际上它还是一种有效并且直观的相似性测量手段。 直观的解释是:如果 x 高的地方 y 也比较高, x 低的地方 y 也比较低,那么整体的内积是偏大的,也就是说 x 和 y 是相似的。
向量内积的结果是没有界限的,一种解决办法是除以长度之后再求内积,这就是应用十分广泛的余弦相似度(Cosine similarity)。 余弦相似度与向量的幅值无关,只与向量的方向相关,在文档相似度(TF-IDF)和图片相似性(histogram)计算上都有它的身影。需要注意一点的是,余弦相似度受到向量的平移影响,上式如果将 x 平移到 x+1,余弦值就会改变。怎样才能实现平移不变性?这就是下面要说的皮尔逊相关系数(Pearson correlation),有时候也直接叫相关系数。 皮尔逊相关系数具有平移不变性和尺度不变性,计算出了两个向量(维度)的相关性。不过,一般我们在谈论相关系数的时候,将 x 与 y 对应位置的两个数值看作一个样本点,皮尔逊系数用来表示这些样本点分布的相关性。
4. 分类数据点间的距离汉明距离(Hamming distance)和杰卡德相似系数(Jaccard similarity),具体可以参考我的上一篇博客《【Matlab开发】matlab中bar绘图设置与各种距离度量》。 5. 序列之间的距离【转自《漫谈机器学习中的距离和相似性度量方法》】上一小节我们知道,汉明距离可以度量两个长度相同的字符串之间的相似度,如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离(Edit distance,Levenshtein distance)等算法。编辑距离是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一 个字符,删除一个字符。编辑距离求的是最少编辑次数,这是一个动态规划的问题,有兴趣的同学可以自己研究研究。 实现代码(转自 McKelvin’s Blog ):、 #!/usr/bin/python2 # -*- coding:UTF-8 -*- # code related at: http://blog.mckelv.in/articles/1453.html import sys distance = lambda a,b : 0 if a==b else 1 def dtw(sa,sb): ''' >>>dtw(u"干啦今今今今今天天气气气气气好好好好啊啊啊",u"今天天气好好啊") 2 ''' MAX_COST = 1<<32 #初始化一个len(sb) 行(i),len(sa)列(j)的二维矩阵 len_sa = len(sa) len_sb = len(sb) # BUG:这样是错误的(浅拷贝): dtw_array = [[MAX_COST]*len(sa)]*len(sb) dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)] dtw_array[0][0] = distance(sa[0],sb[0]) for i in xrange(0,len_sb): for j in xrange(0,len_sa): if i+j==0: continue nb = [] if i > 0: nb.append(dtw_array[i-1][j]) if j > 0: nb.append(dtw_array[i][j-1]) if i > 0 and j > 0: nb.append(dtw_array[i-1][j-1]) min_route = min(nb) cost = distance(sa[j],sb[i]) dtw_array[i][j] = cost + min_route return dtw_array[len_sb-1][len_sa-1] def main(argv): s1 = u'干啦今今今今今天天气气气气气好好好好啊啊啊' s2 = u'今天天气好好啊' d = dtw(s1,s2) print d return 0 if __name__ == '__main__': sys.exit(main(sys.argv))
6. 概率分布之间的距离
参考资料距离和相似性度量
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |