统计机器学习6：kNN算法

统计机器学习06：kNN

基本概念

kNN的基本思路

kNN：k-Nearest Neighbor算法是一种分类算法，其核心想法是根据给定的训练集，对于需要判别的测试集中的样本，在训练集中找到与之最接近的k个样本，并统计这k个样本的分类情况，将出现次数最多的类别作为测试集中的样本的分类结果。如果将k个最近的样本用来表示，那么kNN的分类决策用公式表示就是： kNN的基本思路其实就是：如果一个东西看起来像鸭子，走路像鸭子，吃饭也像鸭子，那么它很可能就是一只鸭子。而"最接近"这个概念是有待商榷的，因为我们没有统一的距离度量法则，因此需要确定一种度量距离的方法。此外k也需要自己选择，k=1的时候这个算法被称为最近邻算法

距离度量的选择

我们需要在n维的特征空间中度量两个点之间的距离，对于n维空间中的两个向量，我们定义距离： 上面的公式中p=2的时候称为欧几里得距离，而p=1的时候称为曼哈顿距离，当p为无穷大的时候，L就是每个坐标中距离最大值.

k的选择

k的选择也对最终的结果有比较大的影响，k选择太小的话学习时的误差会减小，但是估计误差会增大，预测结果会对样本的位置关系非常敏感。 如果k选的太大，则估计误差会降低，但是学习时的误差会增大，二者各有利弊，当然如果k=N那么就是按照出现次数最多的作为结果，完全忽略了模型中的大量有用信息。

kd树：kNN求解

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，是一种二叉树，用来表示对k维空间的一个划分，使得每个k维空间中数据集的点对应到一个k维空间超矩形上面去。

kd树的构造

一般来说构造kd树的方法是先选择根节点，然后每次选定一个坐标轴，并用该方向的样本点坐标的中位数作为划分的依据，并沿着垂直于坐标轴的方向作超矩形，然后将k维空间分出了新的两个区域，之后就在两个新的区域里面换一个坐标轴重复上面的操作，直到每个样本点都进行了划分，每个子区域中没有样本点的时候停止。

kd树的搜索

对于一棵构造好的kd树进行k近邻搜索可以省去对大部分数据点的搜索，从而减少搜索的计算量，以最近邻为例，对于给定的目标点，搜索其最 邻近的点需要首先找到包含目标点的叶节点(注意，kd树里的节点代表的是超平面里的一块超矩形，不是样本点)，然后从该叶节点出发，回退到 父节点，并不断查找与目标点最邻近的节点，当确定不可能存在更近的节点的时候终止。