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

Prototype Selection Algorithm Based on Natural Neighbor and MST

作　　者：朱庆生[1] 段浪军 杨力军[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机科学》2017年第4期241-245,268,共6页Computer Science

基　　金：国家自然科学基金(61272194)资助

摘　　要：K最近邻居是最流行的有监督分类算法之一。然而,传统的K最近邻居有两个主要的问题:参数K的选择以及在大规模数据集下过高的时间和空间复杂度需求。为了解决这些问题,提出了一种新的原型选择算法,它保留了一些对分类贡献很大的关键原型点,同时移除噪声点和大多数对分类贡献较小的点。不同于其他原型选择算法,该算法使用了自然邻居这个新的邻居概念来做数据预处理,然后基于设定的终止条件构建若干个最小生成树。基于最小生成树,保留边界原型,同时生成一些具有代表性的内部原型。基于UCI基准数据集进行实验,结果表明提出的算法有效地约简了原型的数量,同时保持了与传统KNN相同水平的分类准确率;而且,该算法在分类准确率和原型保留率上优于其他原型选择算法。K-nearest neighbor（KNN）is one of the most popular algorithms for supervised classification.However,the traditional KNN classification has two limitations that the option of parameter K and prohibitive computational and storage demand for large datasets.To overcome these limitations,a new prototype selection algorithm was proposed,which retains some key prototypes that make a large contribution to classification and removes the most of other prototypes with little contribution for classification.Differing from other prototype selection algorithms,the proposal uses a novel neighbor concept natural neighbor to preprocess the dataset and builds minimum spanning tree based on the specific terminal conditions.According to the MST,the prototypes close to boundaries and some internal prototypes are preserved.Experimental results show that the proposed algorithm effectively reduces the number of prototypes while maintaining the same level of classification accuracy as the traditional KNN classification algorithm.Moreover,it is a little bit superior to other prototype selection algorithms in classification accuracy and retention ratio.

关 键 词：K最近邻居 原型选择 自然邻居 最小生成树 分类 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]