（应用数学专业论文）基于co_training的数据集重叠问题研究.pdf

中山大学硕士学位论文 基于c o _ t r ainin g 的数据集重叠问题研究 专 业：应用数学 硕士生：周志轩 指导教师：张磊副教授 摘要 分类问题一直是机器学习和数据挖掘领域的重要问题之一。数据集的不平衡 问题一度被视为影响分类效果的主要因素，学术界分别于2 0 0 0 年和2 0 0 3 年举行会 议进行了讨论，学术成果相当丰富。但随着研究的深入，陆续有学者提出数据 集的不平衡问题并不是影响分类效果的关键因素，而不同类别的样本在样本空间 上的重叠问题才是导致分类精度不高的主要原因。目前数据集重叠问题已逐渐成 为新的研究热点，受到越来越多研究者的关注。 现有的处理数据集的重叠问题的方法主要是选择性删除数据和特征提取。选 择性删除数据的目的是找出数据集重叠的区域，并将该区域的样本删除，常用方 法有d a t ac l e a n 和e d i t 。而利用特征提取算法处理数据集的重叠问题的研究目前 还只停留在理论阶段。 本文提出了两个处理数据集重叠问题的方法：基于离群点检测的处理方法， 融合了t o m e kl i n k s 和k n n 两种传统方法，从样本集中找出最近邻类标与之相反 的样本，然后利用k n n 方法判断其是否是离群点，若是，则将其删除。基于半监 督学习法的处理方法，采用的是c ot r a i n i n g 方法。本文将这两种方法应用于u c i 数据库中的数据集，并且与传统处理方法进行比较，相对于传统方法，本文提出 的两种处理方法适用性较广且大多数情况下分类效果有较好的改进。 关键词：数据集重叠离群点k n n神经网络c o _ t r a i n i n g 中山大学硕l ：学位论文 r e s e a r c ho fo v e r l a p p i n gd a t as e tu s i n gc o _ t r a i n i n g m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：z h o uz h 改u a l l s u p e r v i s o r 戈。o f e s r 办a n g l e i a | ；oe , a c e a b s t r a c t c l a s s i f i c a t i o ni so i l eo ft h em o s ti m p o r t a n tp r o b l e m so fr m c h i n el e a r n i n ga n d d a t am i n i n g i m b a l a m e dd a t as e tp r o b l e mw a ss a i dt ob ep r i n c i p a l f a c t o rf o r i n f l u e n ei n gc l a s s i f i c a t i o n sr e s u l t t h e r ew e r et w oa c a d e m i cw o r k s h o p sh o l df o r d i s c u s s i n gi m b a l a n e e dd a t a s e tp r o b l e mi n2 0 0 0a n d2 0 0 3 b u ti l k ) r ea n dn l o r e r e s e a r c h e r sp o i n to u tt h a td a t as e t si m b a l a n e e di sn o tt h ek e yr e a s o nf o rc l a s s i f i e rw i t h b wa c c u r a c yb u td a t a so v e r l a p p i n gi sa f t e ras e r i e se x p e ri m e n t s a tp r e s e n t , t h e p r o b l e mo fd a t a so v e r l a p p i n gh a sb e c o m ea ni n c r e a s i n g l yh o tb e ws t u d ya n dh a s a t t r a c t e dn 】0 r ea n dm e r er e s e a r c h e r s a t t e n t i 0 1 1 t h e r ea r et w om e t h o d so f t e nu s e dt od e a lw i t hd a t a so v e r l a p p i n g ：d e l e t ed a t a o p t i o n a la n df e a t u r ee x t r a c t i o n d e l e t e d a t ao p t i o n a li sa i mt of i n dt h ea r e aw h e r e d a t a so v e r l a p p e da n dd e l e t es o m ed a t as u i t a b l y f o rd e l e t i n gd a t a , t h e r ea l et w o a l g o r i t h m s ：d a t ac l e a na n de d i t f e a t u r ee x t r a c t i o nt m y b eag o o di n e a i l st od e a lw i t h i ti nt h e 如t u r eb u tc a nn o tb eu s ej u s tn o w i nt h i s p a p e r , w eb r i n gf o r w a r dt w op r o c e s sm e t h o d s ：o n ei s b a s i so fo u t l i e r d e t e c t i o n , i tc o m b i n e st w ot r a d i t i o m lm e t h o d s ，t o m e kl i n k sa n dk n n ，i d e n t i f yt h e s a m p l ew h o s en e a r e s tn e r g h b o rb e l o n g st oad i f f e r e n tc l a s s ，a n dt h e n , t od e t e r m i n e w h e t h e rt h e ya r eo u t l i e r sb a s e do nt h ek n nm e t h o d ，a n dd e l e t eo u t l i e r s ；t h eo t h e ri s b a s i so fs e m i - s u p e r v i s e dl e a r n i n ga l g o r i t h m , u s i n gc o _ t r a i n i n gm e t h o d t w om e t h o d s a r ev e r i f i e db yt h ed a t as e t si nu c id a t a b a s e r e s u l ti u d j c a t e st h a tm e t h o d sm e n t i o n e d i nt h i sp a p e rg i v eo u t s t a n d i n gp e r f o r r m n e e k e y w o r d s ： o v e r l a p p e dd a t as e t ，o u t l i e r ，k n n ，a r t i f i c i a ln e u t r a ln e t w o r k s , c o j r a i n m g 2 中山大学硕士学位论文 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名踬妊黧 1 日期：知，年们斗日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论 导师签 日期：日 中山大学硕士学位论文 第一章引言 本章首先介绍本文的选题背景，然后介绍本文的主要内容和体系结构。 1 1 选题背景 数据挖掘与机器学习是一门交叉性的学科，从许多学科吸收了成果和概念， 包括统计学、人工智能、哲学、信息论、生物学、认知科学、计算复杂性和控制 论等。该学科所关注的问题是：计算机如何随着经验积累自动提高性能。近年来， 机器学习被广泛的运用于很多领域，如：检测信用卡交易欺诈的数据挖掘系统， 垃圾电子邮件过滤系统，人脸识别系统等。同时，这个学科的基础理论和算法 也有了重大的进展，是近二十年来迅速发展的学科之一。 分类问题一直是机器学习领域的重要问题之一，在商业领域中的客户行为分 析、网络管理中的安全检测、金融领域中的智能预测、医疗卫生的精确诊断等方 面都有着广泛的应用。为了建立理想的分类模型，研究者除了致力于分类器的构 造和优化外，也专注于对影响分类效果的各种因素的探究。 早期研究者的注意力主要放在分类器的模型设计上，提出了如决策树、神经 网络、贝叶斯分类器等经典工具，近年来兴起的支持向量机也是成果之一。但是， 面对复杂的现实问题，单一分类器很多时候已无法胜任，如：手写字识别、多媒 体信号识别、生物信息识别等，于是信息融合技术如组合分类器技术应运而生。 另一方面，很多研究者开始了针对数据集本身性质的研究，提出了一系列数据集 的预处理方法。这些方法可以分为两类：一类针对数据集中样本的属性作处理， 如：特征选择、特征提取、缺值样本处理、属性为离散值与连续值混合情形的样 本处理等；另一类针对数据集的构成作处理，如：离群点检测问题、数据集不平 衡问题、数据集重叠问题等。 数据集不平衡问题一度被视为影响分类效果的主因，学术界于2 0 0 0 年和 2 0 0 3 年分别举行会议进行了讨论，学术成果相当丰富。但随着研究的深入，陆 续有学者提出：数据集的不平衡并非是数据分类精度不高的关键，而不同类别的 样本在样本空间上的重叠才是导致分类精度不高的主要原因 2 3 4 5 6 。更有学 中山大学硕士学位论文 者进一步指出：不论数据集是否平衡，数据集的重叠都会对分类精度产生很大影 响 7 。 这些文献的结论可总结为下面四点 1 数据集的不平衡往往并不直接影响分类效果。 2 数据集的不平衡通常伴随数据间的重叠。 3 不论使用何种分类器，重叠区域的样本对分类效果的都会有影响。 4 分类器的分类效果受影响程度与样本的重叠程度成正比。 目前数据集重叠问题已逐渐成为新的热点，受到越来越多研究者的关注。 1 2 相关工作与简要评述 现有的处理数据集重叠的方法主要有两类：选择性删除数据和特征提取。 1 选择性删除数据的目的是找出数据集重叠的区域，并将该区域的样本删 除。该类方法主要有两种：e d i t 8 9 和d a t ac l e a n 1o j 。e d i t 通过交叉验证等形式， 找出每次验证时被分错的样本，存入集合s 中，在验证过程结束后在原数据集上 删除s 中的样本。d a mc l e a n 常用的有t o m e kl i n k sa l g o r i t h m 和n e i g h b o u r h o o d c l e a n i n gr u l e s 等，该类方法是通过寻找近邻的方式，探测出可能重叠的样本并 删除。 e d i t 由于需要交叉验证，故时效性较差，而且对验证集个数的选取敏感， 稳定性欠佳。d a t ac l e a n 时效性较e d i t 好，但容易将两类样本的边界误判，效 果还不够理想。 2 特征提取的方法常用的有p c a 、l d a 1 1 和k p c a 1 2 、k l d a 1 z 等，针对 时间序列、文本分类、生物序列识别等还有其特定的方法 1 4 】 1 5 【1 6 1 7 。也有人 用遗传算法加神经网络的方法尝试了一般问题的特征提取 1 8 ，也是一个很好的 尝试。 特征提取从理论上讲是解决数据集重叠最理想的方法。从样本的角度来说， 如果要区分两类样本，则该两类样本间一定有一些根本的区别，这些区别就是特 征。所以，对于数据集重叠问题，我们可以认为是由于没有提取到特征。换句话 说，如果两类问题的特征明显，将不会出现数据集重叠的问题。但是至今几乎没 6 中山大学硕士学位论文 有研究者使用特征提取的方法解决数据集重叠的问题。因为像p c a 、l d a 等方 法往往只是在使用原有数据属性已经具有一定的分类精度的情况下，对分类结果 起到进一步的提高作用。但是若数据集有较多的重叠现象，分类精度将会受到极 大的影响，而p c a 、l d a 等同样无能为力。所以从这个角度来讲，称p c a 、l d a 等方法为“特征增强”更加合适。为了寻找理想的特征提取方法，最近有人用遗 传算法加神经网络做了尝试，但是由于没有一套完整的理论规则作指导，其实用 性欠佳。可以说，该类算法目前还只停留在理论阶段。 1 3 本文主要工作 本文提出了两个处理数据集重叠问题的方法：基于离群点检测的处理方法一 弋h e c k l e a n 和基于半监督学习法的处理方法叫0 一t r a i n i n g 。 c h e c k _ c l e a n 方法的提出完全源自于处理数据重叠问题的d a t ac l e a n 方法中 的t o m e kl i n k s 方法。t o m e kl i n k s 方法是个比较优秀的传统方法，其即具有很好 的时效性，又能比较精确的检测出孤立点。但是，其仍存在两点不足： 第一，t o m e kl i n k s 样本对要求双方互为最近邻且类标相反。假设样本x i 是 一个孤立点，其最近邻x j 类标与之不同，但是样本x j 的最近邻可能是另一个样本 x k ，而不是x i ，这时就无法对孤立点x i 作出正确判断。 第二，由于其将所有t o m e kl i n k s 样本对都删除，这就造成了许多非孤立点 样本被删除和一些边界上的非重叠样本被误删。 本文提出的c h e c k _ c l e a n 方法正是看到了t o m e kl i n k s 方法的这两点不足，不 再以t o m e kl i n k s 样本对为单位，而是以t o m e k 样本为单位，即只要最近邻的类标 不同，就标记为t o m e k 样本。然后再对每一个t o m e k 样本采用k n n 方法判断其是否 为孤立点，只删除其中的孤立点。这样其即继承和改进了t o m e kl i n k s 方法的优 良传统，又克服了以上两点不足。 传统的c o _ t r a i n i n g 方法，分类器f 1 和f 2 分别对应于样本的属性x 1 和x 2 ，对 于高维数据，可以减少近一半的计算量，不失为一个好的处理方法，但是对于维 数不是很高的数据，若再将属性一分为二，分类精度就会受到影响。 因此，本文提出的c o _ t r a i n i n g 方法，对于低维数据，分类器f l 和f 2 都可以 7 中山大学硕士学位论文 对应全部属性，对于一些高维数据，两个分类器都可以对应多于半数的属性，即 它们可以同时使用一部分属性。例如样本x 有1 5 个属性，分类器f l 可以对应前1 0 个属性，而分类器f 2 可以对应后1 0 个属性，其中中间5 个属性为二者共用，这样 两个分类器通过共享信息，从而达到相互影响的目的。并且仿效f a c er e c o g n i t i o n u s i n gu n l a b e l e dd a t a 【2 7 】，分类器f 1 和也都使用多个分类器的组合，在一定程度上 优于单个分类器。 1 4 本文主要内容 文章余下部分是这样安排的：文章第二部分，介绍数据挖掘的现状及本文涉 及的若干主题；第三部分，介绍基于离群点检测的重叠问题处理方法；第四部分， 介绍基于c o t r a i n i n g 的处理方法；第五部分，通过实验验证本文提出的两种处 理方法，并进行分析、总结。 8 中山大学硕士学位论文 第二章论文涉及的若干主题 本章先介绍数据挖掘，接着介绍人工神经网络模型，然后介绍数据集重叠问 题的背景和意义、神经网络模型，最后介绍两类常用的处理方法：d a t ac l e a n 和 e d i t 。 2 1 数据挖掘的定义 数据挖掘 2 1 2 2 1 ( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊 的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。数据挖掘更确切的来说应当命名为“从数据中挖掘 知识”，只是那样显得有点长了，所以普遍采用“数据挖掘”这一短术语。还有一 些术语，具有和数据挖掘类似但稍不同的含义，如数据库中知识挖掘、知识提取、 数据模式分析、数据考古、数据捕捞等。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据 可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、 图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也 可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信 息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人 工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大 量业务数据进行抽取、转换、分析和其他模型化处理，从中提取出可能有潜在价 值的、辅助商业决策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经 有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外， 由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限 制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这 些数据不再是为了分析的目的而收集的，而是由于纯机会的( o p p o r t u n i s t i c ) 商 9 中山大学硕士学位论文 业运作而产生。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决 策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是： 企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过 深层分析，获得有利于商业运作、提高竞争力的信息。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行 探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的 先进有效的方法。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信 息应具有先未知，有效和可实用三个特征。 数据挖掘不是为了替代传统的统计分析技术。相反，他是统计分析方法学的 延伸和扩展。大多数的统计分析技术都基于完善的数学理论和高超的技巧，预测 的准确度还是令人满意的，但对使用者的要求很高。而随着计算机计算能力的不 断增强，我们有可能利用计算机强大的计算能力只通过相对简单和固定的方法完 成同样的功能。一些新兴的技术同样在知识发现领域取得了很好的效果，如神经 元网络和决策树，在足够多的数据和计算能力下，他们几乎不用人的关照自动就 能完成许多有价值的功能。 数据挖掘就是利用了统计和人工智能技术的应用程序，他把这些高深复杂的 技术封装起来。 2 2 人工神经网络模型 本小节涉及到的概念参照了文献【1 9 】。 2 2 1 人工神经网络概述 人工神经网络1 1 9 ( a r t i f i c i a ln e u t r a ln e t w o r k s ，a n n ) 是由大量简单的基本 元件神经元相互连接，通过模拟人的大脑神经处理信息的方式，进行信息并 行处理和非线性转换的复杂网络系统。由于神经网络具有强大的学习功能，可以 比较轻松地实现非线性映射过程，并且具有大规模计算的能力。因此，它在自动 1 0 中山大学硕士学位论文 化、计算机和人工智能领域都有着广泛的适用性，实际上也确实得到了大量的应 用，解决了很多利用传统方法验证以解决的问题。 自第一台计算机于1 9 4 6 年问世以来，电子计算机经过多次更新换代，信息 处理能力不断完善和提高，在信息化社会中占有十分重要的地位。但是计算机在 识别能力上却与人相去甚远。例如，个人可以很容易地识别他人的脸孔，但计 算机很难做到这一点。这是因为脸孔的识别不能用一个精确的数学模型加以描 述，而计算机工作则必须有对模型进行各种运算的指令才行，得不到精确的模型， 程序也就无法编制。而大脑是由生物神经元构成的巨型网络，它在本质上不同于 计算机，是一种大规模的并行处理系统，它具有学习、联想记忆、综合等能力， 并有巧妙的信息处理方法。人工神经网络( 简称神经网络) 也是由大量的功能比 较简单的形式神经元互相连接而构成的复杂网络系统，用它可以模拟大脑的许多 基本功能和简单的思维方式。尽管它还不是大脑的完美无缺的模型，但它可以通 过学习来获取外部的知识并将其存储在网络内，可以解决计算机不易处理的难 题，特别是主意和图像的识别、理解，知识的处理，组合优化计算和智能控制等 一系列本质上为非计算的问题。 因此，神经网络技术在很多领域中等到了广泛的应用，同时已成为当前人工 智能领域中最令人感兴趣和最富有魅力的研究课题之一。 神经网络系统的应用研究主要集中在模式识别( 语音和图像识别) 、经济管 理和优化控制等方面，它和数学、统计中的多个学习有着密切的联系，如线性和 非线性规划问题、数值逼近、统计计算等。另外，在其他信息处理问题中也有很 多的应用，如数据压缩、编码、密码和股市分析等领域，应用内容十分丰富。 2 2 2 人工神经网络模型简介 神经网络【1 9 】是由大量的处理单元( 神经元) 互相连接而成的网络。为了模拟 大脑的基本特性，在神经科学研究的基础上，提出了神经网络的模型。但是，实 际上神经网络并没有完全反映大脑的功能，只是对生物神经网络进行了某种抽 象、简化和模拟。神经网络的信息处理通过神经元的相互作用来实现，知识与信 息的存储表现为网络元件互连分布式的物理联系。神经网络的学习和识别取决于 各神经元连接权系数的动态演化过程。 中山大学硕上学位论文 1 人工神经网络的基本处理单元【1 9 1 归纳一下生物神经元传递信息的过程，可以看出神经元一般表现为一个多输 入( 即它的多个树突和细胞体与其他多个神经元轴突末梢突触连接) 、单输出( 每 个神经元只有一个轴突作为输出通道) 的非线性器件，通用的结构模型【1 9 】如图2 1 所示。 图2 - 1 神经元结构模型 其中，够为神经元，的内部状态，9 为阂值，一为输入信号，吻表示与神经 元t 连接的权值，乃表示某一外部输入的控制信号。 f - 妣z - - - z ，s ( 卅删以 【以( ，) = ( 约( 力) 神经元的输出由函数表示，般利用以下函数表达式来表现网络的非线性 ( 1 ) 阈值型 1 9 1 ，为阶跃函数 俐= 骺描 ( 2 ) 线性型【1 9 】 1 2 中山大学硕士学位论文 ( 3 ) s 型【1 9 】 r ( 彬，= 够+ 易 彬u 2 彬0 u 2 彬 ( 砌2 雨而1 而， 其中f 为常数 s 型函数反映了神经元的饱和特性，由于其函数连续可导，调节曲线的参数 可以得到类似阈值函数的功能，因此，该函数被广泛应用于许多神经元的输出特 性中。 2 人工神经网络的结构 根据连接方式的不同，神经网络的神经元之间的连接的如下几种形式。 以前向网络【1 9 】 前向网络结构如图2 2 所示，神经元分层排列，分别组成输入层、中间层( 也 称为隐含层，可以由若干层组成) 和输出层。每一层的神经元只接受来自前一层 神经元的输入，后面的层对前面的层没有信号反馈。输入模式经过各层次的顺序 传播，最后在输出层上得到输出。感知器网络和b p 网络均属于前向网络。 h 有反馈的前向网络【1 9 】 图2 - 2 前向网络结构 其结构图如图2 3 所示，输出层对输入层有信息反馈，这种网络可用于存储 某种模式序列，如神经认知机和回归b p 网络都属于这种类型。 中山大学硕士学位论文 图2 3 有反馈的前向网络结构 层内有相互结合的前向网络【1 9 】 其结构如图2 4 所示，通过层内神经元的相互结合，可以实现同一层内神经 元之间的横向抑制或兴奋机制。这样可以限制每层内可以同时动作的神经元素， 或者把每层内的神经元分为若干组，让每一组作为一个整体进行运作。例如，可 利用横向抑制机理把某层内具有最大输出的神经元挑选出来，从而抑制其它神经 元，使之处于无输出的状态。 图2 _ 4 层内有相互结合的前向网络结构 人工神经网络的学习方式 神经网络的学习也称为训练，指的是通过神经网络所在环境的刺激作用调整 神经网络的参数( 权值和域值) ，使神经网络以一种新的方式对外部环境做出反 应的一个过程。能够从环境中学习和在学习中提高自身性能是神经网络的最有意 义的性质。根据学习过程的组织方式不同，学习方式分为两类：有监督学习和无 监督学习。 厶有监督学习( s u p e r v i s e dl e a r n i n g , s l ) 对于有监督学习，网络训练往往要基于一定数量的训练样本。训练样本通常 由输入矢量和目标矢量组成。在学习和训练过程中，网络根据实际输出与期望输 1 4 中山大学硕士学位论文 出的比较，进行连接权值和域值的调节。通学将期望输出称为教师信号，它是评 价学习的标准。最典型的有监督学习算法是b p ( b a c kp r o p a g a t i o n ) 算法，即误差 反向传播算法。 h 无监督学习( n o m u p e r v i s e dl e a r n i n g , n s l ) 对于无监督学习，则无教师信号提供给网络，网络能根据其特有的结构和学 习规则，进行连接权值和域值的调整。此时，网络的学习评价标准隐含于其内部。 c 神经网络的学习规则 对应于不同的神经网络结构和模型，在网络学习过程中，有不同的学习规则， 通过这些学习规则来调整神经元之间的连接权重，实现神经网络的学习。 1 ) h e b b 规则 它是d o n a l lh e b b 根据生理学中的条件反射机理，于1 9 4 9 年提出的神经元连 接强度变化的规则。其内容为：如果两个神经元同时兴奋( 即同时被激活) ，则 它们之间的突触连接加强，否则被减弱。常用于自联想网络，如h o p f i e l d 网络。 2 ) d e l t a 规则 它根据输出切点的外部反馈来改变权系数。在方法上它和梯度下降法等效， 按局部改善最大的方向一步步进行优化，从而最终找到全局优化值。感知器学习 就采用这种纠错学习规则，例如b p 算法。用于统计性算法的模拟退火算法也属 于这种学习规则。 3 ) 相近学习规则 它根据神经元之间的输出决定权值的调整，如果两个神经元的输出比较相 似，则连接它们的权值调整大，反之调整小。这种规则多用于竞争型神经网络的 学习中。在a r t 和s o f m 等自组织竞争型网络中就采用了这种学习规则。 2 3 数据集重叠问题的提出 如引言所述，数据集重叠问题是在研究者们研究不平衡数据集时发现的。不 平衡问题是有监督的模式识别中常见的问题。数据集的不平衡意味着某些类存在 着大量的样本而另外一些类存在仅有的一点样本。研究者普遍认为这是造成分类 1 5 中山大学硕士学位论文 器分类精度不高的主要原因。但是在吲中，作者发现，对于数据集s i c kd a t a s e t ， 虽然多数类占到整个数据集的9 3 5 ，分类器的表现仍然十分优异( t 6 j 也得到了 相同的结果) 。作者猜想可能是多数类与少数类之间没有重叠的缘故。接下来， 作者进一步思考，对于重叠的数据集，不同程度、不同形式下的重叠，对于分类 器的影响又是否一样呢? 图2 5 是四组不同重叠程度的数据集，究竟哪种情形下 分类效果最好，哪种情况下分类效果最差呢? 为了回答这一问题，作者设计了如下一组实验： 1 生成十个人工数据集。每个数据集的样本含有5 个属性，每个属性按照 均值为0 ，标准差为1 的高斯分布随机生成。每个数据集都含有两类样本各1 0 0 0 0 例，显然两类样本间是平衡的。 2 对于第一个数据集，两类样本间距为0 ；对于第二个数据集，两例间距 增加l ；对于第三个数据集，两例间距增加2 ；依次类推，对于第十个数据集， 两例间距增加9 。两类的间距增大，意味着重叠的程度降低。 3 为了检验不平衡数据对分类器的影响，训练集中正例的比例依次为1 、 5 、1 0 、2 0 、3 0 、2 0 、2 5 、3 0 、3 5 、4 0 、4 5 、5 0 ，其余均为 负例。 通过该组实验，可以说明两方面问题： 1 不平衡问题和重叠问题哪一个才是影响分类效果的主因。 2 分类器在不同重叠程度的数据集上表现是否一样。 1 6 中山大学硕士学位论文 图2 5四个重叠程度不同的数据集 实验结果见表2 3 ( 分类器为c 4 5 决策树，结果为a u c 值) 。 可以看出，当间距为0 时，即数据重叠程度最高时，即使两类平衡，a u c 仍然只有5 0 ，而当间距为9 时，即使正例仅占训练集的1 ，a u c 仍然达到了 9 9 9 9 。 由此得出结论：分类器的分类效果主要被数据集中的重叠问题影响且分类器 的分类效果受影响的程度与数据集的重叠程度成正比。 事实上，该实验虽然仅使用了决策树，但当使用其他分类器时，数据集重叠 问题所带来的影响同样无法避免。所以在做分类问题时，如果数据集存在重叠， 有必要先做处理。 表2 3 关于重叠问题的实验结果 正例占数据 两类中心的间距 集的比例 o1239 1 5 0 6 4 9 5 9 0 8 7 9 8 4 5 9 9 9 9 2 5 5 0 7 6 0 l 9 5 8 2 9 7 9 5 1 0 0 5 5 0 8 1 o o 9 8 2 5 9 8 9 5 9 9 9 9 1 0 5 0 8 6 6 9 9 8 2 2 9 9 6 l 9 9 9 9 1 5 5 0 8 8 4 1 9 8 9 2 9 9 6 8 9 9 9 9 2 0 5 0 9 0 6 2 9 9 0 8 9 9 9 0 9 9 9 9 2 5 5 0 9 0 8 8 9 9 3 3 9 9 9 0 9 9 9 8 3 0 5 0 9 0 7 5 9 9 2 4 9 9 8 6 9 9 9 9 3 5 5 0 9 1 1 9 9 9 3 6 9 9 9 1 9 9 9 9 4 0 5 0 9 0 9 1 9 9 4 6 9 9 9 0 9 9 9 9 4 5 5 0 9 1 7 3 9 9 4 4 9 9 9 0 9 9 9 8 5 0 5 0 9 1 3 2 9 9 3 3 9 9 8 7 9 9 9 9 1 7 中山大学硕士学位论文 _ - _ 一- _ 2 4 处理数据集重叠问题的常用方法 本节介绍两类常用的处理数据集重叠的方法忱组c l e a n 和e d i t 。 2 4 1d a t ac l e a n d a t ac l e a n 1 是一类常用的消除数据集重叠影响的处理方法，有下列两种常 用方法。 1 t o m e kl i n k s 该方法先定义一个样本对，该样本对满足下述条件：构成样本对的两个样本 历和弓满足：对任意样本乞，有烈名，乞) r ， 得出一个离群因子，用来描述离群特征。函数f 通过计算检测点x 与数据集中 的其它点的距离来实现。基于距离的离群检测算法最重要的是定义好距离，选用 不同的距离对离群检测影响很大。 5 基于密度的离群检测算法 基于密度的方法是的主要思想是把点与点之间的距离和某一给定范围内数 据点的数目结合起来，得到密度的概念，然后根据密度引入局部离群因子，从而 根据该因子判断离群程度，该方法能有效地识别处于边沿的离群点的同时识别出 那些处于内部的离群点。 2 s 中山大学硕士学位论文 3 2 基于离群点检测的重叠问题处理方法 叫h 咄a 翰n 方法 本文将离群点检测算法引入到解决数据集重叠问题上来，可以认为，两簇数 据若重叠，重叠部分应该是这两簇数据的边缘。而离群点往往也出现在数据集的 边缘，如果找出离群点并删除，就可以在尽量保持数据集分布的同时起到去噪的 作用，“净化”数据集。该方法的重点就是找出各类样本的离群点。 本文主要考虑对数据重叠区域即分类边缘区域的数据的处理，出发点是既要 能有郊的删除噪声点，又要尽可能的避免和减少对边界上的非重叠样本的误删。 本文的做法主要是选择性删除数据，即常说的除噪，从而达到消除数据集重叠影 响，作者整合了d a t ac l e a n 的两种常用方法，取长补短，提出了c h e c kc l e a n 方 法。 3 2 1 c h e c k _ c l e a n 算法的有关定义 c h e c k c l e a n 方法整合了d a t ac l e a n 的t o m e kl i n k s 和n e i g h b o u r h o o d c l e a n i n gr u l e s 两种传统方法，从样本集中找出最近邻类标相反的样本对，然 后利用k n n 方法判断出其中的离群点，将其删除。 1 t o m e kl i n k s 该方法已在第二章的2 5 节做了详细介绍。 2 最近邻法【2 3 】 最近邻法就是将测试样本的最近邻样本的类别作为决策的方法。假设有f 个 类别。，c 0 2 ，。，每个类有彤个样本，p l ，2 ，仍则第，类，的判别函数为： 岛( 力= 叩肛一i ，后= 1 ，2 ，彤 其中衫中的，表示国，类，后表示，类的肜个样本中的第后个，i 0 表示距离。 决策规则可以写为： g j ( x ) = m 扣岛( 功，= 1 ，2 ，f 2 6 中山大学硕士学位论文 从而决策z 0 3 。 3 k 近邻法【2 3 】 近邻法k n n ( kn e a r e s tn e i g h b o rc l a s s i f l z a t i o nr u l e ) 的基本思想是：对于测 试样本z ，寻找离其最近的后个样本( 距离最小的后个近邻) ，然后一一找出这后 个近邻的类别，而后对z 进行判别，将z 归为这后个近邻中包含样本数最多的那 个类。 假设有6 - 个类别国。，0 3 2 , * - ，每个类有彤个样本，卢1 ，2 ，f ，令 ? - - - - 以，首先计算出样本z 与其它样本的距离： t 皇i 矿-