机器学习中的各种相似性、距离度量

本文主要关注点在于各个距离、相似度之间的优缺点，及使用时候的注意事项。

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) 的距离等于(1+1)1/p>2, 而 (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, y, 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, y, Z)

# 求马氏距离
print '\n到原点的马氏距离分别是：'
print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)

# 求变换后的欧几里得距离
dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
print '\n变换后到原点的欧几里得距离分别是：'
print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)

马氏距离的变换和 PCA 分解的白化处理颇 有异曲同工之妙，不同之处在于：就二维来看，PCA 是将数据主成分旋转到 x 轴（正交矩阵的酉变换），再在尺度上缩放（对角矩阵），实现尺度相同。而马氏距离的 L逆矩阵是一个下三角，先在 x 和 y 方向进行缩放，再在 y 方向进行错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射变换。

3. 向量内积、余弦相似度和皮尔逊相关系数

向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相似性测量手段。

直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。

举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理中 DFT 和 DCT也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT是正交标准基，也可以看做投影）。向量和信号都是离散值，如果是连续的函数值，比如求区间[-1, 1]两个函数之间的相似度，同样也可以得到（系数）组分，这种方法可以应用于多项式逼近连续函数，也可以用到连续函数逼近离散样本点.

向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相似度（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）等算法。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一 个字符，删除一个字符。编辑距离求的是最少编辑次数，这是一个动态规划的问题，有兴趣的同学可以自己研究研究。
时间序列是序列之间距离的另外一个例子。DTW 距离（Dynamic Time Warp）是序列信号在时间或者速度上不匹配的时候一种衡量相似度的方法。神马意思？举个例子，两份原本一样声音样本A、B都说了“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短距离的算法。
DTW 距离在保持信号先后顺序的限制下对时间信号进行“膨胀”或者“收缩”，找到最优的匹配，与编辑距离相似，这其实也是一个动态规划的问题:
 
实现代码:、

#!/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. 概率分布之间的距离

概率分布之间的距离度量是一个非常重要的课题，这个回头肯定能遇到，等到时做一个专题来总结好了，这里不再叙述。