【译文】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课翻译小组作品,未经需求严禁转载

原文发布于微信公众号 - PPV课数据科学社区(ppvke123)

原文发表时间:2016-06-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

论文Express | 英伟达最新:多模态无监督图像迁移网络框架

1322
来自专栏大数据挖掘DT机器学习

支持向量机及Python代码实现

做机器学习的一定对支持向量机(support vector machine-SVM)颇为熟悉,因为在深度学习出现之前,SVM一直霸占着机器学习老大哥...

4556
来自专栏机器学习算法原理与实践

谱聚类(spectral clustering)原理总结

    谱聚类(spectral clustering)是广泛使用的聚类算法,比起传统的K-Means算法,谱聚类对数据分布的适应性更强,聚类效果也很优秀,同时...

973
来自专栏机器学习入门

深度学习系列(2):前向传播和后向传播算法

深度学习系列(2):前向传播和后向传播算法 前言 讲真,之前学吴恩达的机器学习课时,还手写实现过后向传播算法,但如今忘得也一干二净。总结两个原因:1. 理解不够...

3437
来自专栏专知

【专知荟萃11】GAN生成式对抗网络知识资料全集(理论/报告/教程/综述/代码等)

生成对抗网络(GAN)专知荟萃 一、理论学习 二、报告 三、教程 四、综述 五、中文博客资料 六、Github资源以及模型 七、最新研究论文 一、理论学习 训...

4338
来自专栏机器学习算法工程师

听说比K-means厉害多了:谱聚类

地址:https://www.cnblogs.com/pinard/p/6221564.html

8214
来自专栏林欣哲

深度学习的训练

今天来聊聊深度学习的训练方法和注意事项 数据集的拆分: 首先要准备好已经处理好的数据集(注意数据集要满足独立同分布),分为训练集、验证集、测试集。可按80%,1...

4298
来自专栏和蔼的张星的图像处理专栏

FHOG传统hog特征提取。FHOG

关于HOG特征(梯度统计直方图)简单介绍一下,首先是对原图进行灰度化(hog统计的是梯度信息,色彩几乎没有贡献),再进行gamma压缩和归一化(减轻光照影响)。...

1.3K2
来自专栏CreateAMind

Efficient Deep Learning for Stereo Matching:代码

在今年6月于美国拉斯维加斯召开的CVRP大会上,多伦多大学的Raquel Urtasun教授和她的学生改进了深度学习中的Siamese网络,用一个内积层代替了拼...

1572
来自专栏梦里茶室

读论文系列:Object Detection SPP-net

本文为您解读SPP-net: Spatial Pyramid Pooling in Deep Convolutional Networks for Visua...

37010

扫码关注云+社区

领取腾讯云代金券