本文目录

1. 欧氏距离(Euclidean Distance)
2. 曼哈顿距离(Manhattan Distance)
3. 切比雪夫距离 ( Chebyshev Distance )
4. 闵可夫斯基距离(Minkowski Distance)
5. 标准化欧氏距离 (Standardized Euclidean Distance)
6. 马氏距离(Mahalanobis Distance)
7. 余弦距离(Cosine Distance)
8. 汉明距离(Hamming Distance)
9. 杰卡德距离(Jaccard Distance)
10. 相关距离(Correlation distance)
11. 信息熵(Information Entropy)

 

1. 欧氏距离(Euclidean Distance)

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

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

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

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

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

 

2. 曼哈顿距离(Manhattan Distance)

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

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

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

 

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

国际象棋玩过么?国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?这个距离就叫切比雪夫距离。

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

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

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

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

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

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

  其中p是一个变参数。

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

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

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

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

 

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

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

  • 标准化后的值 =  ( 标准化前的值  分量的均值 ) /分量的标准差
  • 经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n) b(x21,x22,…,x2n)间的标准化欧氏距离的公式:

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

 

6. 马氏距离(Mahalanobis Distance)

马氏距离的引出:

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

  • 概念

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

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

  • 而其中向量XiXj之间的马氏距离定义为:

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

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

 

7. 余弦距离(Cosine Distance)

几何中,夹角余弦可用来衡量两个向量方向的差异;

机器学习中,借用这一概念来衡量样本向量之间的差异。

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

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

即:

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

 

8. 汉明距离(Hamming Distance)

  • 定义

两个等长字符串s1s2的汉明距离为:将其中一个变为另外一个所需要作的最小字符替换次数。

例如

      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。因此,如果向量空间中的元素ab之间的汉明距离等于它们汉明重量的差a-b

  • 应用

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

 

9. 杰卡德距离(Jaccard Distance)

  • 杰卡德相似系数(Jaccard similarity coefficient)

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

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

  • 杰卡德距离(Jaccard Distance)

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

 

10. 相关距离(Correlation distance)

  • 相关系数

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

  • 相关距离

 

11. 信息熵(Information Entropy)

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

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

  • 参数的含义:

n:样本集X的分类数

piX中第 i 类元素出现的概率

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

Trackback

no comment untill now

Add your comment now