k近邻法

 k近邻算法

输入：训练数据集；实例特征向量x；

输出：实例x所属的类y。

（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作Nk(x)；

（2）在x的邻域中根据分类决策规则决定x的类别y。

k近邻法的特殊情况是 k=1 的情形，称为最近邻算法。对于输入的实例点x，最近邻法将训练集中与x最邻近点的类作为x的类。

k近邻没有显式的学习过程。

3.2 k近邻模型

k近邻模型使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

每个训练实例拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

最近邻法将实例xi的类yi作为其单元中所有点的类标记。

距离有：欧式距离，Lp距离、Minkowski距离。

k值的选择会对k近邻法的结果产生重大影响。

在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

 

3.2.4 分类决策规则

规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则等价于 经验缝线最小化。

 

3.3 k近邻法的实现：kd树

k近邻法最简单的实现方法是线性扫描。

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。其中一种方法就是kd树方法。

3.3.1 构造kd树

 

 

算法3.2 （构造平衡kd树）