统计学习方法笔记：3.k近邻法
这是我参加mlhub123组织的书籍共读计划的读书笔记，活动见mlhub第一期读书计划
- 阅读章节：第三章：k近邻法
- 开始时间：2018-09-29
- 结束时间：2018-10-23（比较忙）
- 目标：读完第三章，掌握基本概念，产出一篇笔记
- 博客地址
k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归方法，本书只讨论分类形式：
- k近邻算法
- k近邻模型
- k近邻法的实现：kd树
k近邻算法
什么是k近邻算法？
给定一个训练集：，其中
为实例的特征向量，
，输入实例特征向量
，输出该实例特征向量的类别
关键点在于是如何进行类别的判断，描述如下：
image
思想很简单，就是给定一个训练集，输入一个实例，就在训练集中找出与该实例最邻近的k个实例，然后进行多数表决，这k个实例的多数属于某个类，就把该输入实例分为这个类
上面3.1的公式这里解释一下：随着变量j的递增，代表不同的类别，每次
对应的
会和
进行比较，如果
等于
，该类别计数加一，直到
与
比较完毕，累加之和最高的
就是输出
（意思就是判断输入实例邻域的实例在此类别占据多少个数目），至此，分类成功
k近邻模型
k近邻法使用的模型实际上对应于对特征空间的划分，模型由三个基本要素——距离 度量、k值的选择和分类决策规则决定
模型
通过上面的叙述，当我们知道：
- 训练集
- 距离度量（明可夫斯基距离）
- k值
- 分类决策规则（多数表决）
此时对于任何一个新的输入实例，都可以确定其所属的类
什么是单元？
特征空间中，对每个训练实例点，距离该点比其他点更近的所有点组成一个区域，叫作单元
（cell），最终会将特征空间划分为下图所示：
image
距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映，k近邻模型的特征空间一般是n维实数向量空间，使用的距离是欧氏距离，但也可以是其他距离，如更一般的
距离（
distance）或Minkowski距离（Minkowski distance）
image
k值的选择
k值的选择会对k近邻法的结果产生重大影响：
- 如果较小：k值的减小就意味着整体模型变得复杂，容易发生过拟合
- 如果较大：k值的增大就意味着整体的模型变得简单
分类决策规则
k近邻法中的分类决策规则往往是多数表决（majority voting rule），即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类，实际上等价于经验风险最小化
k近邻法的实现：kd树
实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索
k近邻法最简单的实现方法是线性扫描（linear scan），这时要计算输入实例与每一个训练实例的距离，当训练集很大时，计算非常耗时，这种方法是不可行的
为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，具体方法很多，下面介绍其中的kd树（kd tree）方法
构造kd树
k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）
k-d树是二叉树，表示对k维空间的一个划分（partition），其中每个结点对应于一 个k维超矩形区域，且该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树
image
实际做一道例题有助于对算法的理解：
image
- 首先对数据集排序：(2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)，其中值为(7,2)
- 根结点生成深度为1的左、右子结点，(2,3)，(4,7)，(5,4)挂在(7,2)节点的左子树，(8,1)，(9,6)挂在(7,2)节点的右子树
- 构建(7,2)节点的左子树，此时切分维度k=2（可以理解为y轴），中值(5,4)作为分割平面，(2,3)挂在其左子树，(4,7)挂在其右子树
- 构建(7,2)节点的右子树，此时切分维度k=2（可以理解为y轴），中值(6,6)作为分割平面
- 无法继续划分，k-d tree构建完成
image
搜索kd树
给定一个目标点，搜索其最近邻，首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高
image
说明
有助于理解kd树的博客文章：
