数据挖掘实验报告

大数据理论与技术读书报告 -K最近邻分类算法指导老师 : 陈 莉 学生姓名 : 李阳帆 学 号 : 201531467 专 业 : 计算机技术 日 期 : 2016年8月31日 摘 要 数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能技术和数据库技术紧密结合，让计算机帮助人们从庞大的数据中智能地、自动地提取出有价值的知识模式，以满足人们不同应用的需要。K 近邻算法（KNN）是基于统计的分类方法，是大数据理论与分析的分类算法中比较常用的一种方法。该算法具有直观、无需先验统计知识、无师学习等特点，目前已经成为数据挖掘技术的理论和应用研究方法之一。本文主要研究了 K 近邻分类算法，首先简要地介绍了数据挖掘中的各种分类算法，详细地阐述了K 近邻算法的基本原理和应用领域，最后在matlab环境里仿真实现，并对实验结果进行分析，提出了改进的方法。 关键词：K 近邻，聚类算法，权重，复杂度，准确度 1.引言12.研究目的与意义13.算法思想24.算法实现24.1 参数设置24.2数据集24.3实验步骤34.4实验结果与分析35.总结与反思4附件161.引言随着数据库技术的飞速发展，人工智能领域的一个分支机器学习的研究自 20 世纪 50 年代开始以来也取得了很大进展。用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现（Knowledge Discovery in Databases，简记 KDD）的产生，也称作数据挖掘（Data Ming，简记 DM）。 数据挖掘是信息技术自然演化的结果。信息技术的发展大致可以描述为如下的过程：初期的是简单的数据收集和数据库的构造；后来发展到对数据的管理，包括：数据存储、检索以及数据库事务处理；再后来发展到对数据的分析和理解，这时候出现了数据仓库技术和数据挖掘技术。数据挖掘是涉及数据库和人工智能等学科的一门当前相当活跃的研究领域。 数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能技术和数据库技术紧密结合，让计算机帮助人们从庞大的数据中智能地、自动地抽取出有价值的知识模式，以满足人们不同应用的需要1。目前，数据挖掘已经成为一个具有迫切实现需要的很有前途的热点研究课题。2.研究目的与意义近邻方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史纪录的已知特征值来预测当前记录的未知或遗失特征值14。近邻方法是数据挖掘分类算法中比较常用的一种方法。K 近邻算法（简称 KNN）是基于统计的分类方法15。KNN 分类算法根据待识样本在特征空间中 K 个最近邻样本中的多数样本的类别来进行分类，因此具有直观、无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要方法。 大多数分类方法是基于向量空间模型的。当前在分类方法中，对任意两个向量：x=和存在 3 种最通用的距离度量：欧氏距离、余弦距离16和内积17。有两种常用的分类策略：一种是计算待分类向量到所有训练集中的向量间的距离：如 K 近邻选择K个距离最小的向量然后进行综合，以决定其类别。另一种是用训练集中的向量构成类别向量，仅计算待分类向量到所有类别向量的距离，选择一个距离最小的类别向量决定类别的归属。很明显，距离计算在分类中起关键作用。由于以上 3 种距离度量不涉及向量的特征之间的关系，这使得距离的计算不精确，从而影响分类的效果。3.算法思想K最近邻(K-Nearest Neighbor,KNN)算法，是著名的模式识别统计学方法，在机器学习分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算法之一，也是基于实例的学习方法中最基本的，又是最好的文本分类算法之一。其基本思想是：假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN就是计算每个样本数据到待分类数据的距离，如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N维数值属性描述，每个样本代表N维空间的一个点。这样，所有训练样本都存放在N维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K个训练样本。这K个训练样本是未知样本的K个“近邻”。“临近性”又称为相异度（Dissimilarity），由欧几里德距离定义，其中两个点 X（x1,x2,xn）和Y（y1,y2,yn）的欧几里德距离是：未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。4.算法实现4.1 参数设置K值的设定K值设置过小会降低分类精度；若设置过大，且测试样本属于训练集中包含数据较少的类，则会增加噪声，降低分类效果。通常，K值的设定采用交叉检验的方式（以K=1为基准），通过查找相关资料，K一般低于训练样本数的平方根，本实验中的训练样本数为100个，因此选取k=7。4.2数据集本文的实验数据采用软木塞的数据集，软木塞的样本可分为三类，分别用1，2，3代表，共150个样本，我们选取其中的100个样本为训练集，其余的50个样本为测试集。每个样本均包含10维特征，由于用10维特征计算量太大，本实验的目的主要是明白K-最近邻算法的思想，重点不在计算，因此我们选取其中的两个属性作为本实验的数据，实验数据的部分截图如图1所示。图1.部分实验数据 4.3实验步骤第一步，初始化距离为最大值。第二步，计算未知样本和每个训练样本的距离dist。第三步，得到目前K个最临近样本中的最大距离maxdist。第四步，如果dist小于maxdist，则将该训练样本作为K-最近邻样本。第五步，重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完。第六步，统计K-最近邻样本中每个类标号出现的次数。第七步，选择出现频率最大的类标号作为未知样本的类标号。4.4实验结果与分析按照上述实验步骤，在matlab中仿真实现k-近邻分类算法的结果如下图2所示，图中的第一列数据表示样本编号，第二列和第三列表示软如塞数据的两位特征的值，第三列的数字表示本实验的分类结果图，第四列表示样本实际所属类別。图3中列出了详细错误信息。第一行和第一列表示样本类别，第i行第j列的元素表示第i类样本被分为第j类样本的个数（2i,j4），第五列表示每类样本分类错误总数，第六列表示错误率。由图中数据易得，本实验的平均正确率为86.7%。 图2.7-最近邻分类结果图图3.错误统计图KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。5.总结与反思模式分类在现实领域有着非常广泛的应用。K近邻算法是模式分类算法中一类常用的算法。本文针对传统的 KNN 算法的不足之处，提出了两点改进措施。 1.针对 KNN 算法的计算量大、速度慢的缺点，对训练数据采用了预处理的方法。首先采用某一聚类方法对训练数据进行分类，然后再与K近邻方法相结合来判断待测样本的类别。现有的方法都是经过聚类之后确定类别，按一定的规则挑选出来具有代表性的数据。然后再将这些挑选出来的数据作为训练样本。但这类方法能去除的数据非常有限，因此对计算量大的改进不大，而本文提出的新的算法：在聚类之后，首先计算出来各个类别的中心，然后只需要考虑待测样本和聚类中心的距离就可以。然后再根据最终得到的距离的大小判断该点所属的类别。通过实例验证表明，该方法在算法的时间复杂度方面有一定的改进。 2.关于准确度的问题，我们主要是舍弃了原来常用的欧式距离的计算公式，主要考虑了属性对分类的影响，在欧式距离的计算中引入了权值。尽管权值的确定在一定程度上增加了计算时间的代价，但是从改进分类准确率上来说仍然是必要的，尤其是在数据中无关属性比较多，传统的分类算法误差较大的情况下学习特征权值尤其适用。权值的确定也已经有了不少的方法，如可以通过神经网络来确定权值等。本文从训练样本出发，逐一统计计算每一个属性对分类结果的影响，根据影响的大小来确定权值。通过实例验证，可知这种方法得到的权值和其他常用的方法相比，在分类准确度方面有一定的提高。 参考文献1邓箴,包宏.用模拟退火改进的 KNN 分类算法J计算机与应用化学，2010,27(3):3033072郭躬德，黄杰，陈黎飞.基于 KNN 模型的增量学习算法J模式识别与人工智能，2010，23( 5):7017073黄杰，郭躬德，陈黎飞.增量 KNN 模型的修剪策略研究J小型微型计算机系统，2011，5(5):8458494李欢，焦建民简化的粒子群优化快速 KNN 分类算法J计算机工程与应用，2008，44( 32): 57595王晓晔，王正欧K最近邻分类技术的改进算法J电子与信息学报，2005，27(3):4874916Guo Gongde，Wang Hui，Bell D，et al Using KNN model for automatic text categorizationJ.Soft Computing-A Fusion of Foundation， Methodologies and Application,2006,10(5):4234307余小鹏，周德翼一种自适应k最近邻算法的研究J计算机应用研究，2006(2): 7072附件1：源代码 KNN.m% KNN.m K-最近邻分类算法%A=xlsread(E:上课机器学习模式识别课件数据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);for i=1:150 for j=1:150 cls(i,j)=norm(f(i,1:2)-f(j,1:2); endend %对计算出的每个样本和其他150个样本（包括自己）的距离排序，选K=10array=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&array(2*ii,:)100&array(2*ii,:)150); if(max(max(a11,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) 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 endfor k=1:3%D第四列表示错误数error(k,4)=error(k,1)+error(k,2)+error(k,3);error(k,5)=error(k,4)/50;end