{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "在前一节中，我们学习了 kNN 算法就是要找到距离输入样本最近的 k 个样本，然后再通过多数表决规则进行分类。那么这里的距离应该如何定义？\n", "\n", "我们在中学时就学过怎么计算平面几何中（二维空间）两点之间的距离：\n", "\n", "

\n", "\n", "如上图所示，点 $P_1(x_1, y_1)$ 和点 $P_2(x_2, y_2)$ 之间的距离可以定义为：\n", "\n", "$$\n", "d = \\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\n", "$$\n", "\n", "在立体几何中（三维空间）两点之间的距离为：\n", "\n", "$$\n", "d = \\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2}\n", "$$\n", "\n", "这其实就是 **欧氏距离**（Euclidean Distance，亦称 **欧几里得距离**）或 **毕达哥拉斯距离**（Pythagorean Distince），它的更一般形式可以扩展到 n 维空间：\n", "\n", "$$\n", "d = \\sqrt{\\sum_{k=1}^n (x_{1k} - x_{2k})^2}\n", "$$\n", "\n", "这是最基本的距离度量方法，除此之外，这一节还将介绍几种其他的距离度量方法。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 曼哈顿距离\n", "\n", "**曼哈顿距离**（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所提出的，它表示在欧式空间中的两点所形成的线段对轴产生的投影的距离总和。如下图所示，绿色代表两点之间的直线距离，也就是欧式距离，红色则代表曼哈顿距离，蓝色和橙色代表等价的曼哈顿距离。\n", "\n", "

\n", "\n", "曼哈顿是美国纽约市最小的一个行政区，这里的街道就像棋盘网格一样，类似于上图，假设要从 A 点开车去 B 点，只能沿着街道行走，这就是曼哈顿距离这个名称的由来。所以它也被称为 **城市街区距离**（City Block Distance），它的计算公式如下：\n", "\n", "$$\n", "d = \\sum_{k=1}^n |x_{1k} - x_{2k}|\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 切比雪夫距离\n", "\n", "**切比雪夫距离**（Chebyshev Distance）起源于国际象棋中国王的走法，玩过国际象棋的朋友都知道，国王既能横着走，又能斜着走，走一步能够移动到相邻的 8 个方格中的任意一个，那么它从点 $P_1(x_1, y_1)$ 走到点 $P_2(x_2, y_2)$ 最少需要几步呢？如下图所示：\n", "\n", "

\n", "\n", "很显然：\n", "\n", "$$\n", "d = max(|x_1-x_2|, y_1-y_2)\n", "$$\n", "\n", "这就是切比雪夫距离，或者叫做棋盘距离。\n", "\n", "// TODO 切比雪夫距离和曼哈顿距离的转换：https://www.biaodianfu.com/chebyshev-distance.html" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 闵可夫斯基距离\n", "\n", "**闵可夫斯基距离**（Minkowski Distance）又叫 **闵氏距离**，它并不是一种距离，而是一组距离的定义：\n", "\n", "$$\n", "d = \\sqrt[p]{\\sum_{k=1}^n |x_{1k} - x_{2k}|^p}\n", "$$\n", "\n", "可以看出：\n", "\n", "* 当 p = 1 时，就是曼哈顿距离\n", "* 当 p = 2 时，就是欧式距离\n", "* 当 $p \\to \\infty$ 时，就是切比雪夫距离" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 标准化欧式距离\n", "\n", "闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。假设在平面坐标系中有三个点：$A(180,50)$、$B(190,50)$、$C(180,60)$ 分别代表三个人的身高和体重特征，根据闵氏距离的定义，可以计算出 AB 之间的距离和 AC 之间的距离是相等的，但是很显然，身高上的 10cm 和体重上的 10kg 并不能划等号。这就是闵氏距离的缺点：它忽略了每个分量的单位，也就是量纲（scale），而且它没有考虑每个分量的分布（期望、方差等）可能是不同的。\n", "\n", "**标准化欧氏距离**（Standardized Euclidean Distance）就是针对闵氏距离的缺点而提出的改进方案。假设样本集 X 的数学期望或均值（mean）为 m，标准差（standard deviation）为 s，那么可以将 X 标准化为：\n", "\n", "$$\n", "X^* = \\frac{X - m}{s}\n", "$$\n", "\n", "比如上面的 ABC 三个人，我们计算出身高的均值和标准差：\n", "\n", "$$\n", "\\begin{align}\n", "m_{height} &= \\frac{180+190+180}{3} = 183.33 \\\\\n", "m_{weight} &= \\frac{50+50+60}{3} = 53.33 \\\\\n", "s^2_{height} &= \\frac{(180-m_{height})^2+(190-m_{height})^2+(180-m_{height})^2}{3} = 22.22 \\\\\n", "s^2_{weight} &= \\frac{(50-m_{weight})^2+(50-m_{weight})^2+(60-m_{weight})^2}{3} = 22.22 \\\\\n", "s_{height} &= \\sqrt{s^2_{height}} = 4.71 \\\\\n", "s_{weight} &= \\sqrt{s^2_{weight}} = 4.71 \\\\\n", "\\end{align}\n", "$$\n", "\n", "将 ABC 标准化：\n", "\n", "$$\n", "\\begin{align}\n", "A^* &= (\\frac{180-m_{height}}{s_{height}}, \\frac{50-m_{weight}}{s_{weight}}) = (-0.707, -0.707) \\\\\n", "B^* &= (\\frac{190-m_{height}}{s_{height}}, \\frac{50-m_{weight}}{s_{weight}}) = (1.416, -0.707) \\\\\n", "C^* &= (\\frac{180-m_{height}}{s_{height}}, \\frac{60-m_{weight}}{s_{weight}}) = (-0.707, 1.416) \\\\\n", "\\end{align}\n", "$$\n", "\n", "标准化后的 $X^*$ 数学期望为 0，方差为 1。然后就可以计算标准化后的 $A^*B^*$ 和 $A^*C^*$ 之间的距离。这里计算出来的结果还是相等，这是因为样本数据较少，还不足以反映各个分量的分布情况。\n", "\n", "经过简单的推导可以得到标准化欧式距离的公式：\n", "\n", "$$\n", "d = \\sqrt{\\sum_{k=1}^n (\\frac{x_{1k}-x_{2k}}{s_k})^2}\n", "= \\sqrt{\\sum_{k=1}^n \\frac{1}{s_k^2} (x_{1k}-x_{2k})^2}\n", "$$\n", "\n", "其中标准差的平方 $s^2$ 代表方差，如果将方差的倒数看成一个权重，这个公式可以看成是一种 **加权欧式距离**（Weighted Euclidean Distance）。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 马哈拉诺比斯距离\n", "\n", "**马哈拉诺比斯距离**（Mahalanobis distance）简称马氏距离，它考虑各个分量（特征）之间的相关性，和各个分量的尺度无关，马氏距离越小，相似度越大。\n", "\n", "给定样本集合 $X = (x_{ij})_{m \\times n}$，其协方差矩阵记作 $S$，则样本 $x_i$ 和 $x_j$ 之间的马氏距离定义为：\n", "\n", "$$\n", "d_{ij} = \\big [ (x_i-x_j)^T S^{-1} (x_i-x_j) \\big ] ^{1/2}\n", "$$\n", "\n", "其中，\n", "\n", "$$\n", "\\begin{align}\n", "x_i = (x_{1i}, x_{2i}, ..., x_{mi})^T \\\\\n", "x_j = (x_{1j}, x_{2j}, ..., x_{mj})^T \\\\\n", "\\end{align}\n", "$$\n", "\n", "当 $S$ 为单位矩阵时，即样本数据的各个分量互相独立，且各个分量的方差为 1 时，马氏距离就是欧式距离。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 相关系数\n", "\n", "样本之间的相似度也可以用 **相关系数**（correlation coefficient）来表示，相关系数的绝对值越接近 1，表示样本越相似，越接近 0，表示样本越不相似。\n", "\n", "样本 X 和 Y 的相关系数定义如下：\n", "\n", "$$\n", "Corr(X, Y) = \\frac {Cov(X, Y)}{\\sqrt{Var(X)} \\sqrt{Var(Y)}} = \\frac {Cov(X, Y)}{\\delta(X)\\delta(Y)}\n", "$$\n", "\n", "其中，$Cov(X, Y)$ 表示 X 和 Y 的协方差：\n", "\n", "$$\n", "Cov(X, Y) = E \\Big ( \\big [ X-E(X) \\big ] \\big [ Y-E(Y) \\big ] \\Big )\n", "$$\n", "\n", "$E(X)$ 和 $E(Y)$ 分别表示 X 和 Y 的数学期望，$X-E(X)$ 和 $Y-E(Y)$ 分别表示 X 和 Y 的偏差，协方差也就是 X 的偏差和 Y 的偏差乘积的数学期望。\n", "\n", "$Var(X)$ 和 $Var(Y)$ 表示 X 和 Y 的方差，$\\delta(X)$ 和 $\\delta(Y)$ 表示 X 和 Y 的标准差。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 余弦相似度\n", "\n", "**余弦相似度**（Cosine similarity）用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小，相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。两个向量方向相同时，余弦相似度的值为1；两个向量夹角为90°时，余弦相似度的值为0；两个向量方向相反时，余弦相似度的值为-1。\n", "\n", "余弦相似度通常用于信息检索领域，譬如给每个词赋予不同的维度，每个维度由一个向量表示，其各个维度上的值对应于该词在文档中出现的频率，通过余弦相似度可以计算出两篇文档在其主题方面的相似度。\n", "\n", "余弦相似度可以由 **欧几里得点积公式** 导出，根据欧几里得点积公式，两个向量的点积为：\n", "\n", "$$\n", "a \\cdot b = \\|a\\| \\|b\\| \\cos \\theta\n", "$$\n", "\n", "从而有：\n", "\n", "$$\n", "\\begin{align}\n", "similarity &= \\cos \\theta \\\\\n", "&= \\frac {a \\cdot b}{\\|a\\| \\|b\\|} \\\\\n", "&= \\frac {\\sum_{i=1}^n a_i \\times b_i} {\\sqrt{\\sum_{i=1}^n a_i^2} \\times \\sqrt{\\sum_{i=1}^n b_i^2}}\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 其他距离度量方法\n", "\n", "除此之外，还有很多其他的距离度量方法，包括：\n", "\n", "* 巴氏距离\n", "* 汉明距离\n", "* 杰卡德距离\n", "* 信息熵" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 参考\n", "\n", "1. [从K近邻算法、距离度量谈到KD树、SIFT+BBF算法](https://blog.csdn.net/v_JULY_v/article/details/8203674)\n", "2. [机器学习——几种距离度量方法比较](https://my.oschina.net/hunglish/blog/787596)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.1" } }, "nbformat": 4, "nbformat_minor": 2 }