（计算机应用技术专业论文）基于sliq的分布式医学图像分类系统设计与实现.pdf

江苏大学硕士学位论文 摘要 随着电子计算机断层摄影、核磁共振成像技术等医学成像技术 的产生和发展，人们获得了越来越多可供临床诊断的医学图像，如 何有效地利用计算机技术对其进行分类已成为国内外许多学者研究 的一个热点问题。另外，在现实环境中，许多医院的医学图像数据 是分散存放的，它们之间除了通过网络传递信息外，其它资源全部 独立。因此，研究并提出适合于分布式医学图像的分类方法具有较 高的学术价值和广泛的应用前景。 论文讨论了分布式医学图像分类挖掘的背景、意义和国内外研 究状况。针对医学图像存放的特点及分布式医学图像分类挖掘的实 际应用要求，提出了解决分布式医学图像分类的方法。对现有决策 树算法存在的问题，提出基于s u q 的改进算法d m is u q ，较好地 解决了分布式分类挖掘问题，初步建立了基于s l i q 的分布式医学图 像分类框架。 论文从理论、算法和应用三个方面对分布式医学图像分类方法 进行了研究，主要工作包括： 1 、本文将分类技术与数字图像处理技术有机结合，研究了分布 式医学图像的主要分类方法，并给出了本文实验所用到的医学图像 特征。 2 、针对s u q 算法的缺点，提出了d m is u q 算法，从而解决 了s u q 算法搜索空间巨大，耗时多等问题。 3 、设计并实现了一个分布式协调器算法，用来初始化和管理 江苏大学硕士学位论文 a g e n t 的分类活动，管理和控制事务的运行。 4 、针对医学图像分布式存放的特点，提出了一个适用于分布式 医学图像分类的框架。该框架包括：表示层、处理层、采掘层。 5 、实现了分布式医学图像分类实验系统- d m i d m ，在系统中 实现了本文提出的分布式协调器任务调度算法、全局模型规则生成 算法。 关键词：数据挖掘，分布式，协调器，分类，医学图像 江苏大学硕士学位论文 a b s t r c t w i t ht h ed e v e l o p m e n to fc o n l p u t e rt o m o 铲a p h y ，m a 印e t i cr e s o n a n c e i m a g i n gt e e h n o l o g y ，a n do t h e rm e d i c a li n l a g i n gt e c l m o l o g y ；p e o p l eh a s g a i n e dt h em o r ea n dm o r ed i a g n o s i so fm e d i c a li m a g e ，h o we f l e c t i v e u s eo fc o i 印u t e rt e c l m o l o g yt oc l a s s 匆s om a n ys c h o l a r sh a sb e c o m ea h o ti s s u eb o t ha th o m ea n da b r o a d i nr e a l i t y ，m e d i c a li i l l a g ed a t aa r e s c a t t e r e ds t o r ei nm a n yh o s p i t a l s t h e yt r a n s f e rt h ei i l f o m a t i o no u t s i d e b e 俩e e nt h e me x c e p tp a s s i i l gan e 俩o r k ，o t h e ra l l i i l d e p e n d e n c e so f r e s o u r c e t h e r e f o r e ， t h e s t l l d y a n d p r o p o s ea p p r o p r i a t e t ot h e d a s s i f i c a t i o no fm e d i c a li m a g e sd i s t r i b u t e dm e t h o dh a saf a i r l y h i 曲 a c a d e r n j cv a l u ea n db r o a da p p l i c a t i o np r o s p e c t s t h ep a p e rt a k et h em e d i c i n e 油a g ed a t aa st h er e s e a r c ho b j e c t ，仃o m t h et h e o r y ；t h e a l g o r i t l l i na n da p p l i e dt 1 1 r e ea s p e c t st oc o n d u c tt h e r e s e a r c ht ot h ed i s t r i b u t i o n a lm e d i d n ep i c t u r ed a s s i f i c a t i o nm e t h o d i n v i e wo ft h ee x i s t i n gp o l i c y m a l d n gt r e ea l g o r i t l l l ne x i s t e n c eq u e s t i o n ，w e p r o p o s e di n l p r o v e m e n ta l g o r i t l u nd m l s l i qb a s e d o n s u q ， d m l s u q h a ss o l v e dt h ed i s t r i b u t i o n a ld a s s i f i e de x c a v a t i o np r o b l e m t b j sp a p e rh a se s t a b l i s h e dd i s t r i b u t i o n a lm e d i d n ei 】m a g ec l a s s i f i c a t i o n 仃a m e b a s e do nt h es l i q t h ep a p e r6 o mt h et h e o r y ；t h ea l g o r i t h ma n da p p l i e dt h r e ea s p e c t s t oc o n d u c tt h er e s e a r c ht ot h e d i s t r i b u t i o n a lm e d i c i n e p i c t u r e c l a s s i f i c a t i o nm e t h o d ，t h em a i l lw o r ki n d u d e d 江苏大学硕士学位论文 1 1 1 ：1 i sa n i c l ed a s s i f i e st e c h l l i c a la n dt h ed i g i t a lm e d i c a li m a g e p r o c e s s i i l gt e c b n o l o g y a n dh a ss t u d i e dt h em a i l lm e t h o da b o u tt h e d i s t r i b u t i o n a lm e d i c i n ep i 曲【l r ec l a s s i f i e d ，a n dh a sp r o d u c e dt h em e d i c i n e p i c t u r ec h a r a c t e r i s t i cw m c h t h i sa r t i d et e s t su s e s 2 i nv i e wo ft h ed e c i s i o nt r e ea l g o r i t h ms u qs h o r t c o 面n g ，t h i s p a p e ri l p r o v e da n dp r o p o s e dt h ed m l s l i qa l g o r i t l 1 1 t h u ss o l v e st h e s u qa l g o r i t h ms e a r c hs p a c e 伊e a t l y c o n s u m e sw h e na r et om a n ya n d s oo nt h eq u e s t i o n ，a n dc o m p a r e dw i t ha l g o r i t l u i lp e r f o 皿a n c e ，t l l r o u g l l a n a l y s i se x p e r i i n e n tr e s u l t 3 i nv i e wo ft h em e d i c i n e p i c t u r e d i s t r i b u t i o n a l d e p o s i t i n g c h a r a c t e r i s t i c ，d i s t r i b u t i o n a lm e d i c i n ei m a g ec l a s s i f i c a t i o nt h e o 巧仃a m e i sp r o p o s e ds u i t a b l ef o r t h ei s s u e t b j sf 锄ed i v i d e si n t ot h r e ep a r t s ，w e p r o d u c e se a c hd e t a i l e dd e s i g nt h o u g h ta n dt h ep 血c i p l eo f w o r k 4 t h j s p a p e r h a sr e a l i z e dd i s t r i b u t i o n a lm e d i c i n e i 】【1 1 a g e d a s s i f i c a t i o n e x p e r i m e n ts y s t e md m i d m ， a n dr e a l i z e dt h e d i s t r i b u t i o n a ls y n c l l r d n i z e rd u t yd i s p a t c ha l g o r i t l u n ，t h eo v e r a l ls i t l l a t i o n i n o d e lr u l e p r o d u c t i o na l g o r i t l n i nt h e s y s t e mw m c ht h i s a n i c l e p r o p o s e d t h e 仃a m e w o r ki n c l u d e s ：t h a tl a y e r ，l a y e rh a n d l i l l g ，a n d 血n i n gl a y e r k e yw o l i s ：d i s t r i b u t i o n d a t am i 幽唱，c l a s s i f i c a t i o 玛m e d i c a l l i m a g e 江苏大学学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 以外，本论文不包含任何其它个人或集体已经发表或撰写过的 作品成果。对本文的研究做出重要贡献的个人和集体，均己在 文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作者签名：殳锨 日期：矽口妒年 多月，口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密 学位论文作者签名：雾0 彩l 呻年多月f 口日 指导教师签名：等净参 哥年厶月i 。日 江苏大学硕士学位论文 1 1 课题研究背景与意义 第一章绪论 随着电子计算机断层摄影( c o m p u t i 甜t o m o g r a p h y ：c 、核磁共振成像技术 u c l e a rm a 印e t i cr e s o n a i l c ci m a g i n g ：m r i ) 等医学成像技术的产生和发展，人们 获得了越来越多的可供临床诊断和分析的医学图像，如c r 、m r 、s p e c t 、p e t 、 d s a 、超声图像、电阻抗图像等，医学诊断越来越离不开医学图像【1 1 。仅以镇江 江滨医院为例，平均每年所产生的病人图像数据高达2 6 g 。随着计算机及其相关 技术的迅速发展以及图形图像技术的同趋成熟，人们可以对这些医学图像进行任 意放大、缩小、旋转、对比调整、分割、配准、三维重建等处理，医务工作者可 以从多方位、多层次、多角度对医学图像进行观察，从而辅助医生对病变体及其 它感兴趣区域进行重点分析，提高了临床诊断的准确性，开创了数字医疗的新时 代。但是，目前图像诊断方法仍是通过肉眼观察图像中的病变区域，依靠医生个 人的临床经验和主观判断来进行诊断。该方法存在如下不足：( 1 ) 信息利用率不 高，由于医学图像一般不具有很高的分辨率( 如c t 图像灰度级高达4 0 9 6 级) ， 那些人眼无法分辨的图像信息和图像特征就得不到充分应用，从而会影响病情的 早期判断。( 2 ) 医生带有个人的主观性，诊断结果很大程度上依赖于医生个人的 临床经验，对于那些临床经验较少的医生来说，要做出正确的诊断是非常困难的。 另外，同一张医学图像，不同的医生也有可能得出不同的诊断结果，相互之间的 差别可能很大，发生误诊或漏诊的现象是不可避免的。( 3 ) 人工观察耗时多，对 于单个病人的诊断，医生直接观察患者的病变区域所耗时间和精力是可以接受 的，如果若对大量临床图像进行病理研究时，仍然采取人工读图的方式就让人显 得难以接受。因此，如何充分利用计算机图像处理技术快速、准确地将医学图像 中的病变区域检测或分辨出来，即确定医学图像中各组织器官所属的类别( 正常 或何种类型的异常) ，确保临床诊断更客观、准确和科学，已成为医学图像诊断 中的一个关键技术。 美国可视人计划( 皿) 于1 9 8 9 年立项，在1 9 9 4 年和1 9 9 5 年相继采集了 一男一女的断层图像数据，并开始对断层图像数据进行分割、分类、三维重建和 江苏大学硕士学位论文 可视化工作【2 j 。可视人是数字虚拟人体的第一代，图像分类是其中的一个重要处 理及应用技术。另外，自2 0 0 1 年开始，中国虚拟人计划获得资助，在该计划中， 为了确定可视化人体的具体部位，需要进行大量的图像分类工作。此外，在图像 指导治疗技术中，医学图像后处理及其治疗方法、手术计划与导航和医学虚拟现 实及其相关技术等都需要进行大量的医学图像分类工作。 综上所述，医学图像分类方法的研究具有十分广泛的应用前景。目前可用的 分类方法有很多，如神经网络分类法、决策树法、贝叶斯统计分类法、遗传算法 和k - 邻近值法等。这些方法可以有效地解决单机环境下医学图像的分类问题。然 而，在现实环境中，许多医院的医学图像数据是分散存放的，它们之问除了通过 网络传递信息外，其他资源全部独立，因此，研究并提出适合于分布式医学图像 的分类方法将有着重要的现实意义。 1 2 国内外研究现状 1 2 1 医学图像分类的研究现状 近年来，在一些发达国家，围绕包括医学图像分类在内的医学图像挖掘技术 已经开展了广泛而深入的研究，并已取得了一定的进展。如美国爱荷华州立大学 的a k u s i a k 等人提取了5 0 个肺癌病人的一般信息( 如年龄、性别等) 和x 光影像 数据等1 8 个特征数据，将粗糙集理论应用于数据挖掘，从而提高了肺癌病人早 期诊断的正确率。日本合作研究发展中心的m i t s u mk a k i m o t 等人提出了用逻辑 回归分析算法( l o g i 咖r e 伊e s s i o na n a l y s i su 提取关联规则，发现了脑部功能 与手指活动和说话行为之间的关系。日本y u s u k eu e h a r c a 等人在m d m k d d 2 0 0 2 年会上提出了基于假设驱动( 1 l y p o t h e s i s d 由e n ) 的多媒体数据挖掘过程的思想理 论。加拿大劬e r t a 大学计算机系的o s m a rr z a i y a i l e 等人就神经网络和关联规则 挖掘技术在乳腺癌分类研究中的应用进行了分析对比，认为神经网络的方法对数 据集不平衡性的敏感程度低于关联规则挖掘方法。o r d o n e z 提出了一种不依赖特 定应用领域知识的图像关联规则算法，但是该算法只能产生图像对象共同出现的 关联规则，仅仅适用于相伺类型且只包含少量对象的图像，在很大程度上受着海 量数据库集在快速执行时常见的算法问题的限制。 在国内，清华大学石纯一、陆玉昌教授、中科院计算所史忠植研究员、中国 2 江苏大学硕士学位论文 科技大学王煦法教授等已在数据挖掘研究方面取得了许多研究成果。上海交通大 学生物医学工程系庄天戈教授采用当代乳腺疾病x 线诊断图谱中的2 3 0 个 病例数据，应用决策树算法进行了数据挖掘的尝试。由中国科学院自动化研究所 田捷教授、北京大学包尚联教授、西北大学周明全教授合著的专著医学影像处 理与分析一书，系统地介绍了医学影像处理与分析技术，涵盖计算机断层扫描 成像技术、医学图像的分割、医学图像的配准、医学图像的三维重建与可视化技 术、虚拟内窥镜技术及p a c s 系统等内容。江苏大学朱玉全、杨鹤标等人在所著 数据挖掘技术中，对医学图像分类框架模型进行了分析，并利用关联规则进 行了挖掘研究【3 】。总之，国内在这方面的研究还处于起步阶段。 1 2 2 分布式医学图像分类系统的研究现状 在分布式数据挖掘系统方面，h i l l o l 勋曙u p t a 等人提出的一个基于a g e n t 的分布式数据挖掘系统p a d m a ，该系统不限定于特定的数据挖掘领域【4 1 。 p a d m a 系统由数据挖掘a g e n t 、协调各a g e n t 工作的f a c i l i t a t o r 和用户接口等组 件构成，数据挖掘a g e n t 负责读取数据并提取高层次的信息。f a d i t a t o r 负责协 调各a g e m 工作并提供信息给用户接口，它同时接收用户的反馈信息给各个 a g e n t 。p a d m a 系统有一个图形化的基于w 曲的用户接口，用来把各a g e n t 提 取与特定查询相关的信息展现给用户。f a c i l i t a t o r 接收用户接口以标准s q l 格式 提交的查询，这些查询被广播给各个a g e n t ，f a c i l i t a t o r 负责收集这些信息并将其 展现给用户。该系统使用p p f s ( p a r a l l e lp o r t a b l ef i l es y s t e m ) 开发，以面向对象的 方式用c + + 语言编码，提供了一个可扩展的架构，使用m p i ( m e s s a g ep a s s i n g i i l t e r f a c e ) 进行底层的消息交换和通信。该系统可以划分为如下三个功能模块：并 行数据读取和查询处理模块、收集汇总模块、用户交互、结果展现模块。 几w ( j a v aa g e n t sf o rm e t a 1 e a m i n 曲系统是a l p r o d r o m i d i s 等人共同设计的 一个分布式数据开采系统【5 1 。该系统提出了使用m e t a 1 e a m i n g 进行分布式数据 开采的思想。m e t a l e a m i n g 是一种计算高层c l 弱s i f i e r s ( 称为m e t a d 雒s i f i e r s ) 的技 术，即把各个数据库上分别独立计算的d a s s i f i e r s 以某种原则汇集成高层 d a s s i f i e r s 的技术。该系统使用j 趟，a 语言编写，具有较好的平台无关性。很多分 布式数据挖掘系统都是针对数据源“水平划分 的情形，即各个数据分块中的记 3 江苏大学硕士学位论文 录具有相同的属性结构。h i l l o lk 哪卵t a 等最近提出一种称为c o l l e c t i v ed a t a m i n i i l g 的思想来实现对数据源“垂直划分”的情形进行分布式数据挖掘【5 1 。其主 要方法是首先各个站点根据自己的数据集分别计算一个近似规范正交基系数，然 后从各个站点的数据集选取一些特定的样本移到一个站点上，根据这个集成数据 集来计算针对于非线性交叉项的近似基系数，最后根据基系数将局部模型合并成 全局模型并提交给用户。 在信息科学的第七届联合会议上，j e r z yb a l a 和aw i l l i 锄s 等人提出了题为 a p p l i c a t i o n so fd i s t 曲u t e dm i n i n gt e c h i l i q u e sf o rk n o w l e d g ed i s c 0 v e 巧的研究，并 提出了基于决策树的分布式分类算法的研究成果。在j e r z y 等人提出的基于决策 树的分布式分类算法中，分饰式分类算法经由a g e n t s 和m e d i a t o r 之间的同步协 作机制来完成，m e d i a t o r 负责各个a g e n t 之间的通信。分布式数据挖掘的结果通 过树的归纳算法以一系列的规则集来表示。该算法是以一种反复迭代的方式，找 到最佳的分类属性，利用这个属性特征来划分数据。各个a g e n t 通过协商、合作 和行为规范的方式，产生出局部子树，并且把局部结果传达给各个a g e n t 。 p a p y m s 系统：该系统基于与j 舢系统相似的理论基础，主要用于对分布在 广域网内的数据进行有效的分布式数据挖掘。 k e n s i n 昏o n 系统：该系统采用了分布式组件技术，主要用于1 1 1 t e m e t 上的分 布式数据挖掘。 其它的分布式数据挖掘系统还有美国p i t t s b u 础大学的a d o n i s 教授等设计的 w b r l d 系统、c h a v e z 的c h a l l e n g e r 【6 】系统等。 综上所述，目前国内外学者对医学图像分类的研究已经取得了一些成果，但 基本上都是基于集中存放的数据，没有针对分布式存放的医学图像数据进行挖 掘，并且针对医学图像知识的获取与表达上存在困难，且带有一定的主观性，同 时用于特定医学图像领域的复杂数据类型处理的数据挖掘工具也是少之更少。而 分布式医学图像分类挖掘是一项复杂的、具有挑战性的和多学科交叉的领域，对 它的研究仍处于起步阶段，因此开展分布式医学图像分类挖掘的研究具有广阔的 前景。 4 江苏大学硕士学位论文 1 3 本论文研究内容 基于上述的国内外研究现状，本文提出了一种分布式医学图像分类系统的框 架，设计并实现其中的主要部分。本文研究的具体内容包括： 1 、本文将分类技术与数字图像处理技术有机结合，研究了分布式医学图像 的主要分类方法，并给出了本文实验所用到的医学图像特征。 2 、对现有的分类算法进行总结分析，实现了s u q 算法。针对s u q 算法 的缺点，引入了索引技术，提出了d m is u q 算法，解决了s u 0 算法搜索空间 巨大，耗时多等问题。 3 、设计并实现了一个分布式协调器算法，用来初始化和管理a g e n t 的分类 活动，管理和控制事务的运行。 4 、针对医学图像分布式存放的特点，提出了一个适用于分布式医学图像分 类的框架。该框架包括：表示层、处理层、采掘层。 5 、实现了分布式医学图像分类实验系统d m d m ，系统实现了本文提出 的分布式协调器任务调度算法、全局模型规则生成算法，该算法可以将局部站点 生成的模型融合成全局模型。解决了分类任务互斥的问题，并给出了该模型的协 调算法。 1 4 本文的结构 本文共分六章，具体安排如下： 第一章介绍课题的研究背景、研究意义、国内外研究现状以及论文研究的 主要内容和结构。 第二章介绍了图像分类的过程，给出了分布式医学图像分类的概念。介绍 了常用的分类算法和试验用到的医学图像特征。 第三章分析并实现了s u q 算法。并对s u q 预处理阶段进行改进，设计 并实现了d m l j u q 算法，使它适用于分布式环境下的分类挖掘。 第四章提出了分布式医学图像分类模型- d m i m m 的基本设计思想， 介绍了系统的工作原理，以及核心模块的设计思想。 第五章实现d m i i d m 试验系统，详细介绍了分布式协调器任务调度算法 和全局模型生成的实现方法。 5 江苏大学硕士学位论文 第六章对本文研究工作进行了总结，根据自己研究的成果和体会，确定了 下一步研究工作的重点与研究方法。 6 江苏大学硕士学位论文 第二章医学图像分类技术研究 本章简单地介绍了医学图像分类的基本流程、医学图像的预处理技术、特征 提取技术及几种常用的分类算法。 2 1 医学图像分类 医学图像分类的目的是构造一个分类函数或分类模型( 也称分类器) ，该函 数能把医学图像数据库中的每一幅医学图像映射到给定类别中的某一个类。即给 定医学图像数据库d = t l ，t 2 ，t n ) ，其中每个元组表示一幅医学图像，分类问题定 义为从医学图像数据库d 到类别属性集合c 的映射f ：d c ，该映射能将医学 图像数据库中的元组t i 分配到某个类中，分类的目的就是采用某种方法将隐含函 数f 表示出来【们。 要构造分类器，需要一个训练样本医学图像数据集，该数据集称为“训练集， 它是指医学图像数据库中为建立模型或构造分类函数的医学图像集合。训练集中 的单个医学图像称为训练样本，每个训练样本的类别属性值是已知的。分类的任 务就是根据从训练样本中发现的规则对未知其类别属性值的医学图像进行分类。 也就是说，分类是从训练样本的属性中发现个体或对象的一般分类规则，从而根 据这些规则对未知类别属性的医学图像进行分类。一般情况下，医学图像分类需 要经历以下三个阶段： 1 、分类模型训练阶段。这一阶段也称为监督学习。在该阶段，每个训练样 本的类别属性值是事先己知的，需要做的工作是建立一个分类模型，用该分类模 型来描述这些预先定义好的数据类别，依据训练集中每幅医学图像已知的类别归 属总结出一般性的分类规则，并建立分类模型。一般情况下，分类模型以分类规 则、决策树或数学公式的形式给出。 2 、分类模型评估阶段。该阶段用来评判分类模型的好坏，可以使用以下5 个指标来对分类模型进行比较和评估： ( 1 ) 模型的准确率：该指标描述分类模型正确地预测类别属性未知的医学图 像类别的能力，通常情况下，可以使用测试集来评估模型的准确率。 ( 2 ) 计算复杂度：产生和使用模型的计算开销，计算复杂度依赖于具体的实 现细节和硬件环境，在医学图像数据挖掘中，由于操作对象是非常巨量的，因此 7 江苏大学硕士学位论文 空间和时间复杂度是分类问题中必须考虑的一个重要环节。 ( 3 ) 强壮性：强壮性是对模型准确率的一个补充，是在存在噪声数据及数据 缺省的情况下，对未知其类的数据进行分类的能力。 ( 4 ) 可伸缩性：医学数据挖掘所处理的对象数据是巨大的，这就要求所构建 的分类模型可以适用于各种不同规模的数据量。 ( 5 ) 模型描述的简洁度：这是针对分类模型对问题的描述方法以及该描述方 法的可理解程度提出的。分类模型的最终目的是方便决策人员的使用，所以，对 于决策人员来讲，模型描述的越简洁，也就越易于理解，同时也就越受欢迎。例 如，采用规则表示的分类器构造法所提供的分类模型的描述方法就比较简洁、易 于理解，而神经网络方法所产生的描述结果相对来说就难以理解。 3 、分类阶段。运用分类模型对未知其类别属性值的医学图像进行分类处理。 在上述三个阶段中，第一阶段是重点，亦是难点，分类的主要工作将集中在 分类器的构造上。 2 2 常用的分类方法 目前，常用的分类方法有：决策树算法、贝叶斯方法、决策树方法、人工神 经网络方法和遗传算法。 2 2 1 决策树方法 决策树( d e c i s i o nt r e e ) 又称为判定树，是一种运用于分类的树结构。其中每 个内部结点( i n t e m 甜n o d e ) 代表对某个属性的一次测试，每条边代表一个测试结 果，叶结点( 1 e 田代表某个类( c l 硒s ) 或者类的分布( c l a s sd i s t 曲u t i o n ) ，最上面的结 点是根结点。 决策树是以实例为基础的归纳学习算法，它从一组无次序、无规则的元组中 推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内 部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要 学习划分的类。从根到叶结点的一条路径就对应着一条合取规则，整个决策树就 对应着一组析取表达式规则。 1 9 8 6 年q u i n l 锄提出了著名的d 3 决策树算法。在d 3 算法的基础上，1 9 9 3 8 江苏大学硕士学位论文 年q u i n l a i l 又提出了c 4 5 算法。为了适应处理大规模数据集的需要，后来又提 出了许多改进算法，其中s u q ( s u p e i s e dk a 血gi i lq u e s t ) 和s p r 烈t ( s c a l a b l e p a r a l l e l 也a b l em d u c t i o no fd e c i s i o n1 1 r e e s ) 是比较有代表性的两个算法。 1 、d 3 算法 i d 3 算法的核心是：在决策树各级结点上选择属性时，用信息增益 ( i i 怕n n a t i o ng 作为属性的选择标准，在每一个非叶子结点进行测试时，获得 关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增 益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子 集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据 为止，最后得到一棵决策树，该树可以用来对新的样本进行分类。d 3 算法使用 信息增益( h b 衄a t i o ng a i n ) 作为衡量节点分裂质量的指标，信息增益最高的s p l i t 将被作为分裂方案。信息增益的计算方法为：设s 是s 个数据样本的集合，假定 类标号属性具有m 个不同值，定义m 个不同类c i ( i = 1 ，i n ) ，设s i 是类c i 中的 样本数。p i = s 幽是任意样本属于c i 的概率f 7 l 。 设属性a 具有v 个不同值 a 1 ，a 2 ，a v ) ，可以用属性a 将s 划分为v 个子 集 s 1 ，s 2 ，s v ，其中s j 中的样本在属性a 上具有相同的值a j ( j = 1 ，2 ，v ) 。 设踟是子集s j 中类c i 的样本数。属性a 的信息增益是： g a i l l ( a ) = i ( s l ，s 2 ，s m ) - e ( a ) e ( a ) = is l ，+ & ，+ + 品ji i s i 宰i ( s l j ，s 2 j ，s m j ) ，总墒e ( a ) 是各个子集信息量 的加权平均。 d 3 算法的优点：算法的理论清晰，方法简单，学习能力较强。d 3 算法也 暴露出一些问题：( 1 ) 只对比较小的数据集有效，信息增益的计算依赖于特征数 目较多的特征，而属性取值最多的属性并不一定最优，且对噪声比较敏感，当训 练数据集较大时，决策树效率会随之降低。( 2 ) 工d 3 是非递增算法。( 3 ) i d 3 是单 变量决策树( 在分枝节点上只考虑单个属性) ，许多复杂概念的表达困难，属性相 互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径 上被检验多次。( 4 ) 抗噪性差，训练例子中正例和反例的比例较难控制。 2 、c 4 5 算法 9 江苏大学硕士学位论文 c 4 5 算法继承了d 3 算法的优点，并在以下几方面对d 3 算法进行了改进： ( 1 ) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值 多的属性的不足。 ( 2 ) 在树构造过程中进行剪枝。 ( 3 ) 能够完成对连续属性的离散化处理。 ( 4 ) 能够对不完整数据进行处理。 c 4 5 算法与其它分类算法如统计方法、神经网络等比较起来有如下优点： 产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对 数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，c 4 5 只适合 于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。 3 、s u q 算法 s u q 算法对c 4 5 决策树分类算法的实现方法进行了改进，在决策树的构造 过程中采用了“预排序”和“广度优先策略 两种技术。本文在第三章将会详细 介绍。 4 、s p 脚算法 为了减少驻留于内存的数据量，s p r 矾t 算法进一步改进了决策树算法的数 据结构，去掉了在s u q 中需要驻留于内存的类别列表，将它的类别列合并到每 个属性列表中。这样，在遍历每个属性列表寻找当i j 结点的最优分裂标准时，不 必参照其他信息，将对结点的分裂表现在对属性列表的分裂，即将每个属性列表 分成两个，分别存放属于各个结点的记录。 s p 脚算法的优点是在寻找每个结点的最优分裂标准时变得更简单，其缺 点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进 行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈 希表，其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集 的大小成正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分 批执行，这使得s p 肿算法的可伸缩性仍然不是很好【刚。 1 0 江苏大学硕士学位论文 2 2 2 贝叶斯分类 贝叶斯分类是统计学分类方法，它是一类利用概率统计知识进行分类的算 法。在许多场合，朴素贝叶斯( n a j c i 、，eb a y e s ，n b ) 分类算法可以与决策树和神经 网络分类算法相媲美，该算法能运用到大型数据库中，且方法简单、分类准确率 高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的 值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为 此，就出现了许多降低独立性假设的贝叶斯分类算法，如仉悄( t r e ea u 舯e n t e d b a y e sn e t 、7 l ，o r l 【) 算法。 贝叶斯分类方法是一种具有最小错误率的概率分类方法，可以用数学公式的 精确方法表示出来，并且可以用很多种概率理论来解决。贝叶斯分类器是一个简 单、有效而且在实际使用中很成功的分类器，其性能可以与神经网络、决策树分 类器相比，在某些场合还优于其它的分类器【9 1 。 样本空间s 由特征空间i 和类别空间c 组成：s = 书，s ：，s 。 = ； 每个实例是m 个属性的笛卡尔积：i = ，特征属性a 取离散值 址 ，类别属性取1 个离散值c = c 1 ，c 2 ，c l 。分类问题的实质是找出实例 空间到类别空间的映射f ，使得对任意实例x = ( a 1 ，a 2 ，a 1 ) 属于i ，存在唯一 的c ，c 与之对应，我们把具有最大后验概率的类别作为x 的像，即 尸( c ；c 。x ) 尸( c = c ，x ) ( j 一1 ，2 ，班根据贝叶斯定理，有 p ( c = 坠号掣 ( 1 ) 在全概率公式和各特征属性相对于类别独立的假定下，式( 1 ) 变为 ，、p ( c c t ) i = i p c 4 ，电c c t ) p ( c = c f x ) = 号- 一 p ( c g ) 兀p “，- 口，c ；c ；)一 、 工 、j ， ， 分类有规则分类和非规则分类，贝叶斯分类是非规则分类，它通过训练集训 练而归纳出分类器，并利用分类器对没有分类的数据进行分类。 贝叶斯分类具有如下特点： 江苏大学硕士学位论文 ( 1 ) 贝叶斯分类并不把一个对象绝对地指派给某一类，而是通过计算得出属 于某一类的概率，具有最大概率的类便是该对象所属的类。 ( 萄一般情况下在贝叶斯分类中所有的属性都潜在地起作用，即并不是一个 或几个属性决定分类，而是所有的属性都参与分类。 ( 3 ) 贝叶斯分类对象的属性可以是离散的、连续的，也可以是混合的。贝叶 斯定理给出了最小化误差的最优解决方法，可用于分类和预测。理论上，它看起 来很完美，但在实际中并不能直接利用，它需要知道证据的确切分布概率，而实 际上我们并不能确切的给出证据的分布概率。因此我们在很多分类方法中都会做 出某种假设以逼近贝叶斯定理的要求【1 0 】。 2 2 3 神经元网络 人工神经网络是一门活跃的边缘性交叉学科，它以工程技术手段模拟人脑神 经网络的结构和功能，其特色在于信息的分布式存储和并行协同处理，是巨量信 息并行处理和大规模平行计算的基础，既是高度非线性动力系统，又是自适应组 织系统。人工神经网络可用来描述认识，决策及控制的智能行为，广泛用于分类、 聚类、特征采掘、控制系统、动态系统建模和模式识别等领域。 在人工神经网络中，人工神经元又被称为处理单元( p e ：p r o c e s s i n ge l e m e n t ) 或节点( n o d e ) ，它是神经网络的基本处理单元【1 11 2 1 。一般地来说，一个神经元 结构应具备以下几个要素： ( 1 ) 输入矢量x ( 勋，砣，而) 和输出标量y ； ( 2 ) 权重矢量w ( 聊，耽，) 和阈值标量护； ( 3 ) 神经元功能，包括求和函数和传递函数f 。f 一般根据需要选取各种函 数形式。人工神经元是一个多输入、单输出的非线性单元，我们用，f 表示神经 元从各个连接获取的输入量，其输入输出关系可描述为： 弘矿幺 y 。= 厂o ，) j 上式中，x j ( j = 1 ，2 ，3 ，n ) 是从其它细胞传来的输入信号。oi 为阈值， w j i 表示从细胞j 到细胞i 的连接权值。将i i 统一表达成： 1 2 江苏大学硕士学位论文 上式中，= 一b ，而一1 。 小荟w 传递函数f g ) 可为线性函数，或s 状的非线性函数，或具有任意阶导数的非 线性函数。常见的传递函数有如下形式： ( 1 ) 阶跃函数 例如，当y i 取0 或者1 时，f ( x ) 取： 删= 仁： ( 2 ) s i g m o i d 型函数 厂g ) 2 南。 ( 3 ) 高斯型函数 例如，在径向基神经网络中，神经元的结构用高斯函数描述为： 胪唧( _ 击莩g ，1 ) 2 ) o 式中，盯；为标准化参数。 神经网络是一个大规模的复杂系统( 一般包含大量的人工神经元) ，它提供 大量可供调节的变量。人工神经网络的主要特征有： ( 1 ) 它实现了并行处理机制( 网络内各神经元或层内各神经元之间都并行工 作和调整) ，从而可提供高速处理的能力。 ( 2 ) 它的信息是分布式存储的( 存储于各人工神经元的权值内) ，从而提供 了联想和全息记忆的能力。 ( 3 ) 由于它的连接强度可变，使得网络拓扑结构具有非常大的可塑性，从而 具有很高的自适应能力。 ( 4 ) 通常神经网络总包含巨量的处理单元和超巨量的连接关系，形成了高度 冗余，因而具有高度的容错能力和鲁棒性。 ( 5 ) 人工神经网络的重要特征是它的集体计算，并且具有很强的计算能力。 ( 6 ) 人工神经网络的处理单元( 人工神经元) 通常都比较简单，这就为大规 江苏大学硕士学位论文 模集成提供了方便。 ( 7 ) 人工神经网络原则上是一种非编程方式，它是按照示例学习的方式通过 集体计算来解决问题的。 ( 8 ) 人工神经网络既可用数学方式来实现也可用模拟方式实现，而且通常是 数模共存的，这更接近人脑神经网络的工作方式。 2 2 4 遗传算法 遗传算法( g e n e t i c g o r i t l l i n ) 是一类借鉴生物界的进化规律( 适者生存，优 胜劣汰遗传机制) 演化而来的随机化搜索方法。它是由美国的j h o l l a i l d 教授1 9 7 5 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性 的限定1 1 3 】；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方 法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的 规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号 处理、自适应控制和人工生命等领域，它是现代有关智能计算中的关键技术之一。 1 、遗传算法的基本步骤 初始群体的生成：随机产生n 个初始串结构数据，每个串结构数据称为一 个个体，n 个个体构成了一个群体。遗传算法以这n 个串结构数据作为初始点 开始迭代。 适应性值评估检测：适应性函数表明个体或解的优劣性，不同的问题，适应 性函数的定义方式也不同。 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为 父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则 是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的 适者生存原则。 交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新