本文目录一览：
- 1、曼哈顿距离公式
- 2、曼哈顿距离计算公式
- 3、距离度量方法
- 4、曼哈顿距离计算公式
- 5、在数字图像处理中看到“计算两点之间的城市距离”,
- 6、知识点：曼哈顿距离和切比雪夫距离的互相转化
- 7、曼哈顿距离的简介
- 8、两点间最小的距离是什么？
- 9、曼哈顿距离vs欧氏距离
曼哈顿距离公式
曼哈顿距离公式是：d(i,j)=|X1-X2|+|Y1-Y2|。这个公式表示两点在南北和东西方向上的距离的绝对值之和。
1、曼哈顿距离的定义：
曼哈顿距离—两点在南北方向上的距离加上在东西方向上的距离，即d(i,j)=|x-x|+|y-y|。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。
2、曼哈顿距离的特征：
①它表示的是两点在南北和东西方向上的距离的绝对值之和。
②对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。
③曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。
④在出租车几何学中，一个圆是由从圆心向各个固定曼哈顿距离标示出来的点围成的区域。因此这种圆其实就是旋转了45度的正方形。
曼哈顿距离的用途：
1、城市规划：
曼哈顿距离可以帮助规划者更好地设计城市街区的网格状路网，使人们更便于出行和交通。它计算的北南向和东西向距离相等，可以更好地满足人们的步行和骑行需求。如果在设计中能合理控制曼哈顿距离的大小，还能促进城市的商业活力和社会交往，提高居民的生活质量。
2、计算机科学和机器学习：
曼哈顿距离在计算机科学和机器学习中经常被用于衡量两个点之间的距离，特别适用于在一个离散的网格中计算两个点的距离，例如在图像处理、路径规划等领域。
3、物理学：
在物理学中，曼哈顿距离也被称为欧几里得距离，是衡量两点之间距离的指标。
4、棋类游戏：
在棋类游戏中，曼哈顿距离常被用来计算棋子之间的距离。例如，在象棋和国际象棋中，棋子移动的距离是固定的，因此可以使用曼哈顿距离来评估棋局中棋子的位置。
曼哈顿距离计算公式
曼哈顿距离计算公式：d(i，j)=|xi-xj|+|yi-yj|。
曼哈顿距离是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。
曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。曼哈顿距离示意图在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差。
如果直接使用AB的欧氏距离，则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。
曼哈顿距离是两点在南北方向上的距离加上在东西方向上的距离，主要用来计算两个点在标准坐标系上的绝对轴距总和。计算公式是d(i,j)=|xi-xj|+|yi-yj|。曼哈顿距离具有非负性、同一性、对称性、三角不等式等数学性质。
要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。
距离度量方法
1.曼哈顿距离(Manhattan Distance)
定义：在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾 驶距离就是这个“曼哈顿距离”,也称为城市街区距离(City Block distance)。
2.欧式距离(Euclidean Distance)
定义：欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”（即直线）距离。
欧式距离是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）
图中红线代表曼哈顿距离，绿色代表欧式距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。
3.切比雪夫距离(Chebyshev distance)
定义：切比雪夫距离是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。
4.闵可夫斯基距离(Minkowski Distance)
其中p是一个变参数。当 p = 1 时，就是曼哈顿距离当 p = 2 时，就是欧氏距离当 p → ∞ 时，就是切比雪夫距离
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就 会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差（即 标准化欧式 距离）。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的 信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。
5. 标准化欧式距离(Standardized Euclidean distance)
思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。假设样本集 X 的均值(mean)为 m ，标准差(standard deviation)为 s ， X 的“标准化变量”表示为：
则标准化后的欧式距离公式为：
如果将方差的倒数看成一个权重，也可称之为加权欧氏距离(Weighted Euclidean distance)
6.马氏距离(Mahalanobis distance)
马氏距离表示数据的协方差距离，是一种有效的计算两个未知样本集的相似度的方法。其计算是建立在总体样本的基础上的。即，它考虑到各种特性之间的联系，是尺度无关的（独立于测量尺度）。
一原始多维样本数据 Xnm ( m 维，n 个样本 X=(X1, X2,...,Xn))：
对于一个样本的总体均值为μX=(μX1,μX2,...,μXm)，其协方差为Σ，的多变量矢量X=(X1, X2,...,Xn)T，其到样本中心 u 的马氏距离为：
而马氏距离也可以定义两个服从同一分布并且其协方差矩阵为Σ的两个随机变量的差异程度：
如果协方差矩阵为单位矩阵，马氏距离就简化为欧氏距离。
而马氏距离如何不受到量纲的影响呢？
1. 下图为二元数据的散点图：
将坐标拿掉以后，如下图：
2. 根据数据本身的提示信息来引入新的坐标轴。 坐标的原点在这些点的中央（根据点的平均值算得）。第一个坐标轴（下图中蓝色的线）沿着数据点的“脊椎”，并向两端延伸，定义为使得数据方差最大的方向。第二个坐标轴（下图红色的线）会与第一个坐标轴垂直并向两端延伸。
3. 然后，我们需要一个比例尺度。用数据沿着每一个坐标轴的标准差来定义一个单位长度。要记住68-95-99.7法则：大约2/3的点需要在离原点一个单位长度的范围内；大约95%的点需要在离原点两个单位的长度范围内。
4.让我们重新沿着正确的方向画图——从左到右，从下到上（相当于旋转一下数据）。同时，并让每个轴方向上的单位长度相同，这样横坐标上一个单位的长度就与纵坐标上的单位长度相同。
假设数据分布是一个二维的正椭圆，x 轴 y 轴均值都为0，x轴的方差为1000，y轴的方差为1，考虑两个点 (1, 0) ， (0, 1) 到原点的距离，如果计算的是欧氏距离那么两者相等，但是仔细想一下，因为x轴的方差大，所以 (0, 1) 应该是更接近中心的点，也就是正态分布标准差的 (68, 95, 99.7) 原则。这时候需要对 x , y 轴进行缩放，对应的操作就是在协方差矩阵的对角上加上归一化的操作，使得方差变为1。 假设数据分布是一个二维的椭圆，但是不是正的，比如椭圆最长的那条线是45°的，因为矩阵的对角只是对坐标轴的归一化，如果不把椭圆旋转回来，这种归一化是没有意义的，所以矩阵上的其他元素（非对角）派上用场了。如果椭圆不是正的，说明变量之间是有相关性的（x 大 y 也大，或者负相关），加上协方差非对角元素的意义就是做旋转。
马氏距离，欧式距离，标准化欧式距离小结：
1. 欧式距离
2. 标准化欧式距离：能够体现各个特性在变差大小上的不同，同时，距离与各个特性所用单位无关
3. 马氏距离 ： 各种特性之间的联系（如身高与体重）
马氏距离的计算是建立在总体样本的基础上的，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同。
在计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧氏距离计算即可。
满足了条件总体样本数大于样本的维数，但是协方差矩阵的逆矩阵仍然不存在，如三个样本在其所处的二维空间平面内共线。这种情况下，也采用欧氏距离计算。
7.余弦相似度(Cosine Similarity)
余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X 和 Y 两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看 X 似乎不喜欢这2个内容，而 Y 比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如 X 和 Y 的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。
8.汉明距离(Hamming Distance)
两个等长字符串 s1 与 s2 的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。
9.杰卡德距离(Jaccard Distance)
杰卡德距离(Jaccard Distance) 是用来衡量两个集合差异性的一种指标，它是杰卡德相似系数的补集，被定义为1减去Jaccard相似系数。而杰卡德相似系数(Jaccard similarity coefficient)，也称杰卡德指数(Jaccard Index)，是用来衡量两个集合相似度的一种指标。
10.皮尔逊系数(Pearson Correlation Coefficient)
在统计学中，皮尔逊相关系数，又称皮尔逊积矩相关系数（Pearson product-moment correlation coefficient，简称 PPMCC或PCCs），是用于度量两个变量X和Y之间的相关（线性相关），其值介于-1与1之间。
皮尔逊距离度量的是两个变量X和Y，它可以根据皮尔逊系数定义成 我们可以发现，皮尔逊系数落在 ，而皮尔逊距离落在 。
曼哈顿距离计算公式
曼哈顿距离计算公式：d(i,j)=|X1-X2|+|Y1-Y2|。
出租车几何或曼哈顿距离（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。
数学性质：
非负性：
d(i,j)≥0 距离是一个非负的数值。
同一性：
d(i,i)= 0 对象到自身的距离为0。
对称性：
d(i,j)= d(j,i)距离是一个对称函数。
三角不等式：
d(i,j)≤d(i,k)+d(k,j)从对象i到对象j的直接距离不会大于途经的任何其他对象k的距离和。
棋盘上的距离计量：
在西洋棋里，车（城堡）是以曼哈顿距离来计算棋盘格上的距离；而王（国王）与后（皇后）使用切比雪夫距离，象（主教）则是用转了45度的曼哈顿距离来算（在同色的格子上），也就是说它以斜线为行走路径。只有国王需要一步一步走的方式移动，皇后、主教与城堡可以在一或两次移动走到任何一格（在没有阻碍物的情况下，且主教忽略它不能走到的另一类颜色）。
曼哈顿与欧几里德距离: 红、蓝与黄线分别表示所有曼哈顿距离都拥有一样长度(12)，而绿线表示欧几里德距离有6×√2 ≈ 8.48的长度。
在数字图像处理中看到“计算两点之间的城市距离”,
所指的应该是曼哈顿距离.曼哈顿距离又称“城市街区距离（city block distance）”,其正式意义为L1距离,度量方法是数据之间的绝对差的和.例如在平面上,坐标（x1,y1）的 i 点与坐标（x2,y2）的 j 点的曼哈顿距离为：d(i,j) = |X1 - X2| + |Y1 - Y2|
知识点：曼哈顿距离和切比雪夫距离的互相转化
曼哈顿距离:横纵坐标距离差的绝对值的和
切比雪夫距离:横纵坐标距离差的绝对值的最大值
考虑离(0,0)点 曼哈顿距离为1的点形成的是一个【倾斜着45度角的正方形】。
而离(0,0)点 切比雪夫距离为1的点形成的是一个【正常正方形】。
所以他们之间一定有一些转化的方式:简单有:
1.
2.
例题1:P3964 [TJOI2013]松鼠聚会 (切比雪夫距离转曼哈顿距离)
题意:最小化若干个点到某个点的切比雪夫距离
题解:利用2式，将切比雪夫距离转成曼哈顿距离。先对X排序，预处理出所有点到i点的X轴上的距离。之后再对y排序，枚举所有点到i的Y轴上的距离，再加上预处理的结果得到最终答案。取最小值即可。
这里注意，2式有除法，可能会产生精度问题。在最后再除也是一样的。
例题2:ARC065 E-Manhattan Compass (曼哈顿距离转切比雪夫距离)
核心需求：设A,B两点的曼哈顿距离为D。求所有与A的曼哈顿距离 为 D的点。
其实不转也可以做.转化成切比雪夫距离之后。所有距离相等的点都在以A为中心，以A,B两点的切比雪夫距离为半径的 正方形 上.
曼哈顿距离的简介
我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1, y1）的i点与坐标（x2, y2）的j点的曼哈顿距离为：d(i,j)=|X1-X2|+|Y1-Y2|.要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来（忽略曼哈顿的单向车道以及只存在于3、14大道的斜向车道）。任何往东三区块、往北六区块的的路径一定最少要走九区块，没有其他捷径。出租车几何学满足除了SAS全等定理之外的希伯特定理，SAS全等指任两个三角型两个边与它们的夹角均分别对应相等，则这两个三角型全等。在出租车几何学中，一个圆是由从圆心向各个固定曼哈顿距离标示出来的点围成的区域。因此这种圆其实就是旋转了45度的正方形。如果有一群圆，任两圆皆相交，则整群圆必在某点相交；因此曼哈顿距离会形成一个超凸度量空间（Injective metric space）。对一个半径为r 的圆来说，这个正方形的圆每边长√2r。此'圆的半径r对切比雪夫距离 (L∞ 空间)的二维平面来说，也是一个对座标轴来说边长为2r的正方形，因此二维切比雪夫距离可视为等同于旋转且放大过的二维曼哈顿距离。然而这种介于L1与L∞的相等关系并不能延伸到更高的维度。
两点间最小的距离是什么？
两点之间的距离公式为 d=√[(x1-x2)2+(y1-y2)2]。
两点间距离公式叙述了点和点之间距离的关系。两点的坐标是（x1,y1)和（x2,y2)，则两点之间的距离公式为d=√［（x1-x2)2+(y1-y2)2]。
注意特例：当x1=x2时，两点间距离为｜y1-y2|；当y1=y2时，两点间距离为｜x1-x2|。
数学中常见的距离
1、欧氏距离，也称欧几里得度量、欧几里得度量，是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。在二维和三维空间中的欧氏距离的就是两点之间的距离。
2、曼哈顿距离，出租车几何或曼哈顿距离是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。
3、在数学中，切比雪夫距离或是L∞度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。
曼哈顿距离vs欧氏距离
欧式距离，即欧几里得距离，是最常见的两点之间的距离表示法，它定义在 欧几里 得空间中，例如x = (x1,x2,...,xn)和y = (y1,y2,...,yn)的欧式距离可表示为：
曼哈顿距离 ，是欧几里得空间中两点之间的线段在坐标轴上的投影的距离的和，例如x = (x1,x2) y = (y1,y2)则两点的曼哈顿距离可表示为：
