相似度计算之切比雪夫距离

标点符 2018-07-04 23:44:26 浏览 2,181 次

切比雪夫距离起源于国际象棋中国王的走法，国际象棋中国王每次只能往周围的8格中走一步，那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步？你会发现最少步数总是max(| x2-x1 |,| y2-y1|) 步。有一种类似的一种距离度量方法叫切比雪夫距离。

若将国际象棋棋盘放在二维直角座标系中，格子的边长定义为1，座标的x轴及y轴和棋盘方格平行，原点恰落在某一格的中心点，则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为棋盘距离。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置，和周围八个位置的切比雪夫距离都是1。

二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离：

$d_{ab} = max(|x_1-x_2|, |y_1 - y_2|)$

两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离：

$d_{ab} = max(|x_{1i}-x_{2i}|)$

可以看到当扩展到多维空间，其实切比雪夫距离就是当p趋向于无穷大时的闵可夫斯基距离：

$dist(X,Y) = \lim_{p\rightarrow \infty }{(\sum_{i=1}^{n}{|x_i-y_i|^p})^{1/p}}=max(|x_i-y_i)$

Python实现：

def chebyshev_distance(p, q):
    assert len(p) == len(q)
    return max([abs(x - y) for x, y in zip(p, q)])


def chebyshev_distance_procedural(p, q):
    assert len(p) == len(q)
    d = 0
    for x, y in zip(p, q):
        d = max(d, abs(x - y))
    return d

参考文档：

https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.spatial.distance.chebyshev.html

二维空间切比雪夫距离与曼哈顿距离的相互转化

曼哈顿距离：设平面空间内存在两点，它们的坐标为(x1,y1)，(x2,y2) 则dis=|x1−x2|+|y1−y2| 。即两点横纵坐标差之和。如图所示，图中A,B两点的曼哈顿距离为AC+BC=4+3=7

切比雪夫距离：设平面空间内存在两点，它们的坐标为(x1,y1)，(x2,y2) 则dis=max(|x1−x2|,|y1−y2|) 。即两点横纵坐标差的最大值。dis=max(AC,BC)=AC=4。

两者的定义看上去好像没有什么关系，但实际上，这两种距离可以相互转化。我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)。如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为1的正方形。

如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形。

仔细对比这两个图形，你会发现什么？第二个图像是由第一个图像放大后旋转45∘得到的。

将代表曼哈顿距离的正方形绕原点旋转45%，我们发现两个正方形现在是相似的。只要把代表曼哈顿距离的正方形扩大到原来的 $\sqrt{2}$ 倍。

曼哈顿距离转化为切比雪夫距离：假设哈顿距离的正方形的四条边上的点A(x,y)，则旋转以后变为：

$(x\cdot cos(45^\circ)-y\cdot sin(45^\circ),y\cdot cos(45^\circ)+x\cdot sin(45^\circ))=(x\cdot \frac{1}{\sqrt{2}}-y\cdot \frac{1}{\sqrt{2}},y\cdot \frac{1}{\sqrt{2}}+x\cdot \frac{1}{\sqrt{2}})$

在此基础上再扩大 $\sqrt{2}$ 倍可得： ${A}'(x-y,x+y)$

已知由曼哈顿距离转化为切比雪夫距离为： $A(x,y)\Rightarrow {A}'(x-y,x+y)$ ，则可以反推出切比雪夫距离转化为曼哈顿距离

$A(x,y)\Rightarrow {A}'(\frac{x-y}{2},\frac{x+y}{2})$

相似度计算之切比雪夫距离

建议继续学习