第二章K近邻算法.ppt

Company Logo K近邻算法应用实践 数据预处理 为了提高判别效果，我们考虑采用分层抽样的方式，由于miete数据集中，待判别变量nmkat的5个等级分布比较均匀，因此采用5个等级按等量抽取样本。 install.packages(“sampling”)下载包 library(sampling)加载包 n = round(2/3*nrow(miete)/5)按照训练集占总数2/3，每一等级中应抽取的样本量 n显示训练集中每一等级中应抽取的样本量 sub_train = strata(miete,stratanames = nmkat,size=rep(n,5),method=srswor)显示训练集抽取的情况，包括nmkat变量取值、该样本在数据集中的序号、被抽取的概率、以及被抽取的层次 Company Logo K近邻算法应用实践 数据预处理 data_train = getdata(miete[,c(-1,-3,-12)],sub_train$ID_unit)获取如上ID_unit所对应的样本构成训练集，并删除变量1、3、12 data_test = getdata(miete[,c(-1,-3,-12)],-sub_train$ID_unit)获取如上ID_unit所对应的样本构成测试集，并删除变量1、3、12 dim(data_train); dim(data_test) 分别显示训练集、测试集的维度 K近邻算法k-nearest neighbor Company Logo 主要内容 K近邻算法 K近邻模型 距离度量 k值选择 分类决策规则 K近邻算法的实现 KD树简介 KD树的构建 用KD树的k近邻搜索 基于距离加权的K近邻算法 K近邻算法应用实践 KNN与推荐 Company Logo KNN算法 K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一，1968年由 Cover 和 Hart 提出。 Company Logo KNN算法 Company Logo KNN算法 特点 基于实例之间距离和投票表决的分类 精度高、对异常值不太敏感 计算复杂度高、空间复杂度高 特别适合多分类 简单易实现 大多数情况下比朴素贝叶斯和中心向量法好 给定训练集、距离度量、k值及分类决策函数时，其结果唯一确定 Company Logo KNN算法 算法描述： 输入：训练数据集 为实例的特征向量， 实例向量x 输出：实例x所属的类别y 根据给定的距离度量，在训练集T中找出与x最近的k个点，涵盖着k个点的x的邻域记作Nk(x) 在Nk(x)中根据分类决策规则（如多数表决）决定x所属的类别y。上式中，I为指示函数，即当yi=cj时，I为1，否则为0 Company Logo KNN模型 K近邻算法中，当训练集、距离度量、k值及分类决策规则确定后，对于任何一个输入实例，它所属的的类唯一地确定 特征空间中，对于每个训练实例点，距离该点比其他点更近的所有点组成了一个区域，叫单元(cell)。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。 Company Logo 距离度量 设特征空间是n维实数向量Rn，xi，xj∈Rn， xi，xj的一般距离定义为闵式距离LP： 当p=2时，为欧几里得距离 当p=1时，为曼哈顿距离 当p=+∞时，为切比雪夫距离 注意：使用的距离不同，k近邻的结果也会不同的，即“由不同的距离度量所确定的最邻近点是不同的” Company Logo k值选择 k值得选择非常重要，对算法结果产生重要影响 如果选择的比较小的话，相当于用较小邻域中的训练实例进行预测，学习的近似误差会减少，只有与输入实例较近的训练实例才会对预测结果起作用，缺点是学习的估计误差会增大，易受噪声影响，极端情况是k=1 如果k值选取的比较大，相当于用较大邻域中的训练实例进行预测，学习的估计误差会减少，但是近似误差会增大，而且与输入实例较远的训练实例也会对预测起作用，是预测结果错误，k值的增大意味着整体模型变得简单。因为划分的区域少了，更容易进行预测结果。极端情况是k=N 在应用中k一般取一个比较小的值，通常采用交叉验证法来选取最优的k值 Company Logo 分类决策规则 k近邻法的分类决策规则往往是多数表决，即由输入实例的k个近邻训练实例多数所属的类来决定