基于密度的样本裁剪算法的改进及在knn中的应用研究

《基于密度的样本裁剪算法的改进及在knn中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文基于密度的样本裁剪算法的改进及在kNN中的应用研究姓名：杨营辉申请学位级别：硕士专业：计算机系统结构指导教师：熊忠阳2010-04重庆大学硕士学位论文摘要中文摘要随着信息技术的飞速发展和迅速普及，人们可以方便快捷地获得大量的信息。然而，在浩瀚的信息海洋里，如何快速准确地找到所需要的信息已经成为人们不得不面对的现实问题。因此，海量信息的组织管理和高效利用已经成为急需解决的问题。目前，大多数信息表现为文本形式，为了有效利用这些文本信息，对它们进行高效、合理的分类是非常必要的。所以，

2、文本分类已经成为处理大量文本信息的关键技术，并已成为数据挖掘领域中一个重要的研究方向。本文对文本分类及其相关技术进行了研究。首先介绍了文本分类的发展概况和文本分类过程中的相关技术，重点介绍了文本预处理、文本的表示、文本特征向量的提取、特征向量的加权、文本分类的经典算法kNN(knearestneighbor)、训练样本裁剪算法以及文本分类效果评估等；其次，分析了kNN算法和训练样本裁剪算法的不足并对其做出了改进。本文研究内容和创新工作主要包括以下两大方面：第一，对训练样本裁剪算法进行改进。在文本分类中，

3、训练集的分布状态会直接影响kNN分类器的效率和准确率。通过分析基于密度的kNN文本分类器训练样本的裁剪方法，发现它存在两大不足：一是裁减之后的均匀状态只是以e为半径的球形区域意义上的均匀状态，而非最理想的均匀状态即两两样本之间的距离相等；二是未对低密度区域的样本做任何处理，裁减之后仍存在大量不均匀的区域。针对这两处不足，提出了以下两点改进：一是优化了裁减策略，使裁减之后的训练集更趋于理想的均匀状态；二是实现了对低密度区域样本的补充。通过实验表明，改进后的算法在稳定性和准确率方面都有明显提高。第二，对kN

4、N算法进行改进。原始kNN算法中最佳k值的确定目前还没有很好的方法，一般采用先设定一个初始值（一般为几百到几千之间），然后根据实验测试的结果来不断的调整k值。这不利于kNN算法在实际中的推广应用。针对这种不足，本文在基于密度的训练样本裁剪算法的基础上提出一种改进算法。改进算法的基本思路是：在给定新文本后，考虑训练文本集中，属于该新文本的e邻域的k篇文本，根据这k篇文本所属的类别判定新文本所属的类别。通过实验表明，改进算法较好的解决了kNN算法中参数k取值的问题，同时，在时间效率上也要优于原始kNN算法。

5、在分类效果上，改进算法跟原始kNN算法基本一致。关键词：文本分类，kNN，快速分类，样本裁剪，样本补充I重庆大学硕士学位论文英文摘要ABSTRACTAlongwiththerapiddevelopmentofinformationtechnologyandpopularizationoftheInternet,largevolumesofinformationcanbeacquiredconvenientlyandquickly.However,howtoquicklyandaccuratelyfin

6、dtherightinformationinthevastinformationoceanhasbecomearealisticproblemwhichpeoplehavetoface.Itbecomesanurgentrequirementthatmassiveinformationcouldbemanagedinawell-organizedwayandcouldbeefficientlyutilized.Atthepresenttime,mostinformationexistsastext.Fo

7、reffectiveutilizationofinformation,theefficientandreasonableclassificationforinformationisverynecessary.Therefore,textclassificationhasbecomeakeytechnologyforvasttextinformationprocessingandhasgraduallybecomeanimportantresearchbranchinthefieldofdataminin

8、g.Researchesontextclassificationanditsrelatedtechnologiesaredoneinthispaper.Thethesisfirstlyintroducesgeneraldevelopmentofautomatedtextcategorization.Specially,someintroductionsaremadesuchastextpreprocessing,textrepresenta