相似度计算之闵可夫斯基距离

[latexpage]

闵可夫斯基距离又称为闵氏距离(由于翻译问题,有时候也被称为明可夫斯基距离或明氏距离)。闵可夫斯基距离是欧氏空间中的一种测度,被看做是欧氏距离和曼哈顿距离的一种推广。闵氏距离不是一种距离,而是一组距离的定义。

闵可夫斯基距离的定义

假设两点:

$$P=(x_{1},x_{2},\ldots ,x_{n}){\text{ and }}Q=(y_{1},y_{2},\ldots ,y_{n})\in \mathbb {R} ^{n}$$

明氏距离公式为:

$$\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{1/p}$$

p取1或2时的明氏距离是最为常用的,p=2即为欧氏距离,而p=1时则为曼哈顿距离。当p取无穷时的极限情况下,可以得到切比雪夫距离

$$\lim _{p\to \infty }{\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{\frac {1}{p}}}=\max _{i=1}^{n}|x_{i}-y_{i}|$$

我们知道平面上到原点欧几里得距离(p = 2)为 1 的点所组成的形状是一个圆,当 p 取其他数值的时候呢?

注意,当 p<1 时,闵可夫斯基距离不再符合三角形法则,举个例子:当 p<1, (0,0) 到 (1,1) 的距离等于 (1+1)^{1/p}>2, 而 (0,1) 到这两个点的距离都是 1。

闵可夫斯基距离比较直观,但是它与数据的分布无关,具有一定的局限性,如果 x 方向的幅值远远大于 y 方向的值,这个距离公式就会过度放大 x 维度的作用。所以,在计算距离之前,我们可能还需要对数据进行z-transform处理,即减去均值,除以标准差:

$$(x_1,y_1)x \mapsto x^2 (\frac{x_1-\mu _x}{\sigma _x},\frac{y_1-\mu _y}{\sigma _y})$$

其中 $\mu $为该维度上的均值,$\sigma$为该维度上的标准差。

可以看到,上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关(例如:身高较高的信息很有可能会带来体重较重的信息,因为两者是有关联的),这时候就要用到马氏距离(Mahalanobis distance)了。

闵氏距离的缺点主要有两个:

  • 将各个分量的量纲(scale),也就是“单位”当作相同看待了
  • 没有考虑各个分量的分布(期望,方差等)可能是不同的

Python实现:

参考资料:

“加权(weighted)”闵可夫斯基距离

当样本中不同属性的重要性不同时,可使用”加权距离”(weighted distance)

$$dist_{wmk}(x,y) = (\sum_{i=1}^{n}{W_i|x_i-y_i|^p})^{\frac{1}{p}}$$

$$\sum_{i=1}^{n}{w_i}=1$$

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

聚类算法之Affinity Propagation(AP)

Affinity Propagation算法简介 AP(Affinity Propagation)通常被翻译为

机器学习算法之朴素贝叶斯

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素贝叶斯分类是贝叶斯分类

频繁项集算法Eclat学习笔记

Equivalence Class Transformation(Eclat)是频繁项挖掘和关联性分析的另外一

发表评论

电子邮件地址不会被公开。 必填项已用*标注