学习笔记34-k近邻算法

k近邻算法

（k-nearest-neighbor kNN）
这是一种分类算法，它的核心思想是：对于新的样本，根据其k个最近邻的样本的类别，通过多数表决等决策规则，决定它的类别。
使用k近邻算法，首先需要确定三个东西：

距离度量，k值的选择，分类决策规则

距离度量

特征空间中两个样本点之间的距离反映了这两个样本的相似程度，距离有多种表示方法：
一般用Lp表示。
1. 曼哈顿距离（L1距离）
L1距离可以看成是一个向量范数——1范数，表示向量中所有元素绝对值之和。这里的向量是两个样本特征向量之差。也就是||X1-X2||1

2. 欧氏距离（L2距离）
L2距离看成是向量的2范数，表示向量中元素的绝对值的平方和的开方。其实就是我们初中数学中计算平面直角坐标系中两个点的距离公式。

3. L无穷距离
当p接近无穷时，Lp距离表示向量中各个元素绝对值中最大的那个。表示为：

最后给出适用于所有p的Lp计算公式：

最后给出向量范数的计算：

k值的选择

k值的选择直接影响了分类的结果。
如果选择较小的k，就是用较小的邻域中的训练样本进行预测，这时学习的近似误差（approximation error）较小，只有那些与测试样本较相似的训练样本对预测结果起作用。但是学习的估计误差（estimation error）较大，因为算法对近邻的样本点非常敏感，如果近邻的样本恰好是噪声，预测就会出错。
也就是说，k值越小，模型越复杂，容易发生过拟合。
如果选择较大的k值，就是用较大的邻域中的训练样本今夕预测，这是可以减小估计误差，减小了可能存在的噪声的影响。但是，近似误差会增大，因为那些与测试样本较远的，不相似的样本也会影响预测结果。
也就是说，k值越大，模型越简单，可能发生欠拟合。

分类决策规则

常用的分类决策规则是多数表决，也叫投票，根据票数最多的类别预测分类。

k近邻算法的实现 ——kd树

1. 构造kd树
kd树是一课二叉树，就是用垂直于坐标轴的超平面对k维空间的一种划分，可以用递归的方法产生子结点。
具体步骤如下：
1. 构造根结点，将区域划分成两个子区域；
2. 递归产生子结点，将子区域再次划分为两个子区域；
3. 直到两个子区域都没有实例，该点是叶结点，递归退出。
2. 搜索kd树
搜索的步骤如下：
1. 从根结点出发，递归地向下访问kd树（遍历二叉树），如果目标点当前维的坐标比切分点的坐标小，则遍历左结点，否则遍历右结点，直到子结点为叶结点为止。
2. 以此叶结点作为当前“最近邻点”。
3. 递归地向上回退，在每个结点执行以下操作：
（1）如果该结点距离目标点更近，则以该结点为“最近邻点”
（2）检查该子结点的兄弟结点对应的区域是否有更近的点，如果有则遍历到兄弟结点，寻找“最近邻点”
4. 当回退到根结点，搜索结束，得到目标点的“最近邻点”。
具体见下图：