闵可夫斯基距离或闵可夫斯基度量是赋范向量空间中的度量,可以看作是欧几里得距离和曼哈顿距离的推广。它以波兰数学家赫尔曼·闵可夫斯基的名字命名。两点之间 p 阶闵可夫斯基距离(其中 p 为整数)
X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)∈Rn
定义为:
D(X,Y)=(i=1∑n∣xi−yi∣p)p1(1)
对于 p≥1,闵可夫斯基距离是根据闵可夫斯基不等式得出的度量。当 p<1 时,(0,0) 和 (1,1) 之间的距离为 21/p>2,但点 (0,1) 与这两个点的距离均为 1。由于这违反了三角不等式,因此对于p<1,它不是度量。但是,只需删除 1 / p 的指数即可获得这些值的度量。得到的度量也是 F 范数。
通常使用闵可夫斯基距离,其中 p 为 1 或 2 ,分别对应于曼哈顿距离和欧几里得距离。 在 p 趋向无穷大的极限情况下,我们得到切比雪夫距离:
p→∞lim(i=1∑n∣xi−yi∣p)p1=i=1maxn∣xi−yi∣
类似地,对于 p 达到负无穷大,我们有:
p→−∞lim(i=1∑n∣xi−yi∣p)p1=i=1minn∣xi−yi∣
闵可夫斯基距离也可以看作是 P 和 Q 之间各分量差异的幂均值的倍数。
Python和C++/C#/Java计算闵可夫斯基距离
给定两个数组 A[] 和 B[] 作为 n 维空间中两个点的位置向量以及一个整数 p,任务是计算这两点之间的闵可夫斯基距离。根据上式(1),假设,输入A[] = {1,2,3,4}, B[] = {5,6,7,8}, P = 3 输出是 6.340,输入A = {1,2,3,4}, B[] = {5,6,7,8} P = 2 ,输出是8。
import math
def minkowski(A, B, P):
X = 0.0
for i in range(len(A)):
X += abs(A[i] - B[i]) ** P
Z = 1.0 / P
return X ** Z
if __name__ == "__main__":
A = [1, 2, 3, 4]
B = [5, 6, 7, 8]
P = 2.0
print(minkowski(A, B, P))
C++计算闵可夫斯基距离
#include <bits/stdc++.h>
using namespace std;
double minkowski(const vector<double>& A,
const vector<double>& B, double P)
{
double X = 0.0;
for (size_t i = 0; i < A.size(); ++i) {
X += pow(abs(A[i] - B[i]), P);
}
double Z = 1.0 / P;
return pow(X, Z);
}
int main()
{
vector<double> A = { 1, 2, 3, 4 };
vector<double> B = { 5, 6, 7, 8 };
double P = 2.0;
cout << minkowski(A, B, P) << endl;
return 0;
}
C#计算闵可夫斯基距离
using System;
using System.Collections.Generic;
public class Program
{
static double Minkowski(List<double> A, List<double> B, double P)
{
double X = 0.0;
for (int i = 0; i < A.Count; ++i)
{
X += Math.Pow(Math.Abs(A[i] - B[i]), P);
}
double Z = 1.0 / P;
return Math.Pow(X, Z);
}
public static void Main()
{
List<double> A = new List<double> { 1, 2, 3, 4 };
List<double> B = new List<double> { 5, 6, 7, 8 };
double P = 2.0;
Console.WriteLine(Minkowski(A, B, P));
}
}
Java计算闵可夫斯基距离
import java.util.ArrayList;
import java.util.List;
public class MinkowskiDistance {
private static double
minkowski(List<Double> A, List<Double> B, double P)
{
double X = 0.0;
for (int i = 0; i < A.size(); ++i) {
X += Math.pow(Math.abs(A.get(i) - B.get(i)), P);
}
double Z = 1.0 / P;
return Math.pow(X, Z);
}
public static void main(String[] args)
{
List<Double> A = List.of(1.0, 2.0, 3.0, 4.0);
List<Double> B = List.of(5.0, 6.0, 7.0, 8.0);
double P = 2.0;
System.out.println(minkowski(A, B, P));
}
}