统计学习方法笔记(第三章个人笔记)
标签： 机器学习深度学习
K近邻算法
1. 描述：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近（可以用欧氏距离或者其他距离，但是要知道，用不同距离得到的最近邻点是会有一定差异的，书中P39例3.1有说明实例）的k个实例，这k个实例属于某个类，就把该输入实例分为这个类。且k近邻算法没有显示的学习过程。
2. K值的选择：
(1) k的选择会对算法产生巨大影响，如果k较小，将会使得“学习”的近似误差减小，但是缺点是“学习”的估计误差会增大，预测结果过会对近邻的实例点非常敏感，换句话说，这样会让整体模型变得复杂，容易发生过拟合。
(2) 如果k较大，优点是会减小学习的估计误差，但缺点是学习的近似误差会增大，对与输入实例较远的(不相似的)训练实例也会起预测作用，使得预测放生错误。k值增大意味着整体模型变得简单。
(3) 在实际运用中，k一般取较小的数值，采取交叉验证法来取得最优K.
3. 分类决策规则
K近邻算法的分类决策规则往往是多数表决，即由输入实例的K个近邻的训练实例中的多数类决定输入实例的类：
如果分类的损失函数为0-1损失函数，分类函数为：
$$f:R^n→{c_1,c_2,\dots,c_k}$$
那么误分类的概率是：
$$P(Y≠f(X))=1-P(Y=f(X))$$
对于给定的实例$x∈X$,起最近邻的K个实例点构成的集合$N_k(x)$.如果涵盖$N_k(x)$的区域类别是c_j，那么误分类率是：
$$\frac1k\sum_{x_i∈N_k(x)}I(y_i≠c_j)=1-\frac1k\sum_{x_i∈N_k(x)}I(y_i=c_i)$$
要使得误分类误差最小，即经验风险最小，就要使得$\sum_{x_i∈N_k(x)}I(y_i=c_i)$,所以多数表决绝规则等价于经验风险最小化。
4. K近邻算法的实现：kd树
实现K近邻算法时，主要考虑的问题是如何对训练数据进行快速K近邻搜索。这点在特征空间的维数大以及训练数据容量大时尤其必要。k近邻算法最简单的实现方法是线性扫描，这时要计算输入实例和每一个训练实例的距离，当训练集很大时计算将非常耗时，是不可取的，为了提高搜索效率，可以使用特殊的结构存储训练数据，以减少计算的次数，下面介绍用kd树方法
(1) 构造kd树
kd树是一种对K维空间（注意，k不是k个邻居的意思）中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切开，构成一系列的k维超矩形区域，kd树的每一个节点对应于一个k维超矩形区域
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样的二道的Kd树是平衡的。注意，平衡的Kd树搜索时的效率未必是最优的(这里的k是指k维，也就是说x有k个特征值)
构造kd树的方法如下：
假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内，如图2：
a）分别计算k维（上图中只有x，y两维）数据中方差最大的一维（也可以依次分割每一维度）且书上是依次分割每一个维度来分的，且在深度为j(j从0开始)的节点选择对$x^{(l)}维切分坐标时，l=j(modk)+1$，是x轴方向，所以先分割x轴；
b）根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以以（7,2）为分割点。这样，该节点的分割超平面就是通过（7,2）并垂直于x轴的直线x = 7；
c）确定左子空间（x <= 7的部分）和右子空间（x > 7的部分）进行上面两步递归操作直到空间中只包含一个数据点。最后生成的k-d树如图1。
（2） 搜索kd树
这里描述最邻近点查找的基本思路。
例一：星号表示要查询的点（2.1,3.1）。
通过二叉搜索，顺着搜索路径很快就能找到最邻近的叶子节点（2,3），首先假设（2,3）为“当前最近邻点”。
最邻近点肯定位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行“回溯”操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中是由点（2,3）回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点，发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。
至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
例二：星号表示要查询的点（2,4.5）。
通过二叉搜索，顺着搜索路径很快就能找到最邻近的叶子节点（4,7），首先假设（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。
回溯到（5,4），计算其与查找点之间的距离为3.041，小于3.202，所以“当前最近邻点”变成（5,4）。以目标点（2,4.5）为圆心，以目标点（2,4.5）到“当前最近邻点”（5,4）的距离（即3.041）为半径作圆，如下图左所示。可见该圆和y = 4超平面相交，所以需要进入（5,4）左子空间进行查找，即回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以“当前最近邻点”更新为（2,3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图右所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。
后方例题参考博客：http://blog.csdn.net/mmc2015/article/details/42838897
