82.k最近邻算法

k最近邻算法

k 最近邻算法（kNN）是一种用于分类和回归的非参数统计方法，由美国统计学家伊芙琳·费克斯和小约瑟夫·霍奇斯于 1951 年提出。kNN 算法的原理是从历史数据中找到 $\small{k}$ 个跟新输入的实例最邻近的实例，根据它们中的多数所属的类别来对新实例进行分类或者输出新实例的目标值，这种算法我们在前面已经为大家做了简单的展示。与主流的机器学习算法不同，k 最近邻算法没有显式的学习训练过程，它用的是“近朱者赤，近墨者黑”这样一种简单朴素的思想来实现分类或回归。k 最近邻算法有两个关键问题，第一个是 $\small{k}$ 值如何选择，即用多少个最近邻来判定新实例所属的类别或确定其目标值；第二个是如何判定两个实例是近还是远，这里就涉及到度量距离的问题。

距离的度量

我们可以用距离（distance）来衡量特征空间中两个实例之间的相似度，常用的距离度量包括闵氏距离、马氏距离、余弦距离、编辑距离等。闵氏距离全称闵可夫斯基距离（Minkowski Distance），对于两个 $\small{n}$ 维向量 $\small{\mathbf{x}=(x_{1}, x_{2}, \cdots, x_{n})}$ 和 $\small{\mathbf{y}=(y_{1}, y_{2}, \cdots, y_{n})}$ ，它们之间的距离可以定义为：

$$ d(\mathbf{x}, \mathbf{y}) = (\sum_{i=1}^{n}{\vert x_{i} - y_{i} \rvert}^{p})^{\frac{1}{p}} $$

其中， $\small{p \ge 1}$ ，虽然 $\small{p \lt 1}$ 可以计算，但不再严格满足距离的定义，通常不被视为真正的距离。

当 $\small{p = 1}$ 时，闵氏距离即曼哈顿距离：

$$ d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} \lvert x_{i} - y_{i} \rvert $$

当 $\small{p = 2}$ 时，闵氏距离即欧几里得距离：

$$ d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n}(x_{i} - y_{i})^{2}} $$

当 $\small{p \to \infty}$ 时，闵氏距离即切比雪夫距离：

$$ d(\mathbf{x}, \mathbf{y}) = \underset{i}{max}(\lvert x_{i} - y_{i} \rvert) $$

其他的距离度量方式我们等用到的时候再为大家介绍。在使用 k 最近邻算法做分类时，我们的数据集通常都是数值型数据，此时直接使用欧几里得距离是一个不错的选择。

数据集介绍

接下来为大家隆重介绍一下我们后续会使用到的一个重要的数据集——鸢尾花数据集（iris dataset）。鸢尾花数据集是机器学习领域中最著名、最经典的数据集之一，由植物学家 Edgar S. Anderson 在加拿大魁北克加斯帕半岛采集，由英国统计学家 Ronald A. Fisher 于 1936 年在他的论文*《The Use of Multiple Measurements in Taxonomic Problems》*中首次引入，被广泛用于机器学习算法的入门和实验。