（一）算法思想：
自然语言描述：给定一个训练数据集，对新的输入实例，在训练数据集上找到与该实例最邻近的k个实例，这k个实例的多数属于哪个类，就将输入划分为该类。
形式化描述：对于给定的输入x，根据给定的距离度量，算出包含k个训练样本的邻域Nk，然后在Nk内进行决策，即y=argmax Σi（i为指示函数，eg（0,0,1））
（二）k邻近模型
1.模型：
cell：特征空间中，每一个训练样本看做xi，距离该点比其他点更近的所有点组成的区域，叫做单元cell
类标记：yi则是xi的cell中的类标记class label
2.距离度量：
距离度量反映了两个点的相似程度，一般采用欧式距离或者曼哈顿距离。
p=1：曼哈顿距离
p=2：欧式距离
3.k值的选择：
k值选的大：减少学习的估计误差，但是近似误差会增大（与样本距离较远，不相似的样本会对估计产生影响），即模型过于简单--欠拟合
k值选的小：近似误差会减小，但是估计误差会增大（如果与样本最近的点是噪声，则会影响预测结果），即模型过于复杂敏感--过拟合
现实应用中一般使用较小的k值，然后使用交叉验证的方式选取最优k
4.分类决策的规则：
多数表决规则（majority voting rule）：k个邻近实例中类别最多的类最为输出。
损失函数：0-1损失函数，使损失函数最小，则应选择所属类别最多的类
（三）k邻近算法的实现---kd树
1.为什么构造kd树：若样本庞大，线性的计算所有的训练样本与输入的距离非常耗时，不可取。于是选择特殊的数据结构对训练样本进行存储，方便计算距离。
2.构造kd树：
（1）构造根节点，选择x1特征为坐标轴，选择x1特征的中位数，将该样本作为切分点，构造垂直于坐标轴的超平面将特征空间分为2份
（2）对深度为j的节点，选择j%k+1（k为特征数量）作为坐标轴，使用同样的办法进行划分
（3）重复步骤2直至划分出的区域中没有实例。
3.搜索kd树--最邻近搜索
1.从根节点出发，递归的向下访问kd树。若目标节点的当前维坐标小于切分点，则走左子树，否则走右子树。走到叶节点为当前最近节点。
2.递归的向上回退，每个节点进行以下操作：
（a）如果该节点距离目标节点更近，则该节点为当前最近节点。
（b）以当前的最近节点为圆心，以最近距离为圆心，判断该圆形（实际上超过二维成为超球体）是否与分割的超平面相交。若相交，递归的进行最邻近搜索；若相离，则向上回退。
3.当退回根节点时，当前节点为最邻近节点。
时间复杂度：如果实例点是随机分布的，则时间复杂度是O(logN).kd树更适用于训练示例远大于空间维数的k邻近扫描，否则几乎接近线性时间。
