# 机器学习基础\_距离

![异世界.png](https://3321220703-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Lz6-7SJjwZD9V_N-3MS%2Fuploads%2Fgit-blob-50ea64a1dc0515db1eb624a09017f6badeb3e5fd%2F%E5%BC%82%E4%B8%96%E7%95%8C%E8%95%BE%E5%A7%86_1.png?alt=media)

\[TOC]

## 距离

> **范数**：常被用来度量某个向量空间(或矩阵)中的每个向量的长度或大小。
>
> 满足一定的条件，即①非负性；②齐次性；③三角不等式。
>
> (1) $$L1$$范数:$$||x||$$为$$x$$向量各个元素绝对值之和
>
> (2) $$L2$$范数(Euclidean范数):$$||x||$$为x向量各个元素平方和的开方
>
> (3) $$Lp$$范数:$$||x||$$为x向量各个元素绝对值$$p$$次方和的$$1/p$$次方
>
> (4) $$Loo$$:$$||x||$$为$$x$$向量各个元素绝对值最大的那个元素

## 闵科夫斯基距离

> 严格意义上讲，阅可夫斯基距离不是一种距离，而是一组距离的定义。
>
> 两个n维变量$$A(x_{11},x_{12},...x_{1n})$$与$$B(x_{21},x_{22},...x_{2n})$$间的闵科夫斯基距离定义为:

```
d_{12}=\sqrt[p]{\sum_{k=1}^{n}{(x_{1k}-x_{2k})^p}}
```

$$$
> 其中p是一个变参数。 > > * 当$$p=1$$时，就是曼哈顿距离 > * 当$$p=2$$时，就是欧式距离 > * 当$$p=3$$时，就是切比雪夫距离 > > 根据变参数的不同，闵可夫斯基距离可以表示一类的距离。 # 曼哈顿距离(Manhattan) > 实际驾驶距离就是这个“曼哈顿距离”（$$L1$$范数），而这也是曼哈顿距离名称的来源。 > > 曼哈顿距离也称为城市街区距离（City Block distance)，如图所示。 > > ![“曼哈顿距离”的图片搜索结果](https://upload.wikimedia.org/wikipedia/commons/thumb/0/08/Manhattan_distance.svg/300px-Manhattan_distance.svg.png) > > (a) 二维平面两点$$A(x_1,y_1)$$与$$B(x_2,y_2)$$间的曼哈顿距离： > > > $$ > d_{12} = |x_1-x_2| + |y_1-y_2| > $$ > > > (b) 两个$$n$$维向量$$A(x_{11},x_{12},...x_{1n})$$与$$B(x_{21},x_{22},...x_{2n})$$间的曼哈顿距离： > $$ > d_{12}=\sum_{k=1}^{n}{|x_{1k}-x_{2k}|} > $$ > # 欧式距离(Euclidean ) > 欧氏距离（$$L2$$范数)是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式，如图所示: > > ![相关图片](res/Machine%20Learning%20Base/images.png) > > (a) 二维平面上两点$$a(x_1,y_1)$$与$$b(x_2,y_2)$$间的欧氏距离： > $$ > d_{12}=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2} > $$ > (b) 三维空间两点$$A(x_1,y_1,z_1)$$与$$B(x_2,y_2,z_2)$$间的欧氏距离： > $$ > d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2(z_1-z_2)^2} > $$ > (c) 两个n维向量$$A(x_{11},x_{12},...,x_{1n})$$与$$B(x_{21},x_{22},...,x_{2n})$$间的欧氏距离： > $$ > d_{12}=\sqrt{\sum_{k=1}^{n}{(x_{1k}-x_{2k})^2}} > $$ > 表示为向量运算的形式： > $$ > d_{12}=\sqrt{(A-B)(A-B)^T} > $$ # 切比雪夫距离(Chebyshev) > 国际象棋玩过吗？国王走一步能够移动到相邻的8个方格中的任意一个。 > > ![1569914201042](res/Machine%20Learning%20Base/1569914201042.png) > > 那么国王从格子$$x_1,y_1$$走到格子$$x_2,y_2$$最少需要多少步？ > > 自己走走试试。你会发现最少步数总是$$max(|x_2-x_1|,|y_2-y_1|)$$步。 > > 有一种类似的距离度量方法叫作切比雪夫距离($$Loo$$范数)。 > > （1）二维平面两点$$A(x_1,y_1)$$与$$B(x_2,y_2)$$间的切比雪夫距离： > $$ > d_{12}=max(|x_1-x_2|,|y_1-y_2|) > $$ > （2) 两个$$n$$维向量$$A(x_{11},x_{12},...,x_{1n})$$与$$B(x_{21},x_{22},...,x_{2n})$$间的切比雪夫距离： > $$ > d_{12}=\underset{i}{max}{(|x_{1i}-x_{2i}|)} > $$ > 这个公式的另一种等价形式是： > $$ > d_{12}=\lim_{k \to \infty}{(\sum_{i=1}^{n}{|x_{1i}-x_{2i}|^k)^{1/k}}} > $$ > # 夹角余弦(Cosine) > 几何中的夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡 量样本向量之间的差异。 > > ![1569916326876](res/Machine%20Learning%20Base/1569916326876.png) > > （1）在二维空间中向量$$A(x_1,y_1)$$与向量$$B(x_2,y_2)$$的夹角余弦公式： > $$ > cos\theta=\frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}{\sqrt{x_2^2+y_x^2}}} > $$ > （2）两个$$n$$维样本点$$A(x_{11},x_{12},...x_{1n})$$与$$B(x_{21},x_{22},...,x_{2n})$$的夹角余弦：类似地，对于两个$$n$$维样本点$$A(x_{11},x_{12},...x_{1n})$$与$$B(x_{21},x_{22},...,x_{2n})$$，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。 > $$ > cos\theta=\frac{AB}{|A||B|} > $$ > 即： > $$ > cos\theta=\frac{\sum_{k=1}^{n}{x_{1k}x_{2k}}}{\sqrt{\sum_{k=1}^{n}{x_{1k}^2}{\sqrt{ \sum_{k=1}^{n}{x_{2k}^2} }}}} > $$ > 夹角余弦取值范围为$$[-1,1]$$。 > > 夹角余弦越大，表示两个向量的夹角越小；夹角余弦越 小，表示两个向量的夹角越大。 > > 当两个向量的方向重合时，夹角余弦取最大值1；当两个向量的方向完全相反时，夹角余弦取最小值-1。 # 汉明距离(Hamming) >（1）汉明距离的定义： > >两个等长字符串$$s1$$与$$s2$$之间的汉明距离定义为将其中一个 变为另外一个所需要的最小替换次数。 > >例如： > >1111 与 1001 之间的汉明距离为 2。 > >1011101 与 1001001 之间的汉明距离是 2。 > >2143896 与 2233796 之间的汉明距离是 3。 > >"toned" 与 "roses" 之间的汉明距离是 3。 > >应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。 > > # 杰卡德相似系数(Jaccard Similarity) >（1）杰卡德相似系数：两个集合A和B的交集元素在$$A$$、$$B$$的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号$$J(A,B)$$表示。 >$$ >J(A,B)=\frac{|A \cap B|}{|A \cup B|} >$$ >杰卡德相似系数是衡量两个集合的相似度的一种指标。 >（2）杰卡德距离：与杰卡德相似系数相反的概念是杰卡德距离(Jaccard Distance)。 >杰卡德距离可用如下公式表示： >$$ >J_{\delta}{(A,B)}=1-J(A,B)=\frac{|A \cup B|-|A \cap B|}{|A \cup B|} >$$ >杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。 >（3）杰卡德相似系数与杰卡德距离的应用。 > 可将杰卡德相似系数用在**衡量样本的相似度**上。 > 样本$$A$$与样本$$B$$是两个$$n$$维向量，而且所有维度的取值都是0或1。 > >​ 例如，$$A(0111)$$ 和$$B(1011)$$。我们将样本看成一个集合，1表示集合包含该元素，0表示集合不包含该 元素。 # 相关系数和相关距离 >（1）相关系数的定义： >$$ >\rho_{XY}=\frac{Cov(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}}=\frac{E((X-EX)(Y-EY))}{\sqrt{D(X)}\sqrt{D(Y)}} >$$ >​ 相关系数是衡量两个特征列之间相关程度的一种方法，其取值范围是$$[-1,1]$$。 > >​ 相关系数的绝对值越大，表明特征列$$X$$与$$Y$$的相关度越高。 > >​ 当$$X$$与$$Y$$线性相关时，相关系数取值为1(正线性相关)或-1(负线性相关)。 >（2）相关距离的定义： >$$ >D_{XY}=1-\rho_{XY} >$$ > # 马氏距离 >（1）马氏距离的定义：有$$M$$个样本向量$$X~X_m$$，协方差矩阵记为$$S$$，均值记为向量$$\mu$$，则其中样本向量$$X$$到$$\mu$$的马氏距离表示为： >$$ >D(X)=\sqrt{(X-\mu)^TS^{-1}(X-\mu)} >$$ >而其中向量$$X_i$$，与$$X_j$$之间的马氏距离定义为： >$$ >D(X_i,X_j)=\sqrt{(X_i-X_j)^{T}S^{-1}(X_i-X_j)} >$$ >若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则公式变成了欧氏距离公式： >$$ >D(X_i,X_j)=\sqrt{(X_i-X_j)^{T}(X_i,X_j)} >$$ >若协方差矩阵是对角矩阵，则公式变成了标准化欧氏距离公式。 >（2）马氏距离的优点：**量纲无关**，排除变量之间的相关性的干扰。 > >
$$$
