明可夫斯基距离

       在机器学习中，距离是一个非常形象并且常用的概念。在分类和聚类问题中，距离的作用尤为明显。除此之外，在回归问题，甚至自然语言处理问题上，距离也有其相应的应用。 
       除了距离之外，相似系数也是解决这一问题的方法之一，显而易见，距离和相似系数应该呈反比，距离越小越相似；距离越大越不同。距离主要是对不同的观测进行度量，相似系数主要是对不同的变量进行度量。但是，距离也可以衡量不同的变量，同理，相似系数也可以衡量不同的观测。 
       本文将介绍距离的定义，并详细介绍两种非常常用的距离：明可夫斯基距离和马氏距离。在后文中，我们将介绍相似系数。 
距离定义 
       设两个n维向量 $\vec{x} = (x_1,x_2,\cdots,x_n)^T$ 和 $\vec{y} = (y_1,y_2,\cdots,y_n)^T$ 为两个观测，其所定义的距离一般需要满足三个条件： 
非负性： $d(\vec{x},\vec{y}) ≥ 0$ ， $d(\vec{x},\vec{y}) = 0$ 当且仅当 $\vec{x} = \vec{y}$ 
对称性： $d(\vec{x},\vec{y}) = d(\vec{y},\vec{x})$ 
三角不等式：假设存在另一个n维向量 $\vec{z}$ ， $d(\vec{x},\vec{y}) ≤ d(\vec{x},\vec{z}) + d(\vec{z},\vec{y})$  
明可夫斯基距离 
       明可夫斯基距离是一类距离的总称。向量 $\vec{x}$ 和 $\vec{y}$ 之间的明可夫斯基距离定义为：
  $d(\vec{x},\vec{y}) = [\sum_{i=1}^{n}|x_i-y_i|^q]^{\frac{1}{q} }$ 其中 $q > 0$ 。 
       明可夫斯基距离有三种特殊且常见的形式： 
当 $q = 1$ 时， $d(\vec{x},\vec{y}) = \sum_{i=1}^{n}|x_i-y_i|$ ，称为绝对值距离，也被称为曼哈顿距离。
当 $q = 2$ 时， $d(\vec{x},\vec{y}) = [\sum_{i=1}^{n}|x_i-y_i|]^\frac{1}{2} = \sqrt{(\vec{x}-\vec{y})^T(\vec{x}-\vec{y})}$ ，称为欧式距离，也是最常用的一种距离。
当 $\infty$ ， $d(\vec{x},\vec{y}) = max_{1&lt;i&lt;n}|x_i - y_i|$ ，称为切比雪夫距离。 
       在明考夫斯基距离中， $q$ 值越大，其受（较大的）异常值影响就越厉害。可以发现当 $\infty$ 时，切比雪夫距离将完全由最大的异常值决定。同理，欧式距离比绝对值距离受异常值的影响程度更高。 
       明考夫斯基距离可以说是生活中最最常见的一种距离，到那时它有一个非常大的缺点，那就是它会受到单位和数据变异程度的不同的影响。 
       举一个简单的例子，如果我们要统计一个单位所有人身高、体重和年龄，那么在统计身高的时候，使用“m”做单位，那么大家身高的变化应该集中在1.55-1.85之间；但是如果使用“cm”做单位，那么身高的变化就应该集中在155-185之间。这两个单位造成的数据变异程度（方差）不同，从而使得身高这个变量在后期计算距离的时候重要程度不同。显然，变异性更大的变量应该占据更加重要的地位，在本例中，选择以“cm”做单位会使得身高变量的重要性提高。 
       为了解决这个问题，我们引入马氏距离。 
马氏距离 
向量 $\vec{x}$ 和 $\vec{y}$ 之间的马氏距离定义为：
  $d(\vec{x},\vec{y}) = \sqrt{(\vec{x}-\vec{y})^TS^{-1}(\vec{x}-\vec{y})}$ 其中， $S$ 代表 $\vec{x}$ 、 $\vec{y}$ 的协方差矩阵。 
使用马氏距离最大的好处在于避免了单位不同以及数据变异程度的不同对计算造成的影响。 
但是，马氏距离也有自己的缺点，协方差矩阵的计算在大规模数据中是困难的。尤其在聚类问题中，每一个类别中的观测都在不停变化导致协方差矩阵也在变化。