（计算机应用技术专业论文）数据挖掘中决策树分类算法的研究(1).pdf

m 砒a s t e 靴r s 赦1 ! l e s i 。 摘要 数据挖掘，也称之为数据库中知识发现是一个可以从海量数据中智能地 和自动地抽取一些有用的、可信的、有效的和可以理解的模式的过程。分类 是数据挖掘的重要内容之一。目前，分类已广泛应用于许多领域，如医疗诊 断、天气预测、信用证实、顾客区分、欺诈甄别。 现已有多种分类的方法，其中决策树分类法在海量数据环境中应用最为 广泛。其原因如下；1 、决策树分类的直观的表示方法较容易转化为标准的数 据库查询。2 、决策树分类归纳的方法行之有效，尤其适合大型数据集。3 、 决策树在分类过程中，除了数据集中已包括的信息外，不再需要额外的信息。 4 、决策树分类模型的精确度较高。 数据库的急剧膨胀使得挖掘算法的可伸缩性变得日益重要，传统的挖掘 算法处理的数据量较少。现代的数据库已大到不能将其数据全部调入内存。 从磁盘读取数据比挖掘算法在内存中处理数据慢得多。因此挖掘算法必须是 可伸缩的，否则挖掘算法的实用性会受到限制。个算法是可伸缩的是指在 一定内存的情况下，算法的运行时间随输入的记录数的增加而线性增加。 各种数据库可使数据挖掘更加有效、方便。但在关系数据库和o l a p 数 据仓库上建立挖掘模型并非易事，开发需要制定挖掘算法，大量的工作需要 丌发者完成。o l ed bf o rd a t am i n i n g ( o l ed bf o rd m ) 是o l ed b 和o l ed bf o r 0 l a p 自然进化的结果。m i c r o s o f t so l ed bf o rd m 规范使数据挖掘工作只通过 一个a p i 完成。其目的是减轻在数据库上开发挖掘应用程序的负担。由于使 用o l ed bf o rd m 没有涉及数据库的内部细节，因此数据挖掘可方便地运行在 多种数据库系统上。j 本文首先研究了评估分类模型的方法。在此基础上着重研究了决策树分 类方法，并对决策树算法的可伸缩性问题进行了具体分析，最后给出了基于 o l ed bf o rd m 开发决策树分类预测应用程序。 关键词数据库中的知识发现；数据挖掘：分类；决策树；决策树算法 的可伸缩性；o l ed b f o f d m 硕士学位论文 a b s t r a c t d a t am i n i n g a l s oc a l e da sk d d ( 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 ) i sa n a d v a n c e dp r o c e s s ，i nw h i c hw ec a np i c ku pm a n yt r u s t f u l ，n o v e l ，u s e f u la n d r e a d a b l ep a t t e r n sf r o mv e r yl a r g ea m o u n t so fd a t a c l a s s i f i c a t i o ni sa ni m p o r t a n t p r o b l e mi nd a t am i n i n g t h et a r g e to f c l a s s i f i c a t i o ni st of i n do u tac l a s s i f i c a t i o n m o d e l g i v e nad a t a b a s eo fr e c o r d s e a c hw i t hac l a s sl a b e l ac l a s s i f i c m i o nm o d e l g e n e r a t e sac o n c i s ea n dm e a n i n g f u ld e s c r i p t i o nf o re a c hc l a s st h a tc a nb eu s e dt o c l a s s i f ys u b s e q u e n t r e c o r d s c l a s s i f i c a t i o nm o d e lc a nb eu s e dt of o r e c a s t c l a s s i f i c a t i o nn o wh a sb e e ns u c c e s s f u l l ya p p l i e dt ow i d er a n g eo fa p p l i c a t i o n a r e a s ，s u c ha sm e d i c a ld i a g n o s i s ，w e a t h e rp r e d i c t i o n ，c r e d i ta p p r o v a l ，c u s t o m e r s e g m e n t a t i o n a n df r a u dd e t e c t i o n b u i l d i n go fam o d e lw i t hg o o dc l a s s i f i c a t i o n a b i l i t y i so fp r i o ri m p o r t a n c ef o rp r a c t i c a lu s e t h i sp a p e r f i r s t l y f o c u s e so n m e t h o d sf o re v a l u a t i o no f t h ea c c u r a c yo f c l a s s i f i c a t i o nm o d e l m a n yd i f f e r e n tt e c h n i q u e sh a v eb e e np r o p o s e df o rc l a s s i f i c a t i o n ，d e c i s i o nt r e e c l a s s i f i e r sh a v ef o u n dt h ew i d e s t a p p l i c a b i l t t v i n l a r g e s c a l e d a t a m i n i n g e n v i r o n m e n t s t h e r ea r es e v e r a lr e a s o n sf o rt h i s f i r s t d e c i s i o nt r e e s0 f f e rav e r y i n t u i t i v er e p r e s e n t a t i o nt h a ti se a s yt oa s s i m i l a t ea n dt r a n s l a t et os t a n d a r dd a t a b a s e q u e r i e s s e c o n d d e c i s i o nt r e ei n d u c t i o ni se f f i c i e n ta n di st h u ss u i t a b l ef o rl a r g e t r a i n i n gs e t s f u r t h e r m o r e ，d e c i s i o n t r e e g e n e r a t i o na l g o r i t h m sd on o tr e q u i r e a d d i t i o n a l i n f o r m a t i o nb e s i d e st h a ta l r e a d yc o n t a i n e di nt h et r a i n i n gd a t a f i n a l l y t h ea c c u r a c yo fd e c i s i o nt r e ec l a s s i f i e r si sc o m p a r a b l eo re v e ns u p e r i o rt ot h a to f o t h e rc l a s s i f i c a t i o nt e c h n i q u e s t h i sp a p e rs e c o n d l vf o c u s e so nd e c i s i o nt r e e c l a s s i f i e r s t h e e x p l o s i v eg r o w t h o fd a t a b a s e sm a k e st h e s c a l a b i l i t y o f d a t a m i n i n g t e c h n i q u e si n c r e a s i n g l yi m p o r t a n t t r a d i t i o n a l l y ，a l g o r i t h m s f o rd a t a a n a l y s i s a s s u m et h a tt h ei n p u td a t ac o n t a i n sr e l a t i v e l yf e wr e c o r d s c u r r e n td a t a b a s e s h o w e v e r ，a r em u c ht o ol a r g et ob eh e l di nm a i nm e m o r y r e t r i e v i n gd a t af r o m d i s ki sm a r k e d l ys l o w e rt h a na c c e s s i n gd a t ai nr a m t h u s t ob ee f f i c i e n t t h e d a t a m i n i n gt e c h n i q u e sa p p l i e dt ov e r yl a r g ed a t a b a s e sm u s tb eh i g h l ys c a l a b l e a na l g o r i t h mi ss a i dt ob es c a l a b l ei fg i v e naf i x e da m o u n to fm a i nm e m o r yi t s r u n t i m ei n c r e a s e s1 i n e a r l yw i t ht h en u m b e ro fr e c o r d si nt h ei n p u td a t a b a s e t h i s p a p e rt h i r d l yf o c u s e do ns c a l i n gd e c i s i o nt r e ea l g o r i t h m st ov e r y1 a r g ed a t as e t s d a t a b a s e sc a n s u p p o r t d a t a m i n i n g i nt e r m so fc o n v e n i e n c ea n de f f i c i e n c y b u i l d i n gm i n i n ga p p l i c a t i o n s o v e rr e l a t i o n a ld a t a b a s e so ro l a pw a r e h o u s ei s n o n t r i v i a l i tn e e d sd i f f e r e n tc u s t o m i z e dd a t am i n i n ga l g o r i t h m sa n dt h e r ei s s i g n i f i c a n tw o r ko nt h ep a r to fa p p l i c a t i o nb u i l d e r s o l ed b f o rd a t am i n i n g r o l ed bf o rd m ) i san a t u r a le v o l u t i o nf r o mo l ed ba n do l ed bf o ro l a p m i c r o s o f t s0 l ed bf o rd m s p e c i f i c a t i o nh a sb e e nd e v e l o p e dt o m a k ed a t a m i n i n gw o r kf o ra p p l i c a t i o nb u i l d e r st b r o l l 曲as i n g l ee s t a b l i s h e da p i t h eg o a l o fi ti st oe a s et h eb u r d e no fd e v e l o p i n gm i n i n ga p p l i c a t i o n si nl a r g er e l a t i o n a l d a t a b a s e s s i n c en oi n t e r n a ld e t a i l so ft h ed a t a b a s ea r ea s s u m e dw i t hu s i n go l e d bf o rd m t h ed a t am i n i n gi m p l e m e n t a t i o n sw i l l b em o r ep o r t a b l ea c r o s s v a r i o u sd b m s t h i sp a p e rl a s t l yf o c u s e s o nh o wt o d e v e l o p d e c i s i o nt r e e a p p l i c a t i o n sw i t ho l e d bf o rd m k e yw o r d s ：k n o w l e d g ed i s c o v e r y i n d e c i s i o nt r e e ，s c a l a b i l i t yo fd e c i s i o nt r e e ， d a t a b a s e ，d a t am i n i n g ，c l a s s i f i c a t i o n ， o l e d b f o r d m i i i 耻m a s t e 鞭r s 敞i i i e s i 。 第一章绪论 1 1 本课题的研究背景及研究意义 近十几年来，计算机广泛应用、人们获取数据的手段日益完善、存放数据 的硬件设备和存储介质大量供应，w w w 的出现。这切导致各行各业的各种 数据愈来愈多。人们淹没在数据海洋中，但却渴望数据中的知识和信息。因此， 人们迫切需要有关方法和技术，能够智能地自动地从海量数据中获取知识和有 用的信息。对数据分析和理解的需要促成了在数据库中发现知识( k n o w l e d g e d i s c o v e r y i nd a t a b a s e ，k d d ) 这一新技术的诞生。k d d 也被称为数据挖掘( d a t a m i n i n g ，d m ) 。 从数据库的发展过程可以看到数据挖掘是数据库技术演化的结果。数据 库技术1 1 1 1 2 1 经历了四个阶段： 1 、1 9 6 0 s - 1 9 7 0 s ： 数据收集和数据创造以及层次数据库系统、网状数据库系统。 2 、1 9 7 0 s 1 9 8 0 s ： 关系数据模型和关系数据库系统的实现。 3 、1 9 8 0 s 1 9 9 0 s ： 关系数据库管理系统，高级数据模型如扩展关系模型、面向对象模型、 演绎对象模型，面向应用的数据库管理系统如空间数据库、时间序列数 据库、科学方面的及工程设计数据库等等。 4 、1 9 9 0 s 现在： 多媒体数据库、数据仓库和o l a p 技术、数据挖掘和知识发现、基于w e b 的数据库技术、w e b 挖掘。 数据库管理系统( d b m s ) 可以高效实现数据录入、检索和维护等管理功 能，但不能发现数据中的关联和规则，也不能根据现有的数据预测未来的发展 趋势。随着各种数据库的广泛应用，对数据分析和理解自然成为数据库研究的 新目标。因此导致k d d 成为数据库研究最活跃、最令人激动的领域之一。 1 9 8 9 年8 月，在美国底特律召开的第”届国际人工智能联合会议的专题 讨论会上，k d d 的概念被首次提出。1 9 9 1 年麻省理工学院的w i l l i a mj f r a w l e y 硕士学位论文 u s4 1 t ! r s1 ji e s i s 等人在他们的论文“k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ：a no v e r v i e w ”中指出： “k d d 是指从数据库中非平凡地抽取一些隐含的、事先未知的、潜在的、有 用信息的过程。”这个定义被广为引用并认为是k d d 的准确定义【3 1 。多数人 认为数据挖掘是k d d 过程中的一个基本步骤，也是k d d 的最重要环节。现在 人们往往不加区分使用k d d 和d m 这两个术语。 图1 1 反映k d d 的处理过程，图中模式是指用高级语言表示的表达一定逻 辑含义的信息，通常指经过挖掘算法处理后，在数据库中找到的数据之间的逻 辑关系。 知识是指一个满足用户送趣廑和量值廑并且能被用户理解的模式。 兴趣度：在一定数据域上为真的知识被用户关注的程度。 置信度：知识在某一数据域上为真的量度。置信度涉及到许多因素，如数 据的完整性、样本数据的大小、领域知识的支持程度等。没有足够的黄信度， 模式不能成为知识。 图1 1k d d 的处理过程 从图1 1 可以看出知识发现的过程由以下四个步骤组成： 1 、数据清理与集成 消除不一致数据，将多种数据源组合在一起 2 、数据选择与变换 从数据库中检索与分析任务相关的数据，将数据变换适合挖掘的形式。 3 、数据挖掘 4 、采用合适的挖掘算法智能地提取模式。 硕士学位论文 m a s t e r st i i e s i s 模式评估与知识表示 根据用户的兴趣度和置信度选择表示知识的模式，用可视化技术向用户 提供知识。 根据数据挖掘任务能够挖掘出的模式类型，可将数据挖掘的功能分为以下几 种1 4 】： 1 、类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 2 、关联分析( a s s o c i a t i o na n a l y s i s ) 3 、分类( c l a s s i f i c a t i o n ) 4 、预测( p r e d i c t i o n l 5 、聚类( c l u s t e r ) 6 、孤立点分析( o u t l i e ra n a l y s i s ) 7 、演变分析( e v o l u t i o na n a l y s i s ) 每种数据挖掘功能可由多种不同的算法实现。分析、研究和设计数据挖掘 算法是研究数据挖掘的一个重要课题。对大型数据库，挖掘算法着重强调有效 性和可伸缩性。算法的可伸缩性是指：在给定内存和磁盘空间等可利用的系统 资源，算法运行的时间应当随数据库大小线性增加。数据挖掘算法的可伸缩性 挖掘算法研究的重要内容之一。 数据挖掘算法的设计涉及多学科技术，包括数据库技术、统计学、机器学 习、高性能计算、模式识别、神经网络、粗糙集理论等。根据挖掘的数据类型 以及涉及的应用领域。数据挖掘技术又可与空间数据分析、信息检索、图象分 析、信号处理、计算机图形学、w w w 、经济、商业、生物信息学以及一t l , 理学 领域技术相关。目前数据挖掘技术已成功的运用于这些应用领域，它既具有多 层次的研究价值又具有很高的应用价值。 1 2l ( d d 的发展历史及国内外研究动态 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 专题讨论会，汇集来 自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、 知识表示、知识运用等问题。随着参与人员的不断增多，数据挖掘界于1 9 9 5 年 硕士学位论文 m a s lf r s t l i e s i s 召开了首届知识发现与数据挖掘国际学术会议k d d 9 5 。会议正式发展成为国 际年会，并于1 9 9 8 年建立了一个新的国际学术组织a c m s i g k d d ，即美国计 算机协会( a c m ) 下的数据库中知识发现专业组( a c ms p e c i a li n t e r e s tg r o u p o n k n o w l e d g ed i s c o v e r ya n dd a t a ) 。自1 9 9 9 年，由a c m s i g k d d 每年组织召 开知识发现与数据挖掘国际学术会议。k d d 的研究重点也逐渐从发现方法转向 系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 1 9 9 7 年第3 届k d d 国际学术大会上开始进行了实实在在的数据挖掘应用k d d c u p 竞赛评奖活动。以后每年a c m - s i g k d d 都组织进行针对定主题的数据 挖掘工具竞赛评奖活动。以下是每年的竞赛主题： k d d c u p 2 0 0 2 f o c u s ：b i o i n f o r m a a c sa n dt e x tm i n i n g k d d c u p2 0 0 1 ，f o c u s ；b i o i n f o r m a l i c sa n dd r u gd i s c o v e r y k d d c u p2 0 0 0 f o c u s ；w e bm i n i n gt a s k s k d d c u p 19 9 9 ，f o c u s ：i n 订u s i o nd e t e c t j o na n dr e p o r t k d d c u p1 9 9 8 ，f o c u s ：d i r e c tm a r k e t i n g ，i i s lw i t hb e s td o n a t i o nv a l u e ；b e s ir e p o r f k d dc u p1 9 9 7 , f o c u s ：p r e d i c t i n gm o s tl i k e l yd o n o r sf o rac h a d l y 其它重要的数据挖掘国际学术会显示议有：p k d d ，s a m d a t am i n i n g ， ( i e e e ) i c d m ，d a w a k ，s p l e d m 等。众多的数据挖掘国际学术会议显示i t 界对数据挖掘研究非常重视。亚太地区也每年召开数据挖掘国际学术会议 p a k d d 。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论 文，空前热烈。 a c m s i g k d d 的数据挖掘专题杂志d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y 于1 9 9 7 正式出版。此外，数据库、人工智能、信息处理、知识工程、统计学等 领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。i e e e 的会刊k n o w l e d g e a n dd a t a e n g i n e e r i n g 领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代 表当时k d d 研究的最新成果和动态。 与国外相比，国内对k d d 的研究稍晚。1 9 9 3 年国家自然科学基金首次支 持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识 发现的基础理论及其应用研究，这些单位包括清华大学、复旦大学、中科院计 4 硕士学位论文 m a s l e r si j l l 2 s i s 算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工程 研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学开展对 数据立方体代数的研究，华中科技大学、复旦大学、浙江大学、中国科技大学、 中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和改造： 南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的 知识发现以及w e b 数据挖掘。 近十年来，数据挖掘研究不仅取得了许多成果，而且大多数研究成果转化 为实际应用，并有大量数据挖掘技术成功应用的例子。 1 关于数据关联、相关以及因果关系的数据挖掘研究 寻找频繁项集的a p r i o r i 算法1 5 】和f p g r o w t h i 6 】算法，针对不同情况和要 求设计了多维关联规则挖掘方法1 7j ，多层关联规则挖掘方法【8 j ，强关联规则 的兴趣度的研究【9 j ，面向查询和基于约束的关联分析【l 。 2 关于数据分类的数据挖掘研究 有多种分类方法和算法：决策树分类方法、贝叶斯分类方法、神经网络分类 方法、k 最临近分类方法、遗传分类方法、粗糙集分类方法、基于案例的分类。 决策树分类算法的可伸缩性技术：s l i q “】、s p r i n t l l 2 1 、r a i n f o r e s t i 】、 b o a t 1 4 i 、c l o u d s ”】等方法和技术。 用关联规则进行分类的方法：聚类关联规则进行分类的方法( a r c s 分类) 1 1 6 1 、基于关联的分类方法”1 、聚集显露模式分类法( c a p e 分类) u s l 。提高分 类法准确率的技术：装袋( b a g g i n g ) 技术和推进( b o o s t i n g ) 技术f 2 。文档资 料分类、w e b 文档分类技术。 3 关于聚类和孤立点分析的数据挖掘研究 基于划分的聚类方法：代表性的算法是k - m e a n s l 2 们、k - m e d o i d s 和c l a r a 【2 j 】 基于层次的聚类方法：代表性的方法是凝聚层次聚类a g n e s 算法和分裂的 层次聚类d i a n a 算法叫。改进的层次的聚类方法有b i r c h l 2 2 1 ，c u r e l 2 3 】， r o c k l 2 4 1 c h a m e l e o n l 2 副。 基于密度的聚类方法：代表性的算法是d b s c a n t 2 卅，o p t i c s i ”1 ，d e n c l u l 2 8 摇冶鬣硕- l - 学位论文 揪h 1 a s l e r ，s 】j ：s j s 基于网格的聚类方法：代表性的算法有三个s t i n g t ”1 ，w a v e c l u s t e r 3 0 1 ， c l i q u e t 3 1 l 基于模型的聚类方法：代表性的方法是统计学方法c o b w e b l 3 2 1 、 c l a s s l t i ”1 、a u t o c c l a s s1 3 4 1 和神经网络方法p 5 i1 3 6 1 。 孤立点的探测和分析：基于统计的孤立点分析【3 7 1 、基于距离的孤立点分析 1 3 8 1 、基于偏离的孤立点分析i ”1 。 基于约束的聚类方法：基于对象选择的约束，基于参数的约束，基于聚类集 合大小的约束，有障距离聚类( c l u s t e r i n gw i t ho b s t r u c t e dd i s t a n c e ，c o d ) ”6 l 和 用户自定义约束的聚类。 4 关于顺序数据和时序数据的数据挖掘研究 趋势分析：在数据周期变化、季节变化、随机波动情况下的趋势分析。 在时序数据库中进行相似搜索：调整处理相似匹配中存在的间隙、偏移、振 幅差异。索引法和时序查询语言。 顺序模式挖掘：用变通的a p r i o r i 挖掘算法进行顺序模式挖掘，其改进算法 有g s p ( o e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 4 0 】算法和p r e f i x s p a n ( 姚一p r o j e c t s e q u e n t i a lp a t t e r nn 缸r a n g ) 1 4 1 1 算法。 用变通的a p r i o r i 挖掘算法进行周期性分析：挖掘全周期模式、挖掘半周期 模式、挖掘循环或周期关联规则。 5 关于相似搜索的数据挖掘研究 针对各种数据类型有多种相似搜索，如相似曲线搜索、相似趋势搜索、相似 图像和相似文本搜索。 根据图像内容搜索相似图像的技术；基于图像样本的搜索；基于图像特征标 识的搜索，如颜色直方图标识、纹理标识、多种特征标识； 搜索具有相似文本的文档资料：基于相似关键字的搜索( 解决同义词和多义 词的问题) 。 基于词频矩阵的搜索技术，用潜在的语义标引减小词频矩阵的大小的方法。 6 。针对文本数据库的挖掘研究 文本数据库中存储最多的数据是半结构化数据，文本挖掘是利用基于关键字 硕士学位论文 m a s l e r sl i i e s i s 的关联和文档分类的方法从半结构化数据中发现知识。 文本数据库的挖掘已可实现文档特征的抽取、文档聚集、文档自动分类和 文档信息检索。 7 针对现代数据库的数据挖掘研究 空问数据库中的数据挖掘；多媒体数据库中的数据挖掘；科学数据库中的数 据挖掘。 8 针对w e b 的数据挖掘研究【4 2 】 w e b 内容挖掘：根据页面内容自动分类w e b 文档的算法【4 3 】、构造w 曲仓库 以及多层w e b 信息库】。 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) ：用识别权威w e b 页面( a u t h o r i t a t i v e p a g e s ) 的方法挖掘合适的w e b 链接结构【4 5 1 ，其主要方法有将页面按重要性分 等级寻找权威页面的p a g e r a n k 方法1 4 6 】，利用h u b 页寻找权威页面的 h u b a u t h o r i t y 的h i t s 算法【4 ”。( 目前g o o g l e 搜索引擎运用了这种算法) w e b 使用记录挖掘：对原始w e b 日志( w e b l o g ) 数据清洗、浓缩和转换， 构造多层w e b 信息库对w e b l o g 进行o l a p 分析。在w e b l o g 记录中挖掘关联 模式、序列模式和w e b 页面的访问趋势。 9 针对数据挖掘工具与工作环境集成的研究 数据挖掘与数据库、o l a p 的集成；不同数据挖掘方法的集成；数据挖掘与 专门领域知识的集成；隐性数据挖掘；将挖掘技术隐藏于信息系统中，使用户 不知不觉的使用挖掘技术。 1 0 关于数据挖掘查询语言和数据挖掘可视化的研究 研究标准化数据挖掘查询语言，挖掘结果的可视化、挖掘过程的可视化。 1 3k d d 的应用慨况 数据挖掘虽然只有十年的历史，但它已广泛地应用于许多的领域，并取徒 了较好的效果。这些应用领域有： 1 银行信用评估：金融服务产品的交叉销售，贷款偿还预测，个人或企业彭 信用评级，欺诈甄别。 2 电子商务：w e b 行为模式分析，个性化设计，网上购买推荐和商品推荐。 3 客户关系管理：客户利润率分析。客户细分，客户流失分析，客户响应率 的分析。 4 生物制药：针对生物医学和d n a 数据分析的数据挖掘，d n a 序列间的相 似搜索和比较分析；基因关联分析识别同时出现的基因序列，基因路径分 析发现在疾病不同阶段的致病基因，药理分析。 5 电信：客户流失分析，盗用模式分析和异常模式识别，电信数据分析可预 测网络通信中的警报。 6 证券：分析并预测股票价格的走势及相关性。分析股民的购买方式。 7 保险：用索赔数据来分离可能出现的保险欺诈。 8 零售：基于数据挖掘的数据仓库的设计与构造。销售、顾客、产品、时间 和地区的多维分析。促销活动的有效性分析。分析保持顾客的方法。购买 推荐和商品推荐。识别最有可能对新产品或服务作出反映的一组客户。识 别交叉销售的新机会。 9 医疗卫生：医疗效果分析，健康发展评估。 1 0 科学数据：实验数据分析；实验数据可视化。 1 1 天文：分析天文数据，发现类星体 目前，绝大部分数据挖掘研究原形的都已转化为数据挖掘产品。数据挖掘 工具如雨后春笋，层出不穷。将数据挖掘技术与信息系统集成是当今的潮流。 数据挖掘作为数据库、数据仓库、w e b 系统的一个组件为智能数据挖掘的发展 开辟了新路。许多大型商业数据库推出了自己的数据挖掘系统组件： m s s q l s e r v e r 一2 0 0 0 的a n a l y s i s s e r v i c e i b m d b 2 的i n t e l l i g e n t m i n e r o r a c l e 的o r a c l e 9 id a t am i n i n g s a s e n t e r p r i s e m i n e r ：d a t aw a r e h o u s i n g + m i n i n g s p s s 的c l e m e n t i n e 数据挖掘技术与数据库、数据仓库的集成有利于充分利用数据库强大的查 询功能、多维分析功能以及相似搜索等功能，并可将普通的数据挖掘升级为智 硕士学位论文 b i a s t e r s i h e s i s 能型的数据挖掘，既具有灵活查询数据库中知识的功能。数据挖掘技术与数据 库系统的高度集成还有助于推进数据挖掘标准化的进行。如： c r i s p - - d m 【4 8 i ：挖掘过程的标准化( c r o s s i n d u s t r ys t a n d a r dp r o c e s sf o r d a t am i n i n g ) x m l 1 4 9 1f o r a n a l y s i s ”1 ：基于s o a p 5 0 1 ( s i m p l e0 b j e e t a e e e s sp r o t o e 0 1 ) 的x m la p i ，用作w e b 上挖掘数据交换的一种标准方式。 p m m l ( p r e d i c t i v em o d e lm a r k u p l a n g u a g e ) 1 5 1 】预言模型交换标准：利 用x m l 描述和存储数据挖掘模型，p m m l 标准的目的；一旦个模型被一种 数据挖掘工具产生，其他数据挖掘工具也能使用这个模型。由于开放的格式， 不同数据挖掘工具产生的数据挖掘模型能够相互共享。 o l e d b f o r d a t a m i n i n g 口2 j ：数据挖掘系统基于a p i 的接口标准，遵守这 个标准的挖掘工具可利用任何与o l ed b 关联的数据源。 数据挖掘查询语言( d m q l ) 的标准化：开发类似于s q l 语言的标准化 d m q l ，使用户能标准化地使用不同的数据挖掘系统。 1 4 本文的内容与组织 本文第一章全面地介绍了数据挖掘的发展历史、研究动态、应用慨况，说 明数据挖掘既具有多层次的研究价值又具有很高的应用价值。 本文余下部分是这样组织的； 分类是一种重要的数据挖掘方法。评估分类模型准确性有着重要意义。本 文在第二章将介绍分类的基本概念和评估分类模型准确性的方法。分类算法的 可伸缩性是保证数据挖掘与大型数据库高度集成切实可行的关键所在。本文将 通过一种分类算法一决策树算法，分析其可伸缩性，并以此为代表简析研究数 据挖掘与大型数据库的集成方法，以及在此基础上开发分类预测应用程序的方 法。本文在第三章将分析决策树算法以及决策树算法的可伸缩性问题。第四章 研究决策树算法与数据库的耦合问题。第五章介绍基于o l ed bf o rd m 和 m s s q ls e r v e r 2 0 0 0a n a l y s i ss e r v i c e s 开发数据挖掘应用程序。第六章是全文总 结和研究展望，概括了本文的贡献和进一步的研究方向。 硕士学位论文 m a s t e r s r i i e s i s 第二章分类和分类模型的准确性 2 1 分类的概念 数据挖掘中的分类方法是将数据集按某个指定的属性划分，并给出分类规 则。分类问题可用数据库术语表示如下：对于一个给定的数据集，该数据集具 有m + 1 个属性( 字段) a l ，a 2 ，a 。，c 。且均为种类字段。c 作为分类 属性。将此数据集按c 的属性值分类，形成个分类模型。再用该模型对新的 数据集进行分类预测，既在已知新数据集a l ，a 2 ，a 。的值的情况下预测 分类属性c 的值。分类问题分为两个步骤； 1 创建分类模型： 这是一个机器学习过程，用分类算法和一个类别已经确定的数据集创建分类 模型。用于创建模型的数据集叫彬绽集。训练集用其分类属性的属性值表 示类别，训练集中每一条记录都属于一个确定的类别。分类模型中的预测模 式可以用分类规则，决策树，或者数学方程的形式来表达。 2 使用模型预测： 使用分类模型前必须用一定的方法估计分类模型的准确率。这可使用创建的 模型对一个类别已知的数据集。涮迸察e 进行预测，并将预测结果和实 际值进行比较。测试集和训练集必需是相互独立的。再用达到一定准确率的 分类模型预测类别未知的数据集。 图2 1 用决策树算法解决分类预测问题的两个步骤 1 0 硕士学位论文 m a s l l e r s f i i e s i s 分类在机器学习中被称之为有监督的学习，这是因为训练集的类别是确 定的，而类别未知的数据集是基于训练集进行分类的。分类具有广泛的应用： 如信誉证实、欺诈甄别、市场调查、疗效诊断、性能调查、选择购物等等。 2 2 分类算法 分类一直都是机器学习、模式识别和数理统计的研究对象。因此有多种 分类方法：常见的分类方法有：决策树归纳方法、贝叶斯方法、神经网络方 法、k 最临近分类法、基于事例的推理方法、遗传方法、粗糙集方法、模糊 集方法。每种方法可由几种代表性的算法实现。对不同的数据类型和应用领 域，每种方法都有其长处和短处。但许多实验比较表明，没有一种分类算法 对所有的数据类型和应用领域都优于其他分类算法【5 3 】1 5 4 1 5 5 1 5 6 1 5 7 1 5 8 1 59 1 。一 般从以下几个方面评估分类算法； 预测准确率：由算法生成的分类模型对新数据的预测能力 速度：创建分类模型的速度使用分类模型的速度 键壮性：处理噪音和空缺值的能力 伸缩性：对大量磁盘驻留数据的处理能力 可解释性：用户对算法产生的分类模式可理解程度。对于描述型的分类 任务，模型描述越简洁越受欢迎。例如，采用规则表示的分类模式就更有 用，而神经网络方法产生的结果就难以理解。 2 3 评估分类模型准确性的方法 分类模型的准确性是分类成功的关键。运用分类算法建立分类模型后，可 用下面几种方法评估分类模型的准确性。 1 保持法( h o l d o u tm e t h o d ) 运用保持法时，将数据集随机地划分成两个独立的数据集；训练集和测试 集。用训练集建立模型，再用测试集评估模型。通常，取三分之二的数据 ， 用于训练集，其余的用于测试集。保持法的评估是保守的，因为只有数据 集的一部分用于建立模型。为保证评估的准确性，可将保持法重复k 次， 硕士学位论文 m a s l e r s7 l i l e s i s 数据集每次随机地划分成不同的训练集和测试集。总体准确率取k 次评估 准确率的平均值。这种方法被称为重复保持法。重复保持法遇到的最大问 题是不同测试集问有重叠的数据。 2 k 一折交叉确认法( k f o l dc r o s s v a l i d a t i o nm e t h o d ) t 6 0 l 交义确认法能避免出现重叠问题，k 折交叉确认法首先将整个数据集划分 为k 个相等子集。然后进行k 次迭代，依次将每个子集用作测试集、另外 k 一1 个子集用作训练集。将k 次评估的正确分类数除以数据集的记录总数 可得到模型的总体准确率。通常取k = 1 0 。 3 留法( l e a v eo r l eo u tm e t h o d ) 留一法是k 一折交叉确认法的变形。若数据集有n 条记录，将数据集划分 为n 个子集。进行n 次迭代，每次留一条记录用作测试，其余n 一1 条记录 用作训练集。 留一法适合于较小的数据集，否则计算量太大。 4 引导法( b o o t s t r a pm e t h o d ) 1 6 “ 从数据集的n 条记录中均匀地、有放回地取样形成训练集。由于取样是有 放回的，任意一条记录在n 次选样后未被选入训练集的几率是f l l n l n = 1 e = o3 6 8 ，因此被选入训练集的几率是0 6 3 2 。建立模型后，用训练集测 试模型的误差。这种误差称之为重新替代误差( r e s u b s t i t u t i o ne r r o r ) ，误 蔗数值记为“。再用狈9 试集测试模型的误差，