（计算机应用技术专业论文）基于粗糙集的多变量决策树的应用研究.pdf

基于粗糙集的多变量决策树的应用研究 摘要 分类在数椐挖掘中是一项非常重要的任务，本文研究的是基于决策树的分 类技术。与其他分类技术相比，决策树技术具有许多优点：决策树更易被用户 理解：生成决策树的效率更高、更适合大训练集；决策树的生成算法不需要除 训练集之外的额外信息；它可以提供更好的精确度。当然决策树技术也有缺点： 一方面，它无法删除带噪声的不相关的属性；另一方面，大多数决策树被限制 在每个节点上只检验单个属性。 为了克服这些困难，本文引入了粗糙集技术。粗糙集理论是一种处理模糊 和不精确知识的数学工具，它具有很强的知识获取能力。粗糙集理论将分类和 知识联系在一起，认为知识即是将对象进行分类的能力。尽管粗糙集理论对知 识的不完全的处理是有效的，但是它的容错能力和推广能力相对较弱，这意味 着需要其他方法补充。 面对决策树技术和粗糙集各自的优缺点，在研究过程中作者将这两者结合 起来取长补短。对于仅有离散值属性的情况下，利用粗糙集理论中条件属性相 对于决策属性的核以及条件属性的区分能力，同时考虑到待建决策树的规模问 题，我们提出了一种新的条件属性的约简算法。以约简后的多个属性构造检验， 解决了决策树中属性的选择问题。改进后的算法可以构造出多变量决策树，与 i d 3 算法相比，两者拥有相同的分类准确率，但前者具有更高的效率，并且大 大减小了决策树的规模。 最后本文在这个新型的算法框架基础上设计了一个k d d 原型系统，并实现 了其中的基于粗糙集技术的数据预处理部分和基于改进后的决策树算法的分类 器部分和预测器部分。应用该系统对心血管住院患者的病案首日f 首页) 数据进行 研究分类，以实现对患者病情的危重度做出较为客观准确的分级，从而对医疗 服务质量和医疗资源的分配情况进行更为有效的考察和改进。 关键词：数据挖掘，粗糙集，决策树， i d 3 r e s e a r c ho ft h em u l t i v a r i a b l ed e c i s i o n1 1 r e e sb a s e do nr o u g h s e la n di t sa p p l i c a t i o n a b s t f a c t c l a s s i 矗c a t o ni sa ni m p o n a n tp r o b l e mi nd a t a m i 面n g c m eo f 协ei m p o n a m c l a s s i f i c a t i o nt e c h n i q u e si sd e c j s i o nt r e e s w h yd e c i s i o nt r e e s ? f i r s t l y ，ad e c i s i o n t r e ei se a s i i yc o m p r e h e n d e db yh u r n a n s ，a n dd e c i s i o nt r e e sj se f 五c i e n ta n di st h u s s u i t a b j ef o r 】a 唱e 删碰n gs e s ：s e c o n d 】y ，d e c i s j 如廿e eg 朋e r a n o na l g 蜊t h j n sd 0n o t r e q u i r ea d d i t i o n a li n f 0 n a t i o nb e s i d e s 也a ta l r c a d yc o n t a i n e dl nt h et r a m i n 叠d a 诅； f i n a l l y ， d e c i s i o nt r e e sd i s p l a yg o o da c c u r a c ya sc o m p a r e dt oo t h e rt e d m i q u e s b u t d e c i s i o n 扛_ e e sa l s oh a v es o f n e ! 打n j a i o n ，0 哩1f h eo n eh a n d 矗c a nn o td e l e ei n l e v a n l 删b u t e s ；o n em eo 山e rh a n d ，l i l o s td e c i s i o n 仃e sc a nt e s to n l yo n e 砌b u t eo ne a c h n o d e i no r d e rt oo v 唧et h e s ei i m j t a t i o 礁，w ei n t r o 出j c er o u 疏s c t ( r s ) t e c h n j q u e s r o u 出s e ti san e wm 砒e m a t i c a lt o o it od e a lw i t hf u z z va n du n c e 蹦n 王【i l o w l e d g e i th a ss t r o n gk n o w i e d g eo b t a i n i t l ga b i i i t yt h em a i np o 曲 o fr o u 咖 s e ti st h a t “c a ni n t e g r a t ek 1 1 0 w i e d g ew i mc l a s s i _ ( i c a t i o n ，a n dt h a tk n o w i e d g ei sm e a b i l i t yo fc l a s s 蛳n gm eo b j e c t s a l t l l o u g hi ti se 脯c t i v ei nd e a i i n gw i t l l 也e i i r i p c t f b c tk n o w l e d g e ，i ti sw e a ki n “e 瑚c ea n d 窟e n e r a 】i t y 1 h 缸；st os a y j tn e c d st o i n t e 伊a t e 、 ，i 血o t h e rt e c h n o i o g y c o n s i d e r i n gt h ea d v a n t a g ea n dd i 鞠d 咖t a g eo ft h ed e c i s i o nt r e e sa n dr s ，w e c o m b i n e dt h ed e c i s i o 玎t 嫩sa n dr sd u r i n gt l l e 豫s e a r c h ，s oi tcano v e r c o m eo n e s w e 出m e s s e sb ya c q u i r 证go 也e r ss t r o n gp o m t s f o ro n i yh a v i n gd i r e t ea t i r i b u t e s ， w ep r o p o s e dan e wc o f i d i t i o na 佃b t i t e sd ed 1 _ i c t i o na l e o r i t m ，w h i c ht a k e si n t o a c c o u n t 啦ec o r co fc o n d i 乏i o na l 土r i b u t e sw j t hr e s p e c t od i s j o na t 埘b u t e si nr o u 曲 s e t st i l e o n 7a n dt i l ec l a s s i f i c a t i o na b i l i t 、，o fc o n d i t i o na 蛐u c e sa n d 血es c a l eo fm e d e c i s i o n sn e st 0b eb u i l t w bp r o v et l l a tm ea c c u r a c yo fd e c i s i o nt r e e s ，c o n s t n l c t e d b y 主h e 主n t p r o v 以a l 笋r i t h r n ，主se q u a l 幻t h a 毫o fi d 3a l 鲥出m ，a n dt h a tt h er 犯w a l g 耐t h mi sm o r ee f i c i e n tt l l 皿i d 3a l g o r i m m a ti 硒t ，a c c o r d i n gt ot i i en e wa i g o 矗m mf 蛳e w o f kw ed e s i 窑剐 dak d d s y s t e m 州c hc o m p l e t e dp r e - p r o c e s s i n gp m 瞬瑚b a s e do nr s ，a n dc o m p i e t e dt l l e d a s s i f i c a t i o nb a d0 ni m p r o v e dd e c i s i o nt r e e sa l g o r i m m a n dp r c d i c t i o nm o d e lo f 伍ea l g d 由硫，w es u c c e s s f i 】l l ya p 佛i e d1 】1 ek d ds y s t 啪i nc l a s s i 母i n 2 也ed a t ao f d 砸v e df 如mt b ef i r s t 出l y ( f 吣mp a g e ) m e d i c a lr c 洲o fm p a t i e n t sw i t l l c a r d i o v a s c u l a rd i s e a s e s 艘y w o r d s ：口i a t am i n i l l g ，r o u g bs e t ，出c i o n 慨s ，j d 3 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥l ：业大学 硕士学位论文质量要求。 主席： 委员： 导师 答辩委员会签名 p 钞仞羽叩影劾1 坂 嬲 吆习弼 d 嘭硝 刁印以 乙心 今托槲 火 贼 & 孔 插图目录 图1 1 知识发现过程示意图2 图1 2k 叻的处理过程模型5 图2 1 购买p c 者的分类决策树 图2 2 心舡管住院患者住院天数决策树。 1 3 2 l 图4 1 单变量决策树3 4 图4 2 分辨矩阵中的非空项3 5 图4 3 属性约简过程3 5 图4 4 分类过程3 5 图4 5 分类得到的多变量决策树3 6 图5 1k d d 系统组成图 图5 2k 叻原型系统主界面 图5 3 数据离散化后的数据表 图5 4 数据一致性检验结果 图55 求得条件属性相对于决策属性的核和一个约简了的属性集 图5 6 经预处理后的数据表 图5 7 多变量决策树 图5 8 对测试数据集分类预测的结果 图5 9 对照测试数据集的原始记录 图5 1 0 计算误分率 强势甜甜 舵 铊们们舭甜 插表目录 表2 1 心血管住院患者信息表2 0 表2 2 决策树中各分类属性的期望信息和信息增益值表2 1 表31 某决策表 表3 2 消去属性c 后的决策表， 表4 1 气象数据模型一 表4 2 数值化气象数据 2 7 ，：8 ，：i ：i 3 z l 表5 1 医学数据( 训练数据集) 4 0 独创性声明 本人声明所旱交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 金蟹工业盍堂 或其他教育机构的学位或证书而使 用过的材料。与我一同r ：作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名= 噫彩砀 签字吼乃年，肭日 学位论文版权使用授权书 本学位论文作者完全了解盒蟹王些盔堂有关保留、使用学位论文的规定- 有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 魍工些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名= 嘞荔勃1 签字日期：f f 年6 月f 。日 导师签名 签字日期：酶月矽日 学位论文作者毕业后去向： 工作单位：安医大卫管学院卫生信息技术与管理系电话：3 3 8 7 3 4 5 通讯地址：合肥梅山路安徽医科大学卫管学院 邮编：2 3 0 0 3 2 致谢 衷心感谢我的导师王浩教授在整个论文阶段给予的悉心指导和帮助。王老 师不仅学识渊博，治学严谨，而且思想开明，实事求是。在王老师的关怀和教 导下，我不仅学到了知识，更重要的是学到了思想，领悟到了许多为学的道理， 促进了我学业上的进步，促成了本论文的完成。 非常感谢胡学钢教授。在本论文选题阶段，我多次参加了王老师和胡老师 共同组织的研究生交流学习讲座，使我深受启发，并由此最终确定了选题方向。 同时，我也深深地感谢计算机学院人工智能与知识挖掘研究室的杨静老师， 在论文撰写过程中杨老师给予我无私的帮助和许多有益的建议，使我受益匪浅! 最后，感谢所有对论文提出宝贵意见的老师和同学，感谢在百忙之中评阅 论文和参加论文答辩的各位专家。 作者：贾亚莉 2 0 0 5 年5 月2 6 日 第一章k d d 综述 1 1 数据挖掘的产生 9 0 年代人类积累的数据量以高于每年5 3 倍的速度增加，数据的丰富带来了 对强有力的数据分析工具的需求。快速增长的数据收集存放在大量的大型数据 库中，从这些海量的、以不同形式存储的数据资料中发现有价值的信息或知识， 为决策服务，便成为一个有着巨大研究价值和现实意义的课题。但是，由于缺 乏强有力的分析工具，理解它们己经远远超出了人的能力，导致了被j o h n n a i s b e r t 称之为“信息丰富而知识贫乏”的窘境的出现，正是在这种传统的学 习方法无法从海量的数据中发现有价值的信息的背景下，数据挖掘( d a t a m i n i n g ，d m ) 技术应运而生，并引起了人们广泛关注。 作为分析处理数据的技术，数据挖掘技术与联机分析( o l a p ) 技术有本质的 区别。o l a p 分析过程在本质上是一个演绎推理的过程，而数据挖掘在本质上 是一个归纳的过程。o l a p 分析师通过建立一系列的假设，然后用o l a p 检 索数据库来证实或推翻这些假设来最终得到自己的结论。与o l a p 不同，数据 挖掘不是用于验证某个假定的模式( 模型) 的正确性，而是在数据库中自己寻找模 型。数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识，数据挖掘所 得到的信息应具有先前未知、有效和可实用三个特征。先前未知是指该信息是 预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识， 甚至是违背直觉的信息或知识，挖掘得到的信息越是出乎意料，就可能越有价 值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布 和啤酒之问有着惊人的联系。信息的有效性要求挖掘前要对被挖掘的数据进行 仔细检查，保证它们的有效性，才能保证挖掘所得信息的有效性。最为重要的 是要求所得的信息有可实用性，即这些信息或知识对于所讨论的业务或研究领 域是有效的，是有实用价值和可实现的。常识性的结论，早已被人们或竞争对 手掌握的或无法实现的事实都是没有意义的。 专家系统也是一种传统的协助专业人员分析处理数据的技术，多年的发展 已经产生了许多应用于特定领域的专家系统。数据挖掘与专家系统的区别在于 事实第一还是经验第一。专家系统实质上是一个问题求解系统，目前的主要理 论工具是基于谓词演算的机器定理证明技术二阶演绎系统。考虑当前的专 家系统技术，通常专家系统依赖用户或领域专家人工的将知识输入知识库，系 统的准确性依赖于这些输入的经验知识。不幸的是这一过程常常有偏差和错误， 并且耗时费用高。应用数据挖掘工具自动的进行数据分析可以发现未知的重要 的数据模式，避免了对经验的依赖，而且与专家系统相比，耗时费用也人大的 减少了。 目前，数据挖掘技术已经广泛用于很多领域。数据挖掘技术在商、i k 方面应用 较早，因为它可增强企业的竞争优势，缩短销售周期，降低生产成本，有利于 制订市场计划和销售策略，数据挖掘技术已经成为电子商务的关键技术之一。 由于数据挖掘在开发信息资源方面的优越性，已逐步推广到保险、医疗、制造 业和电信等各个行业：医疗数据挖掘可以用于病例、病人行为特征分析，以及 用于药方管理等，以安排治疗方案、判断药方的有效性等：司法数据挖掘可以 用于案件调查、案例分析、犯罪控制等，还可以用于犯罪行为特征分析；工业 部门数据挖掘技术可以用于进行故障诊断、生产过程优化等；在通讯网的运行 中，可以使用数据挖掘技术对己有的警告信息进行分析，得到警告之间的关联 规则，这些有价值的信息可用于网络故障的定位检测和严重故障的预测等任务 中。 1 2 数据挖掘和k d d 一般认为数据挖掘是数据库知识发现( k n o w l e d g ed i s c o v e r yi d a t a b a s e s ， k d d ) 过程的核心部分，即将k d d 中进行知识发现的阶段称为数据挖掘( 如 图1 1 所示) ，数据挖掘是k d d 最关键的步骤，也是技术难点所在。所以某些 应用领域对数据挖掘与l 回d 不加区分地使用，某种意义上二者可看作同一个概 念。 图ll 知识发现过程不意图 k d d 一词最早是在1 9 8 9 年8 月于美国底特律市召开的第1 1 届国际人工智 能联合会议上提出的，这届学术会议举行了以k d d 为主题的学术讨论，在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年相继举行了k d d 专题讨论会。随着对l ( d d 的深入研究 以及k d d 在许多领域的广泛成功的应用，于1 9 9 5 年，在加拿大召开了第一届 知识发现和数据挖掘国际学术会议，此后每年召开一次。第一本关于k d d 的国 际学术杂志d a t am i i n g 舳dk n o w l e d g ed i s c o v e r y 也于1 9 9 7 年3 月创刊发 行。亚太地区于1 9 9 7 年在新加坡召开了首次k d d 国际学术研讨会。与国外相 比，国内的k d d 研究起步较晚。1 9 9 4 年4 月在北京召开的第三届亚太地区k d d 国际会议( p a l ( d d 9 9 ) 极大地促进了国内的助d 研究。 目前，在i j c a j 、a a a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据 库技术研究最高水平的国际学术会议上，对l ( d d 的研究都占有较大的比例， l d 已经成为当今计算机科学与技术研究、应用的热点领域之。在数据挖掘 方面还有更多的国际会议，如p a k d d 、p k d d 、s i a m d a t am i n i n g 、 ( 1 e e e ) l c d m 、d a w a k 、s p i e d m 等等。 在国外有许多研究机构、公司和院校从事数据挖掘工具的研究与开发。这 些工具主要采用决策树、神经网络、聚类、遗传算法、贝叶斯信任网络、统计 分析等方法。许多数据挖掘系统已经成功应用于零售业、银行业、市场营销、 电信业、保险业、医疗部门等领域。世界上比较有影响的典型数据挖掘系统有： s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e i h g e tm i e r 、s g i 公司的 s e t m i n e r 、s p s s 公司的c i e m 蛆t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、 r u l e q u e s tr e s e a r c h 公司的s 5 等。 随着l d 在国际上的兴起，我国也积极地开展了相应的研究和应用。1 9 9 3 年国家自然科学基金首次支持该领域的研究项目，目前国内许多学术会议，如 数据库学术会议、机器学习会议等，也都将l d 列为重要的研究方向。国内的 许多科研单位和高等院校竞相开展数据挖掘与知识发现的研究。研究所涉及的 领域一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论 方面的研究，如北京系统工程研究所对模糊方法在知识发现中的应用进行了较 深入的研究：北京大学开展了对数据立方体代数的研究；华中理工大学、复旦 大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了 对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学 等单位探讨、研究了非结构化数据的知识发现以及w 曲数据挖掘；合肥工业大 学开展了基于粗糙集合理论的概念格模型研究，等等。 1 3 数据库中知识发现 1 3 1 k d d 的定义 众多的学者根据自己的对k d d 的认识和理解，下了很多的定义，而其中比 较公认，比较完整、深刻和全面的一个定义是由f a y y a d ，p i a t e t s k y s h a p i r o 和s m y t h 在k d d 9 6 国际会议的会议论文f r o md a t 8m i n i n gt ok n o w l e d g e d i s c o v e r y 一文中将k d d 定义为： “t h en o n t r i v i a lp i o c e s so fi d e t i f 妒n gv a l i d ，n o v e l ，p o t e n t i a n yu s e f h l ， a n du l t i m a t e i yu n d e r s t a n d a b l ep a n e r n sj nd a t a ” 即k d d 是指从大量数据中获取有效的、新颖的、有潜在作用的和最终可理 解的模式的非平凡过程。还有很多和这一术语相近似的术语，如数据挖掘( d m ) 、 数据分析( d a t aa n a l y s i s ) 、数据融合( d a t af u s i o n ) 以及决策支持( d e c i s i o n s u p p o r t i n g ) 等。 f 面对这个定义作详细的解释： 数据：数据是一系列事实的集合，可以是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库，在数据 二进行数据清理、集成和规约后的数据。 这是k d d 处理的最常用的数据形式。 模式：模式是指用语言束表示的一个表达式，它i 一 用来描述数据集的特性， 根据某种兴趣度度量，并f 数据挖掘模块， 1 进行交互挖掘，以便识别和表示知 识的真正有趣的模式。 过程：过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识表 示及知识评估、过程优化等。 非平凡：是指它已经超越了一般封闭形式的数量计算，包括对结构、模式 和参数的搜索。 有效性：通过k d d 从当前数据所发现的模式必须有一定的正确程度，否则 k d d 就毫无作用。 新颖性：经过k d d 提取出的模式必须是新颖的，至少对系统来说应该如此。 模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通过对 比当前得到的数据和以前的数据或期望得到的数据之间的比较，来判断该模式 的新颖程度：其二是在其内部所包含的知识方面，通过对比，发现的模式与已 有的模式的关系来进行判断。 潜在作用：提取出的模式应该是有意义的，有潜在的应用价值。 可理解：k d d 的一个目标就是将数据库中隐含的模式以容易理解的形式表现 出来，从而帮助人们更好地理解数据库中所包含的信息。 1 3 2 k d d 中数据的特点 由于知识发现系统的基本输入是数据库中的原始数据，因此需要特别关注 数据本身固有的一些性质。 ( 1 ) 数据的规模与冗余性 知识发现所面临的数据库一般是非常庞大的且可能包含冗余的信息。数据 的规模包含两方面的含义，其一是数据对象的多少，其二是描述数据对象的属 性的多少。面向属性的归纳与实值离散化技术等是重要的对象约简方法。属性 约简可以根据属性的重要性来应用某种特征选择技术，比如通过基于粗糙集合 的属性约简方法来实现。冗余信息有时会误导知识的发现过程，如此所发现的 知识可能缺乏足够的兴趣度。 ( 2 ) 数据的动态性 大多数数据库的内容会经常发生变化。在一个在线系统中，必须采用预警 机制来保证这些变化不导致错误的发现。一般地认为从数据库发现知识是一种 动态过程。 ( 3 ) 噪声数据和稀疏数据 错误的数据对于现实世界数据库是在所难免的，这主要源于数据采集的各 个环节。数据库中的信息在实例空间中可能是稀疏的，这l j 能会严重影响发现 的效率。另外，有时候异常数据模式不仅不是噪声数据，反而e 是知识发现所 关注的目标。 ( 4 ) 小完整性 由丁不完整的数据域和数据域上值的缺少所造成的不完整数掘，当然会影 响发现的结果。目前数据库并非是面向知识发现进行设计的，而模式的发现、 评价与解释很可能需要数据库中不存在的信息。 ( 5 1 不确定性 数据的不确定性是指并非全域中的每个概念都可以通过属性值来充分与精 确地表达，知识发现的模式也只可能在一部分数据上有效。模糊集合理论与粗 糙集合理论等使用了不同的方式来解决这一问题。 1 3 3k 凹的处理过程模型 人们进行的关于k d d 的研究是为了将知识发现的研究成果应用于实际数据 处理中，为科学的决策提供支持。正是因为这样，目前所进行的关于k d d 的研 究，大多只着眼于对数据挖掘的研究，而忽视了其他方面研究。事实上，k d d 首先是一个处理过程，如果仅仅着重于数据挖掘，可能就看不到在实际工作中， 数据处理过程中的数据提取、组织和显示方式的难度。数据挖掘所完成的工作 对于整个知识发现的过程来说，只是其中较小的一部分，因此对k d d 中其他阶 段及处理过程的研究也是非常重要的。 目前人们对整个处理过程并没有给出非常清楚的划分，而建立合适的处理 过程模型能将各个处理阶段有机地结合在一起，以便于人们开发及使用k d d 应 用系统。比较有代表性的模型有三种： 第一种是u s a m am f a y y “等人给出的多处理阶段模型。 第二种是g e o r g eh j o h n 给出的多处理阶段模型。 第三种是b r a c h m a n a n a n d 提出的以用户为中心的处理模型。 为了使k d d 能更好地应用于实践，下面以第一种面向多阶段处理过程的k 加 处理过程模型为例进行简要地说明，本文后面有关的讨论也是针对这种模型进 行论述的。 图1 2k d d 的处理过程模型 图12 是u s a m af a y y a d 等人给出的处理模型。该处理模型把k d d 过程分 为九个处理阶段：数据准备、数据选择、数据预处理、数据转换、k d d 目标确 定、挖掘算法确定、数据挖掘、模式解释及知识评价。 ( 1 ) 数据准备：了解k d d 相关领域的有关情况，包括实际应用中的预备知 识和f 1 标，熟悉有火的背景知识，并弄清楚_ i j ，、的要求。 ( 2 ) 数据选择：根据用户要求从数据库中提取与k d d 要求相关的数据，k d d 主要从这些数据中进行知识提取。在此过程中，会使用一些数据库操作对数据 进行处理，建立一个目标数据集。 ( 3 ) 数据预处理：主要是对阶段( 2 ) 产生的数据进行再加工，检查数据的完 整性和致性，利用统计方法对丢失的数据进行填补，去除噪音数据和空白数 据域，考虑时间顺序和数据变化等。 “) 数据转换：对经过预处理的数据，根据知识发现的任务对数据进行再 处理，主要通过投影或数据库中的其他操作减少数据量。 ( 5 ) 确定k d d 目标：根据用户要求，确定k d d 发现的知识类型，因为对 k d d 的不同要求，会在具体的知识发现过程中采用不同的知识发现算法。 ( 6 ) 确定知识发现算法：根据阶段5 所确定的任务，选择合适的数据挖掘 算法，包括选取合适的模型和参数，并使得挖掘算法与整个k d d 的评判标准相 一致。 ( 7 ) 数据挖掘：运用选定的挖掘算法，搜索或产生一个特定的感兴趣的模 式或数据集，从数据中提取出用户所需要的知识，这些知识可以用某种特定的 方式表示或使用一些常用的表示方式，如产生式规则等。 ( 8 ) 模式解释：对发现的模式进行解释，去掉多余的不切题意的模式，转 换成某个有用的模式，以使用户理解。在此过程中，为了取得更为有效的知识， 可能会返回前面处理中的某些步骤，以便反复提取，从而提取出更有效的知识。 ( 9 ) 知识评价：将发现的知识以用户可理解的方式呈现给用户或合并到系 统中。也包含对知识的一致性检查，以确信本次发现的知识不与以前发现的知 识相抵触。 在上述的每个处理阶段，k 肋系统提供处理工具完成相应的工作。在对挖掘 的知识进行评测后，根据结果可以决定是否重新进行某些处理过程，在处理的 任意阶段都可以返回到前面的某个阶段进行再处理。 1 4 数据挖掘 1 4 1 数据挖掘的定义 数据挖掘( d a t em i n i n g ) 是从大型数据库或数据仓摩中提取人们感兴趣 的知识，这些知识是隐含的、事先未知的、潜在的、有用的信息【2 ，3 j ，其广泛观 点的定义是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣 的知识过程。许多人把数据挖掘视为另一个常用的术语数据库中的知识发现或 k d d 的同义词。而另一些人只是把数据挖掘视为数据库中的知识发现过程的一 个基本步骤。在这里，我们认为数据挖掘足k d d 的一个阶段。 1 4 2 数据挖掘的对象 根据信息存储格式，用于挖掘的对象有：关系数据库、面向对象数据库、 空问数据库、时序数掘库、义本数据源、多媒体数据、异质数掘库、遗产数据 库，以及w e b 数据源。 1 4 3 数据挖掘发现的模式 数据挖掘任务一般可以分为两类：描述型与预测型。描述型挖掘任务刻画 数据库中数据的一般特性，预测型挖掘任务在当前数据上进行推断，以进行预 测。但是很多情况下，用户并不知道什么类型的模式才是有趣的，因此数据挖 掘系统要能够挖掘出多种类型的模式以适应不同的用户需求或不同的应用。常 用的模式介绍如下： 概念描述( c o n c e p td e s c r i p t i o n ) 描述性数据挖掘的最简单类型就是概念描述。概念通常是指数据的汇集。 概念描述是指机器自动由现有数据获得需要描述的概念定义。即根据数据的微 观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识， 反映同类事物共同性质，是对数据的概括、精炼和抽象。例如，对某一个病症， 给出一些确诊病人的例子，计算机自动归纳该病症患者的特征，然后得到一个 关于患此类新病症的病人的一个通用的描述。 关联分析( a s s o c i a t i o nr u l e s ) 关联规则分析反映一个事件和其他事件之间依赖或关联的知识。挖掘关联 规则就是要在大量数据中发现项集之间有趣的联系。关联规则是形如，x ；y ， 即“x 1 x 2 x 3 a a x 。 y 1 a y 2 a y 3 a y 。j ”这样一类规尉。其中， x ( i 1 ，m ”，y jo l ，m ) ) ，是属性一值对。关联规则x j y 解释为“满足条 件x 的数据库元组也可能同时满足条件y ”。关联分析就是要求机器自动的在数 据库中找出用户感兴趣( 通过置信度和可信性描述) 的关联规则。关联规则有很强 的表达能力及广泛的应用，有单维和多维规则之分。关联规则广泛用于购物篮或 事务的数据分析，在医疗卫生行业中，关联规则也是很常见的一种知识类型。 例如，分析确诊病人的病例特征数据库时，我们可以发现这样一些规则，有1 0 的居住地为a 且具有日常行为习惯b 的患者，它们中有8 0 的人是患有病c ， 其关联规则表示为a 八b 斗c 。这种类型的知识对医学研究人员而言是很难预知 且具有很高的研究价值的。关联规则是目前数据挖掘研究的热点。近年来，有 文献报道将关联规则应用到分类实践中，获得了比较好的效果。 分类模式( c 1 a s s i f i c a t i o n ) 分类反映同类事物共同性质的特征型知识以及不同事物之间的差异型特征 知识。它是这样的过程，找出描述并区分数据类或概念的模型( 或函数) ，以便使 用模型预测类，标记未知的对象类。分类可被用于规则描述和预测。要构造分 类器，需要有一个训练样本数据集作为输入，基于对样本数据的训练生成分类器， 然后把该分类器应用于测试集及将来数据。例如，关于疾病的分类规则可以从 已知病例( i j j | 练集) 提取出来，然后结合新病员的症状，可用于对新病员进行 冷断。 聚类分析( c l u s t e r i n g ) 与分类和预测不同，聚类分析数据对象，而不考虑己知的类标记。使用聚 类分析与分类分析相结合可以学到一些与常识经验关联不那么紧密的知识，避 免了一些常识经验带来的错误。通过聚类分析还可以轻易的得到一些孤立点。 对某些不能明确描述分类标准的事件或对现有分类规则不满意的时候，使用聚 类分析能自动的获得可用于实用的分类规则。如可以使用聚类分析区分、提取 感染某新型病毒致病的患者的特征，并以此对新病例进行分类。 异常检测模式( o u t l i e r ) 即孤立点分析。数据库中可能包含一些数据对象，他们与数据的一般行为 或模式不一致，这些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立 点视为噪音或异常丢弃。然而，在一些应用中，罕见的事件可能比正常出现的 事件更有趣。在医疗实践中，不寻常的病例可能比那些正常的病例更令科研人 员感兴趣。如，现实生活中常有一些常规疗法不起作用的病例，导致这种情况 出现的原因可能是因为某些原因( 病征不明显、有并发症) 使医生误诊，也可能是 出现了一种未知新疾病( 如非典型肺炎) ，缺乏有效的疗法。不管哪一种原因，使 用孤立点分析，找出这些病例再对其进行研究，对提高医学水平是很有帮助的。 演变分析( e v o l u t i o na n a i y s i s ) 数据演变分析也可以认为是以时间为关键属性的关联知识。是根据时间序 列型数据，描述行为随时间变化的对象的规律或趋势，对其建模，并由历史的 和当前的数据去推测未来的数据。可能包含时间相关数据的特征化、区分、关 联、分类和聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模 式匹配和基于相似性的数据分析。在医疗上，经常使用演变分析来预测治疗效 果和治疗周期的长短。如，通过分析以往数据，可以根据患者的实际情况( 如经 济水平、既往病史、具体病情) ，提前预测病人手术后的康复进度，合理安排康 复计划、用药计划。 1 4 4 数据挖掘的方法 数据挖掘的方法通常可以分为两大类，一类是统计型，常用的技术有概率 分析、相关性分析、聚类分析等，另一类是人工智能中的毛e 器学习型，通过训 练和学习大量的样品集得到需要的模式或参数。大致有以下几种，现分别简要 介绍。 ( 1 ) 概念格 概念格是基于二元关系构造的，它描述了对象和特征之问的联系，表明了 概念之脚的泛化和例化关系，是一种完备的概念层次结构，其相应的哈斯图实 现了对数据的可视化，作为知识的一种表示形式，它有助于挖掘概念问的各种 规则。概念是把所感知的事物的共同本质特点抽象出来，并加以概括。概念都 具有内涵和外延，基于概念的这种理解，r w 1 l e 存1 9 8 2 年首先提出根据i 元 关系来构造相应概念格( 或g a l o i s 格) 的思想，也称为形式概念分析，就是 以概念格中的每个节点表示一个形式概念，其中概念的外延代表相应的一组对 象，内涵则为这组对象所具有的公共特征( 属性) ；而概念格所相应的哈斯图则 形象地揭示了概念间的泛化和例化关系，反映出一种概念层次结构( c o n c e p t h i e r a r c h y ) ，实现了对数据的可视化，非常适用于从数据库中进行知识挖掘， 从而成为数据分析和规则提取的一种有效工具，在信息检索、数字图书馆、软 件工程、知识分类、类的设计、网络管理和k d d 等领域，概念格已经显示出一 定的应用价值。 ( 2 ) 粗糙集理论 粗糙集合理论( r o u g hs e t ，也称为r s 理论) 由波兰数学家p a w l a k z 于1 9 8 2 年首先提出。粗糙集理论是一种刻画不完整和不确定性的数学工具，能有效地 分析和处理不精确、不一致、不完整等各种不完备的信息，处理含糊性和不确 定的问题，发现不准确数据或噪音数据内在的结构关系，并从中发现隐含的知 识，揭示潜在的规律。这一方法通常可用于特征的约简和相关分析中，在数据 挖掘中具有重要的作用。相关内容将在第三章具体介绍。 ( 3 ) 决策树 在知识工程领域，决策树是一种简单的知识表示方法，它将事例逐步分成 不同的类别。由于分类规则是比较直观的，因而比较易于理解，在机器学习领 域内，多年来己研究出不少实施决策树的有效算法( 如d 3 及其改进算法等) ，它 们可以在多种多样的商业问题中用于探究和预测，目前己经应用于信用卡损失 预测、国际流通货币兑换率的时序预测问题等。决策树内容将在第二章具体介 绍。 ( 4 ) 遗传算法 遗传算法是按照自然进化原理提出的一种优化策略，即采用一种进化的方 法来指导学习。遗传算法学习模型最初由j o h nh 0 1 1 a n d ( 1 9 8 6 ) 提出。遗传算法 模仿人工选择培育良种的思想，从一个初始规则集合( 知识基因) 开始，逐代地通 过交换对象成员( 杂交、基因突变) ，产生群体( 繁殖) ，评价并择优复制( 适者生存， 不适应者淘汰1 ，逐代积累计算，最终得到优化的知识集。遗传算法广泛应用于 自动控制、机器学习、模式识别和组合优化等领域。 ( 5 ) 神经网络 人工神经元网络具有分布式存储信息、并行地处理信息和进行推理、自组 织学习等特点，可以用于建立基于多种不同问题的正确率很高的预测模型，但 是神经元网络在易用性和应用扩展能力方面有一定的限制。同前神经元网络己 经用于分类、聚类、特征采掘、预测和模式识别。神经网络模仿生物神经删络， 本质上是一个分布式矩阵结构，它通过对训练数据的采掘逐步计算网络连接的 权值。神经网络可分为以下三种：前馈式网络，它以感知机、反向传播模型、 函数型网络为代表，可用于预测、模式识别等方面；反馈式网络，它以h o p f i e i d 的离散模型和连续模型为代表，分别用于联想记忆和优化计算；自组织网络， 它以a r t ，模型、k o h 0 1 0 n 模型为代表，用于聚类。 ( 6 ) 贝叶斯网络 贝叶斯网络基于后验概念的贝叶斯定理，是建立在数据进行统计处理基础 上的方法，将不确定事件通过网络连接起来，可以对其他相关事件的结果进行 预测，其网络变量可以是可见的，也可隐藏在训练样本中。贝叶斯网络具有分 类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效果较好， 缺点是对发生频率很低的事件预测效果不好。贝叶斯网络在医学和制造业等领 域的应用具有较好的效果。 ( 7 ) 统计分析 根据严格的定义，统计和统计技术不是数据挖掘，但是数据挖掘过程中却 使用了很多统计技术和概念，如概率、独立性、偶然性和过适应等。统计方法 可以细分为回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、费歇尔判 别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主元分析 法、相关分析法等) 等闭。以回归分析为例，非线性回归在预定函数的基础上， 寻找目标度量对其它多种变量的依赖关系，这种方法在金融市场和医疗诊断的 应用中有比较好的结果。当要进行预测的仅仅是两个可能的值时f 例如，顾客是 否购买了产品) ，为了得到一个更好的预测模型，可以将预测属性值进行变换， 进行l o g i s t i c 回归分析。 1 4 5 数据挖掘面临的挑战 数据挖掘技术的研究还不成熟，其应用还存在很大的局限性。数据挖掘技 术需要解决的问题，即发展方向主要有： ( 1 ) 数据输入形式的多样性 在不同的应用系统中，有许多不同类型的数据库存在，一个功能强大的数 据挖掘系统应该能够处理不同类型的数据库和数据类型。目前的数据挖掘工具 一般只能提供对结构化数据的处理，对数据中存在缺损或噪声的情况并没有有 效的方法。 f 2 ) 数据挖掘算法的有效性、可测性和可伸缩性 数据挖掘向更大型的数据库、更高的维数、属性之间更复杂的关系等方向 发展。从大型数据库中抽取知识的算法必须高效、可测，即算法的运行时间是 可预测并且是可接受的。目前的研究发展到并行分布式处理或抽样的方法处理 大规模数据以获得较高的计算效率，根据问题的定义和领域知识选择需要的属 性从而降低维数并且有效处理属性之间的复杂关系。 ( 3 ) 不同技术的集成及可扩展性 目前数据挖掘工具或者使用单一的技术，或者是有限的几种技术的集合。 就数据分析而言