简介
k近邻(KNN)是一种基本的分类和回归的方法。KNN的输入为实例的特征向量，输出为实例的类别，不需要训练【实际上利用训练集对特征向量空间进行划分】，给定一个训练集，其中的实例类别已定，分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过投票等方式进行预测。
三个基本要素：$k$值的选择、距离度量、分类决策规则
优点：简单、直观
KNN算法
给定一个训练集，对新的输入实例，在训练集中找到与该实例最近邻的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
算法如下：
输入：训练集$T$
输出：新的实例所属的类
- 根据给定的距离度量，在训练集$T$中找到与实例最接近的k个点，涵盖这k个点的$x$的邻域记作$N_k(x)$
- 在邻域$N_k(x)$中根据分类决策规则(eg 多数表决)决定$x$的类别$y$：$$y=arg \max \limits_{c_j} \sum \limits_{x_j \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.
NOTE:
- knn的特殊情况是k=1时，称为最近邻算法。
- knn没有显式学习，当训练集、距离度量、k值以及分类决策规则确定后，对任何一个新输入的实例，它所属的类就唯一地确定。
距离度量
设特征空间是$n$维实数向量空间$R^n$，$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T$，$x_i,x_j$的距离：
- $L_p$距离：$$L_p(x_i,x_j)=\left(\sum \limits_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^p \right)^{\frac{1}{p}}$$这里的$p\geq 1$
- 当$p=2$时，称为欧式距离，即：$$L_2(x_i,x_j)=\left(\sum \limits_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^2 \right)^{\frac{1}{2}}$$
- 当$p=1$时，称为曼哈顿距离，即：$$L_1(x_i,x_j)=\sum \limits_{l=1}^n |x_i^{(l)}-x_j^{(l)}|$$
- 当$p=+\infty$时,它是各个坐标距离的最大值，即：$$L_{\infty}(x_i,x_j)=\max \limits_{l}|x_i^{(l)}-x_j^{(l)}|$$
更多距离公式请查阅博文《机器学习中距离度量完整版》
k值的选择
k值越小学习误差会减小，缺点是，预测误差会增大，预测结果会对近邻的实例点非常敏感，如果恰巧是噪音，预测就会出错，k值越小整体模型越复杂，容易发生过拟合
k值越大，学习误差会增大，但是预测误差会减小，这是与输入实例较远的训练实例也会对预测起作用，k值增大就意味着模型越简单
NOTE:在应用中，k值一般选取较小值，通常采用交叉验证来选取最优k值
分类决策规则
多数表决规则等价于经验风险最小化。
对给定的实例$x$，其最近邻的$k$个训练实例点构成集合$N_k(x)$，如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是$$\frac{1}{k} \sum \limits_{x_i \in N_k(x)} I(y_i \neq c_j)=1-\frac{1}{k} \sum \limits_{x_i \in N_k(x)} I(y_i =c_j)$$
要使误分类率最小即经验风险最小，就要使$\sum \limits_{x_i \in N_k(x)} I(y_i =c_j)$最大，所以多数表决规则等价于经验风险最小化。
代码实现
补充后加入
kd树🌲
实现knn时，主要考虑的问题是如何对训练集进行快速j近邻搜索，尤其是特征空间维度大以及训练数据容量大的时候
KNN最简单的实现方法是线性扫描，但是当训练集很大时，很费时，为了提高KNN的效率，使用kd树存储数据，减少计算距离的次数。
kd树生成
kd树🌲是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形结构，kd树是二叉树，表示对k维空间的划分，构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的$k$维超矩形区域，kd树的每个结点对应于一个$k$维超矩形区域。
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴的中位数为切分点，这样得到的kd树是平衡的，注意，平衡的kd树搜索效率不一定是最优的。
算法
输入: $k$维空间数据集$T=\lbrace x_1,x_2,…,x_N \rbrace$，其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T,i=1,2,…,N;$
输出：kd树
- 开始：构造根结点，根结点对应于包含$T$的$k$空间的超矩形区域
选择$x^{(1)}$为坐标轴，以$T$中所有实例的$x^{(1)}$坐标的中位数为切分点，将根结点对应的矩形超矩形区域切分成两个区域，切分由通过切分点并与坐标轴$x^{(1)}$垂直，左子结点对应坐标$x^{(1)}$小于切分点，右子结点对应坐标$x^{(1)}$大于切分点。 - 重复切分子结点
- 直至两个子区域没有实例存在时，停止，从而形成kd树的划分
kd树搜索
利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。
搜索🔍：
给定目标点，搜索其最近邻，首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。【目标点的最邻近一定在以目标点为中心并通过当前最近点的超球体的内部】。
具体搜索过程参考李航《统计学习方法》page43
总结
KNN简单且不需要训练，而是利用训练集对特征空间进行分类，当KNN三要素【训练集、距离度量、k值以及分类决策规则】确定后，利用KNN模型进行分类，结果就是唯一确定的；k值的大小与模型复杂度相关，k越小模型复杂度越高，k越大模型复杂度越低；KNN实现需要考虑如何快速搜索k个最近邻的点，利用kd树可以减少搜索的计算量。
