在数据挖掘和机器学习中,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相同水平的分类准确率。而且,在分类准确率和原型保留率上,本文提出的算法与其它原型选择算法相比还有一些优势。