k近邻法/k-NN

k近邻法可以算是机器学习算法中最古老的方法之一，它在1968年被 Cover 和 Hart 提出。除此之外，它也是最容易描述和理解的机器学习算法之一。

算法释义

给定一个已标注输出的训练数据集，对于新的输入实例 x，在训练集中寻找 k 个与其最近邻的实例，根据这 k 个训练实例的类别和分类决策规则对实例 x 做分类。

算法步骤：

输入：训练数据集 T ，输入实例 x输出：实例 x 所属的类 y(1) 找近邻：根据给定的距离度量，在训练集 T 中寻找与实例 x 最近的 k 个近邻(2) 做分类：根据分类决策规则决定 x 的类别 y

重要概念

从 k-NN 的释义中不难看出，该模型主要由三个基本要素构成：用于描述距离远近的距离度量，k 值选择和分类决策规则。换句话说，只要k-NN模型中的这三个要素确定了，对于固定的训练集，任何一个新的输入实例，它所属的类唯一地确定。

距离度量

顾名思义，就是指特征空间中两个实例点相似程度的反应，k-NN 中一般使用欧氏距离，但是使用距离度量也是可行的，比如说更一般的 Lp 距离：$$ Lp(xi, xj) = \left(\sum^ { | xi^{(l)} - xj^{(l)} |^p } \right)^\frac $$

这里当 p = 1 时，称之为曼哈顿距离，即：$$ L1(xi, xj) = \sum^ { | xi^{(l)} - xj^{(l)} | } $$

当 p = 2 时，称之为欧氏距离，即：$$ L2(xi, xj) = \left(\sum^ { | xi^{(l)} - xj^{(l)} |^2 } \right)^\frac $$

当 p = ∞ 时，它是各个维度上距离的最大值，即：$$ L∞(xi, xj) = \maxl { | xi^{(l)} - xj^{(l)} | } $$

P.S. 距离度量的选择在聚类算法中更为重要，因此之后还将重点介绍距离度量。

k 值选择

k 值的选择对 k-NN 算法的结果影响很大，我们设想两个极端：1. 当 k = N (训练集样本总数) 时，这时无论输入实例是什么，它们得到的近邻是一样的，所以都会被归为同一个类，这时模型过于简单，很容易造成欠拟合，也就是 Ein 会很大；2. 当 k = 1 时（称作最近邻算法），这时特征空间的划分会很复杂，因为对于任何一个实输入实例，它的分类结果都只和与它最近的那个训练实例点有关，显然，过于复杂的模型会造成 VC 维的增大，从而很容易导致过拟合。那么如何选择 k 这个超参数呢？经验上，一般先取一个较小的 k 值，然后通过交叉验证法来选取合适的 k 值。

分类决策规则

k-NN 中运用最广的分类决策规则是多数表决法（等价于经验风险最小化），即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类：$$ y = arg \max\sum，i = 1,2,...,N; j = 1,2,...,N $$

经典实现 —— kd 树

从 k-NN 的算法释义中不难看出，有别于其他的机器学习算法，k-NN 算法不存在明显的“学习”过程，其在训练阶段仅仅是把训练样本保存起来，训练开销为零，但其在判别阶段由于需要计算输入实例和每个样本的距离，因此计算开销很大，这种机器学习方式称作懒惰学习。当训练集很大时，这种方法的计算是非常耗时的，这显然是不可行的，因此为了减少计算距离的次数，可以考虑在存储阶段对训练集进行特殊的处理，从而提高 k 近邻的搜索效率，这其中就有一种比较经典的方法，被称作 kd 树。

构造 kd 树

pass

搜索 kd 树

pass

参考文献

《统计学习方法》，李航《机器学习》，周志华