【译文】30分钟让你分清几种距离

做数据挖掘时,我们经常会用到聚类分析,聚类分析的原理简单的说就是:基于样本点之间的距离大小来给样本点分类,我们把距离当做是衡量样本的相似性的大小,可能因此我们经常听到各种距离,今天我们就来一起看看集中距离的对比和详细含义.本文尽量使用通俗易懂的语言,加上图形来给读者介绍一下,轻轻松松30分钟内掌握.

先看看这幅图,

其中绿色线就是欧式距离,蓝色和黄色线,红色线是曼哈顿距离,他们是相等的.这样你是不是一分钟就懂了,什么是欧式距离什么曼哈顿距离.别慌,让我们来深入学习一下几种距离在数学上的推广,首先假设有两点a和b,它们的坐标分别是 a(x1,y1) ,b(x2,y2) 以及两个向量A和B 它们表示为 A(x11,x12,x13….x1n), B(x21,x22,x23…..x2n).

1.欧式距离

欧氏距离就是我们最常见的几何距离,在二维空间也就是空间内两点的直线距离。

　点a和点b的欧式距离公式

　用坐标系画出来就是

在三维空间便是

推广到n维空间我们用向量来表示,即A与B的距离,按照上面的公式推出来也就是:

若学过线性代数的读者便可以知道,向量加减就是向量元素对应加减,(即括号中元素)上面的式子可以化成向量之间的计算:

2.曼哈顿距离:

我们又称为城市街区距离,至于为什么,你看完下面的就知道了.

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

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

3. 切比雪夫距离

切比学夫大家肯定很熟啦,对就是高数那个切比雪夫,这里的切比雪夫距离用一个形象的例子就是下扫雷游戏,一个格子周围总会有8个格子包围,那么从格子a(x1,y1)走到格子b(x2,y2)最少需要多少步？ 自己走走试试。你会发现最少步数总是max(| x2-x1 | , | y2-y1 | ) 步,这就是切比雪夫距离。

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

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

用另一种形式的表达式就是如下,两个公式是等价的,可以推导出来.

4. 闵可夫斯基距离

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

其中p是一个变参数。

当p=1时，你把公式简化一下,发现什么没?

对,就是曼哈顿距离

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

当p→∞时，把p换成k看看,就是切比雪夫距离

　　(2)闵氏距离的缺点

举个例子：某个人的数据 :(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，也就是说,在聚类分析中,a与c之间的相似度和a与b之间的相似度一样咯? 现在马上脑补一下,一个这两个人的身材,你还会这样觉得吗? 因此用闵氏距离来衡量这些样本间的相似度很有问题。

在数学上说，闵氏距离的缺点主要有两个：

(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。

(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。

5.马氏距离

（1）马氏距离定义

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

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

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了如下,也就是欧氏距离了。

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

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

6.汉明距离

(1)汉明距离的定义

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

PPV课翻译小组作品，未经需求严禁转载