机器学习算法：k近邻法（k-NN）
分类与回归算法，多分类。
三个基本要素：K值的选择，距离度量，分类决策规则。
1 k近邻算法（分类）
最近邻居分类器：在单个邻居的情况下（k=1），该方法将训练数据中与实例点x最接近的类别作为其类别。换句话说，在输入实例点x（特征向量）的情况下，在训练数据集中找到与之最接近的一个实例，并将其类别赋予给该输入实例点x。
k近邻法不涉及明显的学习过程。（"懒惰学习"：在训练阶段仅需存储训练样本，在接收测试样本后进行处理。）
1.1 k近邻模型
1.1.1 模型
在三要素确定的情况下，根据每个训练实例点
，对特征空间进行划分。
（对每个训练实例点
，距离该店比其他店更近的所有点组成的区域叫做单元）
1.1.2 三要素
1.1.2.1 距离度量
由不同距离度量所确定的最近邻点是不同的。
1.1.2.2 k值的选择
k值过小，模型越复杂，近似误差较小，估计误差增大。越易过拟合。
k值过大，模型越简单，近似误差越大，估计误差减小。
在应用中，k值一般取一个比较小的数值。
1.1.2.3 分类决策规则
常用多数投票法来确定输入实例所属类别；具体而言，在输入实例的所有k个最近邻训练实例中，属于同一类别的样本数量占多数。
误分类率：
为了将分类错误率降到最低水平，并使其等于经验损失的最低水平，多数投票规则实际上等同于实现了经验损失的最低化。
1.3 k近邻法的实现：kd树
如何对训练数据进行快速k近邻搜索？
（1）线性扫描：计算输入实例与每个训练实例的距离。不可行。
（2）kd树方法
1.3.1 构造kd树
kd树是二叉树，表示对k维空间的一个划分。
1.3.2 搜索kd树
假设实例点呈随机分布，则采用kd树进行搜索可获得平均时间复杂度为O(logN)的结果；相比于其他方法，在数据维度远小于实例数量的情况下（即当空间维数低于训练数据规模时），kd树算法表现出显著的优势。
当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。
2 k邻近算法（回归）
在回归算法中常用均值法来处理问题，在这k个样本中取其实际输出值的算术平均数作为预测结果。此外还可以根据样本间的远近程度来进行加权计算，在这种情况下离得较近的数据点会被赋予更高的权重。
参考文献：
【1】统计学习方法，李航
【2】机器学习，周志华