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

28 sec read

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

闵可夫斯基距离的定义

假设两点:

    \[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

使用Python进行相关性分析

在数据分析时,经常会针对两个变量进行相关性分析。在Python中主要用到的方法是pandas中的corr()方
42 sec read

一维数组的聚类

需求:分析订单的价格分布 方案:按照100为梯度,分析不同价格区间的订单量 缺陷:现实生活中,定价存在一些自然
1 min read

Pandas学习笔记:Excel、CSV文件的读取与导出

在使用Pandas处理数据时,常见的读取数据的方式时从Excel或CSV文件中获取,另外有时也会需要将处理完的
2 min read

发表评论

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