基于自然邻居和最小生成树的原型选择算法研究

发布时间：2017-09-14 01:50

  本文关键词：基于自然邻居和最小生成树的原型选择算法研究

  更多相关文章： K最近邻居 原型选择 自然邻居 最小生成树 分类

【摘要】：在数据挖掘和机器学习中,K最近邻居因其简单有效而得到了长足的发展和广泛的应用。然而,传统的K最近邻居有两个主要的局限性:参数K的选择以及在大规模数据集情况下过高的时间和空间复杂度需求。当KNN算法应用时,参数K取不同的值可能对算法的效果产生很大的影响。同时用于KNN分类的训练集中通常都包含有很多的噪声杂质和冗余的无用信息,在使用这些数据集进行KNN分类任务时,不仅会使得计算处理量巨大,而且还可能会影响算法的分类准确性。因此在处理模式识别、分类学习等相关问题时,对原始训练集进行有效地预处理是非常有必要的。数据集预处理的一个重要手段就是数据约简,而原型选择就是一个常用的数据约简方法。原型选择是对原始数据集进行选择性的约简,在保证最终保留的原型集能够不降低甚至提升分类准确率的前提下,获取具有较高分类贡献的,同时能够反映原始数据集的分布状况,具有一定代表性的原型子集。通过原型选择算法对数据集进行约简,不仅可以有效降低数据集的规模,提高分类算法的计算处理效率;还可以对数据集的分类准确率有所提升。虽然KNN算法应用中的时间复杂度和空间复杂度高的问题已经被研究多年,但是在实际应用中依然没有得到很好的解决,多数原型选择算法获得较低的分类准确率和较高的原型保留率。为了既能有效降低数据集的规模,同时又能保证最终保留的原型集的分类准确率不降低甚至有所提升;通过对现有原型选择算法的研究与分析,本文提出了一个新的原型选择算法,即基于自然邻居和最小生成树的原型选择算法。主要研究内容如下:(1)归纳和阐述了k最近邻居分类和原型选择相关概念和问题,给出了原型选择算法的不同分类方式,阐述了k最近邻分类和原型选择问题的关系。最后对一些经典的原型选择算法以及近年来新提出的原型选择算法进行了较为详细的介绍。(2)针对KNN应用中的参数k值选择难问题,引入了自然邻居的概念,并研究了在均匀分布和高斯分布等不同数据结构和不同数据规模下的自然邻居特性。具体研究了数据集平均自然邻居数目的稳定性和变化趋势,并研究构造了几种有用的自适应自然邻域图。通过实验发现均匀分布数据集的平均自然邻居数目相对高斯分布更为稳定,高斯分布数据集的值容易受离群点的影响。因此针对自然邻居的搜索算法进行改进,引入到原型选择中,有效去除离群点的影响。(3)针对现有原型选择算法存在原型选择约简率不够高和分类准确率有所下降的问题,提出了基于自然邻居和最小生成树的原型选择算法(Prototype Selection based on Natural Neighbor and MST,PS2NM),算法保留了一些对分类贡献较大的关键原型点,同时移除大多数对分类没有什么贡献的点。不同于其它原型选择算法,我们提出的算法使用了自然邻居这个新的邻居概念来做数据预处理,然后基于设定的控制策略建立最小生成树。基于最小生成树,我们保留大多数有用的边界原型,同时生成少量具有代表性的内部原型保留下来。本文提出的算法使用自然邻居做数据预处理,取代基于KNN的预处理操作,有效去除了参数选择问题。通过人工数据集实验展示了PS2NM算法能够有效去除噪声数据和冗余原型,保留的原型集具有跟原始训练集相同的分布情况;通过UCI基准数据集实验,将PS2NM同传统的原型选择算法(CNN、ENN)和最近的原型选择算法(TRKNN、PSC、BNNT)进行比较,结果显示本文提出的算法有效的约简了原型的数量,算法最终选择的原型集用于分类时,保持了与传统KNN相同水平的分类准确率。而且,在分类准确率和原型保留率上,本文提出的算法与其它原型选择算法相比还有一些优势。
【关键词】：K最近邻居 原型选择 自然邻居 最小生成树 分类
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP181
【目录】：

• 中文摘要3-5
• 英文摘要5-10
• 1 绪论10-15
• 1.1 研究背景及意义10-11
• 1.2 国内外研究现状11-13
• 1.3 本文研究的主要内容13
• 1.4 组织结构13-15
• 2 基于k最近邻分类的原型选择概述15-25
• 2.1 K最近邻分类15
• 2.2 原型选择基础15-16
• 2.3 原型选择相关概念16-17
• 2.4 原型选择评价标准17
• 2.5 原型选择算法的分类17-19
• 2.5.1 搜索方向17-19
• 2.5.2 选择类型19
• 2.6 基于k最近邻分类的原型选择19-24
• 2.6.1 CNN算法19-20
• 2.6.2 ENN算法20-21
• 2.6.3 TRKNN算法21-22
• 2.6.4 PSC算法22-23
• 2.6.5 BNNT算法23-24
• 2.7 本章小结24-25
• 3 自然邻居25-33
• 3.1 自然邻居的形成25-26
• 3.2 自然邻居的定义26
• 3.3 自然邻居相关特性26-31
• 3.3.1 值的稳定性26-29
• 3.3.2 自然邻域图29-31
• 3.4 本章小结31-33
• 4 基于自然邻居和最小生成树的原型选择算法33-50
• 4.1 数据预处理33-35
• 4.2 最小生成树的建立35-38
• 4.3 原型选择38-39
• 4.4 算法时间复杂度分析39-40
• 4.5 实验及分析40-48
• 4.5.1 人工数据集实验40-41
• 4.5.2 UCI数据集实验41-48
• 4.6 本章小结48-50
• 5 总结与展望50-53
• 5.1 总结50-51
• 5.2 展望51-53
• 致谢53-54
• 参考文献54-57
• 附录57
• A. 作者在攻读学位期间发表的论文目录57
• B. 作者在攻读学位期间参与的科研项目目录57

【相似文献】

中国期刊全文数据库 前10条

1 薛春艳;;最小生成树在城市高速公路问题中的应用[J];电脑编程技巧与维护;2009年06期

2 胡红;;最小生成树的应用及拓展探讨[J];洛阳师范学院学报;2012年02期

3 毛华;史田敏;高瑞;;求最小生成树的矩阵算法[J];郑州大学学报(理学版);2013年04期

4 杨国慧,周春光,黄艳新,吕慧英;最小生成树用于基因表示数据的聚类算法[J];计算机研究与发展;2003年10期

5 杨旭;;求最小生成树的另一算法及其与其它算法的比较[J];重庆电力高等专科学校学报;2003年02期

6 周玉林;最小生成树与次小生成树上的算法分析与设计[J];上饶师范学院学报(自然科学版);2005年03期

7 陈国龙;郭文忠;涂雪珠;陈火旺;;求解多目标最小生成树问题的改进算法[J];软件学报;2006年03期

8 欧阳浩;肖建华;;基于网格的最小生成树聚类算法[J];计算机与现代化;2006年12期

9 阎少宏;王秋丽;杨爱民;;最小生成树问题的分析与研究[J];商场现代化;2007年11期

10 余荣祖;王宇平;;求解多目标最小生成树的一种改进的非支配排序遗传算法[J];电子科技;2007年06期

中国重要会议论文全文数据库 前10条

1 黄宜真;张世R，

本文编号：847168