（计算机应用技术专业论文）基于遗传算法的分类器的研究及其应用.pdf

摘要 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据 库不仅在数量上快速增长，规模也越来越大。激增的数据背后隐藏着许 多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利 用这些数据。 医院信息管理系统( h o s p i t a li n f o r m a t i o ns y s t e m ，h i s ) 在国内己发 展多年，许多医院也都建立了较为成熟和先进的h i s 系统。通过多年的 发展，h i s 系统在为医院创造了良好的经济效益和社会效益的同时，也 积累了大量的数据。如何在这大量的数据资源中挖掘深层次的、隐含的、 有价值的知识，是我们面临的一个难题。利用数据挖掘技术开展科学研 究，提高医学技术和医院管理水平是很有必要的。将数据挖掘技术应用 到医学信息数据库中，可以发现其中的医学诊断规则和模式，从而辅助 医生进行医疗诊断。 本文主要探讨了数据挖掘中的分类技术在医院这一特殊行业中的 医疗预测中的应用。首先介绍了课题的相关技术背景和领域背景、发展 状况等，探讨了其在医院信息系统中的应用状况及发展前景。其次，研 究了两种传统的分类算法：决策树分类算法( 包括i d 3 算法，j 4 8 算法) ， b a y e s 分类法( 包括朴素贝叶斯分类法，a o d e 分类法) 。对它们的推理 过程和适用性进行了详细的阐述。通过分析和比较，验证了模型的精度 和可靠性。然后，本文详细分析了基于遗传算法的分类器模型的构建过 程，在原有的基本遗传算法的基础上，对个体编码方案进行了改进，并 利用改进的编码方案求出支持度和置信度以衡量规则的适应性。 最后，本文以某社区医院医疗数据库系统中的居民健康报告为样 本，对各类分类算法进行比较、分析，其中本文提出的改进算法表现出 了良好的分类效果。分类结果在预测的准确率、可解释性方面令人满意。 武汉工程大学硕士学位论文 关键词：分类，决策树分类，贝叶斯算法，遗传算法，医疗诊断 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n dt h ew i d e l y u s e dm a n a g i n gs y s t e mo fd a t a b a s e s ，t h ed a t a b a s e sh a v ei n c r e a s e ds h a r p l y n o t o n l y i n q u a n t i t i e s b u ta l s oi ns c a l e s t h e r ei sm u c hi m p o r t a n t i n f o r m a t i o nh i d d e nb e h i n dt h er a p i d l yi n c r e a s e dd a t a b a s e s p e o p l eh o p et o i m p l e m e n tam o r ea d v a n c e da n a l y s i s ，i no r d e rt om a k eb e t t e ru s eo ft h e s e d a t a h o s p i t a li n f o r m a t i o ns y s t e m ( h i s ) h a sb e e nd e v e l o p i n gf o rm a n y y e a r sd o m e s t i c a l l y l o t so fh o s p i t a l sh a v ee s t a b l i s h e dh i st h a ta r eb o t h m a t u r ea n d a d v a n c e d t h r o u g hm a n yy e a r s o fd e v e l o p m e n t ，h i sh a s a c c u m u l a t e dv a s ta m o u n t so fd a t a ，w h i l e c r e a t i n gg r e a t s o c i a la n d e c o n o m i c a lb e n e f i t sf o rh o s p i t a l s t h ep r o b l e mw ea r ef a c i n gi sh o wt om i n e d e e p l e v e l e d ，c o n n o t a t i v e ，v a l u a b l ek n o w l e d g ef r o mt h e s ev a s ta m o u n t so f d a t a i ti sn e c e s s a r yt oi m p r o v et h em e d i c i n et e c h n o l o g ya n dt h eh o s p i t a l s m a n a g e m e n tb yu s i n gt h et e c h n o l o g yo fd a t am i n i n gt od ot h e s c i e n c e r e s e a r c h u s i n gd a t am i n i n gi nt h em e d i c i n ei n f o r m a t i o nd a t a b a s e ，w ec a n f i n dh i d d e nd i a g n o s t i cr u l e sa n dp a t t e m s ，w h i c hi s h e l p f u lf o rd o c t o r st o m a k ed i a g n o s i s t h i sa r t i c l ew i l lm a i n l yd i s c u s st h ea p p l i c a t i o n so fd a t am i n i n gi nt h e s p e c i a lf i e l do fh o s p i t a lm e d i c a ld i a g n o s i s f i r s t l y , t h er e l a t e db a c k g r o u n d ， d e v e l o p e dc o n d i t i o na n dt h ed e v e l o p m e n tp r o s p e c to fd a t am i n i n gu s i n gi n t h eh o s p i t a li n f o r m a t i o ns y s t e ma r ed i s c u s s e d s e c o n d l y , t w ot r a d i t i o n a l c l a s s i f ym e t h o d sa r ed i s c u s s e d ：d e c i s i o nt r e e ( i n c l u d i n gi d 3a n dj 4 8 ) ， b a y e s i a na l g o r i t h m ( i n c l u d i n gn a i v eb a y e sa n da o d e ) t h e i ri l l a t i v e i i i 武汉王堡奎堂堡圭堂垡迨壅一 一一一 p r o c e s sa n da p p l i c a b i l i t y a r ea l s oe x p a t i a t e d t h er o o d e l s p 陀c l s l o na n d 二印e n d a b i l i t ya r ev a l i d a t e d 咖g h a n a l y s i sa n dc 。m p a r e t h e n ，t h i s 矾c l e d e t a i l e da n a l y s e st h ec l 砥鸟m o d e l sc o n s t r u c t i o nb a s e d o nt h eg e n e t l c a l g o r i t h m ，a n dp u t sf o r w a r d a i li m p r o v e di n d i v i d u a lc o d i n g m e t h o db a s e do n t h ef o r m e rg e n e t i ca l g o r i t h m ，i m p o r t i n gs u p p o r ta n d c o n f i d e n c ec a l c u l a t e d b vt h ei m p r o v e dm e t h o d t om e a s u r et h ea d a p t a b i l i t yo f t h em l e s l a s t l y a b o v ec l a s s i f ym e t h o d sa r ec o m p a r e da n d a n a l y z e db a s e do n t h er e s i d e n t h e a l t h r e p o r t o ft h ec e r t a i nc o m m u n i t yh o s p i t a l s d a t a b a s e s v s t e m t h ei m p r o v e da l g o r i t h mp u tf o r w a r d b yt h ea n i c l er 印r e s e n t sa n l c e r e 日e c t t h er e s u i ti sc o n v i c t i v e i nt h ef o r e c a s t sv e r a c i t ya n dc o m p r e h e n s l o n k e v w o r d s ：c l a s s i f y , d e c i s i o nt r e e ，b a y e s i a na l g o r i t h m ，g e n e t l c a l g o n t h m ， m e d i c a ld i a g n o s i s i v 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对 本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：余乞 2 0 0 3 年多月2 日 学位论文版权使用授权书 本学位论文作者完全了解我校有关保留、使用学位论文的规定， 即：我校有权保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅。本人授权武汉工程大学研究生处可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。 保密o ，在年解密后适用本授权书。 本论文属于 不保密z ( 请在以上方框内打“4 ) 学位论文作者签名：惫屯 加d 9 年多月z _ e t 指导教师签名：蕉瑶 伽署年占月2 - e i 第1 章绪论 1 1课题背景 1 1 1技术背景 第1 章绪论 近年来，随着计算机技术的飞速发展和应用的普及，人类社会已经 进入了一个信息化的时代，人们利用信息技术产生和搜集数据的能力大 幅度提高。数以千万计的数据库被用于商业管理、政府办公、科学研究 和工程开发等方面。特别是在一些采用集中或者分布式数据库存储技术 的领域，比如：金融投资、卫生保健、制造生产、通信网络、科学领域、 万维网( w w w ) 等n 1 。 收集工具的进步使我们拥有了数量庞大的数据。面对浩如烟海的数 据，急需一些新的工具和技术，能够将这些数据转化为有用的信息和知 识，从而解决“信息爆炸 所带来的问题数据丰富，信息贫乏瞳1 。 过去对于数据的分析主要依赖人类分析员来进行，从而对数据的分析工 作也就变成了简单的根据专家知识从数据库进行查询和获取数据，并呈 现给分析人员做出决策。这种对收集数据进行传统的数理统计和数据管 理工具进行的分析不再适用。如何从海量数据中及时发现有用的知识， 提高信息利用率，并将这些有用的信息和知识运用到实际工作中去成为 一个迫切需要解决的问题，而数据挖掘就是种从海量数据库中挖掘信 息的技术呤。4 1 。因此，数据挖掘( d a t am i n i n g ，d m ) ，通常又称为数据 库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) ，越来越受到人 们的重视。 因此，数据挖掘和知识发现可以说是数据库技术与信息技术发展的 一个必然趋势。当人们不再为获取数据而烦恼时，如何分析、理解并利 用这些数据就成为必然的要求。 知识发现畸6 1 与数据挖掘是人工智能、机器学习与数据库技术相结合 的产物。k d d 一词首选出现在1 9 8 9 年8 月在美国底特律召开的第1 1 武汉工程大学硕士学位论文 届国际人工智能联合会议的专题讨论会上。随后在1 9 9 1 年、1 9 9 3 年和 1 9 9 4 年都举行k d d 专题讨论会，汇集来自各个领域的研究人员和应用 开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用 等问题。随着参与人员的不断增多，k d d 国际会议发展成为年会。1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不仅进 行了学术讨论，并且有3 0 多家软件公司展示了他们的数据挖掘软件产 品，不少软件己在北美、欧洲等地得到应用。1 9 9 9 年在美国圣地亚哥举 行的第五界k d d 国际学术大会，参加人数近千人，投稿2 8 0 多篇。近 年来的国际会议涉及的范围更广，如数据挖掘与知识发现的基础理论、 新的发现算法、数据挖掘与数据仓库o l a p 的结合、可视化技术、知识 表示方法、w e b 中的数据挖掘等。此外，i e e e ，a c m ，i f i s ，v l d b ， s i g m o d 等其他学会、学刊也纷纷把数据挖掘与知识发现列为会议议题 或出版专刊，成为当前国际上的一个研究热点。 数据挖掘口，可以说是数据库研究中的一个非常有应用价值的新领 域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等 多个领域的理论和技术。从数据分析的观点来看，数据挖掘分为两类： 描述性数据挖掘和预测性数据挖掘。描述性数据挖掘以概要方式描述数 据，提供数据所具有的一般性质；预测性数据挖掘分析数据，建立一个 或一组模型，产生关于数据的预测。包括分类和回归。分类可用于提取 描述重要数据的模型或预测未来的数据趋势。 分类技术隋1 是数据挖掘的重要分支，它能够对各个行业提供良好的 决策支持，对整个社会的发展产生重要而深远的影响。用于分类挖掘技 术的方法有很多，如决策树方法、遗传算法、贝叶斯网络、粗糙集、k 最临近方法、关联规则方法等等。目前分类挖掘在实际应用中有着 很重要的应用价值，在很多行业领域都取得一定的成功。比如：在股票 市场上对每只股票的历史数据进行分析，通过相应的技术进行预测，从 而做出相对比较准确的判断；在零售业领域，由同一顾客在不同时期购 买的商品可以分组为序列，通过该序列模式可用于分析顾客的消费或忠 诚的变化，据此对价格和商品的花样加以调整，以便留住老客户，吸引 新顾客；在金融领域中将贷款对象分为低贷款风险与高贷款风险两类， 第1 章绪论 通过分类器，我们可以很容易地确定贷款申请者是属于高风险的还是低 风险的。 遗传算法是多学科结合与渗透的产物，已经发展成一种自组织、白适 应的综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。分 类系统属于基于遗传算法的机器学习中的一类，包括一个简单的基于串 规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统 被人们越来越多地应用在科学、工程和经济领域中，是目前遗传算法研 究中一个十分活跃的领域。 1 1 2 应用领域背景 高血压( h y p e r t e n s i o n ) 是一种世界性的常见疾病，世界各国的患 病率高达1 0 - - 一2 0 ，并可导致脑血管、心脏、肾脏的病变，是危害人 类健康的主要疾病。随着我国经济的发展，人民生活水平的提高，高血 压已日益成为一个重要的公共卫生问题。但是高血压的发病原因迄今尚 未阐明，普遍认为是在一定的遗传背景下由于多种环境因素参与使正常 血压调节机制失代偿所致【9 】。 自上世纪8 0 年代以来我国一直处于高血压发病的急剧上升期。随 着社会进步，经济发展，人们生活水平的不断提高，饮食结构的改变且 多不合理，工作节奏的加快，交通发达、体力活动减少，高血压病的发 病率继续呈上升趋势，严重危及人们的身体健康，而且年龄年轻化，随 着医疗人员工作的深入开展，许多6 0 岁以下的高血压患者也被发现。 我国1 9 9 1 年对1 5 岁以上9 4 万人群抽样普查，高血压标化患病率为 1 1 2 6 ，与1 9 7 9 1 9 8 0 年相比，1 0 年问患病率增加2 5 。2 0 0 5 年卫生 部的普查显示，我国高血压患病率为1 8 8 左右，患病人数约1 6 亿人。 据世界卫生组织预测，至2 0 2 0 年，非传染性疾病将占我国死亡原因的 7 9 ，其中心血管病将占首位。高血压逐渐成为威胁我国国民健康的“第 一疾病 。 为了遏制这一心血管病高峰的到来，保证人民健康，在全国范围内 武汉工程大学硕士学位论文 大力开展高血压病的防治，积极治疗高血压病患者，同时控制整个人群 的血压水平，已刻不容缓。治疗高血压的目的不仅在于降低血压本身， 还在于全面降低心血管病的发病率和死亡率。高血压患者的心血管病危 险是多因素的，因此，高血压的治疗还应包括影响高血压患者的其它危 险因素的治疗。虽然严重高血压造成的死亡率和罹患率最高，但人群中 轻、中度高血压的影响面最广，故防治应以此为重点。 本文以某社区医院的信息系统数据为背景，以历年的居民健康档案 为基础，主要研究社区居民中高血压的高危人群，强调预防概念。 1 2 课题的研究价值和意义 随着科学技术的突飞猛进，信息化的浪潮也席卷到医疗卫生领域。 计算机信息管理系统在医疗机构的广泛应用，促进了医学信息的数字 化，同时电子病历和病案的大量应用、医疗设备和仪器的数字化、医学 影像系统的应用使得医院数据库的信息容量不断地膨胀。这些宝贵的医 学信息资源对于疾病的诊断、治疗和医学研究具有重要的价值。然而， 目前大多数医院对数据库的处理仅限于数据的录入、修改、查询、删除 以及简单的报表统计等通常过程，缺乏数据的集成和分析，以及实现医 学决策和知识的自动获取，从而出现了“数据丰富，知识贫乏”的现象。 如何利用这些海量的信息资源来为疾病的预防和治疗提供科学的决策， 总结各种医治方案的疗效，更好地为医院的决策管理、医疗、科研和教 学服务，已越来越被大家关注。 随着医疗理念的不断进步，人们对于医疗的消费不仅局限于病痛的 医治，更多的融入了预防、保健等整体增值服务的消费。对于预防，保 健，就要对过去的历史数据进行分析，以得出哪种类型的人容易患哪种 疾病。但是传统的统计分析任务基本为手工结合原有的管理系统，不仅 工作量大、繁琐，而且主观性较强，并且发现的规则一般都不全面，最 终将会导致不准确预防信息流向社会。鉴于此，迫切需要一种分类技术， 第1 章绪论 能自动高效、准确得找出某种疾病的高危人群，提前对这类人群提供预 防服务，降低患病几率。 1 3 分类技术概述 分类技术是数据挖掘中一个十分重要的研究领域，有着几乎最广泛 的应用范围，在商务领域中普遍存在。有很多成功的应用案例，如客户 购买行为分析、信用评级、畅销商品分类、医疗诊断、客户忠诚度分析、 客户关系管理等等。目前对分类的研究比较集中于挖掘算法的研究，己 出现许多的挖掘算法，包括来自机器学习、专家系统、统计学和神经生 物学方面的各种技术，每种算法各有其优缺点，在理论上还没有发现有 一种方法对所有数据都优于其他方法。 分类的目的是学会一个分类函数或者分类模型( 也常称为分类器) ， 该模型能把数据库中的数据项根据其共同属性，映射到给定类别中的某 一个。分类和回归都可以用于预测。预测的目的是利用历史数据记录自 动推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归 方法不同，分类的输出是离散的类别值，而回归的输出则是连续值。要 构造分类器，需要有一个训练样本数据( 训练集) 作为输入。训练集由 一组数据库记录或者元组数据构成，每个元组数据是一个关键字段( 又 称为属性或特征) 值组成的特征向量，这些字段和大数据库( 测试集) 中的记录字段相同。另外，每个训练样本还有一个类标记。一个具体样 本的形式可以表示为：( k ，v 2 ，；c ) ，其中，v i 表示字段值，c 表示类别。 分类器的构造有统计方法、机器学习方法和神经网络方法等等。 统计方法包括贝叶斯法和非参数法( 近邻学习或基于事例学习： i n s t a n c e b a s e dl e a r n i n g ，i b l ) ，对应的知识表示为判别函数和原型事例。 机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或 判别树，后者则一般为产生式规则。神经网络方法主要是b p 算法，它 的模型表示是前向反馈神经网络模型( 由代表神经元的节点和代表联接 权值的边组成的一种体系结构) ，b p 算法本质上是一种非线性判别函 数。粗糙集( r o u g h s e t ) 和支持向量机( s u p p o r tv e c t o rm a c h i n e ) 是最 武汉工程大学硕士学位论文 近兴起的新方法。下面介绍几个主要的分类方法。 ( 1 ) 贝叶斯分类法 贝叶斯分类是统计分类方法，可预测类成员关系的可能性。贝叶斯 分类的基础是贝叶斯定理。当类条件独立假设成立时，即假定一个属性 值对给定类的影响独立与其他属性值，称为朴素贝叶斯分类算法。朴素 贝叶斯分类算法性能可以和决策树与神经网络算法相媲美，而对于大型 数据库，具有高准确率和高速度的特点。 ( 2 ) 决策树分类法 决策树是较早应用于数据挖掘分类问题的一种方法。在数据量较大 时，决策树方法能较快地构造出分类器；其树型结构可以很方便地转化 为s q l 语言形式，以便用来更有效地访问数据库；且i f t h e n 规则可 以很容易地从这种结构转化中得到，因此这种方法引起了研究者的广泛 兴趣。 绝大多数决策树分类方法分两步构造分类器：树的生成与树的剪 枝。在树的生成阶段，决策树是通过反复地分拆训练集而成。在每一次 分拆时，都是利用某种分拆准则选择一个属性。由所选属性值不同将训 练集分成多个子集。然后在每个子集上重复同样的分拆过程，直到每个 分拆后的训练集的子集样本均属于同一类别为止。 对树的剪枝操作是为了避免出现模型的过分拟合现象。因为如果完 全按训练集中的样本生成决策树，那么当样本数据存在噪声时，就会出 现过分拟合的现象，即把噪声数据当作正确的样本而同样要求决策树拟 合。这实际会导致决策树泛化能力的下降，甚至可能会使生成的决策树 几乎不可用。因此必须对过分拟合的分支进行修剪。通常的修剪方法有 两种：一是利用测试集，选择使得对测试集分类的误差最小的子树；另 外的一种方法是借助于m d l ( 最小描述长度) 原理进行剪枝，它是从 概率描述的层面来验证决策树的结构。上述两种方法的基本思想和目的 是一致的，都是为了弱化噪声数据的消极影响，提高分类模型的表达能 力。 这种分类方法的关键是在树的生成阶段找出合适的分拆准则。 ( 3 ) 支持向量机( s v m ) 6 第1 章绪论 支持向量机是统计学习理论的一个实现方法。统计学习理论是目前 针对小样本统计估计和预测学习的最佳理论，它从理论上系统地研究了 经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关 系及如何利用这些理论找到新的学习原则和方法等问题。 不同的分类器有不同的特点。分类方法可以根据下列标准进行比较 和评估： ( 1 ) 分类准确率：分类准确率是用得最广泛的一种比较尺度，特 别是对于预测型分类任务。常见的方法是n 折交叉验证法( n 一般取 1 0 ) 。 ( 2 ) 计算复杂度：计算复杂度依赖于算法的实现细节与硬件环境。 在d m 中，由于操作对象是大型数据库，并且在实际应用中数据规模越 来越大。因此空间和时间的复杂度问题将是一个非常重要的环节。 ( 3 ) 健壮性：这涉及对于数据集中噪声数据或空缺数据的处理， 它反应在有噪声数据或空缺数据的情况下模型是否有正确分类的能力。 ( 4 ) 可伸缩性：大部分的分类算法是内存驻留算法，通常假定数 据量很小。算法的可伸缩性意味着对于海量数据而言是否具有有效的构 造模型的能力。这一点在硬件性能提高且数据规模不断扩大的情况下显 得很重要。 ( 5 ) 模型的简洁度与可理解性：对于描述型的分类任务，模型描 述越简洁且越容易理解就越受欢迎。例如，采用规则表示的分类器比较 简明好用，而用神经网络构造产生的分类器则比较难以理解。 1 4 本文主要研究工作 本文是以某社区医院的信息系统数据为背景，对数据挖掘中的分类 技术进行深入研究的。 ( 1 ) 分析了几种传统的分类方法，包括决策树分类和贝叶斯分类。 重点研究了i d 3 算法和朴素贝叶斯算法的分类推理机制，并对这两种分 类算法的优缺点进行了进一步的探讨，得到更好的分类模型。 ( 2 ) 详细介绍了遗传算法的基本思想，逐一分析了基本遗传算法 武汉工程大学硕士学位论文 的实现技术，并通过对遗传算法的基本理论的研究，分析了基本遗传算 法收敛的充分条件。 ( 3 ) 针对基本遗传算法的编码在数据分类方面的不足，本文对个 体编码方案进行了两点改进，并结合改进后的编码方案求出支持度和置 信度以衡量规则的适应度。 ( 4 ) 本文采用j a v a 语言编写了一套基于遗传算法的分类器( 包 括基本遗传算法和改进后的遗传算法) ，通过与传统分类方法的比较验 证了模型的正确性和有效性。 1 5 全文章节安排 本文各章节安排如下： 第l 章：绪论，介绍了课题的背景情况、研究价值、数据挖掘中的 几种分类技术、论文的研究内容、研究方法及论文的组织结构。 第2 章：传统分类技术，详细分析了两种传统的分类技术：决策树 分类和贝叶斯分类。对它们的推理过程和适用性进行了详细的阐述。并 通过数据对传统分类技术进行了比较分析。 第3 章：遗传算法及其原理，详细介绍了遗传算法的生物基础和基 本思想，然后逐一分析了遗传算法的实现技术，最后给出遗传算法的基 本理论一模式定理和积木块假设，分析了基本遗传算法收敛的充分条件。 第4 章：基于遗传算法的分类器，对基于遗传算法的分类器模型进 行了研究，在基本遗传算法分类器的基础上，提出两点染色体编码方案 的改进方法，并将改进后的方案运用到分类器的构造上。最后通过实验 对改进前后的分类器模型进行了比较分析。 第5 章：系统实现及实验分析，本章主要介绍了本文开发的分类系 统的体系结构、运转流程和主要设计思想。最后采用同样的学习数据， 给出了前几个章节讨论的分类器的分类结果，对分类精度进行了比较。 第6 章：总结与展望，对本文的工作进行了总结，指出了论文研究 中的不足之处，对下一步的研究提出了设想和展望。 第2 章传统分类技术 第2 章传统分类技术 分类在数据挖掘中是一个非常重要的课题，且前在商业上应用的最 多。数据分类就是在一个数据库中找出一组对象的共同特征，并将数据 按照分类模型划分成不同的类的过程。分类的任务是找出一个类别的概 念描述( 通常称之为分类器) ，它代表了这类数据的整体信息，即该类 的内涵描述，一般用规则或决策树模式表示。该模式能够把数据库中的 元组映射到给定类别集中的某一个。分类的应用包括：医疗诊断、性能 预测、决策控制等。本章将详细讨论传统分类技术中的决策树归纳分类 和贝叶斯分类法。 2 1 决策树归纳分类 决策树方法是目前应用最广泛的归纳推理算法之一，是一种逼近离 散值函数的方法，也可以把它看作是一个布尔函数。它是以实例为基础 的归纳学习算法，通常用来形成分类器和预测模型，着眼于从一组无次 序、无规则的事例中推理出决策树表示形成的分类规则。 2 1 1决策树的基本概念 决策树算法n 阳最初由q u i n l a n 提出，是一种广泛使用的数据挖掘算 法和机器学习的算法。决策树使用的是“分而治之 的策略。它将一个 复杂的问题分成更简单的问题并重复使用这一战术来解决子问题，从而 将复杂的问题瓦解。子问题的解通过组合可以产生复杂问题的解 这种算法通过自上而下地划分训练数据，将习得的训练集函数表示 成树结构。树的每个节点对应一个非类别属性，每条边对应该属性的每 个可能值。最初将所有训练数据赋予根结点，以信息熵的下降速度作为 选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚 武汉工程大学硕士学位论文 未被考虑的具有最高信息增益的属性。然后选择该属性，根据可能得到 的属性值将根分枝，这样将训练集分为子集，每个分支包含一个子集。 对每个分支重复这个过程，直到一个结点下的所有训练数据都属于同一 类或者没有剩余属性可划分。如果没有属性可分，则将结点中大多数数 据所属的类赋给这个结点。 2 1 2ld 3 决策树构造算法 决策树归纳的基本算法是贪心算法，它以自顶向下递归的各个击破 方式构造树，它的构造思路是：如果训练数据集合中的所有数据是同类 的，则将之作为叶子节点，节点内容即是该类别标记；否则，在训练集 中根据某种策略选择一个属性，按照属性的各个取值，把数据集合划分 为若干子集合，使得每个子集上的所有数据在该属性上具有同样的属性 值；然后再依次递归处理各个子集。这种思路实际上就是“分而治之 的道理。 下面是由训练样本产生决策树的基本算法【8 】： 算法：g e n e r a t ed e c i s i o nt r e e 由给定的训练数据产生一棵决策树。 输入：训练数据s a m p l e s ，由离散值属性表示；候选属性集合 a t t r i b u t e l i s t 。 输出：一棵决策树。 方法： ( 1 ) 创建节点n ； ( 2 ) i f s a m p l e s 都在同一个类ct h e n ( 3 ) 返回n 作为叶节点，以类c 标记； ( 4 ) i f a t t r i b u t el i s t 为空t h e n ( 5 ) 返回n 作为叶节点，标记为s a m p l e s 中最普通的类； ( 6 ) 选择a t t r i b u t el i s t 中具有最高信息增益的属性t e s ta t t r i b u t e ； 1 0 第2 章传统分类技术 ( 7 ) 标记节点n 为t e s ta t t r i b u t e ； ( 8 ) f o re a c ht e s ta t t r i b u t e 中的己知值珥 ( 9 ) 由节点n 长出一个条件为t e s ta t t r i b u t e = a , 的分支； ( 1 0 ) 设最是s a m p l e s 中t e s ta t t r i b u t e = a i 的样本的集合； ( 11 ) i f 最为空t h e n ( 1 2 ) 加上一个树叶，标记为s a m p l e s 中最普通的类； ( 13 ) e l s e 加上一个由g e n e r a t ed e c i s i o nt r e e ( 墨， a t t r i b u t el i s t t e s ta t t r i b u t e ) 返回的节点。 在上述在决策树形成过程中，最重要的部分是对分裂属性的选择。 比较常用的一种方法是使用信息增益度量选择测试属性。信息增益的原 理来自信息论，它是使某个属性用来分割训练集而导致的期望熵降低。 因此，信息增益越大的属性分裂数据集的可能性越大。决策树的形成就 是递归的对数据集中的每个节点进行分裂，直到节点的所有类别都属于 同一类或没有多余的属性来划分训练样本集。这种信息理论方法使得对 一个对象分类所需的期望测试数目达到最小，并确保找到一颗简单的 ( 但不必是最简单的) 树n 卜1 2 1 。 按照信息论的定义，设s 是s 个数据样本的集合。假定类标号属性 具有m 个不同值，定义m 个不同类c ( i = 1 ，2 - - - m ) 。设置是类g 中的样 本数。对一个给定的样本分类所需的期望信息由下式给出： l ，( s l ，) = 一届l 0 9 2 ( a ) i = 1 其中肛是任意样本g 的概率，并用最s 估计。注意，对数函数以2 为底，因为信息用二进制编码。 设属性a 具有v 个不同的值他，吃，q ，。可以用属性a 将s 划分为 v 个子集 墨，是，墨) ；其中，s ，包含s 中这样的一些样本，它们在a 上具 有值a ，。假设选取a 作为本次分类的属性，则这些子集对应于由包含集 合s 的节点生长出来的分枝。设是子集s ，中类c 的样本数。根据由a 武汉工程大学硕士学位论文 划分成子集的熵由下式得出： e(4)：=：娄华，(&，s。，) 其中项羔生皇为第j 个子集的权值，并等于子集( 即a 值为口，) 中的样本个数除以s 中的样本总数。熵值越小，子集划分的纯度越高。 对应给定的子集s ， i ( s 。，) = 一岛l o g ：( 岛) 其中，功2 尚是t 中的样本属于类g 的概率。 在a 上分枝将获得的编码信息即节点的信息增益为： g a i n ( a ) = i ( s l ，s 2 ，s 。) 一e ( 彳) 也就是说，g a i n ( a ) 是由于知道属性a 的值而导致的熵的期望压 缩。 为了使下一步所需的信息量最小，要求每一次都选择其信息增益最 大的属性作为决策树的新结点，并对属性的每个值创建分枝，依据此思 想划分训练数据样本集n 副。 2 1 3 j 4 8 分类算法 j 4 8 算法n 7 1 是i d 3 算法的改进，增加了对连续型属性、属性值空 缺情况的处理( i d 3 算法只适用于所有属性都是离散字段的情况) 。算 法主体由决策树生成算法、剪枝算法、规则生成算法3 部分组成。决策 树生成算法依据信息熵理论，选择当前样本集中具有最大信息增益率的 属性作为测试属性不断对样本集进行划分，最终构造出一棵完全决策 树。对于连续型的属性先进行离散化，即把连续型属性的值划分成不同 的区间，便于处理。为消除完全决策树对样本分类时产生的“过度拟合 问题，必须对它进行化简。剪枝算法采用基于错误的剪枝方法对完全决 第2 章传统分类技术 策树进行修剪，得到简化决策树。规则生成算法把完全决策树转化成一 组i f t h e n 规则集并进行化简。经剪枝或规则生成过程得到的简化决策 树和规则集都可用于分类。 2 2 贝叶斯分类法 贝叶斯分类是统计学分类方法，他们可以预测类成员关系的可能 性，如给定样本属于一个特定类的概率。贝叶斯分类基于贝叶斯定理， 一种称作朴素贝叶斯分类的简单贝叶斯分类算法可以与判定树和神经 网络分类算法相媲美，用于大型数据库，贝叶斯分类也已表现出高准确 率与高速度。朴素贝叶斯分类假定一个属性值对给定类的影响独立于其 他属性的值。这一假定称作类条件独立。做此假定是为了简化所需计算， 并在此意义下称为“朴素的”。 2 2 1 贝叶斯定理 贝叶斯定理n 踟是贝叶斯理论中最重要的一个公式，是贝叶斯学习方 法的理论基础，它将事件的先验概率与后验概率巧妙地联系起来，利用先 验信息和样本数据信息确定事件的后验概率。 设x 是类标号未知的数据样本，h 为某种假定，如数据样本x 属 于某特定的类c 。对于分类问题，我们希望确定p ( h i x ) ，即给定观测 数据样本x ，假定h 成立的概率。 由条件概率，尸( hix ) = 晕等，尸( xih ) = 罩等 得贝叶斯定理： 尸( h i x ) = 丛警。 武汉工程大学硕士学位论文 2 2 2 朴素贝叶斯分类 朴素贝叶斯分类的工作过程如下阻3 ： 1 每个数据样本用一个n 雒特征向量x = 五，屯，吒) 表示，分别描 述n 个属性4 ，4 ，4 样本的n 个度量。 2 假定有m 个类q ，c 2 ，q 。一个未知的数据样本x ( 即没有类标 号) ，分类法将预测x 属于具有最高后验概率( 条件x 下) 的类。即使 说，朴素贝叶斯分类将未知的样本分配给类c ，当且仅当 p ( c ：i x ) 以qi x ) ，1 j m ，j i 。 这样，最大化p ( ql x ) 。其尸( qi x ) 最大的类q 称为最大后验假定。 根据贝叶斯定理，p ( qlx ) = 旦等簪等盟。 3 由于p ( x ) 对于所有类为常数，只需要p ( x i q ) 只g ) 最大即可。 如果类的先验概率未知，则通常假定这些类是等概率的，即 尸( g ) = p ( c 2 ) = = p ( q ) 。并据此只对p ( xig ) 最大化。否则，最大化 p ( x ic ：) p ( c ) 。注意，类的先验概率可以用p ( g ) = 墨s 计算，其中s 是类 g 中的训练样本数，而s 是训练样本总数。 4 给定具有许多属性的数据集，计算p ( xic ) 的开销可能非常大。 为降低计算p ( x l c ) 的开销，可以做类条件独立的朴素假定。给定样本 的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。 这样，p ( x l q ) = 兀p ( x ki q ) ，概率p ( 五i g ) ，尸( 置i c ) ，p ( 以lc ：f ) 可以由训 练样本估值，其中 ( a ) 如果4 是离散属性，则尸( 墨ic ) = & 墨，其中& 是在属性4 上 具有值墨的类c 的训练样本数，而墨是g 中的训练样本数。 ( b ) 如果4 是连续值属性，则通常假定该属性服从高斯分布。因 ( 以一心) 。 1 z 产 而，尸( 瓦ic ：f ) = g ( 五，心，气) = 1 三一p 加q ，其中，给定类g 的训 。 z 冗o 、 i 1 4 第2 章传统分类技术 练样本属性4 的值，g ( 五，心。气) 是属性4 的高斯密度函数，而心，气分 别为平均值和标准差。 在本论文的研究中，分类对象是离散的。 5 为对未知样本x 分类，对每个类q ，计算p ( xig ) p ( c ) 。样本x 被指派到类q ，当且仅当p ( xic ：) p ( q ) p ( xlc ，) p ( c ，) ，1 ，m ，j i ，换 言之，x 被指派到其p ( xiq ) 以q ) 最大的类g 。 相对于其他分类方法，朴素贝叶斯分类算法的最大特点是不需要搜 索，只需简单地计算训练例中各个属性值发生的频率数，就可以估计出每 个属性的概率估计值，因而朴素贝叶斯分类算法的效率特别高，分类效 果与很多经典的分类器不相上下。 然而，由于其对属性变量间的独立性要求很强，在实际中较难得到 满足。如果问题中属性之间有较强的相关性，则分类效果并不十分理想。 朴素贝叶斯分类是以贝叶斯定理作为基础的，是贝叶斯分类器之中 最简单的一种，也是对贝叶斯网络结构的限制最大的，它将类别节点作 为根节点，其各属性节点相互独立，且都以类别节点为父节点。如图2 1 ， 它假设所有的属性节点都是相互独立的，因为结构简单，因此称之为朴 素。尽管朴素贝叶斯分类器的结构简单，但是它经常能给出很好的分类 结果。 2 2 3 a o d e 分类器 图2 1 朴素贝叶斯分类器 由于朴素贝叶斯是基于描述一个事件的属性都是相互独立的假设， 与客观世界的情况不符，因此精度尚有提高的空间，此后很多的研究者 武汉工程大学硕士学位论文 都在想法设法弱化这个假设。在这些改进工作中，有两个取得了精度上 的巨大进展，它们是l b r n 们( l a yb a y e s i a nr u l e s ) 以及s p t a n 眩们( s u p e r p a r e n tt a n ) 。 l b r 提出了一种弱化属性之间依赖的方法，其原理公式为： 上 m a x ( p ( ci 形) l jp ( 五ic ，形) ) ， 扣1 可以看到其基本思路跟朴素贝叶斯很像，所不同的是它多了一个集 合w ，在朴素贝叶斯中假设所有的属性相互独立，既然这样的假设太强， 那么就把独立属性的范围缩小一点，置与集合w 中的属性仍然保持相互 独立的关系，但是与不属于这个集合的属性相互依赖，要作为一个整体 来考察，通过调解w 的大小，来调整算法的效率与精度之间的平衡，朴 素贝叶斯就可以看成是w 为全体属性集合时候的特殊情况。当w 比较小 的时候就必须判断z 与很多其它非独立属性之间的“捆绑”的情况，因 此l b r 在做分类预测的时候，效率有很大下降。 s p t a n 与l b r 的思想互为补充，l b r 定义了一个属性独立的集合， s p t a n 就定义了属性依赖的关系，它为当前属性定义了一个母属性， 当前属性与母属性相互依赖，要放在一起考虑。其原理如下： 一上一 m a x ( p ( c ) i ip ( 五ic ，尸( 置) ) ) ， 扭i 定义了置与其家长属性p ( 五) 的依赖关系，p ( 置) 方法是s p t a n 在 训练时要得到的一个方法，它通过两两分析所有属性组合的相关性来构 造这个映射，因此s p t a n 在训练时性能较朴素贝叶斯有所下降。 a o d e 针对了l b r 以及s p t a n 的弱点，综合了两种算法的优点， 提出了一个高效而精准的实用解决方案乜