欢迎转载，作者：Ling，注明出处：机器学习：原理简明教程03-k近邻法

参考：《统计学习方法》

一句话概括：在训练数据中找到最邻近的K个实例，投票决定属于哪类，其中为了避免每次要全部求距离，提出了KD Tree，就是不断以不同维度进行空间划分，找到叶子，回溯求最短距离。

k近邻法：

• 基本分类与回归
• 输入为实例的特征向量，对应于特征空间的点，输出为实例类别，可取多类
• 三要素：K值选择，距离度量以及分类决策规则

• 1968年由Cover和 Hart提出

• 一种实现方法：kd tree用于计算最近点

k近邻算法

K近邻法没有显式的学习过程.

k近邻模型

k 近邻法使用的模型实际上对应于对特征空间的划分. 模型由三个基本要素—

距离度量, K值的选择和分类决策规则决定.

模型

距离度量:

    特征空间中两个实例点的距离是两个实例点相似程度的反映. K 近邻模型的特

征空间一般是n维实数向量空间Rn.  使用的距离是欧氏距离, 但也可以是其他距离,

如更一般的距离 (Lp distance) 或 Minkowski距离（Minkowski distance).

实例：

k值的选择

k较小，容易被噪声影响，发生过拟合。

k较大，较远的训练实例也会对预测起作用，容易发生错误。

分类决策规则

k近邻法的实现：kd树

    算法核心在于怎么快速搜索k个近邻出来，朴素做法是线性扫描，不可取，这里介绍的方法是kd树。

构造kd树：实际上就是依次以每个轴的中位点进行划分,直到不可划分

实例：

搜索kd树 ：实际上就是先从根起，依次与s比距离，找到最近的点，直到叶子节点，然后回退，如果

    下面介绍如何利用kd树进行k近邻搜索. 可以看到，利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量. 这里以最近邻为例加以叙述，同样的方法可以应用到k近邻.

实例：

来个自己写的实例理解构建树和搜索过程：