实例约简是基于实例的学习算法中的一个比较关键的任务。基于实例的学习算法使用整个训练集来构造决策面,如果训练集中包含过多的实例,就会造成算法在分类阶段消耗大量的内存空间和计算时间,甚至让人无法忍受。实例约简通过对训练集进行约简从而降低算法在分类阶段的空间和时间消耗。k-最近邻居分类是一种典型的基于实例的学习算法,因其直观、简单和易用性等特点,在机器学习、数据挖掘和模式识别等邻域中获得了广泛的应用,当前已经成为数据挖掘领域的十大算法之一。k-最近邻居的实例约简方法主要可以分为:裁剪的方法、压缩的方法和混合的方法。裁剪的方法通过删除数据集对分类有害的数据(噪声)来提高算法的分类精度。压缩的方法则认为决策边界上的数据包含了分类中的关键的信息,而远离决策边界的数据则包含少量的或者不包含决策信息。所以经典的压缩最近邻居算法试图通过最近邻居决策对训练集进行约简,通过删除那些能够被最近邻居准则正确分类的数据,从而获得一个和训练集一致的子集来代替原始训练集进行分类。而混合的方法则综合了上述两种算法的特性,通常来说,裁剪算法被用来作为数据的噪声过滤器,去除噪声、平滑决策边界,然后再使用压缩的算法对数据集进行约简。虽然当前实例约简算法已经取得了大量的成果,但是其面临三个主要的问题:参数依赖问题、噪声敏感问题和约简率低的问题。为了克服以上问题,本文将自然邻居概念引入到实例约简中。自然邻居是一种新的邻居形式,它是一种无尺度的邻居概念。每个数据点的自然邻居可以由自然邻居搜索算法自动获得。自然邻居的提出解决了最近邻居的邻域参数选择问题,但是其结构也适合于处理最近邻居思想所面临的实例约简问题。本文对自然邻居在实例约简中的应用进行了研究,主要创新和贡献包括以下几个方面:(1)提出一种自适应的裁剪自然邻居算法ENaN,解决基于裁剪的实例约简算法的参数依赖和噪声敏感等问题。该算法通过删除那些不能被自身的自然邻居正确分类的点,从而对噪声数据进行裁剪。自然邻居无尺度的特性,使得ENa N算法不需要参数。自然邻居个数不固定的特性,使得ENaN算法可以降低因为噪声数据的影响所导致的误删,从而具有抗噪能力。最具代表性的实例裁剪算法就是裁剪自然邻居算法ENN,它通过删除那些不能被它的k-最近邻居正确分类的点,从而对数据集进行去噪,以提高算法的分类精度。但是,ENN算法计算复杂性高,需要设置参数k,而且还对噪声点敏感。ENaN算法解决了ENN所遇到的上述问题。此外,自然邻居算法的离群点检测能力,使得ENaN能够删除掉数据集中的全局离群点。以上特性使得新提出的算法能够非常容易的使用到其它约简算法中作为预处理算法(噪声过滤器),用以去除噪声和平滑决策边界。(2)提出一种融合自然邻居的混合实例约简算法IRNN,解决基于压缩的实例约简算法的参数依赖、噪声敏感和压缩率低的问题。该算法使用自然邻居暗含的密度信息来搜索数据集核心点,使用约束最近邻居链来查找边界点。基于压缩的实例约简算法认为处于决策边界附近的点对分类精度的贡献最大,而远离决策边界的点对分类精度的贡献非常弱。因此,基于压缩的实例约简算法通过保留决策边界附近的点,而删除远离决策边界的点,来对数据集进行压缩。但是,通过大量的实验发现,虽然边界点含有的信息在决策中占主要地位,但是适当的保留内部核心点可以极大的提高分类精度,特别是在数据集分布特别复杂的情况下。由于自然邻居中隐含有密度信息,利用这些信息能够对内部核心点进行搜索。另外一方面,使用约束最近邻居链对边界点进行查找。最后,将核心点和边界点融合起来,就构成了最终的约简集。该算法的优点在于不需要参数,对噪声不敏感。而且在极大的提高算法的约简率的同时能够保证甚至提高精度。(3)提出一种无参数的基于自然邻域图的实例约简算法NNGIR,解决基于图的实例约简算法的约简率低和参数依赖等问题。图是一种常用的数据点之间关系表示的有效方式,被大量运用于聚类和流行学习中。当我们给一个图的节点加上类别信息之后,图结构中就包含了我们所需要的决策信息。自然邻居邻域图是一种自动生成的图结构,是一种扩展的最近邻居邻域图。将带标签的自然邻居邻域图应用到实例约简中,定义了两种边来对数据集进行约简,即顶点类别相同的定义为同构边,反之,则定义为异构边。同构边和异构边可以判断数据点相对于决策面的位置,从而查找出边界点集合和核心数据点集合,二者构成最终的约简集。该算法在无参数的情况下,对训练集进行了极大的约简。更重要的是该算法在不同类型的数据集上都可以获得很高的压缩率,而且压缩率的波动幅度小,具有很强的适应性。