算法简介
给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的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成为新的最近邻点。
网友评论