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近邻搜索。
