参考文献方面毕业论文的格式范文,与一种改进的K值最近邻自动分类方法相关论文范文检索

这是一篇参考文献方面毕业论文的格式范文,与一种改进的K值最近邻自动分类方法相关毕业论文格式。是参考文献专业与参考文献及样本及互联网方面相关的免费优秀学术论文范文资料，可作为参考文献方面的大学硕士与本科毕业论文开题报告范文和职称论文论文写作参考文献下载。

摘 要：K值最近邻法是常用的一种自动分类算法.当待分类文本与样本集中多个决策样本的距离相等的时候,固定的K值取法不能充分利用样本集,给分类结果带来一定的随机性,影响了自动分类的准确性.本文通过对K值最近邻算法的原理进行深入分析,提出了一种K值动态选取的方案,使得K值最近邻算法的分类准确性有了显著的提高.

关 键 词 ：K值最近邻算法；自动分类；决策样本选取；KNN

中图分类号：TP302.1

随着互联网的发展,互联网网页信息数量急剧增加,根据中国互联网络信息中心（CNNIC）第31次报告,截至2012年12月底,中国网页数量为1227亿个,其中文本信息网页占绝大多数.网页数量的急剧增加使得对互联网信息的分类需求越发迫切.文本自动分类是数据挖掘领域中一种重要的技术,它从一组已知的训练样样本中发现分类模型,并且使用这个分类模型来预测待分类样本的类别[1].

K值最近邻算法（KNN算法）[2]是比较常见的一种用来做文本自动分类的算法,最初的近邻法由Cover和Hart于1968年提出[3].该方法的思路是：如果一个文献在特征空间中的K个最近邻文献中的大多数属于一个类别,则该文献也属于这个类别.KNN算法使用后验概率的估值作为后验概率,是一个次优方法.KNN算法只与邻近的样本有关,通过邻近样本所属的类别来决策,这就使它对于具体的分类体系没有较大的依赖,比较适合于文本自动分类.

一般认为,KNN算法的主要缺点有：一是计算量较大,因为对每一个待分类的文献,都要计算它到全体已知样本的距离,才能求得它的K个最近邻点.常用的解决方法一是事先对已经样本点进行剪辑,去除对分类作用不大的样本,另一种方法是用空间换时间,事先将所有样本点的两两距离计算出来并存入相应的位置以备检索.二是处理过程中,所有的临近K值对结果点的影响效果是一样的,不管这个点离它有多远.而在实际应用中,可以采取附加权值的方法,放大临近点对结果的影响.

业界对KNN算法的研究多专注于减少计算量的角度.参考文献[3]提出用概念树来管理类别特征从而减少运算量的思路,参考文献[4][5]提出通过对分类体系各类别均建立代表点来减少运算量的思路,参考文献[6][7]是通过多步骤分级计算来减少计算量提高系统有效性,参考文献[8]则提出利用每次k-NN查询中保存的近邻点到被查询点的距离汁算出近邻点孤立程度上界的提前修剪算法.这些思路和方法,都取得了一定的效果,提高了自动分类系统的有效性.各类文献中关于充分利用样本库的资源来进一步提高分类准确率的方面,讨论的不多.

怎样撰写参考文献本科论文
播放:34061次 评论:3669人

1.等距离样本不公问题及解决

KNN算法严重依赖样本库.一方面来说,如果样本库分布不均匀,某些类型偏多某些类型偏少,则会对分类结果的正确性产生较大的影响,另一方便来说,如果不能充分利用样本库的资源,也可能使得分类结果产生一定的偏差.

KNN算法最重要的步骤就是要计算待分类文本与样本库中各文本的距离,并排序,然后取出前K个文本.文本的距离有多种计算方法,其中一个常用的有效方法是：提取文本的属性向量,然后计算代表文本的属性向量之间的距离,即用向量的距离代表文本的距离.在实际的开发测试过程中我们发现,在样本数量比较大的时候,两个向量之间的距离相同是比较常见的现象,这就导致了等距离文本也是比较常见的.

设T为待分类的文本,Si（i等于1,2,3,等N,N为样本总数）为知识库中的样本,定义Dti为待分文本T到样本Si的距离,根据KNN算法,我们应该取Dti（i等于1,2,3,等N）中最小的K（K≤N）个值,并按照这K个值对应的K个样本来进行分类决策.

设di为Dti（i等于1,2,3,等N）按照从小到大进行排序以后所得的序列,其对应的样本为Si,即T到Si的距离为di,并有d1≤d2≤d3≤等≤dN.按照KNN算法,取di（i等于1,2,3,等N）的前K个值即为距离待分文本T最近的K个样本Si（i等于1,2,3,等K）到待分文本T的距离,只需要根据Si（i等于1,2,3,等K）这K个样本进行分类决策即可.

然而,我们发现,如果dK等于dK+1,那么我们采用Sk而不采用Sk+1进行分类决策就对样本Sk+1不公平,我们没有任何理由选取Sk却不选Sk+1作为分类决策样本,因为这两个样本到待分文本T的距离是完全相等的.但是由于我们只能选取K个样本,Sk与Sk+1必舍其一,这样得到的最后的分类结果可能不是最优.事实上,在我们实验中发现,dK-1

图1 等距离样本不公问题

仔细分析等距离样本不公问题,我们发现固定决策样本个数K是产生问题的直接原因,那么能不能动态修订K值,使得在分类过程中能更加充分的利用已知样本从而获取更高的分类准确率呢?

将K值变大或变小都能解决等距离样本不公的问题.如果存在正整数m或n,能满足dK-m0,那么针对待分类文本T的决策样本就取S1到SK-m这K-m个样本作为决策样本,或者取S1到SK+n共计K+n个样本作为决策样本,这样取到的决策样本对于待分类文本T来说,用于分类决策的样本都是公平的.我们称此方案为基本修正方案.

基本修正方案解决了等距离样本不公问题,但在极端情况下,会出现K为1或者K为样本总量的情况.如果K值取无限大,相当于所有的样本都参与决策,决策起来反而变得困难.如果K值取1,相当于只有距离最近的一个样本参与决策,使用到的决策样本数太少,决策信息不足.以上两种极端情形都会使得分类准确率明显下降.为了提高总体分准率,在基本修正方案的基础上做些修改,可以得到一个次优修正方案：次优修正方案的思路是：设定一个区间[Kmin,Kmax],使得K在这个范围内波动,如果存在dKmin-1等于dKmin,或者存在dKmax等于dKmax+1,K仍然取Kmin或Kmax,而不再持续的增大或缩小K值,这种思路没有完全解决等距离样本不公问题,但他还是解决了部分问题并且使得K值处于一个可控的范围之内. 动态修改KNN算法中K值过程的本质,其实是针对不同的待分类文本的特点,在一定的范围内,动态选取决策样本数量的过程.由于每个待分类文档相互独立,没有相关性,所以实际上并不需要要求对每个待分类文档都采用相同的决策样本数量.根据待分文本的特点动态选取决策样本数量是有效提高分类准确率的可行的思路.

2.测试结果

我们采用已手工分类的100000篇网络文章作为基础,选取其中99000作为样本库,涉及19个大类,另外1000篇作为待分文本.采用KNN算法对1000篇待分文本进行自动分类.分别采用固定K值法、基本修正方案法和次优修正方案法三种方法来进行分类,并对分类结果与已知的手工结