数据挖掘实验报告资料.pdf

《数据挖掘实验报告资料.pdf》由会员分享，可在线阅读，更多相关《数据挖掘实验报告资料.pdf（12页珍藏版）》请在三一文库上搜索。

1、大数据理论与技术读书报告 -K 最近邻分类算法 指导老师: 陈 莉 学生姓名: 李阳帆 学号 : 201531467 专业 : 计算机技术 日期 :2016 年 8 月 31 日 摘要 数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能 技术和数据库技术紧密结合， 让计算机帮助人们从庞大的数据中智能 地、自动地提取出有价值的知识模式，以满足人们不同应用的需要。 K 近邻算法（ KNN）是基于统计的分类方法，是大数据理论与分析 的分类算法中比较常用的一种方法。该算法具有直观、 无需先验统计 知识、无师学习等特点， 目前已经成为数据挖掘技术的理论和应用研 究方法之一。本文主要研究了K 近邻分

2、类算法，首先简要地介绍了 数据挖掘中的各种分类算法，详细地阐述了K 近邻算法的基本原理 和应用领域，最后在matlab 环境里仿真实现，并对实验结果进行分 析，提出了改进的方法。 关键词： K 近邻，聚类算法，权重，复杂度，准确度 1.引言 . 1 2.研究目的与意义 1 3.算法思想 . 2 4.算法实现 . 2 4.1 参数设置 . 2 4.2 数据集 2 4.3 实验步骤 3 4.4 实验结果与分析 3 5.总结与反思 4 附件 1 6 1 1.引言 随着数据库技术的飞速发展，人工智能领域的一个分支 机器学习的研究自 20 世纪 50 年代开始以来也取得了很大进展。用数据库管理系统来 存

3、储数据， 用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了 数据库中的知识发现（Knowledge Discovery in Databases ，简记 KDD）的产生，也称作数 据挖掘（ Data Ming ，简记 DM ）。 数据挖掘是信息技术自然演化的结果。信息技术的发展大致可以描述为如下的过程：初 期的是简单的数据收集和数据库的构造；后来发展到对数据的管理，包括：数据存储、 检索 以及数据库事务处理；再后来发展到对数据的分析和理解， 这时候出现了数据仓库技术和数据挖掘技术。数据挖掘是涉及数据库和人工智能等学科 的一门当前相当活跃的研究领域。 数据挖掘是机器学习领域

4、内广泛研究的知识领域，是将人工智能技术和数据库技术紧密 结合， 让计算机帮助人们从庞大的数据中智能地、自动地抽取出有价值的知识模式，以满足 人们不同应用的需要1 。目前，数据挖掘已经成为一个具有迫切实现需要的很有前途的热 点研究课题。 2.研究目的与意义 近邻方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史纪录 的已知特征值来预测当前记录的未知或遗失特征值14 。 近邻方法是数据挖掘分类算法中比 较常用的一种方法。K 近邻算法 （简称 KNN）是基于统计的分类方法15 。KNN 分类算法根 据待识样本在特征空间中 K 个最近邻样本中的多数样本的类别来进行分类，因此具有直观、

5、无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要方法。 大多数分类方法是基于向量空间模型的。当前在分类方法中，对任意两个向量： x= ),.,( 21xxxn 和 ),.,( 2 1 xxxx n 存在 3 种最通用的距离度量：欧氏距离、余弦距 离16 和内积 17 。 有两种常用的分类策略：一种是计算待分类向量到所有训练集中的向量 间的距离：如 K 近邻选择K个距离最小的向量然后进行综合，以决定其类别。另一种是用 训练集中的向量构成类别向量，仅计算待分类向量到所有类别向量的距离，选择一个距离最 小的类别向量决定类别的归属。很明显，距离计算在分类中起关键作用。由于以上 3 种距

6、离度量不涉及向量的特征之间的关系，这使得距离的计算不精确，从而影响分类的效果。 2 3.算法思想 K最近邻 (K-Nearest Neighbor,KNN) 算法，是著名的模式识别统计学方法，在机器学习 分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算 法之一，也是基于实例的学习方法中最基本的，又是最好的文本分类算法之一。 其基本思想是： 假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记 表示这些样本是属于哪一个分类， KNN 就是计算每个样本数据到待分类数据的距离，如果 一个样本在特征空间中的k 个最相似 ( 即特征空间中最邻近) 的样本中的大多

7、数属于某一个 类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的 类别来决定待分样本所属的类别。 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并 且直到新的 （未标记的） 样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练 样本由 N维数值属性描述，每个样本代表N维空间的一个点。这样， 所有训练样本都存放在 N维模式空间中。给定一个未知样本，k- 最临近分类法搜索模式空间，找出最接近未知样本 的 K 个训练样本。这K 个训练样本是未知样本的K 个“近邻”。“临近性”又称为相异度 （Dissimilarity），由欧几里德距

8、离定义，其中两个点 X（ x1,x2, xn）和 Y （ y1,y2, yn） 的欧几里德距离是： 22 22 2 11 )(.)()(),( nn yxyxyxyxD 未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时， 未知样本被指定到模式空间中与之最临近的训练样本的类。 4.算法实现 4.1 参数设置 K 值的设定 K 值设置过小会降低分类精度；若设置过大，且测试样本属于训练集中包含数据较少的类， 则会增加噪声，降低分类效果。通常，K 值的设定采用交叉检验的方式（以K=1 为基准）， 通过查找相关资料，K 一般低于训练样本数的平方根，本实验中的训练样本数为100

9、 个， 因此选取 k=7 。 4.2 数据集 本文的实验数据采用软木塞的数据集，软木塞的样本可分为三类，分别用1， 2， 3 3 代表，共150 个样本，我们选取其中的100 个样本为训练集，其余的50 个样本为测 试集。每个样本均包含10 维特征，由于用10 维特征计算量太大，本实验的目的主要 是明白K- 最近邻算法的思想，重点不在计算，因此我们选取其中的两个属性作为本实 验的数据，实验数据的部分截图如图1 所示。 图 1.部分实验数据 4.3 实验步骤 第一步，初始化距离为最大值。 第二步，计算未知样本和每个训练样本的距离dist。 第三步，得到目前K 个最临近样本中的最大距离maxdis

10、t 。 第四步，如果dist小于maxdist ，则将该训练样本作为K- 最近邻样本。 第五步，重复步骤2、3、 4，直到未知样本和所有训练样本的距离都算完。 第六步，统计K- 最近邻样本中每个类标号出现的次数。 第七步，选择出现频率最大的类标号作为未知样本的类标号。 4.4 实验结果与分析 按照上述实验步骤，在matlab 中仿真实现k-近邻分类算法的结果如下图2 所示，图中 的第一列数据表示样本编号，第二列和第三列表示软如塞数据的两位特征的值，第三列的数 字表示本实验的分类结果图，第四列表示样本实际所属类別。 图 3 中列出了详细错误信息。第一行和第一列表示样本类别，第i 行第 j 列的元

11、素表示 第 i 类样本被分为第j 类样本的个数（2 i,j 4），第五列表示每类样本分类错误总数，第六 列表示错误率。由图中数据易得，本实验的平均正确率为86.7%。 4 图 2.7-最近邻分类结果图 图 3.错误统计图 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻 样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因 此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。该 方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知

12、样 本的距离，才能求得它的K 个最近邻点。目前常用的解决方法是事先对已知样本点进 行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域 的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 5.总结与反思 模式分类在现实领域有着非常广泛的应用。 K 近邻算法是模式分类算法中一类常用的算法。本文针对传统的 KNN 算法的不 足之处，提出了两点改进措施。 1. 针对 KNN 算法的计算量大、速度慢的缺点，对训练数据采用了预处理的方法。 首先采用某一聚类方法对训练数据进行分类，然后再与K近邻方法相结合来判断待测 样本的类别。现有的方法都是经过聚类之后确定类别，按一

13、定的规则挑选出来具有代 表性的数据。然后再将这些挑选出来的数据作为训练样本。但这类方法能去除的数据 非常有限，因此对计算量大的改进不大，而本文提出的新的算法：在聚类之后，首先 5 计算出来各个类别的中心，然后只需要考虑待测样本和聚类中心的距离就可以。然后 再根据最终得到的距离的大小判断该点所属的类别。通过实例验证表明，该方法在算 法的时间复杂度方面有一定的改进。 2. 关于准确度的问题，我们主要是舍弃了原来常用的欧式距离的计算公式，主要 考虑了属性对分类的影响，在欧式距离的计算中引入了权值。尽管权值的确定在一定 程度上增加了计算时间的代价，但是从改进分类准确率上来说仍然是必要的，尤其是 在数据

14、中无关属性比较多，传统的分类算法误差较大的情况下学习特征权值尤其适 用。权值的确定也已经有了不少的方法，如可以通过神经网络来确定权值等。本文从 训练样本出发，逐一统计计算每一个属性对分类结果的影响，根据影响的大小来确定 权值。通过实例验证，可知这种方法得到的权值和其他常用的方法相比，在分类准确 度方面有一定的提高。 6 参考文献 1 邓 箴 , 包 宏 . 用 模 拟 退 火 改 进 的KNN 分 类 算 法 J 计 算 机 与 应 用 化 学 ， 2010,27(3):303 307 2郭躬德，黄杰，陈黎飞. 基于 KNN 模型的增量学习算法J模式识别与人工 智能， 2010 ， 23( 5

15、):701 707 3黄杰，郭躬德，陈黎飞. 增量 KNN 模型的修剪策略研究J小型微型计算机 系统， 2011 ， 5(5):845 849 4李欢， 焦建民 简化的粒子群优化快速 KNN 分类算法 J 计算机工程与应用， 2008 ， 44( 32): 57 59 5王晓晔， 王正欧 K最近邻分类技术的改进算法 J电子与信息学报，2005， 27(3):487 491 6 Guo Gongde， Wang Hui ， Bell D， et al Using KNN model for automatic text categorizationJ.Soft Computing-A Fusio

16、n of Foundation， Methodologies and Application,2006,10(5):423 430 7余小鹏，周德翼一种自适应k最近邻算法的研究J计算机应用研究， 2006(2): 70 72 7 附件 1： 源代码KNN.m % % KNN.m K- 最近邻分类算法 % % 上课机器学习模式识别课件数据 CORK_STOPPERS.xls,2); f=zeros(150,5); f(:,1:2)=A(1:150,3:4); f1=A(1:50,3:4); f2=A(51:100,3:4); f3=A(101:150,3:4); cls=zeros(150,10

17、); for i=1:150 for j=1:150 cls(i,j)=norm(f(i,1:2)-f(j,1:2); end end 8 % 对计算出的每个样本和其他150 个样本（包括自己）的距离排序，选K=10 array=zeros(300,11); for ii=1:150 value,index=sort(cls(ii,:); array(2*ii-1,:)=value(1:11); array(2*ii,:)=index(1:11); end % 对每个样本分类 for ii=1:150 a11=length(find(array(2*ii,:)50 if(max(max(a11

18、,a12),a13)=a11) f(ii,3)=1; else if(max(max(a11,a12),a13)=a12) f(ii,3)=2; else f(ii,3)=3; end end end % 错误计算 error=zeros(3,5); for i=1:50 if(f(i,3)=2) error(1,2)=error(1,2)+1; end if(f(i,3)=3) 9 error(1,3)=error(1,3)+1; end if(f(50+i,3)=1) error(2,1)=error(2,1)+1; end if(f(50+i,3)=3) error(2,3)=error(2,3)+1; end if(f(100+i,3)=1) error(3,1)=error(3,1)+1; end if(f(100+i,3)=2) error(3,2)=error(3,2)+1; end end for k=1:3 %D 第四列表示错误数 error(k,4)=error(k,1)+error(k,2)+error(k,3); error(k,5)=error(k,4)/50; end