李航机器学习 | (4) 统计学习方法(第2版)笔记 --- k近邻法
k近邻(k-nearest neighbor,k-NN)是一种基本分类与回归方法，本博客只谈论分类问题中的k近邻法。
k近邻法的输入是实例的特征向量，对应特征空间中的点，输出为实例的类别，可以取多类。
k近邻法假定给定一个训练数据集，其中的实例类别已确定。分类时，对于新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测（即，k个最近邻训练实例中哪个类别的实例最多，就把新实例预测为这个类别）。因此，k近邻法不具有显式的学习过程，也就是说k近邻法与一般的机器学习方法不同，他训练阶段几乎不花费时间，主要是对训练实例的存储，时间主要花费在测试阶段。
k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的"模型"。
k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。
kd树是k近邻法的一种比较高效的实现方法。
目录
1. k近邻算法
k近邻的思想很简单：给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最近的前k个实例，这k个实例中多数属于哪个类，就把该输入实例分为哪个类。
- k近邻算法
输入：训练数据集 ,
为训练实例特征向量，
为训练实例类别；新实例特征向量x。
输出：新实例x所属的类别y。
1）根据给定的距离度量，在T中找到与x最近的k个点，涵盖这k个点的x的邻域记为.
2）在中根据分类决策规则(如多数表决)决定x的类别y。
其中I为指示函数，时为1，否则为0.
当k=1时，称为最近邻算法，对输入的实例点(特征向量)x，把训练集中与x最近邻的点的类别作为x的类别。
k近邻法的简单说明：
对于任何一个统计学习方法来说，都需要有一个训练数据集，图中所有蓝色正方形和红色三角形代表训练集的数据，绿色的圆形表示要预测的数据，在图中，输入变量是一个二维向量(点的坐标)，颜色对应了输出变量，训练集中有 11个实例，判断绿色圆形属于哪一类(红色或蓝色)。如果k=3 (实线圆圈)它被分配给第二 类，因为有2个三角形和只有1个正方形在内侧圆圈之内。如果 k=5(虚线圆圈)它被分配到第一类(3个正方形与2个三角形在外侧圆圈之内)。
2. k近邻模型
k近邻法使用的模型实际上对应于对特征空间的划分。
- 模型
当k近邻法中的训练集和三要素：距离度量、k值和分类决策规则确定后，对于任何一个新的输入实例，它所属的类别就唯一确定了。相当于上述要素把特征空间划分为一些子空间，确定子空间中每个点所属的类别。
在特征空间中，对于每个训练实例,距离该点比其他点更近的所有点组成的区域称为单元(cell).每个训练实例点都拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。最近邻算法将实例
的类别
作为其单元内所有实例点的类别，因此，每个单元中实例点的类别是确定的。
下图是2维特征空间中一个划分（k近邻法的模型对应特征空间的一个划分）的例子：
- 距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映。
设特征空间是n维实数向量空间
,
,
,
的
距离定义为：
当p=2时，为欧氏距离（Euclidean distance）:
当p=1时，为曼哈顿距离（Manhattan distance）:
当p=时,他是各个坐标距离的最大值：
距离间的关系：
上图中，取原点为基准点，和该点距离相等的点(
).当取p=1时，在正方形边上的点和原点的距离相等
，这
就是1-范数;当取p=2时，在圆形边上的点和原点的距离相等，这就是2-范数;当取
时，在最外面正方形边上的点和原点的距离相等
，这就是
-范数;
不同的距离度量所确定的最近邻点是不同的，例如：
- k值的选择
当k值选择较小时，相当于用较小邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例接近或相似的训练实例才会对预测结果起作用。缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰好是噪声，预测就会出错。即k值的减小意味着整体模型变得复杂，容易发生过拟合。
当k值选择较大时，相当于用较大邻域中的训练实例进行预测。优点是可以减小学习的估计误差，缺点是学习的近似误差会增大。这是与输入实例较远或不相似的训练实例也会对预测起作用，使预测发生错误。k值的增大意味着整体模型变得简单。
若k=N，那么无论输入的实例是什么，都会简单的预测为训练实例中出现最多的类别。此时，模型将过于简单，完全忽略了训练实例中的大量有用信息，不可取。
实际应用中，k一般取较小的值。一般使用交叉验证的方法，将训练数据集分成m份，每次取其中的m-1份进行训练，剩下的一份进行验证，验证预测实例的类别和真实类别相比的准确率，并对m次验证取平均。通过比较取不同k值时的准确率，选择在验证集上平均准确率最高时对应的k值。
- 分类决策规则
k近邻法的分类决策规则一般是多数表决，即由输入实例的k个邻近的训练实例中的多数类别决定输入实例的类别。
多数表决规则的解释如下：如果分类的损失函数是0-1损失函数，分类函数为:
那么误分类的概率为：
对给定的实例,其最近邻的k个训练实例点构成的集合
,如果涵盖
的区域的类别是
（truth）,那么误分类率为：
要使误分类率最小即经验风险最小，就要使最大，所以多数表决规则（选择k个最近邻训练实例中出现最多的类别，作为新实例的类别）等价于经验风险最小化。
例如，之前图片中的那个例子：取k=3（实线圆圈），用唯一的类别给该区域内的点打标签，假如标签为红色，考察训练集上的损失值，易得,以上为把区域中的点都判定为红色的损失。当判定为蓝色时，损失为
,取损失值最小的类别，即把区域中的点判定为红色类别。因为区域中大多数训练实例是红色，也就是说多数表决规则等价于经验风险最小化。
3. k近邻法的实现：kd树
实现k近邻法时，主要的问题是如果对训练集进行快速k近邻搜索。这点在特征空间维数大以及训练数据容量大时尤其重要。
k近邻法的最简单实现是线性扫描。这时要计算输入实例与每一个训练实例的距离，当训练集很大时，计算非常耗时，是不可行的。
为提高k近邻搜索的效率，可以考虑用特殊的结构存储训练数据，减少计算距离的次数，如kd树。
- 构造平衡kd树
平衡kd树，也就是选定坐标轴上的中位数（一组数据按大小顺序排列起来，处于中间位置的一个数或最中间两个数的平均值）作为切分点。注意平衡kd树搜索时的效率未必是最优的。
输入：k维空间数据集
输出：kd树
1）开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域。
选择作为坐标轴，以T中所有实例的
坐标的中位数作为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点与坐标轴
垂直的超平面实现。
由根结点生成深度为1的左右子结点：左子结点对应坐标小于切分点的子区域，右子结点对应坐标
大于切分点的子区域。
将落在切分超平面上的实例点保存在根结点。
2）重复：对深度为j的结点，选择为切分的坐标轴，l = j mod(k) +1 ,以该结点的区域中所有实例的
坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴
垂直的超平面实现。
由该结点生成深度j+1的左右子结点：左子结点对应坐标小于切分点的子区域，右子结点对应坐标
大于切分点的子区域。
将落在切分超平面上的实例点保存在该结点。
3）直到两个子区域没有实例存在时停止。从而形成kd树的区域划分。
例题：
注意第一次切分时的中位数为6，但是
=6上没有数据点，所以选择
=7.
- 搜索kd树
用kd树进行k近邻搜索，可以省去对大部分数据点的搜索，从而减少搜索的计算量。这里以最近邻为例进行叙述，同样的方法可以应用到k近邻。
输入：已构造的kd树，目标点x
输出：x的最近邻
1）在kd树中找到包含目标点x的叶结点：从根结点出发，递归的向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
2）以此叶结点为当前最近点。
3）递归的向上回退，在每个结点进行以下操作：
a) 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为当前最近点。
b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近 的点。具体地，检查另一子结点对应的区域是否有以目标点为球心、以目标点与当前最近点的距离为半径的超球体相交。如果相交，可能在另一子结点对应的区域内存在与目标点更近的点，移动到另一子结点。接着，递归地进行最近邻搜索。如果不相交，则向上回退。
4）当回退到根结点时，搜索结束。最后的当前最近点即为x的最近邻点。
如果实例点是随机分布的，kd树搜索的平均计算复杂度为O(log N),N是训练实例数。kd树更适用于训练实例数N远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，他的效率会迅速下降，几乎接近于线性扫描。
例题：
4. 小结
- k近邻法是基本且简单的分类与回归方法。k近邻法的基本做法：对给定训练实例点和输入实例点，首先确定与输入实例点最近的k个训练实例点，然后利用这k个训练实例点的类的多数来预测输入实例点的类。
- k近邻模型对应于基于训练集对特征空间的一个划分。k近邻法中，当训练集、距离度量、k值集分类决策规则确定后，其结果唯一确定。
- k近邻法三要素：距离度量、k值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的Lp距离。k值较小时，k近邻模型更复杂；k值较大时，k近邻模型更简单。k值的选择反映了对近似误差和估计误差之间的权衡，通常用交叉验证选择最优的k。常用的分类决策规则是多数表决，对应于经验风险最小化。
- k近邻法的实现需要考虑如何快速搜索k个最近邻点。kd树是一种便于对k维空间中的数据进行快速检索的数据结构。kd树是二叉树，表示对k维空间的一个划分，其每个结点对应于k维空间划分中的一个超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。
- 感知机和最近邻介绍的都是分类问题的方法，这两种方法都可以用于解决二分类问题，针对输入变量是连续变量。下面对比两种方法的不同:感知机模型，需要使用所有的训练集数据，找到一个可以分割两类的超平面，并要求数据是线性可分的，当然对于数据不是线性可分时，也有相应的感知机算法。当找到这个超平面，训练数据集就可以不再需要了，仅根据该超平面，就可以判定新实例的类别。总的来说，感知机模型用全部数据找到了一个全局的结构，保留这个结构并遗弃训练集数据，用该结构预测新实例；k近邻算法，并没有用全部数据寻找一个结构，所用的是一个局部的信息，所找的是要预测的这个实例离该点最近的那些点，然后使用这些实例进行预测。当使用局部信息时，需要存储全部的训练数据集。要如何在这两种算法中选择呢?当数据具有线性可分结构时，用感知机模型更好，因为计算简单，但当数据不是线性可分时，只能使用预测点周围的信息(局部信息)进行分类判定，此时k近邻算法更好，该算法对整个数据集的结构(即模型的结构)没有那么强的假设。