（计算机软件与理论专业论文）数据挖掘中决策树分类算法研究与应用.pdf

摘要 摘要 决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相 比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模 数据集，除t n 练数据中的信息外不再需要其他额外信息，表现了很好的分类精 确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离 散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。 本文以决策树为研究对象，主要研究内容有： ( 1 ) 引入了一种新的降维方法：先对所有条件属性进行重要性排序，再利用神经 网络不需先验知识的“黑箱”分类特点，及其分类效能高的优势，对属性进行 裁减，选择出对数据分类最有效的若干基本属性，从而达到降维的效果； ( 2 ) 提出了加权二分查找算法进行连续属性离散化，该方法克服了传统二分查找 方法单纯划分区域，容易陷入局部最大的缺点，且相对简单，易于实现，效 率高； ( 3 ) 改进了传统的基于信息熵的属性选择标准，在选择测试属性生成决策树时， 克服了i d 3 和c 4 5 算法选择测试属性时的偏向问题，计算量小，运行时间 短，提高了决策树分类器的分类效率： 一 ( 4 ) 基于以上三方面工作，对传统决策树进行优化整合，分析了改进算法的流程， 并通过实验数据与c 4 5 算法进行比较，证明了该算法的优势 ( 5 ) 将上述算法应用于一个图像数据挖掘系统，对从图像中提取的特征数据进行 训练，生成决策树后，对新特征数据进行分类，透明度高，可移植性强，效 果较好 本项研究得到了“十一五”国家科技支撑计划重点项目“综合风险防范( 取g ) 关键技术研究与示范”( 2 0 0 6 b a d 2 0 8 0 2 ) 的支持 关键词：数据挖掘、决策树、离散化、属性降维、属性选择 西北大学硕士学位论文 a b s t r a c t r e s e a r c ha n da p p l i c a t i o no nt h ed e c i s i o nt r e ec l a s s i f i c a t i o n a l g o r i t h mo f d a t am i n i n g a b s t r a c t d e c i s i o nt r e ei st h em o s tu n i v e r s a lm o d e l s a d o p t e d i n a p p l i c a t i o no f c l a s s i f i c a t i o n c o m p a r e dt ot h en e u r a ln e t w o r k s ( n n ) a n db a y sm e t h o d ，i td o e s n t n e e dal o to f t i m ea n dh u n d r e d so fi t e r a t i o u st ot r a i nm o d e l sb u ts u i t a b l ef o r t h el a r g e s e to f d a t 乱m o r eo v e r , t h ec l a s s i f i c a t i o na e e n r a c yo f d e c i s i o nt r e ei sb e t t e rt h a no t h e r t e c h n i q u e s ，a n dt h ea l g o r i t h mn e e d sn oo t h e ri n f o r m a t i o nb u tt h et r a i n i n gd a t a i n f o r m a t i o n t h ec o l ei s s u eo fd e c i s i o nt r e ea l g o r i t h mi st h es t r a t e g yi nc h o o s i n gt e s t a t t r i b u t ea n dp r u n i n gt ot h ed e c i s i o nt r e e d i s e r e t i z a t i o nt h ec o n t i n u o u sa t t r i b u t e sa n d d i m e n s i o nr e d u c t i o nt ot h eh i g hd i m e n s i o nd a t aa r ec r i t i c a lt e c h n i q u e st oe x t e mt h e d e c i s i o nt r e ea l g o r i t h m sa p p l i c a t i o nd o m a i n b a s e do nt h ed e c i s i o nt r e e , t h em a i nr e s e a r c hc o n t e n t so f t h et h e s i sa sf o l l o w s ： ( 1 ) an o v e ld i m e n s i o nr e d u c t i o na l g o r i t h mi sp r o p o s e d f i r s t , t h ei m p o r t a n c eo fa l l t h ec o n d i t i o na t t r i b u t e si so r d e r e d t h e nt h ea t t r i b u t e sa r er e d u c e db yn nw h i c h n e e dn op r i o rk n o w l e d g ea n dh a v em 帆e f f i c i e n c yi nc l a s s i f i c a t i o n a n dt h e n s o m ea t t r i b u t e sa l es e l e c t e dt or e d u e et h ed i m e n s i o n , w h i c hh a v em o r ev a l i di n c l a s s i f y i n gd a t a ( 2 ) aw e i g h t e db i n a r ys e a r c ha l g o r i t h mi sp r o p o s e dt od i s c r e t ec o n t i n u o u sa t t r i b u t e s i ti s s i m p l e r , e a s i e rt oi m p l e r n e n t a t i o na n dm o r ee f f i c i e n c yt h a nt h ec l a s s i c a l b i m x ys e a r c ha l g o r i t h mw h i c hh a v et h es h o r t c o m i n g si ns i m p l yi np a r t i t i o nt h e a r e aa n d g e t t i n gi n t ot h el o c a lm a x i m u mp o i n t ( 3 ) a ni m p r o v e m e n ti nt h ea t t r i b u t es e l e c t i o nc r i t e r i o ni sp r o p o s e d i tc o n q u e r st h e s h o r t c o m i n g so fi d 3a n dc 4 5a l g o r i t h m sa td e f l e c t i o np r o b l e m si ns e l e c t i n g t e s t i n ga t t r i b u t e i th a sl e s sc o m p u t i n gt i m ea n di m p r o v i n gt h ec l a s s i f ye f f i c i e n c y o f d e c i s i o nt r e e c l a s s f i c a t o r 二( 4 ) b a s e do nt h ef o r m e rw o r k s ，o p t i m i z a t i o n ，a n dc o n f o r m i t yi sa p p l i e dt ot h e c l a s s i c a ld e c i s i o n 仃眈a ni m p r o v e m e n tt o a l g o r i t h mp r o c e d u r ei sp r o p o s e d c o m p a r i n gt o t h ec 4 5a l g o r i t h m ，e x p e r i m e n tr e s u l t ss h o wt h es u p e r i o r i t y 西北大学硕士学位论文 h b s 扛a c t ( 5 ) t h ea l g o r i t h mi sa p p l i e di na l li m a g ed a t a b a s ed a t am i n i n gs y s t e m i tt r a i n st h e c h a r a c t e r i s t i cd a t ae x t r a c t e df r o mt h ei m a g e , a n dt h e nad e c i s i o nt r e ei sc r e a t e d a tl a s tt h ed a t ai sc l a s s i f i e d t h er e s u l t sa l em o r et r a n s p a r e n c y , t r a n s p l a n ta n d v a l i d i t y t h er e s e a r c hw o r ki ss u p p o r t e db yk e yn a t i o n a ls c i e n c ea n dt e c h n o l o g yp r o j e c t o ft h e f i v e - y e a rp l a nk e yt e c h n o l o g yr e s e a r c ha n dd e m o n s t r a t i o no fi n t e g r a t e d 斑s k g u a r d i a n s ( n o 2 0 0 6 b a d 2 0 8 0 2 ) k e yw o r d ：d a t am i n i n g , d e c i s i o n 蛾d i s c r c t i z a t i o n , d i m e n s i o nr e d u c t i o n , a t t r i b u t e c h o o s i n g 西北大学硕士学位论文 n i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：三马 亚指导 二胡年6r7 强 l 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：码j 巨 川年6 月眨日 第一章绪论 1 1 本文研究背景 第一章绪论 我们生活在一个网络化的时代，通信、计算机和网络技术正改变着整个人类 和社会。如果用芯片集成度来衡量微电子技术，用c p u 处理速度来衡量计算机 技术，用信道传输速率来衡量通信技术，那么摩尔定律告诉我们，它们都是以每 1 8 个月翻一番的速度在增长，这一势头已经维持了十多年。在美国，广播达到 5 0 0 0 万户用了3 8 年；电视用了1 3 年；i n t e m e t 拨号上网达到5 0 0 0 万户仅用了4 年。全球m 网发展速度达到每6 个月翻一番，国内情况亦然。1 9 9 9 年初，中国 上网用户为2 1 0 万，现在已经达到6 0 0 多万网络的发展导致经济全球化，在 1 9 9 8 年全球产值排序前1 0 0 名中，跨国企业占了5 1 个，国家只占4 9 个因此 有人提出：对待一个跨国企业也许比对待一个国家还要重要在新世纪钟声刚刚 敲响之后，回顾往昔，人们不仅要问：就推动人类社会进步而言，历史上能与网 络技术相比拟的是什么技术呢? 有人甚至提出把网络技术与火的发明相比拟。火 的发明区别了动物和人，种种科学技术的重大发现扩展了自然人的体能、技能和 智能，而网络技术则大大提高了人的生存质量和素质，使人成为社会人、全球人 然而，现在的问题是：网络之后的下一个技术热点是什么? 让我们来看一些 身边俯拾即是的现象：纽约时报由6 0 年代的1 0 2 0 版扩张至现在的1 0 0 2 0 0 版，最高曾达1 5 7 2 版；北京青年报也已经是1 6 4 0 版；市场营销报已 达1 0 0 版但是在现实社会中，人均日阅读时间通常仅为3 0 4 5 分钟，只能浏 览一份2 4 版的报纸。大量信息在给人们带来方便的同时也带来了一大堆问题： 第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保 证；第四是信息形式不一致，难以统一处理人们开始提出一个新的口号：乌要 学会抛弃信息”同时开始考虑：“如何才能不被信息淹没，而从中及时发现有用 的知识、提高信息利用率? ”面对这一挑战，数据挖掘技术应运而生，并显示出 强大的生命力。 另一方面，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人 们积累的数据越来越多激增的数据背后隐藏着许多重要的信息，而目前的数据 西北大学硕士学位论文 第一章绪论 库技术虽然可以高效地实现数据的查询、统计等功能，但却无法发现数据中存在 的关系和规则，无法根据现有的数据预测未来的发展趋势。数据库中存在着大量 的数据，却缺乏挖掘数据背后隐藏的知识的手段，大量的数据似乎使人坠入茫茫 数据的汪洋大海之中，不知哪儿是边缘，哪儿是尽头，有用和无用的数据常常掺 杂在一起，难以分辨，以至于出现了“数据爆炸而知识贫乏”的现象。如果能把这 些信息从数据库中提取出来，则能为用户创造很多潜在的利润。若要提取有用的 信息，需花费大量的人力和时间，传统的数据库概念、方法和技术已经难以解决 现在的新问题。此外，若要从数据中发现和提取知识，更是一件不容易的事情， 而人们最希望的是能够让计算机自动智能地分析数据库中的大量数据，以获取信 息或知识 因此，数据库知识发现口1 ( k d d ) 及其核心技术数据挖掘p m ) 应运而生。 1 9 9 7 年，f r i e d m a n 列举了四个主要的技术理由更是激发了数据挖掘的开发、应 用和研究的兴趣：超大规模数据库的出现，例如商业数据仓库和计算机自动收集 的数据记录：先进的计算机技术，例如更快和更大的计算能力和并行体系结构； 对巨大量数据的快速访问；对这些数据应用精深的统计方法计算的能力 在数据挖掘技术中，决策树是一种简洁而又高效的方法。与神经网络和贝叶 斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，除了 训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。并以其 规则易于提取和容易理解的优点得到了广泛应用。然而，传统决策树在处理大容 量高维数据时的计算代价较高，因而影响了在此类问题中的应用。本文以决策树 为研究对象，对传统决策树进行了改进，从而决策树的应用范围。 1 2 数据挖掘研究现状 数据挖掘和知识发现o ( d d ) p 1 是近年来一个十分活跃的研究领域，逐渐己成 为研究热点和焦点之前，g a r m e rg r o u p 的一次高级技术调查将数据挖掘和人 工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且 还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两纯。篙戳 i t 根据最近g a r t n c 的h p c 研究表明【l l = 随着数据捕获、传输和存储技术的快 西北大学硕士学位论文 2 第一章绪论 速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更 为广阔的并行处理系统来创建新的商业增长点”。美国麻省理工学院2 0 0 1 年1 月 份的科技评论( t e c h n o l o g yr e v i e w ) 杂志提出将在未来5 年对人类产生重大影 响的1 0 大新兴技术，其中第三项就是“数据挖掘”。 从数据库中发现知识( k d d ) 一词首先出现在1 9 8 9 年举行的第十一届国 际联合人工智能学术会议( u c a d 上从1 9 8 9 年到1 9 9 4 年举行了四次k d d 的国际研讨会在此基础上，1 9 9 5 年召开了第一届知识发现与数据挖掘的国际 学术会议1 9 9 8 年建立了新的学术组织a c m s i g m o d ，即a c m 下的数据库中 的知识发现专业组( s p e c i a li n t e r e s t e dg r o u po nk n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。 1 9 9 9 年a c m - s i g m o d 组织了第五届知识发现与数据挖掘国际学术会议 0 c , d d 9 9 ) ，专题杂志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 l u w e r s 出版社出版此外，还有一些国际和地区性数据挖掘会议，如“知识发现 与数据挖掘太平洋亚洲会议 ( p a k i ) d ) ，“数据库中的知识发现原理与实践欧洲会 议”f p k d d ) ，“数据仓库与知识发现国际会议 ( d a w a k ) ， a c m - s i g m o d 数据管 理国际会议 ( s i g m o d ) ，“超大型数据库国际会议 ( v l d b ) ， a c m - s i g m o d - s i g a r t 数据库原理研讨会 ( p o d s ) ，“数据工程国际会 议 ( i c d t ) ，“扩展数据库技术国际会议 0 s d b t ) ，“数据库理论国际会议 0 c i ) a 9 ， “信息与知识管理国际会议( c ( m ) ；“数据库与专家系统应用国际研讨 会 ( d e x a ) ，“数据库系统高级应用国际会议 ( d a s f a a ) ，人工智能国际联合会 t i ( u c a i ) ，“美国人工智能学会会议 ( a a a d 等等到目前为止，由美国人工智 能协会主办的k d d 国际研讨会已召开了多次，规模由原来的专题讨论会发展到 国际学术大会。以k d d 国际会议为例，1 9 9 5 年与会代表3 5 0 人、展示软件6 套；1 9 9 6 年与会代表4 5 7 人、展示软件1 8 套：1 9 9 7 年到会5 7 7 人、展示软件 2 6 套；1 9 9 8 年就有7 7 3 人到会，展示软件3 9 套平均会议代表年增长率为4 0 另外，仅以1 9 9 9 年为例，就有近2 0 个国际会议列有k d d m 的专题。如c f 9 9 、 c i m c a 9 9 、d a w a k 9 9 、d i s c o v e r ys c i e n c e l 9 9 9 、e u r o - p a r 9 9 、i d a - 9 9 、i s s m i s 9 9 、 j s m 9 9 、k d d 9 9 、p k d d 9 9 、r s f d g r c 9 9 、d s 9 9 、v l d b 9 9 、u c a i - 9 9 、s i g m o d 9 p a d d 9 9 、c i m c a 9 9 、p a k d d 9 9 等。近几年，从事数据挖掘研发的人员遍布世 界8 0 多个国家，数据挖掘的研究重点也已从算法研究向具体应用过渡，从实验 西北大学硕士学位论文3 第一章绪论 室原型走向商品化阶段。1 9 9 9 年，国际上从事数据挖掘产品研发的软件公司已 从1 9 8 9 年的几个公司，猛增为上百家公司，每年都有若干软件产品推出。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国 家自然科学基金首次支持对该领域的研究项目t 2 1 ，1 9 9 9 年，第三届p a k d d ( p a c i f i c - a s i ac o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 会议在北京召 开更是加快了国内在该领域的研究步伐。目前，国内的许多科研单位和高等院校 竞相开展数据挖掘的基础理论及其应用研究，如清华大学、中科院计算技术研究 所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊 方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体 代数的研究，华中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学 研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和改造；南京大学、 四川大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘 1 3 决策树算法的应用 数据挖掘技术从一开始就是面向应用的决策树作为其一个分校更是如此。 目前已经有许多开发商可以提供支持决策树方法的软件产品。i s o f l 公司的a c 2 是一个相当流行的决策树分析算法。l s o f t 已与b u s s i n e s so b j e c t s 公司达成合作协 议，根据协议，b u s s i n e s so b j e c t s 公司将负责销售包含有i s o f t 决策树方法的数据 挖掘模块s p s s 公司向市场上销售的是一种基于s i - c h a i d 算法的数据挖掘产 品其他许多开发商则采用了将几种算法组合到一起的方法以增强其产品的性 能此外，还有许多综合了多种数据挖掘方法的软件包也都可以支持决策树算法， 这类产品的例子包括：m m 公司的i n t e l l i g e n tm i l l e t 和c l e m e n t i n e ， t h i n k i n g m a c h i n e 公司的d a r w i n 以及s i l i c o ng r a p h i c 公司的m i n e s e t 等。 k n o w l e d g e s e e k e r 是一个由a n g o s s 公司开发的基于决策树的数据分析程 序该程序具有相当完整的分类树分析功能。k n o w l e d g e s e e k e r 采用了两种著 名的决策树分析算法：c h a d 硼i c a r t 算法。c h a i d 算法可用来对于分类性数：、 据( 如患者属于哪个州或患者的性别) 进行挖掘。c a r t 算法则可对连续型因变量 西北大学硕士学位论文 4 第一章绪论 ( 如月度支出0 1 0 0 0 美元，1 0 0 0 2 0 0 0 美元及2 0 0 0 美元以上) 进行处理。此外 还有其他几种可满足商业用途的决策树分析算法a n g o s s 公司在增强这些算法 的用户友好性方面做了大量工作。 a n g o s s 公司已经宣布，该公司已与一家专门研制终端用户查询工具和决策 支持系统的开发商a n d y n e 公司达成了一项合作协议。根据协议，双方将联合开 拓k n o w l e d g e s e e k e r 的市场。为使其技术能够成为市场主流，a n g o s s 公司己 在积极寻求多方合作伙伴。例如，c u s t o m e ri n s i g h t 公司( 一家数据库营销工具供 应商) 已签署协议将成为k n o w l e d g e s e e k e r 的增值销售商。此外，a n g o s s 公司 还签署了为i n f o r m i x 的通用服务器开发d a t a b l a d e ( 数据刀片) 模块的协议。 a n g o s s 公司己就其产品可以解决的各种各样的问题作了广泛宣传，同时还给出 了其产品在许多行业中实际应用的例子这些例子包括：i s r 将使用 k n o w l e d g e s e e k e r 分析与税务申报有关的各种重要因素并对发生骗税的可能性 进行预测。加拿大读者文摘在研究市场划分以及成本预测方面使用了a n g o s s 的 产品。华盛顿邮报使用k n o w l e d g e s e e k e r 来指导其市场营销。位于伦敦的牛律 移民中心使用a n g o s s 的产品对肯尼亚移民状况进行分析。k n o w l e d g e s e e k e r 被惠普公司用于生产控制系统的规则分析。加拿大帝国商业银行使用a n g o s s 的 产品进行风险控制。 1 4 本文组织结构 本文共分为七章，第一章为本文绪论部分，分析了本文的选题背景，讨论了 数据挖掘的研究现状，介绍了决策树算法的应用，最后介绍了本文的组织结构。 第二章决策树算法研究，首先介绍了几种常见的分类算法，然后分析了决策树的 原理、构造、简化过程以及剪枝算法，总结了决策树剪枝优化时应遵循的原则， 最后分析了经典的几种决策树算法，给出了几种常用决策树算法的优劣评价。第 三章决策树改进研究，从三个方面对决策树进行了改进优化：( 1 ) 分析了降维问 题，先对属性按重要性排序，再引入神经网络对排序结果裁减降维；( 2 ) 讨论了 连续属性离散化问题，并提出了加权二分查找的思想来进行连续属性离散化o ( 3 ) ， 对决策树属性选择标准进行了研究，提出了决策树属性选择标准的改进方法。第 西北大学硕士学位论文 5 第一章绪论 四章决策树优化整合，将神经网络和决策树相结合，提出了一种数据分类新方法。 该方法首先将所有条件属性进行属性重要性排序，再利用神经网络不需先验知识 的“黑箱”分类特点，及其分类效能高的优势，对属性进行裁减降维，选择出对数 据分类最有效的若干属性。对于连续属性，通过加权二分查找法进行离散化最 后在建立决策树时，采用改进后的属性选择标准来选择属性对样本进行分类。后 面简单介绍了该算法分类器设计的流程，给出了应用举例，通过与c 4 5 比较， 说明了该算法的优势。第五章在一个图像数据挖掘系统中对上述算法进行了设 计，简要介绍了总体流程、训练流程、分类流程，数据流转过程和开发运行环境。 第六章总结与展望，主要总结了论文的研究工作，提出了进一步研究方向 西北大学硕士学位论文 6 第二章决策树分类算法研究 第二章决策树分类算法研究 数据挖掘分类中流行的几个技术是贝叶斯分类、神经网络、遗传算法和决策 树等。与神经网络和贝叶斯分类相比，决策树更容易让人理解。而且，训练一个 神经网络将花费大量的时间和进行上千次的迭代，生成一个决策树就要有效的 多，因此适用于大的训练集。还有，决策树生成算法除了包含在训练数据中的信 息外不要求其他的信息( 例如领域知识或数据，类的概率分布的预知信息) 。最后， 与其他技术相比，决策树还表现了很好的分类精确度。 2 1 常见分类算法 数据挖掘的一个重要应用是对大量数据的分类能力，又定义为挖掘分类规 则分类和预测是两种数据分析形式，可以用于提取描述重要数据类的数据模型 或预测未来的趋势。分类是预测分类标号( 离散值) ，而预测是建立连续值函数模 型。分类问题也是机器学习、模式识别、专家系统、统计学和神经生物学的研究 领域，并己开发出许多相应的算法，如决策树方法、统计学方法、贝叶斯方法、 人工神经网络、粗糙集、基于数据库的方法及其它的分类方法等 2 1 1 决策树 决策树算法是数据挖掘领域研究分类问题最常采用的方法，其原因有三：一 是决策树构造的分类器易于理解，二是采用决策树分类，其速度快于其它分类方 法，三是采用决策树的分类方法得到的分类准确性优予其它方法利用决策树分 类通常分为两步生成树和剪技。树的生成采用自上而下的递归分治法，而剪 枝则是剪去那些可能增大树的错误预测率的分枝。生成最优决策树的问题是n p 难的目前，决策树算法通过启发式属性选择策略来实现。决策树方法中最为著 名的算法是q u i n l a a 提出的i d 3 算法 4 1 ，该算法以信息熵的增益进行属性选择， 增益率能克服增益偏向于多值属性的特点c a r t 算法则采用基于最小距离的 g i n ii n d e x 标准和为了克服g i n i 在处理多类问题上的困难而进行的改进1 5 1 i d 3 及后续版本c 4 5 n 、c 5 0 是使用广泛的决策树算法，还有许多其它选择属性的方 西北大学硕士学位论文 7 第二章决策树分类算法研究 法，如矿统计、c - s e p 、m d l 7 等决策树分类的其它算法还有f a c t 、q u e s t 、 c h a i d 及1 1 ) 3 的增量版本i d 4 和1 1 ) 5 等1 8 - - 1 2 】 一些研究者对决策树在超大规模数据集中的应用做了研究。提出了一些可扩 展的算法，如s l i q 算法【1 3 】采用预排序技术以避免将所有数据放入内存的尴尬， 方便了对大数据集的处理，同时采用的最小描述长度( m d l ) 剪枝算法，可以提高 树的精度和有效性。s p r i n t 算法【1 4 】中引入了并行性，具有良好的可扩展性和效 率。传统的决策树算法一般只对一个属性进行分类，b r o d l e y 和u t g o f f 研究了构 造多元决策树的问题，提出了一些构造多元决策树的方法【1 5 】 p u b l i c 算法1 1 6 】是由b e l l 实验室的r a j e e v r e s t o g i 和k y u s e o ks h i m 提出的， 该算法改进了决策树分类器，将剪枝过程和树的生成过程集成，如果一个结点将 会在剪枝时被剪去，则不扩展该结点，算法改善了决策树分类器的性能。c a t l e t t 提出了在分类树的每个结点上样本化的方法，但这样的算法必须将数据库中的数 据全部装入内存【切。由于现有数据库中的大量数据无法一次性的放入内存，c h a r t 和s t o l f o 提出了将数据集划分为子集，只需将子集放入内存，该算法虽然适合于 对大数据集进行分类，但其分类质量比将数据库一次性放入内存，用一个分类器 进行分类的质量差【1 8 lr a i n f o r e s t 1 9 1 是一种快速构造决策树的方法，该算法研究 了c 4 5 、c a r t 、c h a i d 、f a c t 、i d 3 及其扩展算法、s l i q 、s p r i n t 和q u e s t 等算法，提出了一种快速构造决策树的框架，r a i n f o r e s t 算法比s p r i n t 算法的 速度快，具有良好的可伸缩性。 2 1 2 贝叶斯方法 贝叶斯分类是一种基于统计学的分类方法，可以预测一个类成员关系的可能 性，即给定样本属于一个特定类的概率。数据挖掘领域主要使用两种贝叶斯方法， 即朴素贝叶斯方法和贝叶斯网络方法前者使用贝叶斯公式进行预测，把从训练 样本中计算出的各个属性值与类别频率之比作为先验概率，并假定各个属性之间 是独立的，然后利用贝叶斯公式及有关概率公式计算各实例的条件概率值，并选 取其中概率值最大的类别作为预测值此方法简单易行且精度较好。后者是一个 带注释的有向无环图，以有效表示大变量集的联合概率分布。适用于分析大量变 西北大学硕士学位论文 3 第二章决策树分类算法研究 量之间的相互关系，利用贝叶斯公式的学习和推理能力，实现预测、分类等数据 挖掘任务。事实上，贝叶斯网络也是一种适合表示不确定性知识的方法。贝叶斯 网络的构造涉及网络结构和网络参数两部分的学习。但是获得最优结构和参数都 是n p 难的，因此出现了许多启发式的方法。 d u d a 和h a r t 给出了关于贝叶斯分类的全面介绍，朴素贝叶斯分类器 2 0 1 ( n 劭 是一种成功的分类方法，已用于许多领域的分类问题，也出现了一些对朴素贝叶 斯分类方法扩展的算法，大多数算法放松了对类条件独立的假设。k d b 算法利 用参数k 构造一个贝叶斯分类器，其中每个属性最多依赖k 个其它的属性。选 择贝叶斯分类器预处理数据集，通过删除冗余属性来选择特征子集。可调节概率 的n b 算法为每个分类给出了一个权值，利用可调节的概率估计进行分类 n b t r c e 算法则是一种混合的算法，将贝叶斯分类器与决策树方法结合，利用决 策树将实例空间划分成区域，再利用贝叶斯分类器处理每个域n b i b e 算法的 分类准确性好于单纯的n b 算法和决策树算法后来，b o u t i l i e r 等人提出了一种 特定上下文的独立性假设，即变量间的独立性关系只在一定的上下文中成立。 m e r e t a k i s 等人提出了一种算法，利用长项集扩展贝叶斯分类器，并将其称为l b 算法( l a r g eb a y e s ) ，算法性能优于朴素贝叶斯分类器【2 l i u 等人提出了一种类 似于l b 的算法，将关联规则挖掘和分类挖掘集成，利用关联规则产生一个分类 器及分类规则集，使用启发式方法进行修剪圈此外，h e c k e t m a n 给出了贝叶斯 信念网络的介绍i 矧，r u s s e l l 和n o r v i g 给出了利用信念网络进行推理归纳的方法 嗍。k d d 9 9 上，d a v i e s 和m o o r e 提出了利用贝叶斯网络处理具有分类属性的大 项集，进行无损的数据压缩瑙l 。贝叶斯理论已用于文档分类、医疗诊断、预测、 推理和归纳等数据挖掘应用中。 2 1 3 神经网络 神经网络的研究已经取得了许多方面的进展和成果，提出了大量的网络模 型，发现了许多学习算法，人工神经网络在模式分类、机器视觉、机器听觉、智 能计算、机器人控制、信号处理、组合优化求解、医学诊断、数据挖掘等领域具 有很好的应用 西北大学硕士学位论文 9 第二章决策树分类算法研究 神经网络可分为四种类型，即前向型、反馈型、随机型和自组织型。前向神 经网络是数据挖掘中广为应用的一类网络，其原理和算法也是其它一些网络的基 础。神经网络具有对噪声数据的承受能力，尤其是它对未经训练的数据的分类能 力实验表明，神经网络在某些分类问题上具有比符号方法更好的表现，但是神 经网络没有很好地用于数据挖掘的原因在于无法获得显式的规则。近来已经出现 了一些由训练过的神经网络提取规则的一些算法，如k b a n n 等。 近年来，神经网络用于数据挖掘分类的研究逐渐增多，l a i n 和l e e 讨论 了利用人工神经网络构造文本分类器及维数削减的方法f 2 6 】，g u p t a 等人分析了现 有神经网络算法用于分类等问题的现状，认为尽管神经网络在预测精度、鲁棒性、 无需数据分布的假设等方面具有优势，但是在决定合适的网络结构、训练参数， 结果解释及训练时间长等方面仍有许多困难，从而提出了一种规则抽取框架，以 解决神经网络提取的规则缺乏可解释性的问题。f u 则提出了一种新的神经网络 模型，用于从经验数据中归纳符号知识，通过基于事实的激励函数，改善了网络 的泛化能力h a t a n o 等人提出了一种应用于超文本数据的分类视图机制，通过 自组织映射( s o m ) 和搜索引擎交互式的进行w e b 文档的分樊2 7 1 目前，神经网 络作为一种自适应、自学习的算法模型在数据挖掘中已经有一些成功的应用。 2 1 4 支持矢置机 支持矢量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是v a p n i k 根据统计学习理论提出 的一种新的学习方法，近来受到国际学术界的重视。s 讲2 8 1 建立在计算学习理 论的结构风险最小化的原则之上，可以提高学习机的泛化能力。s v m 的复杂度 与实例集的维数无关，适合于两分类问题和线性不可分问题，因为它可将样本空 间映射到一个高维空间，使原来线性不可分的情况在高维空间中解决。现在数据 挖掘领域已经开始使用s v m 原理，构造一些数据预处理算法及挖掘算法，如 s y e d 、l i u 和s u n g 提出了两种增量学习方法，给出了三种评价增量学习算法的 鲁棒性和可行性的标准，并使用s v m 的增量学习算法进行概念提升，证明了得 到的支撑矢量可以形成个简洁而充分的集合由于s v m 可以选择和保存有用 的训练数据即支持矢量，取自大型数据库中的小样本的训练数据可使计算的复杂 西北大学硕士学位论文 1 0 第二章决策树分类算法研究 度降低。所以，s v m 方法可用于数据预处理、样本化等k d d 的过程，也可用于 其它的数据挖掘应用。研究表明：对同一数据库，使用不同核函数训练的s v m ， 在测试数据上均具有较高的预测准确率。 2 1 5 其它方法 除了上述方法外，分类还可以使用k 最邻近分类、基于案例的推理( c a r ) 、 遗传算法、粗糙集和模糊集方法。一般地，商品化的数据挖掘软件中很少使用这 些方法因为k - 最邻近方法要求存储所有的样本，数据集较大时无法使用该方 法，而基于案例的推理、粗糙集方法和遗传算法尚处于成长阶段。还有许多值得 研究的问题。 给定一个样本，k _ 最邻近分类法搜索模式空间，找出最接近未知样本的k 个训练样本，即k 个近邻。临近性可以由欧几里德距离定义。未知样本可以被 分配到k 个最邻近者中最公共的类。最邻近分类是基于要求的或懒散的学习方 法，即它存放所有的训练样本，并且直到新的样本需要分类时才建立分类有关 k 最邻近算法用于数据挖掘的研究已有许多文章 c b r 是基于要求的方法，其存放的样本或案例是复杂的符号描述给定一 个待分类的新案例时，基于案例的推理首先检查是否存在一个同样的训练案例。 如果有，则返回附在该案例上的解。如果没有，则基于案例推理将搜索具有类似 于新案例成分的训练案例，即视为新案例的邻近者基于案例的推理的研究方向 是寻找一种好的相似性度量，探索训练案例索引的有效技术和组合解的方法这 种方法也可与知识库系统集成，杨炳儒等人研究了k d d 与双库协同的机理。 遗传算法和进化计算是基予生物学优胜劣汰、自然进化机理的研究领域，适 合于并行优化问题和数据分类，将免疫机制与遗传算法和进化计算集成用于数据 挖掘问题是一个新的挑战，文 2 9 1 利用免疫算法解决了t s p 闯题等，研究利用神 经网络、遗传算法、进化计算的集成进行数据挖掘是一个新的方向 粗糙集方法也可以用于分类问题，尤其适合于发现不准确数据或噪声数据内 在的结构和联系。它主要用于离散值属性的数据，一般地，对于连续型属性应在 处理前离散化。在数据挖掘中使用租糙集的介绍见文 3 0 , 3 1 1 ，文 3 2 - 3 3 讨论了 西北大学硕士学位论文 第二章决策树分类算法研究 利用粗糙集理论实现特征归约和知识库系统的问题，文 3 4 1 提出了约简问题的分 层约简算法。模糊逻辑也是进行数据挖掘的理论和工具之一，由于模糊逻辑可以 处理不精确的知识，进行不精确的推理，所以，模糊逻辑与神经网络、遗传算法 等集成用于数据挖掘，也是未来的研究方向。 2 2 决策树算法 决策树分类采用自顶向下的贪婪算法，在每个结点选择分类效果最好的属性 对样本进行分类，继续这一过程直到这棵树能准确地分类训练样本，或所有的属 性都已被使用过。通常还需要对决策树进行剪枝处理，以限制决策树的规模来提 高预测精度。决策树算法的核心问题是在每个结点选取要测试的属性，以及对决 策树进行剪枝。传统的属性选择标准有信息增益、信息增益率、g i n i 索引、z 2 相 依表统计等等； 一个决策树包含零个或多个内部节点和一个或多个叶子节点。全部的内部节 点有两个或更多的子节点。所有的内部节点包含一个划分，这个划分是测试的数 字或逻辑表达式的值连接内部节点和它的子节点的边用测试的不同输出来标 注。每一个叶子有一个相关联的类树的建立一般都是通过在内部节点选择一个 最优的测试属性对训练集反复地划分并建立下一级的节点，直到每个划分都只包 含同一种类的样本为止，这时称这个划分是纯的( p u r e ) 。这个最终的纯划分形成 了叶节点下面是构造决策树的一般性描述： ( 1 ) 开始是一个训练集和空树，接着对当前节点应用该节点的测试将其划分； ( 2 ) 如果所有当前节点的训练样本属于同一个类别，创建一个带有该类标签的叶 子节点并停止； ( 3 ) 否则，用最优测量( g o o d n 龉sm e a s u r e ) 计算每个集合的每个可能的划分； ( 4 ) 选择最优划分作为当前节点的测试。刨建与该划分的不同输出数同样多的子 节点； ( 5 ) 使用该划分的输出标注父亲和儿