1. 什么是KNN

   KNN(K近邻)算法：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近邻的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

   KNN使用的模型实际上对应于特征空间的划分，没有显式的训练过程。

2. KNN三要素

   - 距离度量

     特征空间中两个实例点的距离是两个实例点相似程度的反映。设输入实例$x\in \mathbb{R}^n$，$x_i$和$x_j$的$L_p$距离定义为：
     $$
     L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{l}-x_j^{l}|^p)^{(\frac{1}{p})}
     $$
     当p为1时成为曼哈顿距离，当p为2是为欧氏距离，当p为正无穷大时为各个坐标轴距离的最大值。不同的p值可能导致最近邻点的选取不同。

   - k值

     较小的k值代表整体模型变得复杂，分类结果容易被噪声点影响，容易发生过拟合。

     较大的k值代表整体模型变得简单，容易欠拟合。

     在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值。

   - 分类决策规则

     一般采用多数表决规则。

3. kd树

   kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的二叉树结构，表示对l维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将l维空间切分，构成一系列的l维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

   - 构造平衡kd树的算法：

     输入：k维空间数据集$T=\{x_1,x_2,..,x_N\}$，其中$x_i=(x_i^{(0)},x_i^{(1)},...,x_i^{(l-1)})$为$l$维向量。

     输出：kd树。

     1. 开始：构造根结点，根结点对应于包含T的l维空间的超矩形区域。

        选择$x^{(0)}$为坐标轴，以T中所有实例在该坐标轴上的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并于坐标轴$x^{(0)}$垂直的超平面实现。

        由根结点生成深度为1的左、右子结点，分别对应坐标轴$x^{(0)}$小于和大于切分点的子区域，将落在切分超平面上的实例点保存在根结点

     2. 对深度为j的结点，选择$x^{j\bmod l}$为切分坐标轴（也可选择方差最大的坐标轴），重复1所述的切分过程。
     3. 直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

   - kd树的最近邻搜索

     输入：kd树，目标点x；

     输出：x的最近邻；

     1. 在kd树中从根结点出发，递归向下查找包含目标点x的叶结点；
     2. 以此叶结点为当前最近点；
     3. 递归向上回退，在每个结点进行以下操作：
        - 如果该结点保存到实例点比当前最近点距离目标点更近，则以该实例点位当前最近点。
        - 检查该结点的另一子结点是否与以目标点为球心，以目标点与当前最近点间的距离为半径的超球体相交。如果相交，则移动到另一子结点进行递归搜索，，否则向上回退。
        - 当回退到根结点时，搜索结束，当前最近点即为x的最近邻点。

   

   

   