K-近邻法

内容来源于李航博士《统计学习方法》

一、k近邻算法

什么是k近邻

k近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

工作原理

• 存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。
• 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
• 一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类

特点
优点
 精度高
 对异常值不敏感
 无数据输入假定
缺点
 计算复杂度高
 空间复杂度高
 适用数据范围
 数值型和标称型

一般流程

• 收集数据：可以使用任何方法
• 准备数据：距离计算所需要的数值，最后是结构化的数据格式。
• 分析数据：可以使用任何方法
• 训练算法： （此步骤kNN）中不适用
• 测试算法：计算错误率
• 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

二、k近邻模型

k近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。
模型
k近邻法中，当训练集、距离度量（如欧氏距离）、k值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。这一事实从最近邻算法中可以看得很清楚。

特征空间中，对每个训练实例点ix，距离该点比其他点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。最近邻法将实例ix的类iy作为其单元中所有点的类标记（class label）。这样，每个单元的实例点的类别是确定的。

距离度量

k 值的选择
如果选择较小的K值

• “学习”的近似误差（approximation error)会减小，但“学习”的估计误差（estimation error) 会增大，
  噪声敏感
• K值的减小就意味着整体模型变得复杂，容易发生过拟合.

如果选择较大的K值，

• 减少学习的估计误差，但缺点是学习的近似误差会增大.
• K值的增大 就意味着整体的模型变得简单.

分类决策规则

三、k近邻的实现

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。

k近邻法最简单的实现方法是线性扫描（linear scan）。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。