（管理科学与工程专业论文）基于决策树的分类算法研究和应用.pdf

虫末耀范大学磺士学位论文 皇要图表目录 黼3 - l 决策树寐意图1 6 黪3 - 2连续分支熹豹求篷2 5 图3 - 3 离散分支点的求值2 6 图3 4 随着树的复杂度的增加，在训练集以及测试集内的错误率2 9 表4 - 5 按照二进制表示分类法4 2 衮4 - 6 雳二避秘方法瓣离散属毽分类4 3 圈5 一l出训练集生成豹决策树4 7 表5 - 2由训练集生成c c 表4 7 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名 丞去乏 导师签字：鑫蠢习灸 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 主t 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 墨丢去 导师签字：垄蔓友幸疋 签字目期：2 0 0 ( 年l 调1 日 签字日期：2 0 0年月 日 山东师范大学硕士学位论文 基于决策树的分类算法研究与应用 摘要 面对信息时代海量数据的出现，如何有效利用海量的原始数据分 析现状和预测未来，已经成为人类面临的一大挑战。由此，数据挖掘 技术应运而生并得到迅猛发展。 数据挖掘是指从数据库中抽取隐含的、具有潜在使用价值信息的 过程，是一种新型的数据分析技术，被广泛应用于银行金融、保险、 政府、教育、运输等企事业单位及国防科研上。数据挖掘应用的普遍 性及带来的巨大经济和社会效益，吸引了许多专家和研究机构从事该 领域的研究。 数据分类是数据挖掘中一个重要的内容。分类存在很多方法，其 中决策树归纳以其易于提取显式规则、计算量相对较小、可以显示重 要的决策属性和较高的分类准确率等优点而得到广泛的应用。据统计， 目前决策树算法是利用最广泛的数据挖掘算法之一，利用率高达1 9 。 应用领域已由医疗到博弈论和商务等领域，是一些商业规则归纳系统 的基础。 寻找新的构造决策树和简化决策树的方法一直是决策树技术研 究的一个热点。s l i o 算法和s p r i n t 算法很好的解决了磁盘驻留数据 太大以至于无法被内存容纳带来的问题。它没有采纳利用抽样或划分 数据集来获得可容纳于内存的小树据的处理方法，而是采用了一种新 的数据结构，直接在整个数据集上建立一棵决策树。但s p r i n t 、s l i q 等算法处理的训练集的大小都是固定的，来自稳定的环境，人为干预 较少，忽视了数据的变化趋势。在现实生活中，数据集并不是稳定的， 而是连续到来的。将现有的算法改进使其能够适应不断生长的训练集， 生成一棵与旧树相关的树是十分有现实意义的。 本文的研究工作源于上述的背景，目的是对数据库知识发现进行 深入的研究，探索数据挖掘中决策树的更新问题，以更好的应用于实 际工作中，主要进行了以下的研究工作： l 、指出构造好的决策树的关键在于如何选择好的逻辑判断或属 山东师范大学硕士学位论文 性，比较了信息增益、基尼指数属性选择度量方法的优缺点，探讨了 将离散属性值组合计算基尼指数来构造二叉树的方法。 2 、研究了决策树的几种生成算法和剪枝算法，比较了它们的优 缺点，特别是针对可伸缩的s p r i n t 算法做了全面的分析。深入探讨了 建树算法与剪枝算法的集成问题，即p u b l i c 算法以及一个可应用于其 它算法的r m n f o r e s t 框架结构，并应用于后面的实例中。 3 、针对现实生活中，数据集高速到来的情况，由s p r i n t 算法、 p u b l i c 算法的思想以及r a i n f o r e s t 框架结构一c c 表，提出了一种新的 数据集动态变化的决策树生成与剪枝算法，使其能够适应数据集的连 续性，从而提高算法的实时有效性。 4 、将决策树数据挖掘方法应用到汽车销售中。从调查问卷中挖 掘出最近一年内有购车意愿的客户的特征，为营销策略的制定、广告 的投放提供依据，提高汽车销售公司的市场竞争力，从而提高汽车的 销售量。 关键词：知识发现，数据挖掘，决策树，剪枝 分类号：t p 3 1 1 1 3 2 山东师范大学硕士学位论文 c l a s s i f i c a t i o na l g o r i t h ms t u d ya n d a p p l i c a t i o n b a s e do nd e c i s i o nt r e e a b s t r a c t h o wt oi n v e s t i g a t ec u r r e n ts t a t u sa n df o r e c a s tt h ef u t u r ew i t hg o o d u s eo ft r e m e n d o u so r i g i n a ld a t ah a sb e e nb e c o m i n gt h eb i gc h a l l e n g et o h u m a nb e i n g sw h e nf a c i n gt h ee m e r g e n c eo f m a s sd a t ai ni n f o r m a t i o ne r a c o n s e q u e n t l y , d a t am i n i n gt e c h n o l o g ye m e r g ea n db o o mq u i c k l y d a t am i n i n gm e a n st h ep r o c e s so fa d o p t i n g c r y p t i ca n dp o t e n t i a l h e l p f u li n f o r m a t i o nf r o mt h ed a t ab a s e i t so n ek i n do fb r a n dn e wd a t a a n a l y s i st e c h n o l o g ya n di sp o p u l a ru s e di nt h ef i e l do fb a n k i n gf i n a n c e ， i n s u r a n c e ，g o v e r n m e n t ，e d u c a t i o n ，t r a n s p o r t a t i o na n de r e e n t e r p r i s e sa s w e l la sn a t i o n a ld e f e n s es c i e n t i f i cr e s e a r c h t h eu n i v e r s a l i t yo fd a t a m i n i n ga p p l i c a t i o na n di t sg r e a te c o n o m i ca n ds o c i a lb e n e f i ta t t r a c tt h e r e s e a r c ho ft h i sf i e l da m o n g s tm a n ys p e c i a l i s t sa n dr e s e a r c hi n s t i t u t e s d a t ac l a s s i f i c a t i o ni so n eo fi m p o r t a n tc o n t e n t sf r o md a t am i n i n g t h e r ea r em a n ym e t h o d sf o rd a t ac l a s s i f i c a t i o n ，a n da m o n g s tt h e s et h e d e c i s i o nt r e ei n d u c t i o ni s w i d e l yu s e dw i t hi t sc o n v e n i e n c ef o rg e t t i n g a p p a r e n tr u l e s ，s m a l l e rc a l c u l a t i o nw o r k l o a d ，s h o w i n gi m p o r t a n td e c i s i o n c h a r a c t e r i s t i c s ，h i g h e rc l a s s i f i c a t i o n c o r r e c tr a t ea n de t c a d v a n t a g e s c u r r e n t l yd e c i s i o n t r e ea l g o r i t h mi s o n eo fm o s tp o p u l a ru s e dd a t a m i n i n ga l g o r i t h ma c c o r d i n gt or e l a t e ds t a t i s t i c s ，a n dt h eu t i l i z a t i o nr a t e r e a c h e s19 t h ea p p l i c a t i o nh a sb e e ne x t e n d i n gf r o mm e d i c a lt og a m e t h e o r y ，b u s i n e s sa n de t c ，a n db e c o m i n gt h eb a s i so fs o m eb u s i n e s sr u l e i n d u c t i o ns y s t e m i t sa l w a y st h eh o ts p o tt os e e kf o rt h em e t h o do fc o n s t r u c t i n ga n d s i m p l i f y i n gd e c i s i o nt r e e s l i qa n ds p r i n ta l g o r i t h m s o l v e dt h e p r o b l e mv e r yw e l lf o rt h a tt h es t o r e dd a t ao nt h ed i s ci st o ob i gt ob e l o d g e db yt h em e m o r y t h ea l g o r i t h m d o e s n ta p p l yt ot h em e t h o do f g e t t i n gs m a l ld a t a ，l o d g e db ym e m o r y ，b ym e a n so fs a m p l eo rs o r t i n g d a t ab a s e ，b u ti tu t i l i z eo n ek i n do fn e wd a t ac o n f i g u r a t i o nt oc o n s t r u c t o n ed e c i s i o nt r e ed i r e c t l yf r o mt h ew h o l ed a t ab a s e h o w e v e r ，t h es i z e o ft r a i n i n gs e tf o rs p r i n ta n ds l i qa l g o r i t h mi sf i x e d ，f r o ms t a b l e e n v i r o n m e n t ，l e s sa f f e c t e da r t i f i c i a l l y , a n dn o r m a l l yi g n o r e st h et r e n do f 3 山东师范大学硕士学位论文 4 d a t ac h a n g i n g i n r e a l i t y ，t h ed a t ab a s e i sn o ts t a b l e ，b u t i n c o m i n g c o n t i n u o u s l y i t sv e r ys i g n i f i c a t i v et oo p t i m i z et h ec u r r e n ta l g o r i t h m ， m a k et h e mf i tt h eg r o w i n ge x e r c i t a t i o nb a s ea n dc o n s t r u c to n et r e er e l a t e d t oo l d t r e e t h es t u d i e so ft h i sa r t i c l ee m e r g ef r o mt h es a i db a c k g r o u n d ，a n dt h e p u r p o s ei st or e s e a r c hd e e p l yt h ed a t ab a s ek n o w l e d g ed i s c o v e r y ，p r o b e i n t od e c i s i o nt r e eu p d a t i n gd u r i n gd a t am i n i n ga n da p p l yt ot h er e a l i t y t a s k s m a i nr e s e a r c h e ss e eb e l o w ： 1 p o i n to u tt h a tt h ek e yi s s u eo fc o n s t r u c t i n gg o o dd e c i s i o nt r e ei s h o wt os e l e c t g o o dl o g i cj u d g m e n t so rc h a r a c t e r i s t i c s c o m p a r et h e a d v a n t a g e a n dd i s a d v a n t a g eo fi n f o r m a t i o ng a i na n dg i n ii n d e x c h a r a c t e r i s t i c ss e l e c t i v em e a s u r e m e n tm e t h o d o l o g y t r i g g e rt h em e t h o d o fc o n s t r u c t i n gt w ob i f u r c a t i o nt r e eb yc a l c u l a t i n gg i n ii n d e xw i t h d i s c r e t ev a l u ec o m b i n a t i o n 2 s t u d ys e v e r a lc r e a t i n ga n dp r u n i n ga l g o r i t h m so fd e c i s i o nt r e e a sw e l la sc o m p a r et h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s ，a n de s p e c i a l l y a n a l y z e e x t e n s i b l es p r i n t a l g o r i t h m sc o m p l e t e l y i n v e s t i g a t e t h e i n t e g r a t i o no fc o n s t r u c t i n gt r e ea l g o r i t h ma n dp r u n i n ga l g o r i t h m ，i e p u b l i ca l g o r i t h ma n do n er a i n f o r e s tf r a m es t r u c t u r e ，w h i c hc a nb e a d o p t e d t oo t h e ra l g o r i t h m s ，a n du s e di nt h ef o l l o w i n ge x a m p l e sh e r e a f t e r 3 i n t r o d u c eo n ed e c i s i o nt r e ec r e a t i n ga n dp r u n i n ga l g o r i t h mo f n e wd a t ab a s ed y n a m i cc h a n g e sb ym e a n so fi d e a so fs p r i n ta l g o r i t h m ， p u b l i ca l g o r i t h ma n dr a i n f o r e s tf r a m es t r u c t u r e c cs h e e tw i t ht h e c o n d i t i o no fd a t ab a s eh i g hs p e e de m e r g i n gi nr e a l i t y , t of i tc o n t i n u o u s l y g r o w i n gd a t ab a s ea n di m p r o v ea l g o r i t h mr e a lt i m ev a l i d i t y 4 t h ea p p l i c a t i o no fd e c i s i o nt r e ei nt h ef i e l do fa u t os a l e i n v e s t i g a t et h eq u e s t i o n n a i r ed a t at of i n do u tc h a r a c t e r i s t i c so fc u s t o m e r s w i t hp u r c h a s i n gi n t e n tw i t h i no n ey e a r ，a n dt h i sc a l lb er e f e r e n c eo f f i g u r i n g o u tm a r k e t i n gs t r a t e g ya n dl a u n c h i n ga d v e r t i s e m e n t ，t h u st o s t r e n g t h e nm a r k e t i n gc o m p e t i t i o no fa u t os a l ec o m p a n ya n di m p r o v ea u t o s a l e sv o l u m e k e yw o r d s ：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 ) ；d a t am i n i n g ； d e c i s i o nt r e e ；p r u n i n gt r e e c l a s s i f i e dn u m b e r ：t p 311 13 2 山东师范大学顿士学位论文 i 1 数据挖掘技术 第一章综述 1 1 1 数据挖掘技术的产生 晟近几十年以来，随着互联网的发展和企业信息化程度的日益提 高，科研政府部门普遍使用电子事物处理技术，商品条形码被广泛使 用，以及电子商务和科学数据库的急剧增长为我们带来了海量的数据。 激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高 层次的分析以便更好地利用这些数据。而目前的数据库系统可咀高 效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的 关系和规则无法根据现有的数据预测未来的发展趋势，缺乏挖掘数 据背后隐藏的知识的手段，从而导致了“数据爆炸但知识贫乏”的现象。 大量信息在蛤人们带来方便的同时也带来了一大堆问题：第一是 信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难 以保证；第四是信息形式不一致，难以统一处理。人们开始考虑：“如 何才能不被信息淹投，而是从中及时发现有用的知识、提高信息利用 率? ”这就引发了一门新兴的自动信息提取技术：数据中的知识发现， 简称k d d ( k n o w l e d g ed is c o v e r yi no a l ；a b a s e ) 。其内容主要涉及人工 智能领域中的机器学习，模式识别、统计学、智能数据库、知识获取、 专家系统、数据库可视化、数据库领域的数据仓库联机分析处理 ( o l a p ) ，多维数据库等方面。k d d 已经是解决目前信息系统中普遍面 临的“数据爆炸”而“信息缺乏”状况的最有效的手段之一，并且它 的研究领域具有较大的研究意义和较多的研究方向一度成为数据库研 究界最热的研究方向，拥有人数众多的研究群体，受到学术界和企业 界的极大关注。多学科的相互交融和相互促进，使得这一学科得以蓬 勃发展，而且已初具规模。并行计算、计算机网络和信息工程等其他 领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论， 甚至到了脍炙人口的程度。 数据挖掘d m ( d a t am i n in g ) 是k i ) d 的一个最关键步骤，因此实际 数据挖掘d m ( d & t am i n i n g ) 是k d d 的一个最关键步骤，因此实际 山东师瓶大学硕士学位论文 1 1 数据挖掘技术 第一章综述 1 1 1 数据挖掘技术的产生 最逐a 十冬鞋来，疆着蔓联霜熬发震粒念韭痿惑纯程凌貔蠢豢缝 商，科研政府部门普遍使用电子事物处理技术，商晶条形粥被广泛使 弼，以及窀子裔务纛辩学数据簿豹怠黧增长洚筏稻带来了海爨懿数攒。 激增的数据背厝隐藏若许多重疆的信息，人们希望能够对其进行更高 鬃次静分轿，戳便更好缝零j 瘸这些数裰。焉瓣蓠静数据痒系统霹戳商 效地实现数据的录入、痊询、统计等功能，假无法发现数据中存在的 芙系和旒鄹，秃法摄撵现有豹羧据颈灏未来豹发震趋势，靛乏挖耩数 掇背后隐藏的知识的手段，从而导致了“数据爆炸但知识贫芝”的现象。 大螯信息奁给入稻带来方便的同时也带采了一大堆闷麓：第一是 信息过爨，难以消化；第二是信息真假难以辨识；第三是信息安全难 戳保证；第遥建信息形式不一致，难戳统一鲶理。人们开始考虑：“如 何才能不被信息淹没，而是从中及时发现有用的知识、提离信息利用 率? ”这就引发了一门新兴的自动信息提取授术：数搬中豹知识发现， 简称k d d ( k n o w l e d g ed is c o v e r yi nd a t a b a s e ) 。其内容主要涉及人工 篱能领域中的机器学习，模式识剐、统计学、智能数据库、知识获取、 专家系统、数据库可襁化、数据库领域的数据仓库联机分板处理 ( o l a p ) ，多维数据库等方面。k d d 已缀是解决目前倍息系统中普遍面 嗡的“数据爆炸”露“信息缺忑”状擞的最鸯效的挚段之，著旦它 的研究领域具有较大的研究意义和较多的研究方向一度成为数据库研 究赛最热救磅究方囱，拥套人数众多豹磅究群体，受裂学零器帮企妲 界的极大关注。多学科的相互变融和相互促进，使得这一学科得以蓬 魏发展，嚣虽邑襁具鬏模。势行诗算、计算凝网络粒售惠王程等其毽 领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论， 甚至至了验炙人蠢豹穆疫。 数据挖掘d m ( d a t am i n i n g ) 是k d d 的一个最关键步骤，因此实际 山东师范大学硕士学位论文 应用中把d m 和k d d 不作区分。1 9 9 5 年，在美国计算机年会( h e m ) 上， 提出了数据挖掘的概念。即通过从数据库中抽取隐含的，未知的，具 有潜在使用价值信息的过程。 数据挖掘应用的普遍性及带来的巨大的经济和社会效益，吸引了 许多专家和研究机构从事该领域的研究，许多公司推出了自己的数据 库挖掘系统。从1 9 8 9 年举行的第十一界国际联合人工智能学术会议上 k d d 被提出，到现在不过十多年的时间，但在g a r t n e rg r o u p 的一次 高级技术调查中将数据挖掘和人工智能列为“未来5 年内将对工业产 生深远影响的五大关键技术”之首，并且还将数据挖掘列为未来五年 内十大新兴技术投资焦点的第二位。根据最近g a r t n e r 的h p c 研究表 明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更 多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处 理系统来创建新的商业增长点。” 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科学基金首次支持我们对该领域的研究项目。目前，国内 的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研 究，已初步形成了知识发现和数据挖掘的基本框架，研究方向也从发 现方法转向系统应用。 圈卜l 数据挖掘怎样棱认为是i ( d d 中的一个步骣 山东师范犬学硕士学位论史 1 1 2 数据挖掘韵方法 数攒挖掘熬凌链麓予指定数港挖撼任务串蘩我豹模式类激，箕饭 努般w 分为两癸：播述和预测。箍述性挖籀任务刻画数据库中数据的 般待经，预测链挖獬氆务在当前数据土避行推断，戳进行预测。在 实际应用巾，往往根据模式的实际应用细分为以下6 种： 1 分炎模式 2 阐蝴模式 3 时间序捌模式 4 凝类模式 5 关联模式 6 序列模式 在解决实簖阍题时，经常要同对使用多将模式。努类模式彝隧魑 模式是使用最酱遍的模式。分类模式：阐归模戏、时间序列模式也被 认为是骚般督知识，因为在建立模式露数据豹终果是矗知懿，可以意 接用来检测模式的准确性，模式的产生耀在受搬督的情况下进行的。 般在建立这些接式聪，使用一部分数攥馋为样本，翅另部分数撼 来检验、校正模式。 1 。 。3 数攮挖掘溪鲮蚋发展 根据r g r o s s m a n 的戏点“1 ，数据挖掘的发展过程w 分期代： 第一代：第代数数据挖耀爨统投支持一令或少数几令数据豫援 冀法，这些算法只能够挖掘向量数据：如果数摄足够大，并冀频繁的 变诧，这裁爨簧零l 鬟数撰痒或蠹数据仓霹鼓术送行饕璨，第一代系统 显然不能满足甓求。 第二我：第= 铃系统瓣主溪特点建支持与数据辫帮数据仓库懿嵩 蟪戆接鄹，共鸯建豹霹测霪瞧葶爨礁施瞧。第二代系绫掇供￥数据挖糕 模式和数懿挖瓣鸯诲谱害，献孬粪有更离戆昃渍缝。然焉第= 代系统 只：；雯重棱鍪懿生成，如嚣和疆言模型系统集黢鹣阀蘧鼯蘩了第三钱数 据挖搐系统的开发。 第三代：第三代数据挖掘蘩绫胃挖稳i n t r a n e t s 霸e x t r a n e t s 上的 分布的和离度羿璇的数据，并能有效豹和操作系统结含。遮一代数据 挖撼系统静美键技术之一是掇嵩对建意在弄精繁统上熊多个籁言横甏 以及管瑷遮些预言模型的元数据提供第一级剐豹支持。 山东师范大学硕：e 学位论文 第四代：第四代数据挖掘系统可以挖掘嵌入式、移动式以及一般 性的计算设备所产生的各种数据。 1 1 4 数据挖掘的应用与面临的挑战 尽管数据挖掘是一个新兴的研究领域，但是却得到了稳定的发展， 每年市场上都会出现新的数据挖掘系统，各大数据库软件公司也分别 推出了自己的数据挖掘产品。 表i - l 一些：棼名的数据挖掘产品 产品名公司名实现功能算法 关联、分类、回归、强测、馆离橙潮、序 i n t e l l i g e n tx i n e r l 酬 列模式分析和袋类 e n t e r p r i s em i n e r s 幅 回归、分擞和统计分析包 鞋i n e s e ts g l 关联、分类、高级统计和可视化工其 c l e m e n ti n el s l 规划归纳，神经翔终、分豢和可撬化- r j r d b h i n e r瑚n i n e r o l a p 分析、关联、分宪和聚粪 a n a l y s i ss e r v i c e s ) l i c r o s o f t 分娄和聚娄 另外数据挖掘在一些特定领域得到了充分的发展，如生物医学、 d n a 分析、金融业、零售业和电信行业。这些实践将数据挖掘和各特 定领域知识结合起来，满足了特定任务的需要，也取得了一些很大的 成绩。数据挖掘任务和方法的多样性给数据挖掘提出了许多挑战性的 课题。在未来的课题研究中，数据挖掘研究人员、系统和应用开发人 员所厩临的主要问题有： 应用领域的探索。 可伸缩性数据挖掘方法的研究。 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成。 数据挖掘语言的标准化。 可视化数据挖掘。 复杂数据类型挖掘的新方法。 w e b 挖掘和文本挖掘。 山东师范大学硕士学位论文 1 2 决策树分类算法及其研究现状 数据挖掘的分类模式是一种有指导性的学习，即是以实例为基础 的归纳学习算法，通过分析由属性描述的训练数据集来构造模型由此来 预测新元组的分类标记。数据分类存在很多方法，如判定树归纳、贝叶 斯分类、神经网络以及k 最临近分类、遗传算法和粗糙集等。其中决策 树归纳以其易于提取显式规则、计算量相对较小、可以显示重要的决策 属性和较高的分类准确率等优点而得到广泛的应用【2 l 。据统计，目前决 策树算法是利用最广泛的数据挖掘算法之一，利用率高达1 9 。应用领 域已由医疗到博弈论和商务等领域，是些商业规则归纳系统的基础。 在计算机科学中采用树形结构描述数据集已有不短的时间了，但它 一直是一个不受重视的知识发现过程。随着数据挖掘技术的产生，决策 树得到了很快的发展。 决策树的算法己有很多。1 9 8 6 年j r o s sq u i n l a n 引入了i d 3 算法 后，引起了很大的反响。在此基础上，他又于1 9 9 3 年，在其“p r o g r a m f o rm a c h i n el e a r n i n g ”一书中，对i d 3 算法进行了补充和改进，提出 了后来非常流行的c 4 5 ”1 算法。后来又出现了c 4 5 的商业改进版c 5 0 算法，在大数据量情况下的效率和生成规则的数量与正确性方面有了显 著的提高。此外，c h a i d 算法也有相当广泛的应用。1 9 9 6 年又提出了 s l i q 5 1 和s p r i n t “3 算法，r a i n f o r e s t 框架结构”3 ，它们强调算法的可伸 缩性。 由于数据挖掘的对象是规模庞大的数据，已有的分类算法在数据量 小时能够准确、高效的分类，效果很好。但当用于处理大量数据时，已 有的算法都会不同程度的出现各种问题，分类效果不理想。因此，研究 数据挖掘中准确、有效的分类算法，虽然是一个传统的问题，但仍具有 挑战性。 目前，在知识发现和数据挖掘的研究和开发中已经取得了些另人 瞩目的成绩，对关联规则、聚类等基本算法的研究已经基本i 三| 趋成熟，人 们的研究重点逐渐转移到数据挖掘技术在新的数据类型、应用环境中使用 时所出现的新问题的解决上【9 - 1 2 1 。 山东师范大学硕j ：学位论立 l 、决策树技术和神经网络技术相结合。决策树也具有产生n 维空间 下任意复杂的决策边界的功能。因此，可以将决策树重新构造成一个多层 的神经网络。这类方法解决了出神经网络得到的知识难于被人们理解的缺点。 2 、决策树技术和模糊集合原理的结合。决策树技术虽然有许多优点， 但也存在着不稳定的缺点，即决策树带来了较大的变动。模糊集合的融通性 使人们利用模糊逻辑来解决决策树的这一缺点并取得了不错的效果。 3 、决策树技术和进化算法，遗传算法及遗传编程的结合。基于进化算 法的决策树系统具有较好的抗噪声能力，同时进化算法很容易在并行计算 机上运行，因此可以期待基于进化算法的决策树的运算能力有较大的提高。 4 、决策树技术和多智能体的结合。多智能体系统的复杂性，而机器 学习有潜力提供一个鲁棒性较强的机制来有效协调各智能体问的行为，因 此对多智能体结合机器学习是一个很有前途的方向。 5 、寻找新的构造决策树的方法。自从q u i n l a n 提出i d 3 和c 4 5 方法后， 有不少专家提出了其他构造决策树的方法，m a n k e r s t 等提出了基于多维 可视化下的交互式的决策树构造，此方法在决策树构造阶段加入了专家知 识，这样便于用户更深地理解产生决策树的数据及最终产生的决策树，同 时也显著地减小了决策树的大小。 6 、寻找更好的简化决策树的方法。寻找更好的简化决策树的方法，这 一直是决策树技术研究的一个热点。d f o u n r n i e r 等提出的一种新的修剪决 策树的方法2 d i 修剪法。此方法针对数据不确定的情况，利用特性索 ( q u a l i t yi n d e x ) 来权衡处理决策树深度和节点杂质。d 1 2 修剪法将保持那 些虽不能减小错误率但能指出些特殊性质的群体的子树。 7 、研究产生决策树的训练和检验数据的大小及特性与决策树特性之 间的关系。实际上，这就是经常提起的数据预处理技术( d a t ar e p r o c e s s i n g ) ： 与决策树修剪技术( p r u n i n g ) 相对应，也称它为数据减少技术( d a t a r e d u c t i o nt e c h n i q u e s ) 。 8 、决策树技术的软件实现。粥决策树技术软件化一直是决策树技术 的方向之一。目前市场上的大多数据挖掘软件如s a s 等都包含有决策树技 术部分。 以上这些决策树的研究并不是孤立的，它们经常相互联系、相互结合。 决策树技术早己被证明是利用计算机模仿人类决策的有效方法。由于2 0 山东师范大学硕士学位论文 世纪末人工智能陷于低潮，此技术曾不被重视。值得庆幸的是，由于数据 挖掘技术的兴起，作为拟人决策主要方法之一，近年来决策树又重新引起 了人们的兴趣，并得到更广泛的应用。将决策树技术与其他新兴的技术相 结合，决策树技术将焕发出新的生命力。 1 3 本文的主要工作 本文的研究工作源于上述的背景，目的是对数据库知识发现进行深 入的研究，探索数据挖掘中的决策树问题，以更好的应用于实际工作。 主要进行了以下的工作： 1 、指出构造好的决策树的关键在于如何选择好的逻辑判断或属性， 比较了信息增益、基尼指数属性选择度量方法的优缺点，探讨了将离散 属性值组合计算基尼指数来构造二叉树的方法。 2 、研究了决策树的几种生成算法和剪枝算法，比较了它们的优缺 点，特别是针对可伸缩的s p r i n t 算法做了全面的分析。深入探讨了建 树算法与剪枝算法的集成问题，即p u b l i c 算法以及一个可应用于其它算 法的r a i n f o r e s t 框架结构，并应用于后面的实例中。 3 、针对现实生活中，数据集高速到来的情况，由s p r i n t 算法、p u b l i c 算法的思想以及r a i n f o r e s t 框架结构- c c 表，提出了一种新的数据集 动态变化的决策树生成与剪枝算法，使其能够适应数据集的连续性， 从而提高算法的实时有效性。 4 、将决策树数据挖掘方法应用到汽车销售中。从调查问卷中挖 掘出最近年内有购车意愿的客户的特征，为营销策略的制定、广告 的投放提供依据，提高汽车销售公司的市场竞争力，从而提高汽车的 销售量。 山东师范大学硕士学位论文 第二章分类算法及其相关知识 2 1 分类的概念 分类是一类重要的数据挖掘问题，可描述如下【1 3 】： 给定一组训练数据的集合t ( t r a i n i n gs e t ) ，由一条条的数据库记录 ( r e c o r d ) 组成的。t 的每一条记录包含若干条属性( a t t r i b u t e ) ，组成 一个特征向量，用矢量x = ( x 1 ，x n ) 表示，其中x i ( 1 i n ) 对应各非类别 属性，可以有不同的值域，即对于任一属性x i = ( x l ，x m i ) ，m i 随属性的 不同而发生变化。当一属性的值域为连续域时，该属性为连续属性 ( n u m e r i c a la t t r i b u t e ) ，否则为离散属性( d i s c r e t ea t t r i b u t e ) ：用c 表 示类别属性，c = c l ，c k ) ，即数据集有k 个不同类别。那么，t 就隐含 的确定了一个从矢量x 到类别属性c 的映射函数h ：“x ) _ c ，分类的目的 就是分析输入数据，通过在i j i i 练集中的数据表现出来的特性，为每一个 类找到一种准确的描述或者模型，采用该种方法( 模型) 将该隐含函数 h 表示出来。 从以上可以看出分类是根据训练数据集的特点构造一个分类器，利 用分类器对未知的样本赋予类别的一种技术。构造分类器的过程一般分 为训练和预测两个步骤： | 髦i2 _ l 凡l 决策树算法辑决分类预测闽程的两个步臻 第一步，在训练阶段，分析训练数据集的特点，根据给定的训练集， 找到合适的训练函数h ：“x ) _ c 的表示模型，这一步通常称为模型创建 阶段。 山东师范大学硕士学位论文 第二疹，使嗣上一步训练完成的函数模型预测数攒的类别，或利用 该瀚数模型，对数据集中的每一类剐进行描述，形成分类预测e 一般来 说，预测阶段的代价远远低于训练阶段。 2 2 分类算法 目前，针对分类问题已有了若干不同领域方法的算法，如统计学、 机器学习、享孛经嘲络积耀糙集理论等。按照各耱冀法的技术特点，将藏 分成决策树分类、贝叶斯分类、慕于关联规则的分类以及基于数据库技 本瓣分类等几类冀法。 l 、决策树分类算法 决荧撵技术l ”l ( d e c i s i o nt r e e ) 是建予分类嬲预溅瓣主要授零，决策 树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规 剽熬实例串推理窭决策秘袭示形式熬分炎嫂熬。它采髑鑫颈囊下熬递羟 方式，在决策树的内部节点进行桶性值的比较并根据不同属性判断从该 节嶷羹下约分支，在决繁秘熬时节焘餐弱结论。溪致跌壤接蠡裁对盛萋 一条合取娩则，整棵树就对应一组析取寝达式规则。目前已经形成了莎 耱决策摇雾法，翔i d 3 、c 4 。5 、c a r t 、s l i q 、s p r i n t 等。 2 、贝时斯分类算法 爱时籁分类算法是炎巅爱橛率绫诗知谖遴行分类懿雾法。这黧箨 法主要利用贝叶斯分类定理来预测一个未知类别的样本属于各个类别 的可辘毪，选择其串可能经最大豹一个粪鬟雩# 为该徉零的最终类嗣。警 用于大型数据库时，贝叶斯分类装现出商准确率与高速度。 3 、基予数据露技术舱分类舞法 虽然数据挖搬研究的必起是数据库领域的研究人员掀起的，然而至 今为止提出静大多数算法嬲没有剩雳数舔痒的籀关技术，数据挖掘瘦用 也很难与数据库系统集成。其中m n d 和g a c r d b 算法致力于解决此 问题。m n d ( m i n i n g i n d a t a b a s e ) 采用典型豹决策树构造方法构造分类 器，它区别予s l i q 主要在予采用数据库掇供的u d f ( u s e r - d e f i n e df u n c t i o n ) 方法和s q l 语句实现树的构造，易于与数据库系统集成，但u d f 的编 写和维护棚当复杂。 山东师范大学硕士学位论文 4 、基于关联规则的分类算法 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 i o n ) 是基于关联规则发现方法的 分类算法典型代表。第一步发现所有的右部为类别的类别关联规则 ( c l a s s i f i c a t i o no na s s o c i a t i o n ，简称c a r ) ，第二步从已发现的中选择高 优先度的规则来覆盖训练集。它发现的规则相对全面，分类准确度较高。 2 3 评估分类模型准确性的尺度 以上每种方法可由几种代表性的算法实现，对不同的数据类型和应 用领域，每种方法都有其长处和短处。但许多实验比较表明，没有一种 分类算法对所有的数据类型和应用领域都优于其他分类算法。 有下面几种分类器评价、比较尺度【1 4 】： 1 可伸缩性：计算复杂度依赖于具体的实现细节和硬件环境，在数 据挖掘中，由于操作对象是海量的数据库，因此空间和时间的复 杂度问题将是非常重要的一个环节。 2 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越 受欢迎：例如，采用规则表示的分类器构造法就更有用，而神经网 络方法产生的结果就难以理解。 3 强壮性：这涉及给定噪声数据或具有空缺值的数据，模型正确预 测的能力。 4 速度：这涉及产生和使用模型的计算花费。 山东师范火学硕士学位论文 第三章决策树算法的分析与研究 在数据挖掘的知识模式中，分类是比较重要的一种。决策树是数据 挖掘中功能相对比较全面的一种分类工具。决策树按功能划分，主要有 两种类型：对测试数据进行标志并把它们正确分类的分类树和对数值型 的目标变量进行估计的回归树。本文介绍的决策树主要是对离散数据进 行预测。 决策树分类算法起源于概念学习系统c l s ( c o n c e p