Table of Contents

1. k近邻法
2. k近邻法模型
   1. 模型
   2. 距离度量
   3. k 值选择
   4. 分类决策规则
3. k近邻法的实现：kd树
   1. 构造kd树
   2. 搜索kd树

基本的分类和回归方法 输入：实例的特征向量，对应于特征空间中的点 输出：实例的类别 通过多数表决等方法进行预测，不具有显式的学习过程。 三要素：k值的选择、距离度量、分类决策规则

k近邻法

对于新的输入实例，在训练集上找到与该实例最邻近的k个实例，这k个实例的多数属于哪个类，就把该实例分类为这个类

算法

k近邻法模型

模型对应于对特征空间的划分，由三个基本要素：距离度量、k值选择、分类决策规则 决定。

模型

距离度量

欧式距离

k 值选择

k 值过小，模型复杂，容易发生过拟合；k 值过大，模型简单。

分类决策规则

多数表决规则， 经验风险最小化

k近邻法的实现：kd树

提高k近邻搜索的效率，减少距离计算的次数。

构造kd树

平衡的kd树的搜索效率未必是最优的。

构造平衡kd树:对于深度为j的结点，选择x(l)为切分的坐标轴，l = j(mod k) + 1, 以该结点区域所有实例的x(l)坐标的中位数为切分点，切分为两个子区域，直至子区域中没有实例存在。

搜索kd树

最近邻搜索：首先找到包含目标点的叶结点；依次回退到父结点；不断查询与目标点最近的结点，当确定不可能存在更近的结点时终止。