K近邻法

算法简介

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

模型由三个基本要素决定： 距离度量、K值的选择、分类决策规则。

距离度量

Lp距离定义

二维空间中p取不同值时，Lp=1的点的图形

K值的选择

K值过小，会对近邻的实例点非常敏感，容易发生过拟合；

K值过大，与输入实例较远的训练实例也会对预测起作用，如果k=N,则预测为训练实例最多的类，不可取。

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

分类决策规则

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

算法实现

构造kd树

以二维空间为例，给定数据集

1、X(1)轴中位数为7，以平面X(1)=7将空间分为左右两个子矩形（子节点）；

2、左矩形以X(2)=4分为两个子矩形，右矩形以X(2)=6分为两个子矩形；

3、如此递归，得到如下kd树。

搜索kd树

1、在kd树中找到包含点S的叶节点D，则最近邻点在以S为圆心通过D的园内；

2、返回父节点B，B的另一子节点F与圆不相交，不可能有最近邻点；

3、返回上一级父节点A，A的另一子节点C与圆相交，该区域有在圆内的E，E成为新的最近邻点。