度量学习(1)KNN

一、什么是KNN【KD树 + SIFT+BBF算法】

1.1 KNN的通俗解释

何谓K近邻算法,即K-Nearest Neighbor algorithm,简称KNN算法,单从名字来猜想,可以简单粗暴的认为是:K个最近的邻居,当K=1时,算法便成了最近邻算法,即寻找最近的那个邻居。

用官方的话来说,所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居),这K个实例的多数属于某个类,就把该输入实例分类到这个类中。

img

img

如上图所示,有两类不同的样本数据,分别用蓝色的小正方形和红色的小三角形表示,而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说,现在,我们不知道中间那个绿色的数据是从属于哪一类(蓝色小正方形or红色小三角形),KNN就是解决这个问题的。

如果K=3,绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形,少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于红色的三角形一类。

如果K=5,绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形,还是少数从属于多数,基于统计的方法,判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到,当无法判定当前待分类点是从属于已知分类中的哪一类时,我们可以依据统计学的理论看它所处的位置特征,衡量它周围邻居的权重,而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

1.2 近邻的距离度量

我们看到,K近邻算法的核心在于找到实例点的邻居,这个时候,问题就接踵而至了,如何找到邻居,邻居的判定标准是什么,用什么来度量。这一系列问题便是下面要讲的距离度量表示法。

有哪些距离度量的表示法(普及知识点,可以跳过):

1.2.1 欧式距离

欧氏距离, 最常见的两点之间或多点之间的距离表示法, 又称之为欧几里得度量, 它定义于欧几里得空间中, 如点 \(x=(x 1, \ldots, x n)\)\(y=(y 1, \ldots, y n)\) 之间的距离为: \[ d(x, y)=\sqrt{\left(x_1-y_1\right)^2+\left(x_2-y_2\right)^2+\ldots+\left(x_n-y_n\right)^2}=\sqrt{\sum_{i=1}^n\left(x_i-y_i\right)^2} \] 二维平面上两点 \(a(x 1, y 1)\)\(b(x 2, y 2)\) 间的欧氏距离: \[ d_{12}=\sqrt{\left(x_1-x_2\right)^2+\left(y_1-y_2\right)^2} \] 三维空间两点 \(a(x 1, y 1, z 1)\)\(b(x 2, y 2, z 2)\) 间的欧氏距离: \[ d_{12}=\sqrt{\left(x_1-x_2\right)^2+\left(y_1-y_2\right)^2+\left(z_1-z_2\right)^2} \] 两个n维向量 \(a(x 11, \times 12, \ldots, x 1 n)\)\(b(\times 21, \times 22, \ldots, \times 2 n)\) 间的欧氏距离: \[ d_{12}=\sqrt{\sum_{k=1}^n\left(x_{1 k}-x_{2 k}\right)^2} \] 也可以用表示成向量运算的形式:

1.2.2 曼哈顿距离

曼哈顿距离, 我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离, 也就是在欧几里得空间的固定 直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上, 坐标 \((x 1, y 1)\) 的点P1与坐标 \((\mathrm{x} 2, \mathrm{y} 2)\) 的点P2的曼哈顿距离为: \(\left|x_1-x_2\right|+\left|y_1-y_2\right|\), 要注意的是, 曼哈顿距离依赖座标系统的转度, 而非系统在座标轴上的平移或映射。

通俗来讲, 想象你在曼哈顿要从一个十字路口开车到另外一个十字路口, 驾驶距离是两点间的直线距离吗? 显 然不是, 除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”, 此即曼哈顿距离名称的来源, 同时, 曼 哈顿距离也称为城市街区距离(City Block distance)。

二维平面两点 \(a(x 1, y 1)\)\(b(x 2, y 2)\) 间的曼哈顿距离 \[ d_{12}=\left|x_1-x_2\right|+\left|y_1-y_2\right| \] 两个 \(n\) 维向量 \(a(x 11, x 12, \ldots, x 1 n)\)\(b(x 21, x 22, \ldots, x 2 n)\) 间的曼哈顿距离 \[ d_{12}=\sum_{k=1}^n\left|x_{1 k}-x_{2 k}\right| \]

1.2.3 切比雪夫距离

切比雪夫距离, 若二个向量或二个点 \(\mathrm{p} 、\) and \(\mathrm{q}\), 其座标分别为 \(\mathrm{P}\)\(\mathrm{qi}\), 则两者之间的切比雪夫距离定义如 下: \(D_{C h e b y s h e v}(p, q)=\max _i\left(\left|p_i-q_i\right|\right)\)

这也等于以下Lp度量的极值: \(\lim _{x \rightarrow \infty}\left(\sum_{i=1}^n\left|p_i-q_i\right|^k\right)^{1 / k}\), 因此切比雪夫距离也称为 \(\infty\) 度量。

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

在平面几何中, 若二点 \(\mathrm{p} \mathrm{q}\) 的直角坐标系坐标为 \((x 1, y 1)\)\((x 2, y 2)\), 则切比雪夫距离为: \(D_{C h e s s}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right)\)

玩过国际象棋的朋友或许知道,国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1) 走到格子(x2,y2)最少需要多少步? 。你会发现最少步数总是 \(\max (|x 2-x 1| ,|y 2-y 1|)\) 步 。有一种类似的 一种距离度量方法叫切比雪夫距离。

二维平面两点 \(a(x 1, y 1)\)\(b(x 2, y 2)\) 间的切比雪夫距离 : \[ d_{12}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right) \] 两个 \(n\) 维向量 \(a(x 11, x 12, \ldots, x 1 n)\)\(b(x 21, x 22, \ldots, x 2 n)\) 间的切比雪夫距离 : \[ d_{12}=\max _i\left(\left|x_{1 i}-x_{2 i}\right|\right) \]

简单说来,各种“距离”的应用场景简单概括为:

  • 空间:欧氏距离
  • 路径:曼哈顿距离,国际象棋国王:切比雪夫距离
  • 以上三种的统一形式:闵可夫斯基距离,
  • 加权:标准化欧氏距离,
  • 排除量纲和依存:马氏距离,
  • 向量差距:夹角余弦,
  • 编码差别:汉明距离
  • 集合近似度:杰卡德类似系数与距离,
  • 相关:相关系数与相关距离。

1.3 K值选择

  1. 如果选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合;
  2. 如果选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。
  3. K=N,则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的累,模型过于简单,忽略了训练实例中大量有用信息。

在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。

1.4 KNN最近邻分类算法的过程

  1. 计算测试样本和训练样本中每个样本点的距离(常见的距离度量有欧式距离,马氏距离等);
  2. 对上面所有的距离值进行排序;
  3. 选前 k 个最小距离的样本;
  4. 根据这 k 个样本的标签进行投票,得到最后的分类类别;

关于KNN的一些问题

  1. 在k-means或kNN,我们是用欧氏距离来计算最近的邻居之间的距离。为什么不用曼哈顿距离

    答:我们不用曼哈顿距离,因为它只计算水平或垂直距离,有维度的限制。另一方面,欧式距离可用于任何空间的距离计算问题。因为,数据点可以存在于任何空间,欧氏距离是更可行的选择。例如:想象一下国际象棋棋盘,象或车所做的移动是由曼哈顿距离计算的,因为它们是在各自的水平和垂直方向的运动。

  2. KD-Tree相比KNN来进行快速图像特征比对的好处在哪里?

    答:极大的节约了时间成本.点线距离如果 > 最小点,无需回溯上一层,如果<,则再上一层寻找。

参考文献

  1. KNN与KD树
  2. 【数学】kd 树算法之详细篇 - 椰了的文章 - 知乎
  3. KNN是生成式模型还是判别式的,为什么? - 风控算法小白的回答 - 知乎