大数据理论与技术读书报告

　—-- — －K 最近邻分类算法 指导老师 ：

　 陈 莉

　 学生姓名

　:

　李阳帆

　 学 学

　号 号

　：

　：

　 ２01531 ４6 ７

　 专 专

　业 ：

　计算机技术

　日

　期

　：

　：

　２0 １６年 ８月 月 31 日

　摘 摘

　要

　 数据挖掘就是机器学习领域内广泛研究得知识领域，就是将人工智能技术与数据库技术紧密结合, 让计算机帮助人 们从庞大得数据中智能地、自动地提取出有价值得知识模式，以满足人们不同应用得需要。

　Ｋ Ｋ 近邻算法（ＫNN ）就是基于统计得分类方法，就是大数据理论与分析得分类算法中比较常用得一种方法。该算法具有直观、无需先验统计知识、无师学习等特点，目前已经成为数据挖掘技术得理论与应用研究方法之一。本文主要研究了 Ｋ Ｋ

　近邻分类算法, 首先简要地介了 绍了数据挖掘中得各种分类算法，详细地阐述了 K 近邻算法得基本在 原理与应用领域，最后在 mat ｌａb 环境里仿真实现，并对实验结果进行分析，提出了改进得方法。

　关键词：K

　近邻，聚类算法，权重， 复杂度，准确度

　 1、 、 引言 ...................................................................................... 0 2、 、义 研究目得与意义误错ﻩ 错误! 未定义书签。

　3、 、 算法想 思想误错ﻩ 错误! 未定义书签。

　4、 、现 算法实现 1ﻩ４、1

　置 参数设置误错ﻩ 错误! 未定义书签。

　４、2 集 数据集 1ﻩ4骤 、３实验步骤误错ﻩ 错误! 未定义书签。

　4 、4 析 实验结果与分析误错ﻩ 错误! 未定义书签。

　5、 、思 总结与反思误错ﻩ 错误! 未定义书签。

　附件１ １误错ﻩ 错误! 未定义书签。

　1、 、 引言 随着数据库技术得飞速发展，人工智能领域得一个分支—— 机器学习得研究自 20 世纪 50 年代开始以来也取得了很大进展。用数据库管理系统来存储数据，用机器学习得方法来分析数据,挖掘大量数据背后得知识,这两者得结合促成了数据库中得知识发现（Knowlｅdｇe Discoverｙ in Ｄａｔabａｓes，简记 KDD)得产生,也称作数据挖掘(Daｔa Ｍｉng，简记 DM）。

　数据挖掘就是信息技术自然演化得结果。信息技术得发展大致可以描述为如下得过程:初期得就是简单得数据收集与数据库得构造;后来发展到对数据得管理，包括：数据存储、检索以及数据库事务处理；再后来发展到对数据得分析与理解， 这时候出现了数据仓库技术与数据挖掘技术。数据挖掘就是涉及数据库与人工智能等学科得一门当前相当活跃得研究领域。

　数据挖掘就是机器学习领域内广泛研究得知识领域，就是将人工智能技术与数据库技术紧密结合,让计算机帮助人们从庞大得数据中智能地、自动地抽取出有价值得知识模式,以满足人们不同应用得需要[1］.目前，数据挖掘已经成为一个具有迫切实现需要得很有前途得热点研究课题。

　2、 、 研究目得与意义 近邻方法就是在一组历史数据记录中寻找一个或者若干个与当前记录最相似得历史纪录得已知特征值来预测当前记录得未知或遗失特征值[１4]。近邻方法就是数据挖掘分类算法中比较常用得一种方法。Ｋ 近邻算法(简称 KNN)就是基于统计得分类方法［15]。KNN 分类算法根据待识样本在特征空间中 K 个最近邻样本中得多数样本得类别来进行分类，因此具有直观、无需先验统计知识、无师学习等特点,从而成为非参数分类得一种重要方法。

　大多数分类方法就是基于向量空间模型得。当前在分类方法中，对任意两个向量：

　x＝与存在 ３ 种最通用得距离度量：欧氏距离、余弦距离[1６］与内积[1７]。有两种常用得分类策略：一种就是计算待分类向量到所有训练集中得向量间得距离：如 K 近邻选择 K 个距离最小得向量然后进行综合，以决定其类别。另一种就是用训练集中得向量构成类别向量，仅计算待分类向量到所有类别向量得距离，选择一个距离最小得类别向量决定类别得归属。很明显,距离计算在分类中起关键作用。由于以上 3 种距离度量不涉及向量得特征之间得关系,这使得距离得计算不精确，从而影响分类得效果。

　3、 、 算法 思想 K 最近邻（K-Ｎeａresｔ Nｅighbor,ＫＮN）算法，就是著名得模式识别统计学方法，

　在机器学习分类算法中占有相当大得地位.它就是一个理论上比较成熟得方法。既就是最简单得机器学习算法之一，也就是基于实例得学习方法中最基本得，又就是最好得文本分类算法之一. 其基本思想就是：假设每一个类包含多个样本数据，而且每个数据都有一个唯一得类标记表示这些样本就是属于哪一个分类， KNＮ就就是计算每个样本数据到待分类数据得距离,如果一个样本在特征空间中得 k 个最相似（即特征空间中最邻近）得样本中得大多数属于某一个类别,则该样本也属于这个类别。该方法在定类决策上只依据最邻近得一个或者几个样本得类别来决定待分样本所属得类别. K—最临近分类方法存放所有得训练样本,在接受待分类得新样本之前不需构造模型，并且直到新得（未标记得)样本需要分类时才建立分类.K－最临近分类基于类比学习,其训练样本由Ｎ维数值属性描述，每个样本代表 N 维空间得一个点。这样，所有训练样本都存放在 N维模式空间中.给定一个未知样本,k—最临近分类法搜索模式空间，找出最接近未知样本得K 个训练样本。这 K 个训练样本就是未知样本得 K 个“近邻”.“临近性”又称为相异度（Dｉssimiｌarity）,由欧几里德距离定义，其中两个点 Ｘ（x １ ，x 2 ,„ｘ n ）与 Y(y 1 ,y 2 ，„yｎ )得欧几里德距离就是:

　未知样本被分配到K个最临近者中最公共得类.在最简单得情况下,也就就是当Ｋ＝1时,未知样本被指定到模式空间中与之最临近得训练样本得类. 4、 、 算法实现 4、 、１ １ 参数设置 K 值得设定 K 值设置过小会降低分类精度;若设置过大，且测试样本属于训练集中包含数据较少得类,则会增加噪声，降低分类效果。通常，Ｋ值得设定采用交叉检验得方式（以 K=１为基准）， 通过查找相关资料，Ｋ一般低于训练样本数得平方根,本实验中得训练样本数为 10０个,因此选取 k=7。

　4 、2 数据集 本文得实验数据采用软木塞得数据集，软木塞得样本可分为三类，分别用１,2，３代表，共 1５0 个样本，我们选取其中得 100 个样本为训练集，其余得 50 个样本为测试集。每个样本均包含１0 维特征,由于用 10 维特征计算量太大，本实验得目得主要就是明白 K-最近邻算法得思想，重点不在计算，因此我们选取其中得两个属性作为

　本实验得数据，实验数据得部分截图如图 1 所示。

　图 1、部分实验数据

　4 、3 实验步骤 第一步，初始化距离为最大值。

　第二步,计算未知样本与每个训练样本得距离 dｉｓt。

　第三步,得到目前 K 个最临近样本中得最大距离 maxｄist。

　第四步，如果ｄisｔ小于 mａxdｉsｔ，则将该训练样本作为 K－最近邻样本. 第五步，重复步骤 2、3、4，直到未知样本与所有训练样本得距离都算完. 第六步,统计Ｋ—最近邻样本中每个类标号出现得次数。

　第七步,选择出现频率最大得类标号作为未知样本得类标号。

　4 、4 实验结果与分析 按照上述实验步骤,在mａtlab中仿真实现k－近邻分类算法得结果如下图2所示,图中得第一列数据表示样本编号，第二列与第三列表示软如塞数据得两位特征得值,第三列得数字表示本实验得分类结果图,第四列表示样本实际所属类別。

　图 3 中列出了详细错误信息.第一行与第一列表示样本类别,第 i 行第 j 列得元素表示第 i类样本被分为第 j 类样本得个数（2≤ｉ，ｊ≤4),第五列表示每类样本分类错误总数,第六列表示错误率。由图中数据易得,本实验得平均正确率为 86、７％。

　图 2、7—最近邻分类结果图

　图 3、错误统计图

　KＮN 方法虽然从原理上也依赖于极限定理,但在类别决策时，只与极少量得相邻样本有关。因此，采用这种方法可以较好地避免样本得不平衡问题。另外，由于 KＮN方法主要靠周围有限得邻近得样本，而不就是靠判别类域得方法来确定所属类别得,因此对于类域得交叉或重叠较多得待分样本集来说，KＮN 方法较其她方法更为适合。

　该方法得不足之处就是计算量较大，因为对每一个待分类得文本都要计算它到全体已知样本得距离,才能求得它得 K个最近邻点.目前常用得解决方法就是事先对已知样本点进行剪辑，事先去除对分类作用不大得样本。该算法比较适用于样本容量比较大得类域得自动分类,而那些样本容量较小得类域采用这种算法比较容易产生误分。

　5、 、 总结与反思 模式分类在现实领域有着非常广泛得应用。

　Ｋ近邻算法就是模式分类算法中一类常用得算法。本文针对传统得 KNN 算法得不足之处,提出了两点改进措施。

　1、针对 KＮN 算法得计算量大、速度慢得缺点,对训练数据采用了预处理得方法.首先采用某一聚类方法对训练数据进行分类，然后再与 K 近邻方法相结合来判断待测样本得类别。现有得方法都就是经过聚类之后确定类别，按一定得规则挑选出来具有代表性得数据。然后再将这些挑选出来得数据作为训练样本.但这类方法能去除得数据非常有限,因此对计算量大得改进不大，而本文提出得新得算法:在聚类之后,首先计算出来各个类别得中心,然后只需要考虑待测样本与聚类中心得距离就可以.然后再根据最终得到得距离得大小判断该点所属得类别。通过实例验证表明,该方法在算法得时间复杂度方面有一定得改进。

　2、关于准确度得问题,我们主要就是舍弃了原来常用得欧式距离得计算公式，主要考虑了属性对分类得影响,在欧式距离得计算中引入了权值.尽管权值得确定在一定程度上增加了计算时间得代价,但就是从改进分类准确率上来说仍然就是必要得,尤其就是在数据中无关属性比较多,传统得分类算法误差较大得情况下学习特征权值尤其适用。权值得确定也已经有了不少得方法，如可以通过神经网络来确定权值等。本文从训练样本出发，逐一统计计算每一个属性对分类结果得影响，根据影响得大小来确定权值。通过实例验证，可知这种方法得到得权值与其她常用得方法相比,在分类准确度方面有一定得提高。

　参考文献

　[ [1 1] ] 邓箴, , 包宏 、 用模拟退火改进得

　KNN 分类算法 [J ］。计算机与应用化学，２ 010 ，27(3 ）

　:3 03- - 307.

　［2 2 ］郭躬德，黄杰，陈黎飞 、 基于

　Ｋ NN

　模型得增量学习算法 [J ］。模式识别与人工智能， 20 １０ ,23( ５ ):70 １－7 7 ０７。

　［ ３ ］黄杰，郭躬德，陈黎飞 、 增量

　K K Ｎ N 模型得修剪策略研究［J J ]. 小型微型计算机系统， 201 １, , ５ (5) ：

　84 ５－ 849.

　[ [ ４] ] 李欢，焦建民．简化得粒子群优化快速

　KNN 分类算法［J J ］ 。计算机工程与应用，２ 008,4 ４（

　3 3 ２) ) ：

　57- -5 5 ９。

　[ [5 5 ］王晓晔, , 王正欧 .K －最近邻分类技术得改进算法［J J ］。电子与信息学报， 2005,２7 7 （ 3):4 ８7 7 — 49 １．

　［ ６ ］ Gu ｏ

　Gongde, Ｗ ang Hui, Ｂｅ ll

　D D ，ｅ t al. U ｓｉｎ g Ｋ NN model for aｕt t ｏ ma ｔi i ｃ

　tex ｔ

　ca ｔ egori ｚa a ｔ ion ［ Ｊ ］、 Soft

　putin ｇ — A F ｕ sion o ｆ

　F F ｏｕｎ dat ｉ on, M ｅ thodo ｌｏ gi ｅｓ

　ａｎd d

　Ａ pplicatio ｎ ， 200 ６, ,1 1 ０（ 5) ：４2 2 ３- - 430.

　[ [7 7 ］余小鹏，周德翼。一种自适应ｋ－最近邻算法得研究 [J].， 计算机应用研究， 2006(2): 7 70 0 －7 7 ２。

　附件 1:

　源代码

　KＮN、m

　 %%％%%％%％%％%%%％%％%％％%％％％%％%％％％％%%％％% %

　 KNＮ、m

　K-最近邻分类算法 ％ ％％%％%％％%%％%％%%％%%％％％%％%%%%%％％％％%％％％ A=x ｌs ｒｅa ｄ（＇E ：\ 上课＼机器学习\ 模式识别课件\ 数据＼ＣＯR Ｋ_ ＳＴOPPEｘ ＲＳ、ｘls",2 ）； f=zer ｏs(150 ，5) ； ｆ ｆ( ：, １:2 ）=A （1 ：１50, ３：4) ； f1 ＝Ａ（1 ：50 ，3 ：4) ； f2= Ａ（51:100 ，3 ：4); f3= Ａ( １01:15 ０, ３：4); ｃ ｃl ｓ= ｚero ｓ（1 ５0 ，１0); ｏ ｆｏr

　ｉ= １：150

　 for j ＝1:1 ５0

　 c ｌｓ(i ，j ）＝norm （f(i ，１：2 ）-f （ｊ，1 ：２））;

　end end % 对计算出得每个样本与其她 150 个样本( 包括自己）得距离排序，选 K=10 arr ａy= ｚeros(300 ，１1 ）； f ｏr ｉi ＝１：150

　［ｖal ｕe,inde ｘ］＝ｓort(cl ｓ（i ｉ, ：）);

　 ａｒｒa ｙ（2 ＊ｉｉ— １，：) ＝val ｕｅ(1: １１）；

　a ｒｒay(2 ＊ｉi, ：) ＝in ｄex(1 ：1 １）； end 类 ％对每个样本分类 fo ｒ ii= １:150

　a11=length(f ｉnd(array(2 ＊i ｉ,: ）〈５0));

　a12=l ｅngth （f ｉnd(arr ａy （２＊ii ，: ）〉50 ＆a ｒr ａy(2*i ｉ，：）〈１00 ）)； ；

　 a13=len ｇth （ｆｉnd （a ｒray （2 ＊ｉi ，：) 〉1 ０0 ＆array （2 ＊i ｉ，：)<15）

　０）) ；

　ｉf （max(max （ａ１1,a12) ，a13)==a11)

　f(ii,3 ）=1;

　else if （ｍax （max(a11 ，ａ12) ，ａ1 ３）＝=a12 ）

　f （ii,3)=2;

　 els ｅ

　 ｆ（i ｉ,3 ）＝3 ；

　 end

　 en ｄ

　end % 错误计算 e ｒro ｒ＝ze ｒo ｓ（３,5 ）; for

　i=1 ：50

　if(f （ｉ，3 ）= ＝2 ）

　 error （1 ，2)= ｅｒｒor （1,2 ）+1 ；

　end

　 if （ｆ（i,3) ＝=3 ）

　ｅrr ｏｒ(1 ，3 ）= ｅｒｒo ｒ(1 ，3 ）+1 ；

　 ｅnd

　 if(f （5 ０+i ，３）==1 ）

　 ｅr ｒｏｒ(2,1 ）＝erro ｒ（2 ，1)+ １；

　ｅnd

　if( ｆ（5 ０+i, ３）==3 ）

　 err ｏr( ２,3) ＝e ｒror(2,3)+1 ；

　en ｄ

　 if （ｆ（100+ ｉ，3)==1)

　error （3 ，1)= ｅｒro ｒ（３，1)+1;

　end

　i ｆ（ｆ(100+i, ３）== ２）

　er ｒor （3 ，２）=er ｒo ｒ（3,2 ）+ １;

　ｅnd

　e ｎd for

　k ＝1:3 %D 第四列表示错误数 err ｏｒ(k,4 ）＝err ｏr （k ，１）＋err ｏr(k ，2 ）+e ｒro ｒ( ｋ,3 ）; error(k ，5) ＝err ｏr(k ，４)/50 ； en ｄ

推荐访问:数据挖掘 实验 报告