一、k近邻算法
k近邻法（k-nearest neighbor, k-NN）是一种基本的分类与回归方法。该算法简单、直观：给定一个训练数据集，k近邻模型就已经基本固定，对于输入的实例，在训练数据集中找到距离该实例最近的k个实例，在这k个实例中实行多数表决机制，即这k个实例中的多数属于哪个类，该输入实例就属于哪个类。
k近邻算法的数学定义为：
输入：训练数据集\(T=\{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\}\)，其中，\(x_i \in {\cal{X}} \subseteq R^n\)为实例的特征向量，\(y_i\in{\cal{Y}}=\{c_1,c_2,...,c_K\}\)为实例的类别，\(i=1,2,...,N\)；实例向量\(x\)；
输出：实例\(x\)所属的类\(y\)。
（1）根据给定的距离度量，在训练集\(T\)中找出与\(x\)最近邻的\(k\)个点，涵盖这\(k\)个点的\(x\)的邻域记作\(N_k(x)\)；
（2）在\(N_k(x)\)中根据分类决策规则（如多数表决）决定\(x\)的类别\(y\)：
\[y=\arg \max_{c_j}\sum_{x_i \in N_k(x)}I(y_i=c_j), i=1,2,...,N; j=1,2,...K\]其中\(I\)为指示函数，即当\(y_i=c_j\)时\(I\)为1，否则为0。
二、k近邻法的实现：kd树
2.1 构造kd树
kd树（k-dimension tree）是对数据点在k维空间中划分的一种数据结构，方便对其进行快速检索。构造kd树的方法一般为依次选择坐标轴对空间进行切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。构建平衡kd树的算法如下：
输入：\(k\)维空间数据集\(T=\{x_1,x_2,...,x_N\}\)，其中\(x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(K)})^T\),\(i=1,2,...,\)\(N\)；
输出：kd树
（1）构造根节点。选择\(x^{(1)}\)为坐标轴，以所有实例中的\(x^{(1)}\)的中位数为切分点将\(T\)进行分割，左子节点为\(x^{(1)}\)小于当前切分点的子区域，右子节点为\(x^{(1)}\)大于当前切分点的子区域，落在切分超平面上的点即为根节点。
（2）在刚才分割的两个子区域中重复上述操作，选择的坐标轴循环递增。
（3）直到分割后的子区域中没有实例点时停止。
2.2 搜索kd树
利用kd树可以省去对大部分点的搜索，总而减少搜索的计算量。利用kd树的最近邻搜索算法如下：
输入：已构造的kd树，目标点\(x\)；
输出：\(x\)的最近邻
（1）在kd树中找到包含\(x\)的叶节点：从根节点出发，若\(x\)的当前维坐标小于切分点坐标，则移动到左节点，否则移动到右节点，直到子节点为叶节点为止。并以此叶节点为“当前最近点”。
（2） 递归地向上回退，如果该节点的实例点比当前最近点距离\(x\)更近，则以当前实例点为“当前最近点”。然后检查该子节点的父节点的另一子节点对应的区域中是否有更近的点。如果存在，则移动到另一子节点中递归地进行最近邻搜索，否则向上回退。
（3）当回退到根节点时，搜索结束，“当前最近点”即为\(x\)的最近点。
小结
本章主要介绍了一种简单的分类和回归方法，在实际使用中，为了方便快速搜索数据，引入了kd树，通过使用kd树可以快速搜索到距离目标点最近的k个最近邻点。
