第三章 k近邻法

1.基本做法：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用这k个训练实例点的类的多数来预测输入实例点的类。

2.k近邻模型对应于基于训练数据集对特征空间的一个划分。k近邻法中，当训练集、距离度量、k值以及分类决策规则确定后，其结果唯一确定。

3.k近邻法三严肃：距离度量、k值的选择和分类决策规则。

4.k近邻法的实现需要考虑如何快速搜索k个最近邻点。

---

3.1 k近邻算法

k近邻算法

3.2 k近邻模型

3.2.1 模型

单元（cell）：在特征空间中，对每个训练实例点xi，距离该点比其他点更近的所有点组成的区域。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

3.3.2 距离度量

距离：两个实例点相似程度的反映。欧氏距离、Lp距离、Minkowski距离。

距离

3.2.3 k值的选择

k值过小：approximation error会减小，estimation error会增大，预测结果对近邻的实例点敏感，容易过拟合

k值过大：estimation error会减小，approximation error会增大。

通常采用交叉验证法选取最优的k值

3.2.4 分类决策规则

多数表决

3.3 k近邻法的实现：kd树

对训练数据进行快速k近邻搜索

3.3.1 构造kd树

kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

构造kd树 构造kd树

3.3.2 搜索kd树

若实例点随机分布，则kd树搜索平均复杂度维O(logN)。

kd树更适用于训练实例数远大于空间维数的k近邻搜索。