统计机器学习06：kNN¶
本页统计信息
-
本页约 917 个字, 预计阅读时间 3 分钟。
-
本页总阅读量次
基本概念¶
kNN的基本思路¶
kNN：k-Nearest Neighbor算法是一种分类算法，其核心想法是根据给定的训练集，对于需要判别的测试集中的样本，在训练集中找到与之最接近的k个样本，并统计这k个样本的分类情况，将出现次数最多的类别作为测试集中的样本的分类结果。如果将k个最近的样本用\(N_k(x)\)来表示，那么kNN的分类决策用公式表示就是： $$ y=\arg\max\sum_{x_i\in N_k(x)}I(y_i=c_i) $$ kNN的基本思路其实就是：如果一个东西看起来像鸭子，走路像鸭子，吃饭也像鸭子，那么它很可能就是一只鸭子。而\"最接近\"这个概念是有待商榷的，因为我们没有统一的距离度量法则，因此需要确定一种度量距离的方法。此外k也需要自己选择，k=1的时候这个算法被称为最近邻算法
距离度量的选择¶
我们需要在n维的特征空间中度量两个点之间的距离，对于n维空间中的两个向量\(x_i,x_j\)，我们定义距离：
上面的公式中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树里的节点代表的是超平面里的一块超矩形，不是样本点)，然后从该叶节点出发，回退到 父节点，并不断查找与目标点最邻近的节点，当确定不可能存在更近的节点的时候终止。