Data-Method-02kNearestNeighborMethodKeepgoodmencompanyyoushallbethenumber.数据系列：目录｜配置｜代码仓库｜对应实战《数据挖掘导论》第五章，《机器学习》第10章和《统计学习方法（第2版）》第3章。k近邻法是一种基本的分类和回归方法，是惰性学习的著名代表。《数据挖掘导论》和《机器学习》没有单独的章节（只留了一小部分），而《统计学习方法（第2版）》也有一章专门介绍。可见k近邻法并不复杂，但仍然是值得学习的经典方法。1.k近邻算法【主动学习与被动学习】主动学习/渴望学习（eagerlearning）：在训练阶段，开始学习从输入属性到类标签的映射模型，如决策树和基于规则的学习。Negativelearning/lazylearning：在训练阶段，只保存样本直到输入测试样本，如Rote分类器（当测试样本的属性与训练样本完全相同时，再输出）和K最近邻法。【K近邻学习】k-NearestNeighbor(KNN)学习是一种常见的监督学习方法，没有明确的学习过程。工作机制：对于给定的测试样本，使用某种距离度量在训练集中找到最接近它的k个点，然后根据决策规则（如多数表决）预测结果。基本要素：k值的选择、距离测度、决策规则2.k-最近邻元素k-最近邻学习的三个基本要素：k值的选择、距离测度和决策规则【distancemeasure】表示两点之间的距离在特征空间中的相似度，多种距离模型都可以采用k近邻模型。$L_p$距离/闵可夫斯基距离：$L_p(x_i,x_j)=(\sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$$p=1$，曼哈顿距离（Manhattandistance）：$L_1(x_i,x_j)=\sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|$$p=2$，欧式距离：$L_2(x_i,x_j)=\sqrt{\sum^n_{l=1}|x_i^{(l)}-x_j^{(l)}|^2}$$p=\infty$，切比雪夫距离各坐标的最大值：$L_{\infty}(x_i,x_j)=\max_l|x_i^{(l)}-x_j^{(l)}|$不同的距离度量确定的最近邻是不同的。【k值的选取】k值小，相当于使用更小邻域内的训练实例进行预测。好处是减少了“学习”的逼近误差，只有更接近输入实例的训练实例才对预测结果起作用；缺点是估计误差（estimationerror）增大，预测结果会对附近的实例点非常敏感（即如果相邻的实例点恰好是噪声，则预测容易出错）。k值的降低意味着整体模型变得复杂，容易出现过拟合。较大的k值相当于使用较大的训练实例邻域进行预测。优点是可以减少学习的估计误差；缺点是学习的近似误差会增大，远离输入实例的训练样例也会产生影响，可能对测试样本进行错误分类。k值的增加意味着整体模型更简单。在应用中，k值一般取一个比较小的值，通常采用交叉验证的方法来选取最优的k值。【决策规则】分类任务一般可以采用“投票法”（多数表决规则）；“平均法”可用于回归任务；加权平均或加权投票也可以基于距离。多数表决规则：最小化误分类率，相当于最小化经验风险y'=\arg\max_v\sum_{(x_i,y_i)\inD_z}w_i\timesI(v=y_i)$3。k近邻实现【线性扫描】近邻算法的高层描述，最简单的实现伪代码如下，令$k$为最近邻的个数，$D$为训练样本集：对于每个测试样本$z=(x',y')$计算$z$和每个样本之间的距离$(x,y)\inD$${\rmd}(x',x)$Select$k$个训练样本的$D_z\子集D最接近$z$$$y'=\arg\max_v\sum_{(x_i,y_i)\inD_z}w_i\timesI(v=y_i)$endfor这是一个线性扫描（linearscan）的描述，它需要计算输入实例到每个训练实例的距离，当训练集很大时这会很耗时。使用高效的索引技术和特殊的结构来存储训练数据可以减少计算距离的数量。下面介绍书中给出的kd树（kdtree）方法。【kd树介绍】kd树是一种存储k维空间数据的树结构，存储空间中的实例点，用于快速搜索。kd树是二叉树，代表k维空间的一个分区；【kd树的构建】构建kd树相当于用垂直于坐标轴的超平面连续划分k维空间，构建一系列k维超矩形区域。每个节点对应一个k维的超矩形空间。算法描述如下，输入：k维空间数据集$T=\{x_1,x_2,...,x_N\}$，其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T$输出：kd树算法：开始：构造根节点，对应$k$维空间的超矩形区域包含$。以$x^{(1)}$为坐标轴，以$T$中所有实例的$x^{(1)}$坐标的中位数为分界点，划分对应的超矩形区域到根节点分为两个子区域。分割是通过一个超平面通过分割点并垂直于坐标轴$x^{(1)}$来实现的。生成深度为1的左右子节点：左节点对应坐标$x^{(1)}$小于分割点的子区域，右节点对应子区域大于分割点。将落在分割超平面上的实例点存储在根节点中。重复：对于深度为$j$的节点，选择$x^{(l)}$作为坐标轴进行分割，$l=j\{\rmmod}\k+1$，取节点的以区域内所有实例的$x^{(l)}$坐标的中值作为分割点，将该节点对应的超矩形区域划分为两个子区域。通过分割点通过垂直于坐标轴$x^{(l)}$的超平面实现分割。生成深度为$j+1$的左右子节点：左节点对应子节点-坐标$x^{(1)}$小于分割点的区域，右节点对应大于分割点的子区域。将落在分割超平面上的实例点保存在该节点中。结束：停止直到两个子区域中不存在实例。以中位数作为分界点，使得得到的kd树是平衡的。但是平衡kd树搜索的效率可能不是最优的。【kd树的搜索】kd树的搜索首先找到包含目标点的叶子节点，然后从那里返回父节点，不断搜索相邻点，直到确定没有更近的节点终止.算法描述如下（以最近邻为例）：输入：构造的kd树，目标点x输出：x的最近邻算法：在kd树中找到包含目标点x的叶子节点：从根节点开始，递归向下访问，如果目标x当前维度的坐标小于切分点的坐标，则移动到左节点，否则移动到右节点，直到子节点为一个叶子节点，这个点是当前最近的点；递归备份，每一步：如果节点保存的实例点比当前最近点更接近目标点，则将此点作为当前最近点；检查子节点的另一个子节点对应的区域是否有更近的点，移动到另一个子节点，递归进行最近邻搜索；否则，备份；具体来说，寻找交集。当返回到根节点时，搜索结束。如果实例点是随机分布的，则kd树搜索的平均复杂度为$O(\logN)$。当训练实例数远大于空间维数时，kd树更适用于k近邻搜索。当空间维度接近训练实例数时，效率会迅速下降，几乎接近线性扫描。4.k近邻法的特点k近邻法是一种基本的、简单的分类和回归方法。k近邻模型对应的是根据训练数据集对特征空间进行划分。k近邻属于基于实例的学习，使用特定的训练样例进行预测。而不是必须维护从数据派生的抽象（或模型）。k近邻等负学习方法不需要建立模型，但是对测试样本进行分类的开销非常大。k近邻基于局部信息进行预测，当k较小时，对噪声非常敏感。K-NearestNeighbors可以生成任意形状的决策边界，提供更灵活的模型表示。K最近邻需要适当的邻近度量和数据预处理。参考《数据挖掘导论》Chapter5《机器学习》Chapter10《统计学习方法（第2版）》Chapter3
