距离是聚类的基础,是数据挖掘中最重要的概念之一，也是衡量相似度的主要指标之一。距离有很多种，各种距离的应用场景可以简单概括为：

空间：欧氏距离。

路径：曼哈顿距离。

国际象棋国王：切比雪夫距离。

欧氏距离、曼哈顿距离、切比雪夫距离三种距离的统一形式：闵可夫斯基距离。

加权：标准化欧氏距离。

排除量纲和依存：马氏距离。

编码差别：汉明距离。

具体来说，各种距离的含义如下。

1.闵可夫斯基距离

两个n维变量a(x₁₁，x₁₂，…，x_1n)与b(x₂₁，x₂₂，…，x_2n)间的闵可夫斯基距离(Minkowski Distance)定义为：
其中p是一个变参数。

当p=1时，就是曼哈顿距离。

当p=2时，就是欧氏距离。

当p→∞时，就是切比雪夫距离。

根据变参数的不同，闵氏距离可以表示一类距离。

1）欧氏距离。最常见的两点之间或多点之间的距离表示法又称为欧几里得度量，它定义于欧几里得空间中，如点x=(x₁,…,x_n)和y=(y₁,…,y_n)之间的距离为：


二维平面上两点a(x₁,y₁)与b(x₂,y₂)间的欧氏距离：



三维空间两点a(x₁,y₁,z₁)与b(x₂,y₂,z₂)间的欧氏距离：


两个n维向量a(x₁₁,x₁₂,…,x1_n)与b(x₂₁,x₂₂,…,x_2n)间的欧氏距离：


也可以用表示成向量运算的形式：




标准化欧氏距离(Standardized Euclidean distance)是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。

假设样本集X的数学期望或均值为m，标准差为s，那么X的“标准化变量”X*表示为：而且标准化变量的数学期望为0，方差为1。

即样本集的标准化过程(standardization)用公式描述就是：




经过简单推导就可以得到两个n维向量a(x₁₁,x₁₂,…,x_1n)与b(x₂₁,x₂₂,…,x_2n)间的标准化欧氏距离的公式：

曼哈顿距离的正式意义为L1-距离或城市区块距离(City Block distance)，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对坐标轴产生的投影的距离总和。例如在平面上，坐标（x₁,y₁）的点P₁与坐标（x₂,y₂）的点P₂的曼哈顿距离为：x₁-x₂+y₁-y₂，要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。

二维平面两点a(x₁,y₁)与b(x₂,y₂)间的曼哈顿距离：


两个n维向量a(x₁₁,x₁₂,…,x_1n)与b(x₂₁,x₂₂,…,x_2n)间的曼哈顿距离：


3）切比雪夫距离。若两个向量或两个点p、q，其坐标分别为p_i及q_i，则两者之间的切比雪夫距离定义如下：



这也等于以下Lp度量的极值：因此切比雪夫距离也称为L∞度量。

以数学的观点来看，切比雪夫距离是由一致范数（uniform norm，或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。

在平面几何中，若两点p及q的直角坐标系坐标为（x₁,y₁）及（x₂,y₂），则切比雪夫距离为：



在国际象棋中，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x₁,y₁)走到格子(x₂,y₂)最少需要的步数总是步。有一种类似的距离度量方法叫切比雪夫距离。

二维平面两点a(x₁,y₁)与b(x₂,y₂)间的切比雪夫距离：



两个n维向量a(x₁₁,x₁₂,…,x_1n)与b(x₂₁,x₂₂,…,x_2n)间的切比雪夫距离：



这个公式的另一种等价形式是


在闵可夫斯基距离中，最常用的是欧氏距离，它的主要优点是当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，则变换后样本点间的距离和变换前完全相同。

值得注意的是，在采用闵可夫斯基距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，建议首先进行数据的标准化处理，然后计算距离。在采用闵可夫斯基距离时，还应尽可能地避免变量的多重相关性（multi-collinearity）。多重相关性所造成的信息重叠会片面强调某些变量的重要性。

由于闵可夫斯基距离的这些缺点，一种改进的距离就是马氏距离。

2.马氏距离

马氏距离(Mahalanobis Distance)是由协方差矩阵演变而来的。有M个样本向量X1-Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到μ的马氏距离表示为：



（协方差矩阵中每个元素是各个矢量元素之间的协方差Cov(X,Y)，Cov(X,Y)=E{［X-E(X)］［Y-E(Y)］}，其中E为数学期望。）

而其中向量Xi与Xj之间的马氏距离定义为：


若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了欧氏距离：



若协方差矩阵是对角矩阵，公式变成了标准欧氏距离。

马氏距离的特点：与量纲无关，排除变量之间相关性的干扰。

3.巴氏距离

在统计学中，巴氏距离（Bhattacharyya Distance）测量两个离散或连续概率分布的相似性。

离散概率分布p和q在同一域X，巴氏距离被定义为：

D_B（p,q）=-ln（BC（p,q））

其中



是巴氏系数。

对于连续概率分布，巴氏系数被定义为：



在0≤BC≤1和0≤D_B≤∞这两种情况下，巴氏距离DB并没有服从三角不等式（值得一提的是，Hellinger距离不服从三角不等式
 

对于多变量的高斯分布pi=N（mi,Pi），有




和是手段和协方差的分布
 

需要注意的是，在这种情况下，第一项中的巴氏距离与马氏距离有关联。

4.汉明距离

两个等长字符串s₁与s₂之间的汉明距离(Hamming distance)定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

汉明距离经常应用在信息编码中，比如，为了增强容错性，应使得编码间的最小汉明距离尽可能大。