前言

参考：

• 《统计学习》—李航（蓝皮）
• 部分来自网络的内容（主要是liaohuiqiang的博客，以及CSDN上其他博主有关数据结构的部分内容）

KNN（K近邻算法）

基本模型

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

1. 选择距离度量（这里是欧氏距离）
2. 根据k值将每个样本点以其自身为中心划分出等距离的区域
3. 在这个区域内，依照服从多数的原则判断此样本点是哪个类（图中k=3时红星样本点周围紫色点的数量大于黄色点，所以此时红星归为Class B）

KNN没有显式的学习过程。
KNN使用的模型实际上对应于特征空间的划分。特征空间中，对每个训练实例点x_i，距离该点比其它点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例拥有一个单元。所有的训练实例点的单元构成对特征空间的一个划分。如下图所示。

KNN的三要素

KNN模型由三个基本要素——距离度量，K值选择，分类决策规则。当三要素和训练集确定后，对任何一个新的输入实例，它所属的类唯一地确定。

距离度量

由不同的距离度量所确定的最近邻点是不同的。

KNN的特征空间一般是n维实空间\mathbb{R}^n，使用的距离是欧氏距离。但也可以是其他距离，如更一般的L_p距离（闵可夫斯基距离）。
设x_i为第i个样本，n维向量\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{n})^T，则它与其他向量的闵可夫斯基距离为
::: align-center
L_p(\mathbf{x_i},\mathbf{x_j})=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}

:::
特别地

• p=1时称为曼哈顿距离（L1范数）
  
• p=2时称为欧氏距离（L2范数）
  
• p\to\infty时\max\{|x|,|y|\}=1称为切比雪夫距离（L\infty范数）
  
  几者的关系如图所示
  

k值选择

K值的选择会对KNN结果产生重大影响

• 选择较小的k值：
  如果选择较小的k值，相当于用较小的邻域中的训练实例进行预测，只有与输入实例较近的训练实例才会对预测结果起作用。
  • 优点：训练误差（又称近似误差，是在训练集上的预测误差，关注数据的匹配度）会减小。
  • 缺点：测试误差（又称估计误差，是在测试集上的预测误差，关注对未知数据的泛化能力）会增大，预测结果对近邻的异常点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。同时k值的减小意味着整体模型变得复杂，容易发生过拟合问题。
• 选择较大的k值：
  如果选择较大的k值，相当于用较大邻域中的训练实例进行预测。
  • 优点：测试误差（估计误差）会一定程度减小
  • 缺点：训练误差（近似误差）会增大。这时离输入实例较远的训练实例起预测作用，使预测发生错误。同时K值的增大意味着整体模型变得简单，容易发生欠拟合问题。
• 特别地，若选择的k值与训练集样本数相同：
  此时所有样本点都被囊括在内，这会导致每次的结果都指向训练集中类别最多的那一类，忽略了数据中其它的重要信息，模型会过于简单，近似误差和估计误差都达到极大，模型失效，因此需要避免。
• 在应用中：
  k值一般取一个比较小的数值，实际问题需要具体分析，通常采用交叉验证法来选取最优的K值。

分类决策规则

对于分类问题，决策常采用多数投票的方式
::: align-center
c=\arg\max_{c_j}\sum_{x_i\in U_k(x^*)}I(y_i=c_m),i=1,2,\cdots,N;m=1,2,\cdots,M

:::
即在特定k值划分的特征空间U_k(x^*)中，近邻的数量最多点的类别

对于回归问题，决策规则常采用平均法则，即均值思想
::: align-center
\hat{y}^*=\frac{1}{K}\sum_{x_i\in U_k(x^*)}y_i,i=1,2,\cdots,N

:::
即在特定k值划分的特征空间U_k(x^*)中，近邻的数量最多点特征（类别）的平均

如果考虑权重的话，可设权重函数为
::: align-center
w_i=\frac{1}{d(x_i,x_j)+\epsilon}

:::
其中d(x_i,x_j)为x_i与x_j间的距离，\epsilon为一个很小的数，避免除0
则多数投票的方式变为
::: align-center
c=\arg\max_{c_j}\sum_{x_i\in U_k(x^*)}w_i(y_i=c_m),i=1,2,\cdots,N;m=1,2,\cdots,M

:::
回归公式变为
::: align-center
\hat{y}^*=\frac{\sum_{x_i\in U_k(x^*)}w_iy_i}{\sum_{x_i\in U_k(x^*)}w_i},i=1,2,\cdots,N

:::

计算机中KNN的分类决策过程使用到了数据结构中的KD树

树（数据结构）

若已明晰树的读者可跳过这一部分，我们仅给出结构定义，不给出代码实现

定义

树是n(n\ge 0)个结点的有限集。当n=0时，称为空数。在任意一颗非空树中应满足

1. 有且仅有一个特定的称为根的结点
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T_1,T_2,\cdots,T_m，其中每个集合本身又是一颗树，并且称为根的子树

显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时又是一种分层结构，具有以下两个特点

1. 树的根节点没有前驱，除根节点外的所有节点有且只有一个前驱
2. 树中的所有节点可以有零个或多个后继
   因此n个节点的树中有n-1条边

基本概念

1. 考虑结点K，根A到结点K的唯一路径上的任意结点称为结点K的祖先。而结点K是结点A的子孙。路径上最接近结点K的节点E称为K的双亲，而K为结点E的孩子，根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟
2. 树中一个结点的的孩子个数称为该结点的度，树中节点的最大度称为树的度，如节点B的度为2而D为3，树的度为3
3. 度大于0的结点称为分支结点（又称非终端结点），度为0的结点称为叶结点（又称终端结点）。在分支结点中，每个节点的分支数就是该结点的度
4. 结点的深度、高度和层次
   1. 结点的层次：从根结点开始定义，根结点为第一层，它的子节点为第二层，以此类推。双亲在同一层的节点互为堂兄弟
   2. 结点的深度是从根结点开始自顶向下逐层累加的
   3. 结点的高度是从叶结点开始自底向上逐层累加的
   4. 数高度是数中结点的最大层数，例如图中树的高度为
5. 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，则称该树为有序树，否则称为无序树
6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数
7. 森林。森林是m(m\ge 0)颗互不相交的树的集合。森林的概念与树的概念十分相似，因为只要把树的根节点删去就成了森林。反之，只要给m颗独立的树加上一个结点，并把这m颗树作为该结点的子树，则森林就变成了树。

二叉树

二叉树是另一种树形结构，其特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树是一种有序树，子树不能左右颠倒
二叉树的5种基本形态如图所示

几个特殊的二叉树见下

1. 斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树，二者同称斜树
2. 满二叉树：树的每层都含有最多的结点（2个）
3. 完全二叉树：高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树，如下图
   
4. 二叉排序树：左树上所有结点的关键字均小于根结点关键字，右子树上的所有结点的关键字均大于根结点的关键字，左子树和右子树又各是一颗二叉排序树
5. 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1

KD树

KNN最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。

为了提高KNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。具体方法很多，下面介绍其中的KD树方法。

KD树的构造

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

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的KD树是平衡的。注意，平衡的KD树搜索时的效率未必是最优的。

构造过程见下，假设数据向量为\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{n})^T，数据集为T=\{\mathbf{x_1,x_2,\cdots,x_n}\}

1. 开始：构造根结点
   • 选择x^{(1)}为坐标轴，以T中所有实例的x^{(1)}坐标的中位数（实际上计算过程中若总数为偶数，那么排序好偶数个数的中位数通常不取中间两个数的平均值，而是取右边的那个数，这是为了在下面确定KD数中存储的那个实例点）为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x^{(1)}垂直的超平面实现。
   • 由根结点生成的深度为1的左右子结点：左结点对应坐标x^{(1)}小于切分点的子区域，右结点对应坐标x^{(1)}大于切分点的子区域。将落在切分超平面上的实例点保存在根结点。
2. 重复：对深度为j的结点，选择x^{(j)}为切分的坐标轴，
   l=(j+1)\space mod\space k，以该结点的区域中所有实例的x^{(l)}坐标的中位数为切分点。
   由该结点生成深度为j+1的左右子结点：左结点对应坐标x^{(l)}小于切分点的子区域，右结点对应坐标x^{(l)}大于切分点的子区域。将落在切分超平面上的实例点保存在该结点。
3. 直到两个子区域没有实例存在时停止，从而形成KD树的区域划分。
   
   最后，构造好的KD树如图所示，所有实例点应全部分布于树上
   
   每个子节点含有以下数据

• 分裂维序号：即l
• 一个实例点：拿那一层来说，若划分的中位数为7，则找到样本集中第一个坐标为7的一个点（7，2）
• 左右子树的指针

KD树的最近邻搜索

给定一个\mathbf{x}，下面就称它为我们的“数据点”，下给出通过KD树搜索得出离它最近邻点的算法：

1. 搜索：从根结点出发，递归地向下访问KD树。若“数据点”当前维的坐标小于每个结点存储的实例点坐标中该结点分裂维序号指示的分量，则左移，否则右移，直到子结点为叶结点。此时我们已经初步确定“数据点”处于哪个特征空间之中
2. 找出此叶结点中保存的实例点作为“当前最近点”
3. 回溯：沿1.中搜索的路径向上递归，在每个双亲结点进行以下操作：
   1. 比较：若该结点保存的实例点比“当前最近点”离目标点更近，则以该实例点为“当前最近点”
   2. 剪枝：检查此结点的兄弟结点所在的区域是否与“以目标点为球心，以目标前与‘当前最近点’的距离为半径的超球体”相交。若不相交则说明此结点的双亲结点的堂兄弟结点中不存在更近的点，此时可以剪枝兄弟结点，继续向上回朔；若相交，则将兄弟节点作为根节点重回1.
4. 最后回退到根结点时，搜索结束。最后的“当前最近点”即为\mathbf{x}的最近邻点
   

简单练习

绿点是待预测类别的点，在k分别为3，5，11时（对应从中心的圆圈到最外侧的方框）时预测绿点的实际类别

解：

• k=3时，即取最近邻3点预测类别时，绿点附近有2个三角1个方块，多数投票结果为三角
• k=5时类似可得结果为方块
• k=11时类似可得结果为方块

注：同时可注意到，k应该尽量选奇数值，避免多数投票过程中出现平票的情况