《基于欧式距离的实例选择算法研究》由会员分享，可在线阅读，更多相关《基于欧式距离的实例选择算法研究（32页珍藏版）》请在金锄头文库上搜索。
1、河北大学 硕士学位论文 基于欧式距离的实例选择算法研究 姓名：韩光辉 申请学位级别：硕士 专业：应用数学 指导教师：王熙照 2011-05 摘 要 I 摘 要 近邻分类法在训练分类器时需要存储训练集中所有的数据， 这种缺点会导致程序 在运行时需要大量的存储空间和运行时间。 据此， 本文提出了两种新的实例选择算法： 迭代类别实例选择算法 ICIS（Iterative Class Instance Selection）和基于同类 和异类的迭代类别实例选择算法 IISDC （Iterator Instance Selection based on Same and Different Classes
2、） 。两种算法分别提出分类能力评价函数来度量每个实例的分 类能力，挑选分类能力强的实例，删除分类能力弱的实例。经分析得出本文两个算法 的时间复杂度均为 O(n2)。在真实数据库上的实验结果表明， ICIS 和 IISDC 算法在 压缩比、分类精度上优于 FCNN、ICF、ENN 等经典算法。 关键词 实例选择 噪声 近邻法 ICIS IISDC ENN FCNN ICF Abstract Abstract The basic nearest neighbor classifiers suffer from the common problem that the instances used t
3、o train the classifier are all stored indiscriminately, and as a result, the required memory storage is huge and response time becomes slow. In this paper, a new Instances Selection algorithm based on Classification Contribution Function shortly named ISCC and IISDC are presented. Meanwhile，two func
4、tions are introduced to evaluate the classification ability of the instances. Then an instance with the highest value of Classification Contribution Function is added to the condensed subset. The time complexity of ISCC and IISDC are O(n2). Compared to traditional methods, such as FCNN，ICF and ENN,
5、the condensed sets obtained by ISCC and IISDC are superior in storage and classification accuracy. Keywords Instance Selection Noise Nearest Neighbour Rule ICIS IISDC ENN FCNN ICF 第 1 章 绪 论 1 第 1 章 绪 论 1.1 研究背景和意义 机器学习是人工智能的一个子领域，主要用于开发一些让计算机自动“学习”的技 术。更简单的说，机器学习是一种用于设计数据集分析程序的理论。 目前，机器学习在现代生活中已经有了十
6、分广泛的应用例如生物特征识别、搜索引 擎、医学诊断、检测信用卡欺诈、证券市场分析、DNA序列测序、语音和手写识别、 计算机视觉、战略游戏和机器人应用。 通常，基于实例的学习方法不会为目标函数建立起明确的一般化描述，只是简单地 把训练实例存储起来，对这些实例的泛化工作被推迟到分类新的实例时进行。每当学习 器遇到一个新的查询实例，它分析这个新实例与以前存储实例的关系，并据此把一个目 标函数值赋给新实例。因此，基于实例的学习方法有时被称为消极学习法。这种延迟的 或消极的学习方法有一个突出的优点， 即它们不是在整个实例空间上一次性地估计目标 函数，而是针对每个待分类新实例做出局部的和相异的估计，其中最
7、具代表性的算法就 是K 近邻法。K 近邻法是基于实例学习方法的一部分。它有三个关键特性：把在训 练数据上的泛化推迟至一个新的实例查询时执行； 它通过分析相似的实例来分类新的查 询实例，而忽略与查询实例极其不同的实例；它把实例表示为n维欧氏空间中的点。K 近邻算法假定所有的实例对应于n维欧氏空间中的点，一个实例的最近邻是根据标准欧 氏距离定义的。K 近邻算法从来不形成关于目标函数的明确的一般假设，它仅在需要 时计算每个新查询实例的分类。因此，它的归纳偏置是：一个实例的类别最相似于它在 欧氏空间中附近的实例的类别。 基于实例的学习方法与其它机器学习方法相比，一个突出的优点是：基于实例的学 习方法可
8、以为不同的待分类实例建立不同的目标函数逼近函数。事实上，很多技术只建 立目标函数的局部逼近，并将其应用于新分类实例，而不建立在整个实例集合上都表现 良好的逼近。特别是当目标逼近函数很复杂，但可用不太复杂的局部逼近进行描述时， 基于实例的学习方法有着显著的优势。因此，基于实例的推理已经被应用到很多现实任 务中，比如，在咨询台上存储和复用过去的经验；根据以前的法律案件进行推理；通过 复用以前求解的问题的相关部分来解决复杂的调度问题。 河北大学理学硕士学位论文 2 基于实例学习方法的不足是分类新实例的计算量很大， 而且所有的计算都发生在分 类时，而不是在第一次遇到待分类实例时。同时，只有在训练实例足
9、够多时，其分类决 策面才逼近最优分类决策面。 尽管如此，在分类问题中相比于决策树和神经网络等其它学习方法，基于实例的方 法具有训练代价小、假设空间广、增量渐进学习等优点。因此，如何在训练集中选择部 分训练实例， 在保持实例的泛化能力的同时减少查询时所需计算量是基于实例学习的一 个研究重点。 1.2 研究现状 多年来国内外学者已提出许多实例选择算法，按照压缩集中实例产生方式的不同， 这些算法可分为原型法和关键子集法： 原型法利用原始样本产生数目较少的新实例组成 压缩集，研究的重点是新实例的产生方式，这种构造原实例集中并不存在的新实例的方 法可能改变实例集的类分布结构，其合理性仍值得商榷；关键子集
10、法是从原训练集中选 择分类能力强、 有代表性的实例或去除冗余实例。 关键子集法要求有较大的实例压缩比， 同时又不降低近邻学习的分类准确率。 经典算法包括基于启发式搜索方法和基于实例特定邻域的方法。其中，基于启发式 搜索的算法将关键子集的选择看作组合最优化问题，采用启发式搜索策略寻优，如、蒙 特卡罗随机搜索算法 1、遗传算法2，3 Tabu 搜索算法4，5，6 以及蚁群搜索算法7，这些 算法缺点是搜索效果受参数设置影响、所得压缩集具有随机性。基于实例分布的方法又 分为三类：消除噪声实例的方法；基于 CNN（Condensed Nearest Neighbor Rule）系列 方法； 基于实例邻域
11、的方法。 消除噪声的方法是通过删除训练集中被定义为噪声的实例， 目的是减少噪声和提高分类精度。基于 CNN 系列算法充分考虑每个实例的分布，寻找原 始训练集的一致性压缩集。 基于实例特定邻域的方法是通过分析每个实例的特定邻域内 实例集的类别来评价该实例在K 近邻法正确分类中的关键程度，进而决定该实例是否 会被选择到压缩集中。由于基于特定邻域的方法与K 近邻法均是由训练集中实例的相 关邻域决定来决定待分类实例的类别， 所以基于特定邻域的方法一直是实例选择算法研 究的重要方向。 经典的压缩近邻法(Condensed Nearest Neighbor：CNN)8是第一个实例选择算法， 它以待分类实例
12、在当前压缩集中的K个最近邻为特定邻域，若此实例不能被其K-近邻 第 1 章 绪 论 3 正确分类则它被加入当前压缩集中，此算法得到的压缩集是原训练集的一致集，所谓一 致是指在压缩集上使用K 近邻法仍能将原训练集中全部实例正确分类。CNN 算法的 缺点是对原训练集的输入顺序敏感,压缩集中含有冗余样本。1972 年，Gates 针对 CNN 算法的缺点,提出了精简近邻法 ( Reduced Nearest Neighbor Rule：RNN) 9,与 CNN 算法 不同的是RNN以删除样本的方式进行实例选择， 同时证明了如果CNN包含最小一致集， 那么 RNN 也一定包含。1979 年，Gowda
13、 和 Krishna 10对 CNN 算法进行了改进，在 CNN 基础上引入了互近邻值 （Mutual Neighborhood Value： MNV） 的概念。 1987 年， Kibler 和 Aha 提出了与 RNN 选择策略相反的 Shrink 11 算法：在数据集中如果一个实例被去除后 不影响该实例被其近邻正确分类，则此实例可以被删除。1991 年，Aha 提出了 IB1-5 12 系列算法，在实例选择时考虑了每个实例的置信度，并以此作为实例选择的依据。2005 年，Angiulli 提出了 FCNN（Fast Condensed Nearest Neighbor） 13算法，此算法
14、的基本思 想是:初始压缩集为各类类心，每次从各类中选择一个被错误分类且距离当前压缩集中 同类实例最近的实例加入压缩集。2007 年 Angiull 14把 FCNN 算法应用于处理大规模数 据集上，取得了较好的效果。同样，Wilson 等提出的 DROP1-515系列算法也将特定邻 域限定为由实例的 K 个最近邻组成， 若实例所在的特定邻域形成的集合中， 如果其它实 例在剔除该实例时仍能被正确分类，则此实例可排除。CNN 算法和 DROP 系列算法都 固定特定邻域中实例个数为K，显然，这种特定邻域的限定方式忽视了训练集局部疏密 程度对实例选择结果的影响。与此不同，一些算法将特定邻域限定为实例的
15、同类近邻组 成的区域，这些同类近邻位于一个超球体内，超球体半径为实例到此实例的最近异类实 例之间的距离。 实例的特定邻域中实例个数能够体现该实例的最近异类实例位置和训练 集疏密程度。 此实例的是否会被保存到压缩集中取决于实例分类同类近邻域实例集和以 P 为同类近邻的所有实例集被正确分类同类的贡献。例如，迭代样例删除算法(Iterative Case Filtering：ICF) 16将这两个实例集分别称为实例的可达集(Reachable)和覆盖集 (Coverage)，在迭代过程中依据它们的大小关系决定实例的取舍，实验表明 ICF 算法能 较好选择靠近训练集分类边界的实例，且收敛速度快，但不能
16、保证得到一致子集。1995 年，Smyth B. 和 Keane M.T.提出了足迹删除策略算法（Footprint Deletion Policy 17）， 依据 Reachable 和 Coverage 的概念从而确定每个实例的分类能力， 然后依次删除分类能 力弱的实例。选择近邻算法(Selective Nearest Neighbor：SNN18)也使用这两个实例集合 概念，同时考虑最小化一致子集的充分条件：即训练集中所有实例 P 到压缩集中同类实 河北大学理学硕士学位论文 4 例的距离比它到训练集中任一异类实例更近，来获得最小化一致子集，但是，因为使用 了分支界限法来判断充分条件，时间复杂度达到指数级19。1994 年，B. V. Dasarathy 提 出了 MCS 20 (Minimal Consistent Set) 算法， 它以最近异类子
