《机器学习-周志华》学习笔记html

机器学习中的距离

距离度量的基本性质

对函数 $dist(\cdot,\cdot)$ ，若它是一个“距离度量”，则其知足如下性质：web

• 非负性： $dist(x_i,x_j) \ge 0$;
• 同一性： $dist(x_i,x_j) = 0,\text{当且仅当}x_i=x_j$;
• 对称性： $dist(x_i,x_j) = dist(x_j,x_i)$；
• 直递性： $dist(x_i,x_j) \le dist(x_i,x_k)+dist(x_k,x_j)$.

直递性常被称为“三角不等式”app

闵可夫斯基距离（Minkowski distance）

给定样本 $x_i=(x_{i1};x_{i2};\cdots ;x_{in})$ 和 $x_j=(x_{j1};x_{j2};\cdots ;x_{jn})$ ,闵可夫斯基距离为：
$dist_{mk}(x_i,x_j)=\|x_i-x_j\|_p=\left( \sum_{u=1}^{n}|x_{iu}-x_{ju}|^p\right)^{\frac{1}{p}}$机器学习

对 $p\ge 1$ ,公式知足距离度量的全部性质ide

当 $p=1$ 时，闵可夫斯基距离即为曼哈顿距离（Manhattan distance）,此时有
$dist_{man}(x_i,x_j)=\|x_i-x_j\|_1= \sum_{u=1}^{n}|x_{iu}-x_{ju}|$svg

曼哈顿距离也称为“城市街区距离”(City Block distance)。函数

当 $p=2$ 时，闵可夫斯基距离即为欧式距离（Euclidean distance）,此时有
$dist_{ed}(x_i,x_j)=\|x_i-x_j\|_2= \sqrt{\sum_{u=1}^{n}|x_{iu}-x_{ju}|^p}$学习

当 $p\to\infty$ 时，闵可夫斯基距离即为切比雪夫距离（Chebyshev distance）,此时有
$dist_{cd}(x_i,x_j)=\|x_i-x_j\|_{\infty}=lim_{p\to\infty} \left( \sum_{u=1}^{n}|x_{iu}-x_{ju}|^p\right)^{\frac{1}{p}}$idea

闵氏距离的缺点：

1. 将各个份量的量纲(scale)，也就是“单位”相同的看待了;
2. 未考虑各个份量的分布（指望，方差等）多是不一样的。

说明：
机器学习中常将属性划分为连续属性（continuous attr）和离散属性（categorical attr），在讨论距离计算时，属性上是否认义了序关系更为重要，例如定义域 $\{1,2,3\}$的离散属性与连续属性的性质更接近一些，能直接在属性上计算距离：“1”与“2”比较接近、与“3”比较远，这样的属性称为有序属性（ordinal attr）；而定义域为 $\{\text{飞机,火车,轮船}\}$这样的离散属性不能直接在属性值上计算距离，称为无序属性（non-ordinal attr）spa

显然，闵可夫斯基距离可用于有序属性

VDM（Value difference Metric）

当样本属性为无序属性时，使用VDM距离。属性u上两个离散值a与b之间的VDM距离为
$VDM_p(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,a}}|^p$

其中：

• $m_{u,a}$ 表示在属性u上取值为a的样本数
• $m_{u,a,i}$ 表示在第i个样本簇中在属性u上取值为a的样本数
• $k$为样本簇数

混合属性的距离计算

混合属性的距离计算能够将 闵可夫斯基距离 和 VDM 结合。

假定有 $n_c$个有序属性， $n-n_c$个无序属性，令有序属性排列在无序属性以前，则
$MinkovDM_p(x_i,x_j)=\left( \sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=u_c+1}^{n} VDM_p(x_{iu},x_{ju})\right)^{\frac{1}{p}}$

加权距离（weighted distance）

当样本空间中不一样属性的重要性不一样时，可以使用加权距离
以加权闵可夫斯基距离为例：
$dist_{wmk}(x_i,x_j)=\left( w_1\cdot|x_{i1}-x_{j1}|^p+\cdots+ w_n\cdot|x_{in}-x_{jn}|^p\right)^{\frac{1}{p}}$

其中：

权重 $w_i\ge0(i=1,2,\cdots,n)$ 表示不一样属性的重要性，一般 $\sum_{i=1}^nw_i=1$.

最后

一般是基于某种形式的距离来定义“类似度度量”(similarity measure),距离越大，类似度越小。
然而，用于类似度度量的距离未必必定要知足距离度量的全部基本性质，尤为是直递性。
此时不知足某些性质的距离称为“非度量距离”(non-metric distance)

基于数据样原本肯定合适的距离计算式，可经过距离度量学习（distance metric learning）来实现

博客内容是我我的的学习笔记, 因为水平有限, 确定有很多错误或遗漏. 若发现, 欢迎留言告知, 谢谢! 另，欢迎邮件与我探讨交流Email：ice-melt@outlook.com