[转]机器学习中距离和相似性度量分类体系

骑猪看日落 2022-07-03 13:25 833阅读 0赞

[距离度量分类体系][Link 1]

本篇文章并不打算描述所有这些类别，要具体阐述它们的细节和意义实在有点困难。这个大纲的目的，第一：提供一个貌似详细的距离度量的分类体系，列出相关的关键字。 第二：就像一个词典一样供参考和查阅，如果需要了解具体的细节，可以参考wiki或者具体文献。

大纲：   
1. 相似性和不相似性的定义   
2. 预备概念   
3. 距离度量   
    3.1  Numerical Data   
          3.1.1 欧拉距离(Euclidean Distance)   
          3.1.2 曼哈顿距离(Manhattan Distance)   
          3.1.3.最大距离(Maximum Distance)   
          3.1.4 明考夫斯基距离(MinKowski Distance)   
          3.1.5 马式距离（Mahalanobis Distance）   
          3.1.6 平均距离（Average Distance)   
          3.1.7 其他距离：Chord Distance，Geodesic distance,…..   
    3.2 Categorical Data   
         3.2.1. 简单匹配距离（Simple matching Distance)   
         3.2.2  其他匹配距离   
    3.3. Binary Data   
         3.3.1 Jaccard, Dice, Pearson, Yule, Russel-Rao, Sokal-Michener, Rogers-Tanimoto, Rogers-Tanimoto-a, Kulzinsky.   
    3.4  Mixed-type Data   
    3.5  Time Series Data   
    3.7  Other   
          3.7.1 Based on Longest Common Subsequence   
          3.7.2 Based on Probability Models   
          3.7.3 Based on Landmark Model   
          3.7.4 Based on Link Model   
    3.8 概率变量的相似性   
        3.8.1 Pearson 协方差   
        3.8.2 卡方统计（Chi-square Statistic)   
        3.8.3 基于最优预测( Optimal Class Prediction)   
        3.8.4 基于组的距离度量（Group-based Distance）

定义：   
一直误解相似（similarity）度量和不相似（dissimilarity）度量，**相似性度量**在以前的一篇中已经描述过了，通常情况下**不相似度量**满足下面的三条性质：

1） 0<= s(x,y) <=1   
2)   s(x,x) = 1   
3)   s(x,y) = s(y,x)

当然，还有更多的相似度量和不相似度量方法（@see  representation of similarity matrices by trees）

预备概念：   
1. Proximity Matrix   
    给定数据集合D=\{x1,x2,x3,…,xn\}   
    Mdis(D) = (dij)   dij = d(xi, xj)    
    Msim(D) = (sij)   sij = s(xi, xj)

2. 离差矩阵[Scatter Matrix][]

![a478ea0c50c7b5d7cdedab8f6c26e319][]

[![a478ea0c50c7b5d7cdedab8f6c26e319][a478ea0c50c7b5d7cdedab8f6c26e319 1]][a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 1]或者 [![a478ea0c50c7b5d7cdedab8f6c26e319][a478ea0c50c7b5d7cdedab8f6c26e319 2]][a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 2]Cn是中心矩阵 [Centering Matrix][]:

[![a478ea0c50c7b5d7cdedab8f6c26e319][a478ea0c50c7b5d7cdedab8f6c26e319 3]][a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 3]  
3. 协方差矩阵[Covariance Matrix][]:

[![a478ea0c50c7b5d7cdedab8f6c26e319][a478ea0c50c7b5d7cdedab8f6c26e319 4]][a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 4]

来源：http://blog.csdn.net/beta2/article/details/5714733

# [距离和相似性度量][Link 2]    #

相似性度量或者距离函数对于像聚类，邻域搜索这样的[算法][Link 3]是非常重要的。前面也提到，网页去重复也是相似性应用的一个例子。然而，如何定义个合适的相似或者距离函数，完全依赖于手头的任务是什么。一般而言，定义一个距离函数d(x,y),需要满足以下几个准则：

1.  d(x,x) = 0 ;//到自己的距离为0   
2.  d(x,y)>=0 // 距离要非负   
3.  对称性，d(x,y) = d(y,x) //如果A到B距离是a，那么B到A的距离也应该是a   
4.  三角形法则(两个之和大于第三边） d(x,k)+ d(k,y) >= d(x,y)

满足这4个条件的距离函数很多，一般有几类是比较常见的，通常来自比较直观的形象，如平面的一个两点的直线距离。下面讨论应用比较广泛的几类距离或相似性度量函数，欧拉距离，余弦函数cosine，Pearson函数，Jaccard index，edit distance。如果一个对象d(如：一篇文档）表示成一个n维的向量（d1,d2,….,dn),每一个维度都为对象的一个特征，那么这些度量函数极容易得到应用。

**1.范数和欧拉距离 **  
欧拉距离，来自于欧式几何（就是我们小学就开始接触的几何学），在数学上也可以成为范数。如果一个对象对应于空间的一个点，每一个维度就是空间的一个维度。特殊情况，如果n=1，那么，小学我们就学过，直线上两个点的距离是|x1-x2|。推广到高纬情况，一个很自然的想法是，把每一个维度的距离加起来不就可以呢。这就形成了传说中的一范数：

![= /sum\_\{i=1\}^n /left| x\_i - y\_i /right|][_sum_i_1_n _left_ x_i - y_i _right]

看，是不是很简单。有一范数就有二范数，三范数。。。无穷范数。其实，二范数来的更加直观，我们都知道二维空间，三维空间的两点的距离公式。他就是二范数，在二维三维上的形式了。

![= /left( /sum\_\{i=1\}^n /left| x\_i - y\_i /right|^2 /right)^\{1/2\}][_left_ _sum_i_1_n _left_ x_i - y_i _right_2 _right_1_2]

好了，一鼓作气,p范数(p-norm)

![= /left( /sum\_\{i=1\}^n /left| x\_i - y\_i /right|^p /right)^\{1/p\}][_left_ _sum_i_1_n _left_ x_i - y_i _right_p _right_1_p]   
无穷范数：   
![= /lim\_\{p /to /infty\} /left( /sum\_\{i=1\}^n /left| x\_i - y\_i /right|^p /right)^\{1/p\}][_lim_p _to _infty_ _left_ _sum_i_1_n _left_ x_i - y_i _right_p _right_1_p]![= /max /left(|x\_1 - y\_1|,  |x\_2 - y\_2|,  /ldots, |x\_n - y\_n| /right).][_max _left_x_1 - y_1_ _x_2 - y_2_ _ldots_ _x_n - y_n_ _right_.]

空间两点的距离公式（2-范数），是最常用的距离公式，他就是传说中的**欧拉距离**。多简单。

**2. cosine similarity **  
cosine similarity是备受恩宠啊，在学向量几何的时候，应该接触过这个神奇的公式

![/text\{similarity\} = /cos(/theta) = \{A /cdot B /over /|A/| /|B/|\}.][text_similarity_ _ _cos_theta_ _ _A _cdot B _over _A_ _B_.]

分子是两个向量的点积，||A||是向量的长度，这个公式神奇的地方是，随着角度的变化的，函数是从-1，1变化的。向量夹角的余弦就是两个向量的相似度。cosine similarity 说，如果两个向量的夹角定了，那么无论一个向量伸长多少倍，他们的相似性都是不变的。所以，应用cosine 相似性之前，要把对象的每一个维度归一化。在[搜索引擎][Link 4]技术中，cosine 相似性在计算查询和文档的相似性的时得到了很好的应用。对查询语句而言（如：“明天天气如何”），它的每一个维度是对应词的tf-idf.

cosine similarity的一个扩展是，Tonimoto系数：

![T(A,B) = \{A /cdot B /over /|A/|^2 +/|B/|^2 - A /cdot B\}.][T_A_B_ _ _A _cdot B _over _A_2 _B_2 - A _cdot B_.]

其实也没什么大不了。T（A,B）的分母是大于等于 cos similarity的分母，但且仅仅但 A,B长度一样是才相等。这就意味着，Tonimoto系数考虑了两个向量的长度差异，长度差异越大相似性约小。

**3. Jacard index**

Jacard 相似性直观的概念来自，两个集合有多相似，显然，Jacard最好是应用在离散的变量几何上。先看公式（不要头晕）

![J(A,B) = \{\{|A /cap B|\}/over\{|A /cup B|\}\}.][J_A_B_ _ _A _cap B_over_A _cup B_.]

分子是集合交集，分母是集合并集，画个图，马上就明白咋回事了。

和Jacard index 相似的一个公式是Dice‘ coefficient, 它也很直观，

![s = /frac\{2 | X /cap Y |\}\{| X | + | Y |\}][s _ _frac_2 _ X _cap Y _ X _ _ _ Y]

**4. Pearson correlation coefficient**

学过概率论的人都知道，有均值，反差，还有相关系数，相关系数就是就是描述两组变量是否线性相关的那个东西。相关系数的优点是，它跟变量的长度无关，这个都点像cosine相似性。有一个应用是，比如一个商品推荐系统，要给用户A推荐相应的产品，首先要通过对商品的打分，找到与A相似k个用户。但是有些人，可能天生喜欢打高分，有些人偏向于打低分，为了消除这个问题 相关系数是一个很好的度量方法。列公式，

![/rho\_\{X,Y\}=\{/mathrm\{cov\}(X,Y) /over /sigma\_X /sigma\_Y\} =\{E\[(X-/mu\_X)(Y-/mu\_Y)\] /over /sigma\_X/sigma\_Y\},][rho_X_Y_mathrm_cov_X_Y_ _over _sigma_X _sigma_Y_ _E_X-_mu_X_Y-_mu_Y_ _over _sigma_X_sigma_Y]

这个公式貌似和cosine 是有点关系的。至于如何关联，我就不讨论了。参看[correlation][]

**5. 编辑距离或者Levenshtein distance**

编辑距离说的两个字符串的相似程度。串A通过删除，增加，和修改变成串B的可以度量函数（一般是是通过多少步能将A变成B 也可以对每一个编辑步骤加权）wikipedia上有非常好的描述，这里就不再赘述。[Levenshtein Distance][].  与之相关的字符串相似性方法还有[Jaro-Winkler distance][]。

**6 SimRank 相似**

SimRank来自图论，说两个变量相似，因为他们链接了同一个或相似的节点。这个算法需要需要重点讨论。下次在说。

来源：http://blog.csdn.net/beta2/article/details/5045020

# 机器学习中的相似性度量 #

在做分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement)，这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。

本文的目的就是对常用的相似性度量作一个总结。

本文目录：

1. 欧氏距离

2. 曼哈顿距离

3. 切比雪夫距离

4. 闵可夫斯基距离

5. 标准化欧氏距离

6. 马氏距离

7. 夹角余弦

8. 汉明距离

9. 杰卡德距离 & 杰卡德相似系数

10. 相关系数 & 相关距离

11. 信息熵

**1. 欧氏距离(Euclidean Distance)**

欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。

(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

![2011030823203337.png][]

(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

![2011030823204453.png][]

(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

![2011030823205483.png][]

也可以用表示成向量运算的形式：

![2011030823211360.png][]

(4)Matlab计算欧氏距离

Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵，则pdist(X)将X矩阵M行的每一行作为一个N维向量，然后计算这M个向量两两间的距离。

例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离

X = \[0 0 ; 1 0 ; 0 2\]

D = pdist(X,'euclidean')

结果：

D =1.0000    2.0000    2.2361

**2. 曼哈顿距离(Manhattan Distance)**

从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源， 曼哈顿距离也称为**城市街区距离(City Block distance)**。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离

![2011030823213652.png][]

(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离

![2011030823231354.png][]

(3) Matlab计算曼哈顿距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离

X = \[0 0 ; 1 0 ; 0 2\]

D = pdist(X, 'cityblock')

结果：

D = 1     2     3

**3. 切比雪夫距离 ( Chebyshev Distance )**

国际象棋玩过么？国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走试试。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离

![2011030823234117.png][]

(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离

![2011030823235870.png][]

这个公式的另一种等价形式是

![2011030823242560.png][]

看不出两个公式是等价的？提示一下：试试用放缩法和夹逼法则来证明。

(3)Matlab计算切比雪夫距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的切比雪夫距离

X = \[0 0 ; 1 0 ; 0 2\]

D = pdist(X, 'chebychev')

结果：

D = 1     2     2

**4. 闵可夫斯基距离(Minkowski Distance)**

闵氏距离不是一种距离，而是一组距离的定义。

(1) 闵氏距离的定义

两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

![2011030823244080.png][]

其中p是一个变参数。

当p=1时，就是曼哈顿距离

当p=2时，就是欧氏距离

当p→∞时，就是切比雪夫距离

根据变参数的不同，闵氏距离可以表示一类的距离。

(2)闵氏距离的缺点

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

举个例子：二维样本(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。

简单说来，闵氏距离的缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。

(3)Matlab计算闵氏距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的闵氏距离（以变参数为2的欧氏距离为例）

X = \[0 0 ; 1 0 ; 0 2\]

D = pdist(X,'minkowski',2)

结果：

D = 1.0000    2.0000    2.2361

**5. 标准化欧氏距离 (Standardized Euclidean distance )**

(1)标准欧氏距离的定义

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为：

而且标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)用公式描述就是：

![2011030823264688.png][]

标准化后的值 =  ( 标准化前的值  － 分量的均值 ) /分量的标准差

经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

![2011030823272054.png][]

如果将方差的倒数看成是一个权重，这个公式可以看成是一种**加权欧氏距离(Weighted Euclidean distance)**。

(2)Matlab计算标准化欧氏距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的标准化欧氏距离 (假设两个分量的标准差分别为0.5和1)

X = \[0 0 ; 1 0 ; 0 2\]

D = pdist(X, 'seuclidean',\[0.5,1\])

结果：

D = 2.0000    2.0000    2.8284

**6. 马氏距离(Mahalanobis Distance)**

(1)马氏距离定义

有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到u的马氏距离表示为：

**![2011030823274286.png][]**

而其中向量Xi与Xj之间的马氏距离定义为：

![2011030823280193.png][]

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

![2011030823281650.png][]

也就是欧氏距离了。

若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

(2)马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。

(3) Matlab计算(1 2)，( 1 3)，( 2 2)，( 3 1)两两之间的马氏距离

X = \[1 2; 1 3; 2 2; 3 1\]

Y = pdist(X,'mahalanobis')

结果：

Y = 2.3452    2.0000    2.3452    1.2247    2.4495    1.2247

**7. 夹角余弦(Cosine)**

有没有搞错，又不是学几何，怎么扯到夹角余弦了？各位看官稍安勿躁。几何中夹角余弦可用来衡量两个向量方向的差异，[机器学习][Link 5]中借用这一概念来衡量样本向量之间的差异。

(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：

![2011030823283429.png][]

(2) 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦

类似的，对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

![2011030823293892.png][]

即：

![2011030823294588.png][]

夹角余弦取值范围为\[-1,1\]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

夹角余弦的具体应用可以参阅参考文献\[1\]。

(3)Matlab计算夹角余弦

例子：计算(1,0)、( 1,1.732)、( -1,0)两两间的夹角余弦

X = \[1 0 ; 1 1.732 ; -1 0\]

D = 1- pdist(X, 'cosine')  % Matlab中的pdist(X, 'cosine')得到的是1减夹角余弦的值

结果：

D = 0.5000   -1.0000   -0.5000

**8. 汉明距离(Hamming Distance)**

(1)汉明距离的定义

两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

(2)Matlab计算汉明距离

Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比。

例子：计算向量(0,0)、(1,0)、(0,2)两两间的汉明距离

X = \[0 0 ; 1 0 ; 0 2\];

D = PDIST(X, 'hamming')

结果：

D = 0.5000    0.5000    1.0000

**9. 杰卡德相似系数(Jaccard similarity coefficient)**

(1) 杰卡德相似系数

两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。

![2011030823303566.png][]

杰卡德相似系数是衡量两个集合的相似度一种指标。

(2) 杰卡德距离

与杰卡德相似系数相反的概念是**杰卡德距离(**Jaccard distance)。杰卡德距离可用如下公式表示：

![2011030823310119.png][]

杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

(3) 杰卡德相似系数与杰卡德距离的应用

可将杰卡德相似系数用在衡量样本的相似度上。

样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。

p ：样本A与B都是1的维度的个数

q ：样本A是1，样本B是0的维度的个数

r ：样本A是0，样本B是1的维度的个数

s ：样本A与B都是0的维度的个数

那么样本A与B的杰卡德相似系数可以表示为：

这里p+q+r可理解为A与B的并集的元素个数，而p是A与B的交集的元素个数。

而样本A与B的杰卡德距离表示为：

![2011030823313638.png][]

(4)Matlab 计算杰卡德距离

Matlab的pdist函数定义的杰卡德距离跟我这里的定义有一些差别，Matlab中将其定义为不同的维度的个数占“非全零维度”的比例。

例子：计算(1,1,0)、(1,-1,0)、(-1,1,0)两两之间的杰卡德距离

X = \[1 1 0; 1 -1 0; -1 1 0\]

D = pdist( X , 'jaccard')

结果

D = 0.5000    0.5000    1.0000

**10. 相关系数 ( Correlation coefficient )与相关距离(Correlation distance)**

(1) 相关系数的定义

![2011030823322444.png][]

相关系数是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是\[-1,1\]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。

(2)相关距离的定义

![2011030823323390.png][]

(3)Matlab计算(1, 2 ,3 ,4 )与( 3 ,8 ,7 ,6 )之间的相关系数与相关距离

X = \[1 2 3 4 ; 3 8 7 6\]

C = corrcoef( X' )   %将返回相关系数矩阵

D = pdist( X , 'correlation')

结果：

C = 1.0000    0.4781

0.4781    1.0000

D = 0.5219

其中0.4781就是相关系数，0.5219是相关距离。

**11. 信息熵(**Information Entropy)

信息熵并不属于一种相似性度量。信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均)，信息熵就越大。分布越有序（或者说分布越集中），信息熵就越小。

计算给定的样本集X的信息熵的公式：

![2011030823325084.png][]

参数的含义：

n：样本集X的分类数

pi：X中第i类元素出现的概率

信息熵越大表明样本集S分类越分散，信息熵越小则表明样本集X分类越集中。。当S中n个分类出现的概率一样大时（都是1/n），信息熵取最大值log2(n)。当X只有一个分类时，信息熵取最小值0

**参考资料：**

\[1\]吴军. 数学之美 系列 12 – 余弦定理和新闻的分类.

[http://www.google.com.hk/ggblog/googlechinablog/2006/07/12\_4010.html][http_www.google.com.hk_ggblog_googlechinablog_2006_07_12_4010.html]

\[2\] Wikipedia. Jaccard index.

[http://en.wikipedia.org/wiki/Jaccard\_index][http_en.wikipedia.org_wiki_Jaccard_index]

\[3\] Wikipedia. Hamming distance

[http://en.wikipedia.org/wiki/Hamming\_distance][http_en.wikipedia.org_wiki_Hamming_distance]

\[4\] 求马氏距离（Mahalanobis distance ）matlab版

[http://junjun0595.blog.163.com/blog/static/969561420100633351210/][http_junjun0595.blog.163.com_blog_static_969561420100633351210]

\[5\] Pearson product-moment correlation coefficient

[http://en.wikipedia.org/wiki/Pearson\_product-moment\_correlation\_coefficient][http_en.wikipedia.org_wiki_Pearson_product-moment_correlation_coefficient]

转载自：[http://goo.gl/zRXbt][http_goo.gl_zRXbt]

此条目由 [lixiang][] 发表在 [Machine Learning][] 分类目录，并贴了 [Chebyshev Distance][]、[Cosine][]、[Euclidean Distance][]、[Hamming Distance][]、[Information Entropy][]、[Jaccard Distance][]、[Mahalanobis Distance][]、[Manhattan Distance][]、[Minkowski Distance][] 标签。将[固定链接][Link 6]加入收藏夹。

**欧氏距离与余弦相似度**

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

![distance and similarity][]

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标（即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）。

上面都是对距离度量和相似度度量的一些整理和汇总，在现实的使用中选择合适的距离度量或相似度度量可以完成很多的数据分析和数据挖掘的建模，后续会有相关的介绍

补充：编辑距离；K-L divergence

12 hausdorff距离    微分动力系统原理这本书里有介绍    Hausdorff距离是描述两组点集之间相似程度的一种量度，它是两个点集之间距离的一种定义形式：假设有两组集合A=\{a1,…,ap\},B=\{b1,…,bq\},则这两个点集合之间的Hausdorff距离定义为H(A,B)=max(h(A,B),h(B,A)) (1)    其中,     h(A,B)=max（a∈A）min（b∈B）‖a-b‖ (2)    h(B,A)=max（b∈B）min（a∈A）‖b-a‖ (3)     ‖·‖ 是点集A和B点集间的距离范式(如:L2或Euclidean距离).     这里,式(1)称为双向Hausdorff距离,是Hausdorff距离的最基本形式;式(2)中的h(A,B)和h(B,A)分别称为从A集合到B集合和从B集合到A集合的单向Hausdorff距离.即h(A,B)实际上首先对点集A中的每个点ai到距离此点ai最近的B集合中点bj之间的距离‖ai-bj‖进行排序,然后取该距离中的最大值作为h(A,B)的值.h(B,A)同理可得.     由式(1)知,双向Hausdorff距离H(A,B)是单向距离h(A,B)和h(B,A)两者中的较大者,它度量了两个点集间的最大不匹配程度.

13 Bhattacharyya

13 Bhattacharyya距离  在统计学中，Bhattacharyya距离（以下称巴氏距离）测量的是两个离散或连续概率分布的相似性。计算方式和Bhattacharyya系数关系很密切。两种计算方式都以A. Bhattacharyya名字命名，Bhattacharyya是一位30年代在印度统计研究所工作的统计学家。巴氏系数可用来对两组样本的相关性进行测量。这一方法常用来作分类器算法。\[1\]  数学定义  -离散概率分布    对于在X数域上的两个离散概率分布p和q，巴氏距离定义为\[2\]：   DB(p,q) = -ln(BC(p,q))     其中    BC(p,q) = ∑√p(x)q(x)     BC被称作Bhattacharyya系数（巴氏系数）   0≤BC≤1q且0≤DB≤∞ -连续概率分布    在连续情形中，Bhat           其中           BC(p,q) = ∑√p(x)q(x)            BC  被称作  Bhattacharyya  系数（巴氏系数）           0≤BC≤1q  且  0≤DB≤∞     -  连续  概率分布           在  连续  情形中，  Bhattacharyya  系数如下定  义  ：           BC(p,q) = ∫√p(x)q(x)dx            0≤BC≤1q  且  0≤DB≤∞            两  种  情形中，巴氏距离  DB  均不  满  足三角不等式

Bhattacharyya  系数           Bhattacharyya  系数  \[3\]  （  Bhattacharyya Coefficient,   巴氏系数）是  对  两个  统

### [马氏距离的几张截图][Link 7] ###

2011-04-14 21:31  613人阅读  [评论][Link 8](0)  [收藏][Link 7]  [举报][Link 9]

[2010][]

这几张图太形象了，只好收藏了。来自：http://xgli0910.blog.163.com/blog/static/46962168201021932741868/

![0_1302787568i2cc.gif][]

![0_13027875542222.gif][]

![0_130278756040RO.gif][]

![0_1302787572F7S9.gif][]

![0_1302787699JdA5.gif][]

![0_130278770610b0.gif][]

![0_130278771068U6.gif][]

mahalanobis距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化，形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。  
换句话说，主成分分析就是把椭球分布的样本改变到另一个空间里，使其成为球状分布。而mahalanobis距离就是在样本呈球状分布的空间里面所求得的Euclidean距离。  
当然，上面的解释只是对椭球分布而言，对一般分布，只能消除分布的二阶相关性，而不能消除高阶相关性。

# [漫谈：机器学习中距离和相似性度量方法][Link 10] #

在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个距离函数 d(x,y), 需要满足下面几个准则：

1) d(x,x) = 0               // 到自己的距离为0  
2) d(x,y) >= 0              // 距离非负  
3) d(x,y) = d(y,x)             // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a  
4) d(x,k)+ d(k,y) >= d(x,y)    // 三角形法则: (两边之和大于第三边)

这篇博客主要介绍机器学习和数据挖掘中一些常见的距离公式，包括：

闵可夫斯基距离  
欧几里得距离  
曼哈顿距离  
切比雪夫距离  
马氏距离  
余弦相似度  
皮尔逊相关系数  
汉明距离  
杰卡德相似系数  
编辑距离  
DTW 距离  
KL 散度

1. 闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：![大数据][001.png]

那么，闵可夫斯基距离定义为：![大数据][0021.png]

该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：![大数据][0031.png]绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。  
当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：![大数据][0041.png]

我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢？

![大数据][0041.png]注意，当 p < 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p < 1, (0,0) 到 (1,1) 的距离等于 (1+1)^\{1/p\} > 2, 而 (0,1) 到这两个点的距离都是 1。  
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：![大数据][006.gif]

![大数据][1-007-600x60.png]可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。

2. 马氏距离

考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：![大数据][2-001.png]马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。假设样本点（列向量）之间的协方差对称矩阵是[![大数据][2-007.gif]][2-007.gif]

通过 Cholesky Decomposition（实际上是对称矩阵 LU 分解的一种特殊形式，可参考之前的[博客][Link 11]）可以转化为下三角矩阵和上三角矩阵的乘积：![大数据][2-002.gif]消除不同维度之间的相关性和尺度不同，只需要对样本点 x 做如下处理：![大数据][2-003.gif]处理之后的欧几里得距离就是原样本的马氏距离：为了书写方便，这里求马氏距离的平方）：![大数据][2-004.png]下图蓝色表示原样本点的分布，两颗红星坐标分别是（3, 3），（2, -2）:![大数据][2-005-569x429.png]由于 x， y 方向的尺度不同，不能单纯用欧几里得的方法测量它们到原点的距离。并且，由于 x 和 y 是相关的（大致可以看出斜向右上），也不能简单地在 x 和 y 方向上分别减去均值，除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换，即求马氏距离（可以看到，右边的红星离原点较近）：![大数据][2-006-569x429.png]将上面两个图的绘制代码和求马氏距离的代码贴在这里，以备以后查阅：

> \# -\*- 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. 向量内积

向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相似性测量手段。向量内积的定义如下：[![大数据][3-001.gif]][3-001.gif]直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理中 DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT 是正交标准基，也可以看做投影）。向量和信号都是离散值，如果是连续的函数值，比如求区间\[-1, 1\] 两个函数之间的相似度，同样也可以得到（系数）组分，这种方法可以应用于多项式逼近连续函数，也可以用到连续函数逼近离散样本点（最小二乘问题，OLS coefficients）中，扯得有点远了- -!。  
向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相似度（Cosine similarity）：![大数据][3-002.gif]余弦相似度与向量的幅值无关，只与向量的方向相关，在文档相似度（TF-IDF）和图片相似性（[histogram][]）计算上都有它的身影。需要注意一点的是，余弦相似度受到向量的平移影响，上式如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？这就是下面要说的皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数:[  
][Link 12]![大数据][3-005-600x54.png]皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。不过，一般我们在谈论相关系数的时候，将 x 与 y 对应位置的两个数值看作一个样本点，皮尔逊系数用来表示这些样本点分布的相关性。![大数据][Link 12]由于皮尔逊系数具有的良好性质，在各个领域都应用广泛，例如，在推荐系统根据为某一用户查找喜好相似的用户,进而[提供推荐][Link 13]，优点是可以不受每个用户评分标准不同和观看影片数量不一样的影响。

4. 分类数据点间的距离

汉明距离（Hamming distance）是指，两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。举个维基百科上的例子：![大数据][4-001.png]还可以用简单的匹配系数来表示两点之间的相似度——匹配字符数/总字符数。

在一些情况下，某些特定的值相等并不能代表什么。举个例子，用 1 表示用户看过该电影，用 0 表示用户没有看过，那么用户看电影的的信息就可用 0,1 表示成一个序列。考虑到电影基数非常庞大，用户看过的电影只占其中非常小的一部分，如果两个用户都没有看过某一部电影（两个都是 0），并不能说明两者相似。反而言之，如果两个用户都看过某一部电影（序列中都是 1），则说明用户有很大的相似度。在这个例子中，序列中等于 1 所占的权重应该远远大于 0 的权重，这就引出下面要说的杰卡德相似系数（Jaccard similarity）。

在上面的例子中，用 M11 表示两个用户都看过的电影数目，M10 表示用户 A 看过，用户 B 没看过的电影数目，M01 表示用户 A 没看过，用户 B 看过的电影数目，M00 表示两个用户都没有看过的电影数目。Jaccard 相似性系数可以表示为：![大数据][4-002.png]Jaccard similarity 还可以用集合的公式来表达，这里就不多说了。

如果分类数值点是用树形结构来表示的，它们的相似性可以用相同路径的长度来表示，比如，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的距离小于到 “/product/luxury/handbags” 的距离，以为前者相同父节点路径更长。

5. 序列之间的距离

上一小节我们知道，汉明距离可以度量两个长度相同的字符串之间的相似度，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离（Edit distance, Levenshtein distance）等算法。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离求的是最少编辑次数，这是一个动态规划的问题，有兴趣的同学可以自己研究研究。

时间序列是序列之间距离的另外一个例子。DTW 距离（Dynamic Time Warp）是序列信号在时间或者速度上不匹配的时候一种衡量相似度的方法。神马意思？举个例子，两份原本一样声音样本A、B都说了“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短距离的算法。

DTW 距离在保持信号先后顺序的限制下对时间信号进行“膨胀”或者“收缩”，找到最优的匹配，与编辑距离相似，这其实也是一个动态规划的问题:![大数据][5-001.png]  
实现代码（转自 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. 概率分布之间的距离

前面我们谈论的都是两个数值点之间的距离，实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离，进而判断出它们是否出自同一个 population，常见的方法有卡方检验（Chi-Square）和 KL 散度（ KL-Divergence），下面说一说 KL 散度吧。

先从信息熵说起，假设一篇文章的标题叫做“黑洞到底吃什么”，包含词语分别是 \{黑洞, 到底, 吃什么\}, 我们现在要根据一个词语推测这篇文章的类别。哪个词语给予我们的信息最多？很容易就知道是“黑洞”，因为“黑洞”这个词语在所有的文档中出现的概率太低啦，一旦出现，就表明这篇文章很可能是在讲科普知识。而其他两个词语“到底”和“吃什么”出现的概率很高，给予我们的信息反而越少。如何用一个函数 h(x) 表示词语给予的信息量呢？第一，肯定是与 p(x) 相关，并且是负相关。第二，假设 x 和 y 是独立的（黑洞和宇宙不相互独立，谈到黑洞必然会说宇宙）,即 p(x,y) = p(x)p(y), 那么获得的信息也是叠加的，即 h(x, y) = h(x) + h(y)。满足这两个条件的函数肯定是负对数形式：![大数据][6-001.gif]

对假设一个发送者要将随机变量 X 产生的一长串随机值传送给接收者， 接受者获得的平均信息量就是求它的数学期望：![大数据][6-002.gif]![大数据][6-004.gif]这就是熵的概念。另外一个重要特点是，熵的大小与字符平均最短编码长度是一样的（shannon）。设有一个未知的分布 p(x), 而 q(x) 是我们所获得的一个对 p(x) 的近似，按照 q(x) 对该随机变量的各个值进行编码，平均长度比按照真实分布的 p(x) 进行编码要额外长一些，多出来的长度这就是 KL 散度（之所以不说距离，是因为不满足对称性和三角形法则），即：![大数据][6-003-600x132.png]KL 散度又叫相对熵（relative entropy）。了解机器学习的童鞋应该都知道，在 Softmax 回归（或者 Logistic 回归），最后的输出节点上的值表示这个样本分到该类的概率，这就是一个概率分布。对于一个带有标签的样本，我们期望的概率分布是：分到标签类的概率是 1， 其他类概率是 0。但是理想很丰满，现实很骨感，我们不可能得到完美的概率输出，能做的就是尽量减小总样本的 KL 散度之和（目标函数）。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。（PS：因为概率和为 1，一般的 logistic 二分类的图只画了一个输出节点，隐藏了另外一个）

待补充的方法：

卡方检验 Chi-Square

衡量 categorical attributes 相关性的 mutual information

Spearman’s rank coefficient

Earth Mover’s Distance

SimRank 迭代算法等。

参考资料：

[距离和相似性度量][Link 2]  
[Machine Learning: Measuring Similarity and Distance][Machine Learning_ Measuring Similarity and Distance]  
[What is Mahalanobis distance?][What is Mahalanobis distance]  
[Cosine similarity, Pearson correlation, and OLS coefficients][Cosine similarity_ Pearson correlation_ and OLS coefficients]  
[机器学习中的相似性度量][Link 14]  
[动态时间归整 | DTW | Dynamic Time Warping][_ DTW _ Dynamic Time Warping]

Via：来源 daniel-D

来源：http://www.36dsj.com/archives/24325

[  
][Link 15]

[Link 1]: http://blog.csdn.net/beta2/article/details/5714733
[Scatter Matrix]: http://en.wikipedia.org/wiki/Scatter_matrix
[a478ea0c50c7b5d7cdedab8f6c26e319]: /images/20220618/35712205c9ec4fffbcb3955cc2944986.png
[a478ea0c50c7b5d7cdedab8f6c26e319 1]: http://hi.csdn.net/attachment/201007/5/0_1278339831Xm29.gif
[a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 1]: http://hi.csdn.net/attachment/201007/5/0_1278339831B6sR.gif
[a478ea0c50c7b5d7cdedab8f6c26e319 2]: http://hi.csdn.net/attachment/201007/5/0_1278339831ass9.gif
[a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 2]: http://hi.csdn.net/attachment/201007/5/0_1278339831BrLa.gif
[Centering Matrix]: http://en.wikipedia.org/wiki/Centering_matrix
[a478ea0c50c7b5d7cdedab8f6c26e319 3]: http://hi.csdn.net/attachment/201007/5/0_1278339832iuit.gif
[a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 3]: /images/20220618/df7fa7def6c24202a660dcd0ba63639c.png
[Covariance Matrix]: http://en.wikipedia.org/wiki/Covariance_matrix
[a478ea0c50c7b5d7cdedab8f6c26e319 4]: http://hi.csdn.net/attachment/201007/5/0_12783398335N83.gif
[a478ea0c50c7b5d7cdedab8f6c26e319_a478ea0c50c7b5d7cdedab8f6c26e319 4]: /images/20220618/bcb64649f3854901a322764781b4eb2f.png
[Link 2]: http://blog.csdn.net/beta2/article/details/5045020
[Link 3]: http://lib.csdn.net/base/datastructure
[_sum_i_1_n _left_ x_i - y_i _right]: /images/20220618/d268df94c938424989bb4c9fe9d12125.png
[_left_ _sum_i_1_n _left_ x_i - y_i _right_2 _right_1_2]: /images/20220618/8e03e8ff4afc4d58bb66e7a1d90dfd4f.png
[_left_ _sum_i_1_n _left_ x_i - y_i _right_p _right_1_p]: /images/20220618/ee72112280fd47389f4630af5fc1acd7.png
[_lim_p _to _infty_ _left_ _sum_i_1_n _left_ x_i - y_i _right_p _right_1_p]: http://upload.wikimedia.org/math/b/9/2/b926733898053a87197717d6ae2778c3.png
[_max _left_x_1 - y_1_ _x_2 - y_2_ _ldots_ _x_n - y_n_ _right_.]: /images/20220618/f6c7a5da217744e18afd98cb554b21a0.png
[text_similarity_ _ _cos_theta_ _ _A _cdot B _over _A_ _B_.]: /images/20220618/5817792841b84dec9437a67aeedb6f5a.png
[Link 4]: http://lib.csdn.net/base/searchengine
[T_A_B_ _ _A _cdot B _over _A_2 _B_2 - A _cdot B_.]: /images/20220618/f4efb3835ddc431f876fb88fd1e21def.png
[J_A_B_ _ _A _cap B_over_A _cup B_.]: /images/20220618/80a070ec0a604a28b964924834a78ae0.png
[s _ _frac_2 _ X _cap Y _ X _ _ _ Y]: /images/20220618/819820eb20714b578b027ce82e78f7a7.png
[rho_X_Y_mathrm_cov_X_Y_ _over _sigma_X _sigma_Y_ _E_X-_mu_X_Y-_mu_Y_ _over _sigma_X_sigma_Y]: /images/20220618/7425aad586af4bd2b10265a9ae3c5a32.png
[correlation]: http://en.wikipedia.org/wiki/Pearson_correlation_coefficient
[Levenshtein Distance]: http://en.wikipedia.org/wiki/Levenshtein_distance
[Jaro-Winkler distance]: http://en.wikipedia.org/wiki/Jaro-Winkler_distance
[2011030823203337.png]: /images/20220618/17fe3f4d16c9484ca4d4edffc3fe6379.png
[2011030823204453.png]: /images/20220618/dbc0494d3e8a44bb8bfcc963973d8984.png
[2011030823205483.png]: /images/20220618/0be7db8abaf045cc83e5e771b80ccdd5.png
[2011030823211360.png]: /images/20220618/ff1c7e67cb2940a8a22409fb2549d145.png
[2011030823213652.png]: /images/20220618/0a3cddf4c37b44e2a86ef1a0edbad80a.png
[2011030823231354.png]: /images/20220618/d274e86786e0431fae8285935a97d7ec.png
[2011030823234117.png]: /images/20220618/915984943fb94f64ad84230e6ed8f1e7.png
[2011030823235870.png]: /images/20220618/0b4a2b996eec408bbeceffe8574bde6a.png
[2011030823242560.png]: /images/20220618/433dce5a085e43c38486836594288e34.png
[2011030823244080.png]: /images/20220618/4d4b68306c1f40849d7030dcb1c142f9.png
[2011030823264688.png]: /images/20220618/2e64d2ad70e546e2b27129c746800e4e.png
[2011030823272054.png]: /images/20220618/72b6c1cac633489589f0cc53a68f8902.png
[2011030823274286.png]: /images/20220618/ed941871a21842a289e1f9c7376b135c.png
[2011030823280193.png]: /images/20220618/6cac18b5bf524f1f98c412e591cd4fe5.png
[2011030823281650.png]: /images/20220618/85c0963f24f24b2eacb5f775c880712b.png
[Link 5]: http://lib.csdn.net/base/machinelearning
[2011030823283429.png]: /images/20220618/f986da8b03224e98b4d7640c6fc3ee88.png
[2011030823293892.png]: /images/20220618/4573b00a5f7d4df6a28bc5acfbdb9a8e.png
[2011030823294588.png]: /images/20220618/82365c67a80f4312855d1ef1c24953d6.png
[2011030823303566.png]: /images/20220618/f52c04c85fc0472abf587171e0c24771.png
[2011030823310119.png]: /images/20220618/0007b43a2ca24e09adf351ca4a3423a9.png
[2011030823313638.png]: /images/20220618/f001d2cbc49e41c1abb727b367739d7c.png
[2011030823322444.png]: /images/20220618/a2949e387f0347a78ad5ba806f8cb56d.png
[2011030823323390.png]: /images/20220618/1fc4be52e00045b3a2b266b109a4aaf7.png
[2011030823325084.png]: /images/20220618/e6ae85804af448098c8255924b6c20f2.png
[http_www.google.com.hk_ggblog_googlechinablog_2006_07_12_4010.html]: http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html
[http_en.wikipedia.org_wiki_Jaccard_index]: http://en.wikipedia.org/wiki/Jaccard_index
[http_en.wikipedia.org_wiki_Hamming_distance]: http://en.wikipedia.org/wiki/Hamming_distance
[http_junjun0595.blog.163.com_blog_static_969561420100633351210]: http://junjun0595.blog.163.com/blog/static/969561420100633351210/
[http_en.wikipedia.org_wiki_Pearson_product-moment_correlation_coefficient]: http://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
[http_goo.gl_zRXbt]: http://goo.gl/zRXbt
[lixiang]: http://www.leexiang.com/author/lixiang
[Machine Learning]: http://www.leexiang.com/category/ml
[Chebyshev Distance]: http://www.leexiang.com/tag/chebyshev-distance
[Cosine]: http://www.leexiang.com/tag/cosine
[Euclidean Distance]: http://www.leexiang.com/tag/euclidean-distance
[Hamming Distance]: http://www.leexiang.com/tag/hamming-distance
[Information Entropy]: http://www.leexiang.com/tag/information-entropy
[Jaccard Distance]: http://www.leexiang.com/tag/jaccard-distance
[Mahalanobis Distance]: http://www.leexiang.com/tag/mahalanobis-distance
[Manhattan Distance]: http://www.leexiang.com/tag/manhattan-distance
[Minkowski Distance]: http://www.leexiang.com/tag/minkowski-distance
[Link 6]: http://www.leexiang.com/similarity-measurement-of-machine-learning
[distance and similarity]: /images/20220618/1ae7dc48c24a48039dbfab55790701dd.png
[Link 7]: http://blog.csdn.net/luoleicn/article/details/6324266
[Link 8]: http://blog.csdn.net/luoleicn/article/details/6324266#comments
[Link 9]: http://blog.csdn.net/luoleicn/article/details/6324266#report
[2010]: http://blog.csdn.net/tag/details.html?tag=2010
[0_1302787568i2cc.gif]: /images/20220618/952de7e65c3f46b493c9a4dc30ba3827.png
[0_13027875542222.gif]: /images/20220618/ac0f25d75bf64160ba97a434b8f0c82b.png
[0_130278756040RO.gif]: /images/20220618/5da47752ed95409b96daf458bfafdfb4.png
[0_1302787572F7S9.gif]: /images/20220618/5b61daf207a64a659684802bc4e1b9b6.png
[0_1302787699JdA5.gif]: /images/20220618/834d8c3e80d345628899c0ae79644eb8.png
[0_130278770610b0.gif]: /images/20220618/63cacb0e5b084d3388caa478795e0936.png
[0_130278771068U6.gif]: /images/20220618/659e90b045a74164a7708f2b1102c3c1.png
[Link 10]: http://www.36dsj.com/archives/24325
[001.png]: http://www.36dsj.com/wp-content/uploads/2015/03/001.png
[0021.png]: http://www.36dsj.com/wp-content/uploads/2015/03/0021.png
[0031.png]: http://www.36dsj.com/wp-content/uploads/2015/03/0031.png
[0041.png]: http://www.36dsj.com/wp-content/uploads/2015/03/0041.png
[006.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/006.gif
[1-007-600x60.png]: http://www.36dsj.com/wp-content/uploads/2015/03/1-007-600x60.png
[2-001.png]: http://www.36dsj.com/wp-content/uploads/2015/03/2-001.png
[2-007.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/2-007.gif
[Link 11]: http://www.cnblogs.com/daniel-D/p/3204508.html
[2-002.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/2-002.gif
[2-003.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/2-003.gif
[2-004.png]: http://www.36dsj.com/wp-content/uploads/2015/03/2-004.png
[2-005-569x429.png]: http://www.36dsj.com/wp-content/uploads/2015/03/2-005-569x429.png
[2-006-569x429.png]: http://www.36dsj.com/wp-content/uploads/2015/03/2-006-569x429.png
[3-001.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/3-001.gif
[3-002.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/3-002.gif
[histogram]: http://www.ruanyifeng.com/blog/2013/03/similar_image_search_part_ii.html
[Link 12]: http://www.36dsj.com/wp-content/uploads/2015/03/3-004.png
[3-005-600x54.png]: http://www.36dsj.com/wp-content/uploads/2015/03/3-005-600x54.png
[Link 13]: /images/20220618/306f008eb4d14bb19cde73b6072ff5c0.png
[4-001.png]: http://www.36dsj.com/wp-content/uploads/2015/03/4-001.png
[4-002.png]: http://www.36dsj.com/wp-content/uploads/2015/03/4-002.png
[5-001.png]: http://www.36dsj.com/wp-content/uploads/2015/03/5-001.png
[6-001.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/6-001.gif
[6-002.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/6-002.gif
[6-004.gif]: http://www.36dsj.com/wp-content/uploads/2015/03/6-004.gif
[6-003-600x132.png]: http://www.36dsj.com/wp-content/uploads/2015/03/6-003-600x132.png
[Machine Learning_ Measuring Similarity and Distance]: http://architects.dzone.com/articles/machine-learning-measuring
[What is Mahalanobis distance]: http://blogs.sas.com/content/iml/2012/02/15/what-is-mahalanobis-distance/
[Cosine similarity_ Pearson correlation_ and OLS coefficients]: http://brenocon.com/blog/2012/03/cosine-similarity-pearson-correlation-and-ols-coefficients/
[Link 14]: http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html
[_ DTW _ Dynamic Time Warping]: http://blog.mckelv.in/articles/1453.html
[Link 15]: http://blog.csdn.net/beta2/article/details/5714733#