文档章节

机器学习——几种距离度量方法比较

牧师-Panda
 牧师-Panda
发布于 2016/11/14 18:02
字数 2769
阅读 33311
收藏 16

1. 欧氏距离(Euclidean Distance)

欧氏距离是最容易直观理解的距离度量方法,我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。

欧氏距离

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

欧氏距离2维

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

欧氏距离3维

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

欧氏距离n维

  • Matlab计算欧氏距离:

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

        X=[1 1;2 2;3 3;4 4];
        d=pdist(X,'euclidean')
        d=
          1.4142    2.8284    4.2426    1.4142    2.8284    1.4142

2. 曼哈顿距离(Manhattan Distance)

顾名思义,在曼哈顿街区要从一个十字路口开车到另一个十字路口,驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。

曼哈顿距离

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

曼哈顿距离2维

  • n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的曼哈顿距离:

曼哈顿距离n维

  • Matlab计算曼哈顿距离:

      X=[1 1;2 2;3 3;4 4];
      d=pdist(X,'cityblock')
      d=
        2     4     6     2     4     2
    

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

国际象棋中,国王可以直行、横行、斜行,所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?这个距离就叫切比雪夫距离。

切比雪夫距离_国际象棋

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

切比雪夫距离2维

  • n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的切比雪夫距离:

切比雪夫距离n维

  • Matlab计算切比雪夫距离:

      X=[1 1;2 2;3 3;4 4];
      d=pdist(X,'chebychev')
      d=
        1     2     3     1     2     1
    

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

闵氏距离不是一种距离,而是一组距离的定义,是对多个距离度量公式的概括性的表述。

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

闵式距离n维

其中p是一个变参数:

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

当p=2时,就是欧氏距离;

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

因此,根据变参数的不同,闵氏距离可以表示某一类/种的距离。

  • 闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
  • e.g. 二维样本(身高[单位:cm],体重[单位:kg]),现有三个样本:a(180,50),b(190,50),c(180,60)。那么a与b的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。
  • 闵氏距离的缺点:
  • (1)将各个分量的量纲(scale),也就是“单位”相同的看待了;
  • (2)未考虑各个分量的分布(期望,方差等)可能是不同的。

  • Matlab计算闵氏距离(以p=2的欧氏距离为例):

      X=[1 1;2 2;3 3;4 4];
      d=pdist(X,'minkowski',2)
      d=
        1.4142    2.8284    4.2426    1.4142    2.8284    1.4142
    

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

 定义: 标准化欧氏距离是针对欧氏距离的缺点而作的一种改进。标准欧氏距离的思路:既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。假设样本集X的均值(mean)为m,标准差(standard deviation)为s,X的“标准化变量”表示为:

标准化欧氏距离

  • 标准化欧氏距离公式:

标准化欧氏距离公式

如果将方差的倒数看成一个权重,也可称之为加权欧氏距离(Weighted Euclidean distance)。

  • Matlab计算标准化欧氏距离(假设两个分量的标准差分别为0.5和1):

      X=[1 1;2 2;3 3;4 4];
      d=pdist(X,'seuclidean',[0.5,1])
      d=
        2.2361    4.4721    6.7082    2.2361    4.4721    2.2361
    

6. 马氏距离(Mahalanobis Distance)

 马氏距离的引出:

马氏距离来源

上图有两个正态分布的总体,它们的均值分别为a和b,但方差不一样,则图中的A点离哪个总体更近?或者说A有更大的概率属于谁?显然,A离左边的更近,A属于左边总体的概率更大,尽管A与a的欧式距离远一些。这就是马氏距离的直观解释。

  • 概念:马氏距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化,形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。

马氏距离概念

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

马氏距离公式

向量Xi与Xj之间的马氏距离定义为:

马氏距离公式

若协方差矩阵是单位矩阵(各个样本向量之间独立同分布),则Xi与Xj之间的马氏距离等于他们的欧氏距离:

马氏距离公式

若协方差矩阵是对角矩阵,则就是标准化欧氏距离。

  • 欧式距离&马氏距离:

欧式距离&马氏距离

欧式距离&马氏距离

  • 马氏距离的特点:
  • 量纲无关,排除变量之间的相关性的干扰;
  • 马氏距离的计算是建立在总体样本的基础上的,如果拿同样的两个样本,放入两个不同的总体中,最后计算得出的两个样本间的马氏距离通常是不相同的,除非这两个总体的协方差矩阵碰巧相同;
  • 计算马氏距离过程中,要求总体样本数大于样本的维数,否则得到的总体样本协方差矩阵逆矩阵不存在,这种情况下,用欧式距离计算即可。
  • Matlab计算马氏距离:

      X=[1 2;1 3;2 2;3 1];
      d=pdist(X,'mahal')
      d=
        2.3452    2.0000    2.3452    1.2247    2.4495    1.2247
    

7. 余弦距离(Cosine Distance)

几何中,夹角余弦可用来衡量两个向量方向的差异;机器学习中,借用这一概念来衡量样本向量之间的差异。

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

余弦距离

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

余弦距离

即:

余弦距离

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

  • Matlab计算夹角余弦(Matlab中的pdist(X, ‘cosine’)得到的是1减夹角余弦的值):

      X=[1 1;1 2;2 5;1 -4];
      d=1-pdist(X,'cosine')
      d=
        0.9487    0.9191   -0.5145    0.9965   -0.7593   -0.8107
    

8. 汉明距离(Hamming Distance)

汉明距离

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

      The Hamming distance between "1011101" and "1001001" is 2. 
      The Hamming distance between "2143896" and "2233796" is 3. 
      The Hamming distance between "toned" and "roses" is 3.
    
  • 汉明重量:是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。因此,如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。

  • 应用:汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中,为了增强容错性,应使得编码间的最小汉明距离尽可能大。但是,如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离等算法。

  • Matlab计算汉明距离(Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比):

      X=[0 1 1;1 1 2;1 5 2];
      d=pdist(X,'hamming')
      d=
        0.6667    1.0000    0.3333
    

9. 杰卡德距离(Jaccard Distance)

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

杰卡德相似系数

  • 杰卡德距离(Jaccard Distance):与杰卡德相似系数相反,用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度:

杰卡德距离

  • Matlab计算杰卡德距离(Matlab中将杰卡德距离定义为不同的维度的个数占“非全零维度”的比例):

      X=[1 1 0;1 -1 0;-1 1 0];
      d=pdist(X,'jaccard')
      d=
        0.5000    0.5000    1.0000
    

10. 相关距离(Correlation distance)

相关系数示意图

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

相关系数

  • 相关距离:

相关距离

  • Matlab计算相关系数与相关距离:

      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
    

11. 信息熵(Information Entropy)

 以上的距离度量方法度量的皆为两个样本(向量)之间的距离,而信息熵描述的是整个系统内部样本之间的一个距离,或者称之为系统内样本分布的集中程度(一致程度)、分散程度、混乱程度(不一致程度)。系统内样本分布越分散(或者说分布越平均),信息熵就越大。分布越有序(或者说分布越集中),信息熵就越小。

信息熵公式

  • 信息熵的由来:请参考博客:XXXXXXXX。

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

信息熵公式

参数的含义:

n:样本集X的分类数

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

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

本文转载自:http://yuguangchuan.github.io/2015/11/17/Distance-measurements/

下一篇: 如何去学习
牧师-Panda
粉丝 33
博文 146
码字总数 180044
作品 0
浦东
私信 提问
加载中

评论(2)

暴戾的灰灰
感谢分享,学习了
w
woncode
写得真不错,有形象的图片,文字排版很合适,讲解由浅入深,从二维到多维,看得出非常用心,感谢分享。
python机器学习(一):kNN算法

这段时间用opencv中的机器学习算法做了一下目标检测,效果还是不错的。但都是按照命令和库进行调用,基本对我来说是个黑盒子。固然工程师要会用工具,但如果不深入理解内部实现,是很难进步的...

JacobYoung
2018/09/25
0
0
聚类算法中的距离度量有哪些

二话不说,来一段网上的总结,想要了解详细的请猛点链接 1.欧式距离 2.曼哈顿距离 3.切比雪夫距离 4.幂距离 5.余弦相似度 6.皮尔逊相似度 7.修正的余弦相似度 8.Jaccard相似度 9.汉明距离 10...

李理
2017/10/22
0
0
【Python】 字符串相似性度量,用difflib还是Levenshtein

【作者笔记】 difflib(Python自带):不一定为字符串,数组也可以匹配,但数组匹配时只有单个元素完全匹配才计入相似。 Levenshtein(第三方插件):需要输入为字符串,匹配时是整体匹配,数...

qcyfred
03/19
0
0
在几何画板中怎么度量两点间的距离

几何画板可以用来制作很多几何图形,也可以度量出一些长度,前面给大家介绍了用几何画板度量点到直线的距离、两点的坐标距离等等,那么两点间的距离是不是也可以度量呢?下面就一起来看看如何...

学术研究软件
2016/12/21
3
0
分类与聚类的本质区别——机器学习

机器学习中有常见的两类大问题,一个是分类,一个是聚类。 分类与聚类的比较 聚类分析是研究如何在没有训练的条件下把样本划分为若干类。 在分类中,已知存在哪些类,即对于目标数据库中存在...

horacehe16
2018/04/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

详解RPC远程调用和消息队列MQ的区别

什么是RPC RPC(Remote Procedure Call)远程过程调用,主要解决远程通信间的问题,不需要了解底层网络的通信机制。 RPC服务框架有哪些 知名度较高的有Thrift(FB的)、dubbo(阿里的) RPC的一般...

一只会编程的狼
27分钟前
5
0
Dubbo面试题

支持的调用方式 同步调用 异步调用 参数回调 事件通知 支持的注册中心 Dubbo线上支持三种注册中心:自带的Simple Registry、Redis和Zookeeper,当然,最常用的还是Zookeeper作为注册中心,因...

i不歪
34分钟前
5
0
idea打包jar发布到nexus

8.idea打包jar发布到nexus 1. 配置maven的nexus地址 打开maven配置文件:\apache-maven-X.X.X\conf\settings.xml 修改配置为: <localRepository>E:\maven</localRepository> <pluginGroup......

TopDuang
36分钟前
6
0
nvm 使用方式

nvm 使用方式 命令: nvm ls-remote:列出所有可以安装node 版本号 nvm install v10.4.0:安装指定版本号的node nvm use v10.3.0:切换node版本,这个是全局的 nvm current:当前nod...

潇潇程序缘
36分钟前
4
0
八爪鱼爬网页分页数据

一个yuanbeth
40分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部