距离计算方法概述

在进行分类时,常常需要估计不同样本之间的相似性度量。这时,通常的方法是计算样本之间的“距离”。用什么样的方法计算距离是很有讲究的,甚至关系到分类的正确性。

本文的目的是总结常用的相似性度量。

欧氏距离是最容易理解的距离计算方法,它来源于欧氏空间中两点之间的距离公式。\

(1)二维平面上两点a (x1,y1)和b(x 2,y 2)之间的欧氏距离;

(2)三维空间中两点a(x 1,y 1,z 1)和b(x 2,y 2,z 2)之间的欧氏距离:

(3)两个N维向量A (X11,X12,…,X1N)与b(x 21,x 22,…,x 2n)之间的欧氏距离:

从名字就能猜出这个距离的计算方法。想象一下,你必须从曼哈顿的一个十字路口开车到另一个十字路口。两点之间的行驶距离是直线吗?显然不行,除非你能穿过大楼。实际行驶距离就是这个“曼哈顿距离”。这也是曼哈顿距离这个名字的由来,也叫城市街区距离。

(1)二维平面上两点A (X1,Y1)和b(x2,y2)之间的曼哈顿距离。

(2)两个N维向量A (X11,X12,…,X1N)和b(x21,x22,…,x2n)之间的曼哈顿距离

你玩过象棋吗?国王可以一步移动到相邻的八个方格中的任何一个。那么王者从格子(x1,y1)走到格子(x2,y2)需要走多少步呢?试着自己走。你会发现最小步数总是Max (| x2-x1 |,| y2-y1 |)。还有一种类似的距离测量方法叫做切比雪夫距离。

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

(2)两个N维向量A (X11,X12,…,X1N)和b(x21,x22,…,x2n)之间的切比雪夫距离

你看不出这两个公式是等价的吗?提示:试着用缩放和捏来证明。

Min的距离不是一个距离,而是一组距离的定义。

(1)最小距离的定义

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

其中p是可变参数。

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

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

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

根据不同的可变参数,Min的距离可以表示一种距离。

(2)闵距离的不足

包括曼哈顿距离、欧几里德距离和切比雪夫距离在内的Min距离都有明显的缺点。

比如有三个样本:A (150-190),b(190,50),C (50-60)。那么A和B之间的最小距离(不管是曼哈顿距离、欧几里德距离还是切比雪夫距离)等于A和C之间的最小距离,但是10cm的身高真的等同于10kg的体重吗?所以用Min的距离来衡量这些样本之间的相似度是很成问题的。

简单来说,闵的距离有两个主要缺点:

(1)将每个组件的比例(即“单位”)视为相同。

(2)分布(期望、方差等。)可能不同。

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

标准化欧氏距离是针对简单欧氏距离的缺点而提出的一种改进方案。标准欧氏距离的思路:既然数据的各个维度分量分布不一样,那好吧!然后,我将“标准化”所有组件,使其均值和方差相等。均值和方差的标准化程度如何?我们在这里复习一些统计学知识。假设样本集X的均值为m,标准差为s,那么X的“标准化变量”表示为:

如果把方差的倒数看作一个权重,这个公式就可以看作一个加权的欧氏距离。

(1)马氏距离的定义

有m个样本向量X1~Xm,协方差矩阵标为S,均值标为向量μ,则样本向量X到U的马氏距离表示为:

如果协方差矩阵是单位矩阵(每个样本向量是独立且同分布的),则公式变为:

也就是欧几里德距离。

如果协方差矩阵是对角矩阵,则该公式成为标准化的欧几里德距离。

(2)马氏距离的优缺点:维数无关,排除变量间相关性的干扰。

你在开玩笑吗?我不是学几何的。你是怎么得出夹角的余弦的?女士们先生们,放轻松。几何学中的夹角余弦可以用来度量两个向量之间的差异,机器学习中借用了这个概念来度量样本向量之间的差异。

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

(2)两个N维样本点A (X11,X12,…,X1N)与b(x21,x22,…,x2n)的夹角余弦。

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

(1)汉明距离的定义

两个等长字符串s1和s2之间的汉明距离被定义为将其中一个字符串变为另一个字符串所需的最小替换数。例如,字符串“111”和“1001”之间的汉明距离是2。

应用:信息编码(为了增强容错能力,码间最小汉明距离要尽可能大)。

(1) Jakad相似系数

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

Jakade相似系数是衡量两个集合之间相似性的指标。

(2)贾卡德距离

与雅可比相似系数相反的概念是雅克卡距离。雅可比距离可以由以下公式表示:

Jakade距离通过两个集合中所有元素中不同元素的比例来度量两个集合之间的区分度。

(3)Jakade相似系数和Jakade距离的应用。

Jakade相似系数可以用来衡量样本的相似性。

样本a和样本b是两个n维向量,所有维度的值都是0或1。例如:A(0111)和B(1011)。我们把样本看成一个集合,1表示集合包含元素,0表示集合不包含元素。

p:样本a和样本b都是1的维数。

问:样本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之间的jekade距离表示为:

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

(2)相关距离的定义

信息熵不属于相似性度量。那为什么要放在这篇文章里?这个。。。我也不知道。(╯▽╰)

信息熵是对分布的混乱或分散程度的度量。分布越分散(甚至),信息熵越大。分布越有序(或者分布越集中),信息熵越小。

参数的含义:

n:样本集x的分类数。

pi: x中I类元素的概率

信息熵越大,样本集S的分类越分散,信息熵越小,样本集X的分类越集中..。当S中N个分类的概率相同时(都是1/n),信息熵的最大值是log2(n)。当X只有一个分类时,信息熵的最小值为0。