（计算机应用技术专业论文）面向非平衡混合型数据的分类算法及应用研究.pdf

中南大学硕士学位论文 摘要 非平衡混合数据分类处理在现实应用中非常普遍，该数据具有分 布不均匀，属性多样等特性。传统的分类学习方法在处理该类型数据 时有效性不高，而且在少数类样本足够重要时，甚至会导致较大的损 失，因此针对非平衡混合数据的处理方法成为当前国内外数据挖掘研 究的重点之一。 本文的研究工作以传统的分类方法为基础，通过对传统分类算法 的改进，实现对非平衡混合数据的处理。通过分析发现计数最近邻分 类算法( k - - n e a r e s tn e i g h t b o u r sb yc o u n t i n g ，c w k n n ) 可以有效地对混 合型数据进行分类，但该算法对非平衡性数据处理效果不理想。本文 在c w k n n 算法的基础之上结合数据的非平衡性特点提出了三种改进 的分类方法，分别为如下所述： ( 1 ) 全局密度分类算法：针对c w k n n 算法不能处理非平衡型数 据的特点，引入一个全局密度，重新平衡数据对分类的影响度。实验 发现提高了少数类样本的分类精度，降低了多数类样本的分类精度。 ( 2 ) k 一局部密度分类算法：针对全局密度分类算法降低了多数 类样本的分类精度，引入k 一局部密度，保证在提高少数类样本分类 精度的同时，不会降低多数类样本的分类精度，实验证明该方法有效 地提高了非平衡型数据的分类精度。 ( 3 ) 基于密度的边界点检测及分类算法：针对数据中的边界点， 提出了基于密度的边界点检测方法，并对检测出来的边界点采用边界 点三种分类方法进行分类。实验证明通过这些方法对存在边界点的非 平衡数据可进行正确分类。 关键词计数最近邻分类算法，非平衡数据，全局密度，k 一局部密度， 边界点检测 中南大学硕士学位论文 a b s t r a c t t h ep r o c e s s i n go ft h ei m b a l a n c e dm i x e dd a t ai sv e r yc o m m o mi nt h e r e a lw o r l d ，s u c hd a t aa r eu n e v e n l yd i s t r i b u t e d ，a n dd i v e r s i t yo fa t t r i b u t e s t h ee f f e c t i v e n e s so ft r a d i t i o n a lc l a s s i f i c a t i o nl e a r n i n gm e t h o d si sn o th i g h i nd e a l i n gw i t ht h i st y p eo fd a t a ，a n di ft h em i n o rs a m p l e si ss u f f i c i e n t l y i m p o r t a n t ，i tm a yl e a dt og r e a t e rl o s s e s s oa g a i n s tn o n e q u i l i b r i u mm i x e d d a t ap r o c e s s i n gm e t h o d sh a v eb e c o m eo n eo ft h ef o c a l p o i n to ft h e c u r r e n td o m e s t i ca n di n t e r n a t i o n a ld a t am i n i n gr e s e a r c h t h em a i nr e s e a r c hw o r ko ft h i sp a p e ri so nt h eb a s i s 、o ft r a d i t i o n a l c l a s s if i c a t i o n m e t h o d s ，t h r o u g hi m p r o v i n gt h et r a d i t i o n a lm e t h o d s ， a c h i e v e n o n e q u i l i b r i u m m i x e dd a t a p r o c e s s i n g i tw a sf o u n dt h a t k - n e a r e s tn e i g h t b o u r sb yc o u n t i n gc a nb ee f f e c t i v ei nt h em i x e dd a t a c l a s s i f i c a t i o nb ya n a l y z i n gt h ea l g o r i t h m ，b u tt h ee f f e c t i v e n e s so ft h e a l g o r i t h ma r en o ts a t i s f a c t o r yf o rn o n e q u i l i b r i u md a t ap r o c e s s i n g s ot h i s p a p e rp r o p o s e st h r e ei m p r o v e dc l a s s if y i n gm e t h o d sb yc o m b i n i n gt h e c h a r a c t e r i s t i c so fi m b a l a n c e dd a t aw i t hc w a l g o r i t h m w e r ea s f o l l o w s ： ( 1 ) t h e o v e r a l l d e n s i t y c l a s s i f i c a t i o n a l g o r i t h m ：a g a i n s t t h e c h a r a c t e r i s t i c so ft h ec w l 洲a l g o r i t h mc a nn o t h a n d l i n gn o n e q u i l i b r i u m d a t a ，t h ei n t r o d u c t i o no fao v e r a l ld e n s i t y , r e b a l a n c i n go fd a t ao nt h e i m p a c to ft h ec l a s s i f i c a t i o n i tw a sf o u n dt h a tt h em i n o rs a m p l e si n c r e a s e t h ea c c u r a c yo ft h ec l a s s i f i c a t i o n ，a n dt h em a j o r i t ys a m p l e sr e d u c et h e c l a s s i f i c a t i o na c c u r a c yt h r o u g he x p e r i m e n t s ( 2 ) k - - l o c a ld e n s i t yc l a s s i f i c a t i o na l g o r i t h m ：a i ma tt h eo v e r a l l d e n s i t yc l a s s i f i c a t i o na l g o r i t h mr e d u c i n gt h ec l a s s i f i c a t i o na c c u r a c yo ft h e m a j o r i t ys a m p l e s ，t h ei n t r o d u c t i o no fak l o c a ld e n s i t yt oe n s u r et h a t t h em i n o rs a m p l e sw i l li m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n 。a n dt h e m a j o r i t ys a m p l e sw i l ln o tr e d u c et h ec l a s s i f i c a t i o na c c u r a c ya tt h es a m e t i m e i tw a sf o u n dt h a tt h ee f f e c t i v ei n c r e a s ei ni m b a l a n c e dt y p eo fd a t a c l a s s i f i c a t i o na c c u r a c yt h r o u g he x p e r i m e n t s ( 3 ) t h eb o u n d a r yp o i n t sd e t e c t i o na n dc l a s s i f i c a t i o na l g o r i t h m s b a s e do nt h ed e n s i t y ：a i ma tt h eb o u n d a r yp o i n t si nt h ed a t a ，t h ep a p e r p r o p o s e dab o u n d a r yp o i n t sd e t e c t i o nm e t h o db a s e do nt h ed e n s i t y , a n d u s et h et h r e ek i n do fc l a s s i f i c a t i o nm e t h o d so fb o u n d a r yp o i n t st oc l a s s i f y b o u n d a r yp o i n t sd e t e c t e d e x p e r i m e n tp r o v e t h a tt h e s em e t h o dc a n c l a s s i f yt h en o n e q u i l i b r i u md a t aw i t hb o u n d a r yp o i n t sc o r r e c t l y k e yw o r d sk n e a r e s tn e i g h t b o u r sb yc o u n t i n g ，n o n b a l a n c e dd a t a ， o v e r a l ld e n s i t y , k 1 0 c a ld e n s i t y , b o u n d a r yp o i n td e t e c t i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：隘室金日期：j 婴旦年三月盟日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：已至主宣导师签名j 3 迸日期：堕年三月盟日 中南大学硕士学位论文 第一章绪论 第一章绪论 1 1对非平衡混合数据分类算法研究的意义 非平衡混合数据处理是现实生活中的一项重要应用，尤其体现在医疗、交通、 故障处理等方面，因此利用各种分类算法对非平衡混合数据进行处理就成为数据 挖掘中的一项重要研究内容。 所谓非平衡混合数据是指样本数据集中类别不同的样本数量差别较大，而且 样本数据类型为非单一的数据类型，即在这些数据中既包含数值型数据，也包含 文本型数据。如在关于一个不常见病的医疗检查数据库中，大部分的“病人”都 是正常的，只有少数的“病人”才是真正的患病，因此正常数据居多，而病理数 据较少。 在当前的数据挖掘分类算法中一般多用于处理平衡数据集，因此在处理非平 衡数据时其算法有效性不高，因为这些算法主要目的是最小化全局错误率，而没 有对少数类别进行特殊处理。目前有研究者已对这些问题进行了研究，比如欺诈 电话检测( f a w c e t t & p r o v o s t ，1 9 9 7 ) ，信息检索和过滤( l e w is & c a t l e t t ，1 9 9 4 ) ，少 见甲状腺死亡诊断( m u r p h y & a h a ，1 9 9 4 ) 等。 本文利用于中南大学湘雅医学院肝胆肠科激光诱导自体荧光大肠早癌诊断 系统研究小组所提取的荧光光谱数据，通过对这些数据进行除噪、特征提取以及 形成样本数据集，并在此基础上进行非平衡数据的处理，达到较好的处理效果， 分析大肠早癌预警阀值，建立预警模型，为医生诊断提供良好的诊断依据，挽救 癌症病人的生命。 目前对非平衡型数据处理最常用的方法有2 个：一是基于代价敏感度学习， 对错误分类的少数类赋予一个高的代价，尽量最小化全局代价；另外一种方法就 是采样，减采样多数类和增采样少数类。在对混合型数据的分类算法中，通过分 析发现计数最近邻分类算法可以有效地对混合型数据进行分类。 目前，能同时对非平衡混合型数据进行处理的分类算法比较少，在这里研究 非平衡混合型数据处理的新方法，应用于大肠早癌诊断系统中，取得良好的诊断 效果，为临床医生提供更准确更权威的参考信息，就具有很重要的意义了。 1 2 数据挖掘中的分类及其在生命医学中的应用现状 1 2 1 数据挖掘中的分类技术 数据挖掘【2 1 ，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取 中南大学硕士学位论文 第一章绪论 人们感兴趣的知识，这些知识是隐含的，先前未知的、对决策有潜在价值的知识和 规则。提取的知识一般可表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律 ( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。数据挖掘通过预测未来趋势及行为， 做出前瞻的、基于知识的决策。主要分为以下七类功能： 自动预测趋势和行为：数据挖掘根据时间序列型数据，从大量历史的和当前 的数据中发现某种趋势，找到其中蕴减的规律，并根据这个规律和趋势来推测未 来的数据。 关联分析：通过关联分析能找出一个事件和其他事件之间存在的某种依赖或 联系。如果两个事件或多个事件之间存在关联，那么根据相互联系的事物之间相 互作用、相互影响的原理，其中一个事件发展的程度就可以依据其他事件发展的 程度进行预测。 顺序模式：是指从数据序列中抽取出隐含的、有意义的、表示普遍规律的模 式。它广泛应用于医学研究、网络故障分析、股票价格分析等领域。 分类：找出描述并区分数据类或概念的模型( 或函数) ，以便能够使用模型 预测类标记未知的对象类。 聚类：分析数据对象，而不考虑已知的类标记。一般情况下，数据中不提供 类标记，因为不知道从何开始。而聚类恰恰可以用来产生这种类标记。对象根据 最大化类内的相似性、最小化类间的相似性的原则进行聚类。 概念描述：概念描述就是对某类对象的内涵进行描述，并概括这类对象的有 关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征， 后者描述不同类对象之间的区别。 偏差检测：数据库中的数据常有一些异常记录，从数据库中检测这些偏差很 有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、 观测结果与模型预测值的偏差、量值随时间的变化等。 其中，分类规则挖掘是数据挖掘领域中的一个非常重要的研究课题。也是目 前在生命医学中使用的比较多和成功的方法之一。 分类【3 】作为一类重要的数据挖掘问题，其过程可描述为输入数据，或称训练集 ( t r a i n i n gs e t ) ，是一条条的数据库记录( r e c o r d ) 组成的。每一条记录包含若干 个属性( a t t r i b u t e ) ，组成一个特征向量。训练集的每条记录还有一个特定的类标 签( c l a s sl a b e l ) 与之对应。该类标签是系统的输入，通常是以往的一些经验数 据。一个具体样本的形式可为样本向量：( v l ，v 2 ，v i ，v n ：c ) 。在这里v i 表示 字段值，c 表示类别。数据挖掘分类就是分析输入数据，通过在训练集中的数据表 现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词 表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试 2 中南大学硕士学位论文第一章绪论 数据的类标签是未知的，但仍可以由此预测这些新数据所属的类。 ， 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方 法包括贝叶斯法和非参数法( 近邻学习或基于实例的学习：i n s t a n c e g a s e d l e a r n i n g ，i b l ) ，对应的知识表示则为判别函数和原型实例；机器学习方法包 括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者一般为产生 式规则；神经网络方法，为解决大复杂度问题提供了一种相对来说比较有效的简 单方法。主要是b p 算法，它的模型表示是前向反馈神经网络模型( 由代表神经元 的节点和代表联接权值的边组成的一种体系结构) 。这些方法的具体描述如下： 1 贝叶斯分类算法 贝叶斯分类f 4 l 是统计学分类方法，它是一类利用概率统计知识进行分类的算 法。在许多场合，朴素贝叶斯( n a i v e ，n b ) 分类算法可以与决策树和神经网络分 类算法相媲美。它方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个 属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成 立的，因此其分类准确率可能会下降。为此，就出现了许多降低独立性假设的贝 叶斯分类算法，如t a n ( t r e ea u g m e n t e db a y e sn e t w o r k ) 算法f 4 1 。 t a n 算法通过发现属性对之间的关联来降低n b 中任意属性之间独立的假设。 该算法对属性之间独立性的假设有了一定程度的降低，但是属性之间可能存在的 更多的其他的关联性仍没有考虑，因此其适用范围仍然受到限制。 2 七一近邻分类算法 k 近邻分类算法1 5 j ( k - - n e a r e s tn e i g h b o u ra l g o r i t h m ，k n n ) 根据待识别样本 在特征空间中七个最近邻样本中的多数样本的类别来进行分类，因此具有直观、 无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要方法。传 统的七一近邻算法有h a r t 快速算法，聚类划分法和及时终止法等。其缺点是： 将所有的样本都保存起来，分类器就变得笨重并且反应变慢，理想的方法是保留 汇集了所有重要信息的原型样本，并采用有效的索引技术如果有许多的不相 关属性，两个类似的样本会表现出非常不类似的特性，这是因为它们有不同的不 相关的属性值。其优点是容易实现和快速训练，实际上没什么训练过程并且该方 法的启发性搜索是简单的。 3 决策树分类算法【酬 。 决策树学习是一种以实例为基础的归纳学习方法，q u i n l a n 分别在 1 9 8 6 ，1 9 9 2 和1 9 9 7 年成功的开发出了i d 3 分类器，及其改进版c 4 5 ，c 5 0 。决策 树算法对于相对小的数据集是很有效的。当这些算法用于非常大的、现实世界中 的数据库的挖掘时，有效性和可伸缩性就成了关注的问题。为了适应处理大规模 数据集的需要，后来又提出了若干改进的算法，其中比较有代表性的两个算法是 中南人学硕十学位论文 第一章绪论 s l i q 和s p r i n t ，它们都使用了预排序技术，对非常大而不能放入内存的驻留磁盘 的数据集进行预排序。决策树算法有以下几种： i d 3 ( c 4 5 ) 算法【1 7 】q u i n l a n 提出的著名的i d 3 学习算法，它通过选择窗口 来形成决策树，是利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信 息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树 的分支；在每个分支子集中重复建立树的下层节点和分支过程。它的改进算法有 c 4 5 9 法和c a r t 算法等。 这种方法的优点是描述简单，分类速度快，特别适合大规模的数据处理。但 有如下的缺点：( 1 ) 互信息的计算依赖于属性取值的较多特征，而这个属性不一 定是最优的；( 2 ) i d 3 是非递增学习算法；( 3 ) 抗噪性差。对其主要的改进是i d 4 、 i d 5 及c 4 5 、c a r t 、f a c t 和c h a i d 等，后期的有q u e s t 和p u b l i c 等。 s l i q 算法【8 1 ：s l i q 算法对c 4 5 决策树分类算法的实现方法进行了改进，在决 策树的构造过程中采用了“预排序 和“广度优先 两种技术。因此在一定程度 上具有良好的随记录个数和属性个数增长的可扩展性。 它仍然存在如下缺点： 1 由于需要将类别列表存放于内存，而类别列表的长度与训练集的长度是相 同的，这就一定程度上限制了可以处理的数据集的大小。 2 由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线 性关系，因此使得s l i q 算法不可能达到随记录数目增长的线性可扩展性。 s p r i n t 算法【9 j ：为了减少需要驻留于内存的数据量s p r i n t 算法进一步改进了 决策树算法实现时的数据结构，去掉在s l i q 中需要驻留于内存的类别列表，将它 的类别列合并到每个属性列表中。这样，在遍历每个属性列表寻找当前结点的最 优分裂标准时，不必参照其他信息。而对结点的分裂表现在对属性列表的分裂即 将每个属性列表分成两个，分别存放属于各个结点的记录。 其优点是在寻找每个结点的最优分裂标准时变得相对简单一些。其缺点是对 非分裂属性的属性列表进行分裂变得很困难，可扩展性仍然不是很好。 4 规则归纳法【1 0 j 基于关联规则的分类算法主要为c b a ( c l a s s i f i c a t i o nb a s e do na s s o c i a t e o n ) 算法。c b a 是基于关联规则发现方法的分类算法。该算法分两个步骤构造分类 器。第一步：发现所有的右部为类别的类别关联规则。第二步：从已发现的c a r 中选择高优先度的规则来覆盖训练集。 关联规则的发现采用经典算法a p r i o r i ，该算法对于发现隐藏于大量交易记 录之中的关联规则来说是比较有效的。但当利用它发现分类规则时，为了防止漏 掉某些规则，最小支持度经常被设为0 ，此时该算法就发挥不了它的优化作用，结 4 中南大学硕士学位论文 第一章绪论 果是产生的频繁集有时多得在内存无法容纳，从而使得程序无法继续运行。其优 点是其分类准确度较高，因而它发现的规则相对较全面。 5 神经网络分类【1 1 】 人工神经网络由多个神经元按照某种方式相互连接形成，靠网络状态对外部 输入信息的动态响应来处理信息，网络的信息分布式存储于连接权系数中，使网 络具有很强的容错性和鲁棒性。神经网络的核心是结构和算法，例如以结构见长 的h o p f i e l d n 1 2 】和以算法见长的b p ( b a c kp r o p a g a t i o n ) 网【13 1 。在数据挖掘中，神 经网络主要用于获取分类模式。最流行的分类神经网络算法是2 0 世纪8 0 年代提出 的后向传播算法，使用梯度下降方法。它搜索一组权，这组权可以对数据建模，使 得数据样本的网络类预测和实际类标号间的均方距离最小。但是，由于神经网络 分类方法获取的模式隐含在网络结构中，而不是显示地表达为规则，不容易被人 们理解和解释；另外要多次扫描训练数据，网络的训练时间较长。因此，与其他数 据挖掘方法不同，要想把神经网络用于数据挖掘，要解决好两个关键问题：一是降 低训练时间，二是挖掘结果的可理解性。但其噪声数据的高承受能力和错误率低 的优点，以及各种网络训练算法的陆续提出与优化，尤其是最近又提出了网络剪 枝算法和神经规则的提取算法，使得神经网络在数据挖掘分类中的应用越来越为 广大使用者所青睐。 1 2 2 分类在医疗中的应用 随着计算机技术在医学领域中的应用r 益广泛，把病例资料存储在计算机的 存储设备中已比较普遍。这些存储在计算机中的数据是病人的原始数据。经过不 断的积累和汇总后，数据量变得相当的庞大。这样大量的数据中隐藏着潜在的规 律和有用信息，用数据挖掘技术来探求它们之间的相互联系和挖掘出各种疾病的 发展规律，来对疾病的诊断、治疗和医学研究提供有力的辅助手段，这都是非常 有应用价值和发展前景的。 疾病的诊断过程实际上也是一个疾病分类的过程，是根据病人的疾病特征划 归到某个疾病或疾病类的过程。一般的医学书上把这一复杂的问题逐次分解成一 个个小问题( 疾病) ，再根据患者症状特征及不适部位，把这些“小问题 定位到 具体的疾病类中，这一过程与数据挖掘的分类过程十分相似。目前，数据挖掘的 研究和应用非常的热门，虽然医学领域的数据挖掘起步较晚，但医学的特殊性预 示着在该领域进行探索必然有着广阔的前景和价值。 目前数据挖掘中分类在医学领域运用成功的案例很多，如美国加利佛利亚州 立大学的j o h nk e l s o e 博士【1 4 】通过基于数据的研究发现了某些有缺陷的基因导致 了狂躁抑郁症，现在很多研究人员正在寻找生物学和医学上的证据来证明他的研 中南人学硕士学位论文 第一章绪论 究成果。美国南加州大学脊椎病医院利用i n f o r m a t i o nd i s c o v e r y ( 信息发现) 进行医疗数据挖掘【1 5 】：在英国帝国理工大学以及奥斯特大学( d a t am i n i n gi n d i a b e t e s ) ，利用相关数据挖掘技术对糖尿病进行相关研究，将相关病症进行分 类、匹配研究最终进行治疗方案的选择【1 6 ， 】。y i n gj i el e e 等在精神分裂症患 者的动态e e g 分析研究中用时空相关维数预测疾病发作【l8 1 ；t e x a s 健康科学中心 的s h a h b 禾i 用关联分析方法分析了糖尿病患者年龄、性别和跖骨骨密度之间的关 系1 1 9 1 ；h a r r i sn d 和i r e l a n dr h 在研究中运用时间序列关联分析发现，qt 间期和 色型糖尿病患者夜间血糖浓度有关，并指出修正后的qt c 可能可以用于预警患者 在夜间猝死的发掣2 们。k e n t a l ae 等【2 1 】曾从赫尔辛基大学附属医院的鼻神经专家 系统数据库中提取前庭区与晕头有关的6 种发病人数较多的疾病资料，分别为6 种 疾病建立不同规模的决策树，并针对6 棵树单独分析影响每一种疾病发生的重要 因素，而且从决策树中提取诊断规则，从而将专家经验知识转化成了可供年轻医 师随时参考的有价值的信息；j o n a t h a n l 在产科病人早产的三个危险因素的分析 中亦用到了数据挖掘的方法【2 2 1 ；l e e i n 等1 2 3 】将决策树运用于疾病危险因素的筛选 也取得了很好的效果；斯洛文尼亚的m i l a n z o nm a n 和日本的m a s u d ag 等人在用数 据挖掘技术对糖尿病数据库数据进行详细分析的同时还专门探讨了从这类缺乏 先验知识的海量数据中采用决策树和关联规则算法的效率及其改进方法1 2 4 】；钱 宗才教授利用粗糙集构建了骨肿瘤诊断知识库1 2 5 】；罗森林等将决策树算法引入2 型糖尿病的数据处理之中，建立了多条有效规则，通过测试其患病与未患病的平 均正确识别率达9 7 ；中国科学院软件所顾毓清研究员和卫生部合作，对数据挖 掘技术在糖尿病中的应用做了相关研究1 2 6 j ：c h o 和w a l b o t 使用人工神经网络与已 知的非冗余基因组数据匹配，根据得到的匹配结果建立基因模型【2 7 1 ；b a y e s i a n 学 习法对患者c t 图像【2 8 】的自动诊断；模糊神经网络用于分析肝脏的超声图像：决 策树方法对于治疗方法的选择；d r e i s e i t l 将决策树与l o g i s t i c 回归、神经网络 方法联合运用分析影响疾病死亡率的因素，从而弥补了神经网络产生的结果不易 理解的弊端【2 9 】；樊晓平等利用神经网络对抑郁症患者进行病症分类【3 0 1 。 纵观这些方法，他们大多采用一种分类算法对数据进行处理，基于一种算法 的数据处理虽然其算法复杂度相对较低，但是最大的缺陷就是数据处理精度无法 得到保证，且一般只对数值数据或者文本数据进行处理，在处理混合数据时，一 般先要把一种类型的数据转换成另外一种类型，然后再对转换后的数据统一进行 处理，这样会引入一些额外的错误和丢失信息。 所以用分类算法对这些混合型的医疗数据进行统一处理，并且得到较好的诊 断效果，为医务人员提供诊断决策，是当前医疗辅助诊断的重要任务之一。 6 中南大学硕士学位论文第一章绪论 1 3 本文的研究内容 本文主要研究了针对非平衡混合型数据的分类技术和边界点检测及分类的 方法。在计数最近邻算法的基础上，用二种方法解决数据的非平衡性问题。第一 是基于计数最近邻算法的全局密度分类算法。第二是基于计数最近邻算法的七一 局部密度分类算法。全局密度分类算法在计数最近邻算法的基础上加以改进，提 出基于样本类别的全局密度，来消除类别的非平衡性，但该方法只考虑了少数类 样本的分类问题，没有考虑多数类样本的分类。后一局部密度分类算法在计数最 近邻算法的基础上，结合全局密度分类算法的特点，得出基于样本类别的七一局 部密度，在考虑少数类样本分类的同时，也考虑到了多数类样本的分类问题。改 进后的七一局部密度分类算法较好的解决了数据的非平衡性问题。针对数据中存 在的边界点，在计数最近邻算法的基础上，本文采用了一种基于密度的边界点检 测方法，通过边界因子来判断一个数据是否为边界点，对边界点的分类问题，根 据边界点跟类别的拟合度原理，采用边界点分类法一、二和三来进行分类。 在提出理论的同时，本文通过大量实验对算法进行验证，进行了纵横向的性 能比较，最后把算法应用到基于数据挖掘的激光诱导自体荧光大肠早癌诊断系统 中去。； 1 4 本文的结构安排 第一章概述非平衡混合数据分类算法研究的意义，并介绍数据挖掘技术的 主要分类方法及其在生命医学中的应用现状。简述本文研究的主要工作及结构安 排。 第二章介绍目前国内外主流的非平衡数据处理的方法和技术，分析其利与 弊，以此为基础而引出自己的方法。 第三章首先简单介绍k n n 算法体系及各自的优缺点。然后分别介绍全局密 度、七一局部密度分类算法和基于密度的边界点检测和分类算法的基本思想和原 理，算法的详细步骤、计算公式以及伪代码。其中在介绍边界点检测之前简要的 介绍了一些主要的边界点检测方法。然后对这些算法的实验结果和现有的一些算 法进行纵向和横向的比较，评价其性能，包括分类精确度和算法的时间复杂度等。 第四章从全局的角度对系统的整体框架进行说明，然后按软件的开发流程 介绍了分类子系统的分析、设计和实现过程。 第五章介绍本文的研究成果，并给出值得进一步研究的问题。 7 中南大学硕士学位论文 第二章非平衡数据处理方法与技术 第二章非平衡数据处理方法与技术 医疗诊断系统处理的数据是非平衡型数据，目前，对医疗非平衡型数据分类 处理的研究已经成为医疗数据挖掘的重要任务之一。数据本身的特点和传统分类 算法的不足，导致了在对非平衡型数据进行处理时，有很大的困难性。 2 1 非平衡数据分类困难性分析 所谓非平衡数据，是指一个数据集中某些类的样本比其他类的样本多的多， 其中样本多的类一般称为多数类，样本少的类称为少数类。通常少数类包含的信 息是最重要的，例如医疗辅助诊断中的患病数据是少数类数据，比正常数据具有 更好的研究价值和实际意义。 由于数量上的严重倾斜，分类算法对非平衡数据集进行分类的性能不尽人 意，因为少数类样本通常比普通样本难以识别，而且大多数数据挖掘分类算法对 于处理少数类样本有很大困难。 一般的算法中，当对非平衡数据集进行有指导的训练时，其训练算法通常会 对多数类样本产生很高的预测准确率，但是对少数类样本的预测准确率却很差。 通常情况下多数类样本远多于少数类样本，这意味着对所有样本进行预测，可以 在不预测出少数类样本所包含的信息的情况下，得到分类结果。诸如决策树归纳 系统或多层感知器等典型分类器，设计为使整体准确率最高，而不考虑每个类的 相对分布情况，非平衡数据给这类典型的分类器提出了挑战。这些分类器在关注 于将多数类样本尽量分类准确时，倾向于忽视少数类，因此传统算法对于解决非 平衡数据的分类问题的能力有限。 2 2 非平衡型数据的主要分类处理方法与技术 本文研究的大肠早癌医疗数据也是一种典型的非平衡型数据，在对这些数据 进行处理时要采用特殊的方法和技术。目前国内外对非平衡型数据处理的技术和 方法很多，总结起来主要有如下一些。 2 2 1 评估度量选择法 一般情况下，都会用一些评估度量来对分类结果进行评价。这在挖掘过程 属于第七步【3 l l 一解释和评估，在数据挖掘中至关重要，它用于指导数据挖掘算 法并评估数据挖掘结果。例如准确率是分类中最经常使用的评估度量，它是被正 确分类的样本数占数据集样本总数的比例，但这种度量方法有它的局限性，在数 8 中南大学硕士学位论文第二章非平衡数据处理方法与技术 据不平衡的情况下，正确率并不能准确表达分类器的性能。比如信用卡欺诈检测 中的正确率达到0 9 9 的分类算法，可能比随机猜测所有的信用卡都是“正常使 用”的正确率还要低，此时很高的正确率并不能够充分说明分类器性能的好坏， 这时如果还用正确率评价分类结果，一些正确率很高的分类器性能可能会急剧下 降，这会影响对算法的客观评价，此时该评估度量就没有任何实际意义了。所以 必需采用一些新的度量方法来对其进行评估。 最常用的评估度量方法是使用r o c l 3 2 ( r e c e i v e ro p e r a t i n gc h a r a c t e r i s t i c a n a l y s i s ) 分析和r o c 曲线下区域- a u c 【3 3 ( t h ea r e au n d e rt h ec u r v e ) 来评估整 体的分类性能。 r o c 曲线，用来说明分类器命中率和误报警率之间的关系。它像查准率一 查全率曲线一样，也能用于不同程度的折中，在引入额外错误的正类样本的代价 和增加正确分类的正类样本的收益之间进行折中。r o c 分析技术对类别分布、 代价具有不敏感性、直观性以及可理解性的特点，使其在评价和比较分类器问题 上占有优势，足以使它代替正确率成为更好的度量标准。 在r o c 的基础之上，为了能直接比较多个分类器的性能就产生了a u c 。 a u c 不会对任何类给予更多的权重，它不会向不利于少数类的方向偏移。实验 证明a u c 比正确率更适合作为分类评价标准。 查准率和查全率两者都是针对少数类定义的，因而在使用这些度量时，少数 类样本得到了较好的评估。比如使用查准率和查全率来评价的遗传算法数据挖掘 系统- - t i m e w e a v e r ，它能直接对原始网络层的时间序列数据( 其他类型的时间序 列数据也可) 进行操作，它搜索所有潜在模式空间，来发现预测规则。 2 2 2 典型的非贪心搜索技术 贪心搜索技术不适合于处理少数类样本，因为它有可能陷入局部最优。所以 一般采用非贪心搜索技术。 最典型的非贪心搜索技术就是遗传算法1 3 4 1 。遗传算法是一种自适应全局优 化概率搜索算法，使用的是候选解的总数，而不是某个单独的解，并使用随机算 子来指导搜索的过程。这些特征使遗传算法能够处理属性的交互并防止停留在局 部最优上，这也是遗传算法适合处理少数类样本的原因。遗传算法也存在着一些 问题，比如：编码、早熟收敛、进化时间长和参数选择问题。 决策树训练算法几乎都是使用贪心搜索技术的，为了处理这些贪心的、登山 搜索算法，可以使用b r u t e 方法。b r u t e 方法使用穷举的深度限制搜索，以寻找 精确的规则，尽管有的规则只包含少数几个训练样本。相对于其它算法而言， b r u t e 方法的性能相当好，可以发现别的算法所不能发现的“金块”信息，但是 9 中南大学硕士学位论文 第二章非平衡数据处理方法与技术 它产生的规则长度需要受限。 2 2 3 归纳偏移自适应技术 大多数数据挖掘系统使用偏移来进行通用化处理。一个通用偏移对普通样本 来说是有好处的，但是对少数类样本则是不合适的，甚至会导致少数类样本完全 被忽略。 另一种改进非平衡数据处理性能的方法之一就是选择一个更合适的偏移。现 有的最简单的方法就是使用统计权值测试或错误计算技术来去除一些小析取项， 这样能够去除训练不当的小析取项，但是这种简单的去除方法不好，不仅降低了 少数类的分类性能，也降低了总体的分类性能。h o l t e ，a c k e r 和p o r t e r 提出了一 个改进偏移一c n 2 【3 5 1 ，以使偏移更具体，这种方法是为得到的小析取项，计算更 具体的偏移值j 而不是对所有的析取项都使用c n 2 的最大通用偏移值。t i n g 使 用特殊偏移的最大值，采取了一些方法来避免这种偏移使大析取项性能降低的 问题。基本方法就是首先使用c 4 5 决策树训练器来判定一个样本是涵盖于大析 取项还是小析取项，如果是大析取项则使用c 4 5 对样本进行分类，否则使用一 个基于样本的训练器对样本进行分类。 总的来说研究者们采用了不同的方法尝试选择一种适宜的偏移，以便在小析 取项的问题上得到更好的性能。由于研究者还是使用整体分类的准确率来评估方 法的性能，而不是集中关注小析取项的性能，因而从偏移方面着手处理少数类问 题值得更深人的研究。 2 2 4 少数类训练法 分类的时候一般从两类数据中选取样本，即一个正一个负，选好数据后就输 入到分类算法中产生用以区分它们的模型。但事实上在许多实际应用中，要得到 少数类数据的样本是非常困难的，在此情况下，就只有对含有单一类的数据进行 训练了。而目前的许多分类的经典算法不能对单一类的数据进行训练。忽略大部 分负类样本而仅学习正类样本本身，是更快速的方法，但并不是一个可靠的方法。 目前己有采用少数类训练法的系统。比如：h i p p o 是使用这种方法的数据挖 掘系统，其核心是采用神经网络分类算法，只训练正类( 少数类) 样本，忽略多数 类样本，以此发现正类样本的识别模式。另外支持矢量机( s v m l j q ) 也可以用这种 方法训练少数类样本。当然只训练少数类的系统也可以训练来自所有类的样本。 2 2 5 分割数据法 处理非平衡数据的另一种方法就是通过合适的分割数据，以此来降低数据不 1 0 中南大学硕士学位论文第二章非平衡数据处理方法与技术 平衡的程度。有效地分割数据就会让初始的数据挖掘问题分割为子问题，一个是 原来分类中的大样本分类，另外一个是被分割后的少类样本中的多数类。假设某 目标事件是很少见的，只有o 0 0 1 ，那么可以把数据分为两块，r l 和r 2 。在 r 1 中目标事件有2 0 ，而在r 2 中只有0 0 0 0 1 。这样对r 1 的处理就可以避免数 据极端不平衡的问题，而对r 2 可以完全不考虑，因为r 1 涵盖了目标事件的绝 大部分，所以这样的结果可能是可以接受的。 2 2 6 最低支持度阀值自适应技术 为了避免关联规则数量的爆炸，最低支持度的值1 n i n s u p ，不能定得太低， 因为会导致少数类样本之间的关联被埋没。这种问题可以通过这样的方法解决， 根据产生关联的对象出现的频率不同而指定不同的最低支持度。 2 2 7 代价敏感度训练技术 分类的主要任务是建立一个分类误差数量最小的分类器，经典的分类算法一 般都是假定分类错误是具有相同代价的。但是实际上不同的分类错误通常会导致 不同的代价。以一个病人数据集为例，错误地将健康分类为患病的代价是比较小 的，不会造成重大的损失，但如果将患病错误的分类为健康，则会造成比较严重 的后果，病人可能会延误诊断时机，甚至威胁病人的生命安全。显然，后一种情 况的代价比前一种要大得多。 处理非平衡数据挖掘问题的一种方法就是代价敏感训练【3 7 1 。由于正确识别 正类样本的价值远超过正确识别负类样本的价值，因此可以为负类样本误判为正 类样本和正类样本误判为负类样本两种错误指定不同的代价，这可以使分类器向 有利于少数类样本正确分类的方向偏移。 这种方法的问题在于用于指定代价的信息不易得到。部分原因在于代价通常 取决于多个条件，不容易权衡，因此更实用的做法是只预测少数类并产生最佳正 类预测规则的排序表【3 8 】。这样在数据挖掘完成后可以判断阀值取多少合适。大 多数的数据挖掘系统可以直接处理代价敏感方法，代价信息可以传递到数据挖掘 算法中。 2 2 8 非平衡数据采样法 采样方法的基本思想就是通过改变训练数据的分布来消除或减小数据的不 平衡性。 1 基本采样方法 对非平衡型数据的基本采样方法包括减采样( u n d e r - s a m p l i n g ) 和增采样 中南大学硕士学位论文 第二章非平衡数据处理方法与技术 f o v e r - s a m p l i n g ) 。减采样是通过减少多数类样本的数量达到数据平衡的目的，而 增采样则是通过复制少数类样本来完成。s m o t e l 3 9 ( s y n t h e t i cm i n o r i t yo v e r - s a m p i i n gt e c h n i q u e ) 是