（计算机应用技术专业论文）决策树分类算法优化研究.pdf

摘要数据挖掘是指从数据库中抽取隐含的、具有潜在使用价值信息的过程，是一种新型的数据分析技术，己被广泛应用于金融、保险、政府、教育、运输以及国防等领域。数据分类是数据挖掘中一个重要的内容。分类存在很多方法，其中决策树算法是以实例为基础的归纳学习算法，以其易于提取显式规则、计算量相对较小、可以显示重要的决策属性和较高的分类准确率等优点而得到广泛的应用。据统计，目前决策树算法是利用最广泛的数据挖掘算法之一。然而在实际应用过程中，现存的决策树算法也存在着很多不足之处，如计算效率低下、多值偏向等。因此，迸一步改进决策树，提高决策树的性能，使其更加适合数据挖掘技术的应用要求具有重要的理论和实际意义。本文针对上述数据库知识发现的不足，进行深入的研究，探索数据挖掘中决策树分类的组合优化算法，以便更好地提高分类的准确性。应用于实际工作中，主要研究工作如下：首先，从宏观上介绍了数据挖掘和分类技术的理论基础，并重点对决策树算法进行了分析和比较。然后，提出了一种新的适合于高维数据库的组合优化决策树算法。相比于传统的分类算法，该算法从降维、属性选择、可扩展性和剪枝等方面进行了改进。其中最主要是提出基于加权属性协调度并结合简化预剪枝策略的决策树算法d t b a c 算法，以及加强算法可扩展性的f a v c 集。最后，着重介绍了所研发的组合优化决策树分类器系统。它以d t b a c 算法为核心算法生成分类器，并应用到医学领域对病人进行分类。通过对比分析发现，d t b a c 算法在总体性能上要优于目前被广泛采用的i d 3 算法。关键词数据挖掘，分类，决策树算法，i d 3 ，d t b a ca b s t r a c td a t am i n i n gm e a n st h ep r o c e s so fe x t r a c t i n gc r y p t i ca n dp o t e n t i a lh e l p f u li n f o r m a t i o nf r o mam a s so fd a t a i ti so n ek i n do fb r a n dn e wd a t aa n a l y s i st e c h n o l o g ya n dp o p u l a ri 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 dn a t i o n a ld e f e n s ee t c 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 si nd 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 dt h ed e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h mb a s e so nt h ei n s t a n c e sa m o n g s tt h e s ei sw i d e l yu s e dw i t hi t sa d v a n t a g e so fc o n v e n i e n c ef o rg e t t i n ga 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 nc 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 nc o r r e c t n e s se t c d e c i s i o nt r e ea l g o r i t h mi sc u r r e n t l yo n eo ft h em o s tp o p u l a ri nd a t am i n i n ga l g o r i t h m sa c c o r d i n gt or e l a t e ds t a t i s t i c s t h e r ei ss o m ei s s u e si nt h em o s te x i s t e n td e c i s i o nt r e ea l g o r i t h m s ，w h i l ea p p l i e dt ot h er e a l i t yt a s k s ，n a m e l ym u l t i - v a l u eb i a s ，l o w e re f f i c i e n t l yi nc o m p u t a t i o ne t c t h e r e f o r e ，i tp o s s e s s e si m p o r t a n tt h e o r e t i ca n df a c t u a ls i g n i f i c a n c et om a k ef u r t h e ri m p r o v e m e n ta n dr a i s et h ep e r f o r m a n c ef o rd e c i s i o nt r e e ，s oa st om a k ed e c i s i o nt r e em o r es u i t a b l ef o rt h er e q u i r e m e n to ft h ef a c t u a la p p l i c a t i o n t h i sa r t i c l ed e e p l ym a k e sr e s e a r c h e sa i m i n ga tt h ea b o v e - r e l a t e dd a t ab a s ek n o w l e d g ed i s c o v e r yi s s u e s ，a n dt h ep u r p o s ei st op r o b ei n t oo p t i m i z a t i o na n dc o m b i n a t i o no fd e c i s i o nt r e ei nd a t am i n i n g ，i no r d e rt ob ea p p l i e dt ot h er e a l i t yt a s k s t h ei n v o l v e dc o n t e n t se x i s ta sf o l l o w ：f i r s t l y ，t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r yo fd a t am i n i n ga n dc l a s s i f i c a t i o nt e c h n o l o g ym a c r o s c o p i c a l l y ，a n da n a l y s i s e sa n dc o m p a r i s o n so fd e c i s i o nt r e ea l g o r i t h m sw e t ee s p e c i a l l ye m p h a s i z e do n s e c o n d l y ，ac o m b i n e do p t i m i z a t i o nd e c i s i o nt r e ea l g o r i t h mt h a ti ss u i t a b l ef o rm u l t i - d i m e n s i o nd a t a b a s ei sp r o p o s e d c o m p a r e dw i t ht r a d i t i o n a lc l a s s i f i c a t i o na l g o r i t h m s ，t h ea l g o r i t h mm a k e si m p r o v e m e n t sf r o ms e v e r a la s p e c t s ：r e d u c i n gd i m e n s i o n ，a t t r i b u t es e l e c t i o n ，s c a l a b i l i t y ，p r u n i n ge t c t h em a i np o i n ta r et h a tt h i sp a p e rp r o p o s e san e wd e c i s i o nt r e ea 1 9 0 r i t h m ，d t b a ca l g o r i t h m ，w h i c hi sb a s e do nw e i g h e da t t r i b u t e sc o n s i s t e n c v & o p t i m i z a t i o np r u n i n g ，a n dt h ef a v cs e tw h i c he n h a n c e st h ea l g o r i t h ms c a l a b i l i t y f i n a l l v ，ac o m b i n e do p t i m i z a t i o nd e c i s i o nt r e ec l a s s i f i e ru s i n gad t b a ca l g o r i t h mi sd e v e l o p e d ，w h i c hh a sb e e nu s e di nm e d i c i n ef i e l dt oc l a s s i f i c a t i o np a t i e n t a n a l y s i sr e s u l t ss h o wt h a td t b a ca l g o r i t h mi sb e t t e ri nm a n va s p e c t st h a ni d 3a l g o r i t h mw h i c hi sw i d e l yu s e di nm a n yf i e l d sc u r r e n t l y k e yw o r d sd a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o nt r e ea l g o r i t h m ，i d 3 d t b a cm原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：! i ：盗丞日期：丕盟年月卫日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：麓鲢导师签名重雄日期：鱼孚年上月生日硕士学位论文第一章绪论1 1 选题背景和意义第一章绪论随着人类活动能力的增强，以及科学技术的进步，人们能以更快速更容易更廉价的方式获取和存储数据，这就使得数据及其信息量以指数方式增长。早在二十世纪八十年代，据粗略估算，全球信息量每隔二十个月就增加一倍。而进入九十年代，全世界所拥有的数据库及其所存储的数据规模增长更快，据估计，1 9 9 3年全球数据存贮容量约为二千t b 到2 0 0 0 年增加到三百万t b ，面对这极度膨胀的数据量，人们受到“信息爆炸”、“混沌信息空间”和“数据过剩”的巨大压力。大量激增的数据中往往隐藏着许多重要的信息，如果能把这些信息从大量的数据中提取出来，就能为为人类服务并能创造价值。因此，对大量历史数据进行分析处理，挖掘出有用的知识就显得非常迫切。传统的查询技术不能解决目前面临的信息爆炸问题，如何有效地管理，怎样才能有效地利用数据库中数据，以及怎样才能发现其潜在的知识，这就需要有新的、更为有效的手段来对各种数据源整理并进行挖掘，以发现新的知识并发挥这些数据的潜能。数据挖掘正是在这样的信息大爆炸的时代需求下产生并迅速发展起来的一门技术。目前分类和预测技术是数据挖掘中被广泛研究的课题，并且己经广泛地应用于许多领域，如对电信、银行、保险、零售、医疗等诸多行业提供决策支持，并对未来商业和人们的生活也将产生深远的影响。分类研究在国外发展很快，己有很多成型的算法和模型，而在国内发展相对滞后。在数据挖掘中可用于分类的算法很多，如决策树、贝叶斯分类、规则推理、遗传算法和神经网络等，其中决策树方法应用最为广泛。主要有以下原因；决策树算法的复杂度较小，速度快；决策树算法的抗噪声能力强；决策树算法的可伸缩性强，既可用于小数据集，也可用于海量数据集。正因为如此，决策树算法也就成为数据挖掘研究中最活跃的领域之。因此本文选择基于决策树的分类挖掘方法作为研究课题。图1 - 1 给出了决策树的一般形式，从形式上看决策树是一个类似于流程图的有向图，但它与流程图有本质的区别。流程图表达的是一个过程，而决策树表达的则是知识。如图1 - 1 所示，决策树由节点和分支组成，其中节点又分为内节点和叶节点。每一个内节点，如图中的n i ，n 2 1 ，n 2 2 ，代表一个属性；每一个叶节点，如图中的l 1 ，l 2 ，l 3 ，代表一个类别；每一个分支，如图中的r 1 ，t 2 ，硕士学位论文第一章绪论r 3 ，f 4 ，r 5 ，代表属性上的一个测试值。图1 - 1 决策树的一般形式使用决策树表达知识直观而简洁。从决策树中可以直接观察出属性之间的相对重要性。从决策树的根节点开始，沿着每一条路径向下，属性对于分类的重要性逐渐下降。不同的决策树算法有其不同的特性，充分认识各算法的优点和存在的缺点，掌握其特定的适用环境，便于研究者明确对算法的改进点和研究的方向，也便于使用者选择和应用。本文着眼于不同决策树算法的典型代表，分析比较各自的特性为读者提供有益的借鉴。1 2 国内外研究的现状从第一个具有实用价值的决策树算法的提出到今天决策树算法被广泛应用于各个领域，决策树算法的发展经历了一个由简单到复杂、由浅显到深入的过程。以下是国内外决策树算法发展过程中的一些重要进展。最早的决策树学习系统要追溯到h u n t 等人于1 9 6 6 年研制的一个概念学习系统i l j ( c l s ：c o n c e p tl e a r n i n gs y s t e m ) ，该系统第一次提出使用决策树进行概念学习，是许多决策树学习算法的基础。1 9 7 9 年，j r q u i n l a n 提出的迭代分类器( i d 3 ：i t e r a t i v ed i c h o t o m i z c r3 ) 算法【2 j是决策树算法的代表。它采用分治策略，在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，以便在每一个非叶节点上进行测试时，能获得关于被测试记录最大的类别信息。1 i ) 3 算法的贡献在于把信息论中信息熵的概念引入了决策树算法中。1 9 8 3 年，a p a t t e r s o n 和t n i b l e t t 扩展了i d 3 算法，提出了类似概念学习系统( a c l s ：a n a l o gc o n c e p tl e a r n i n gs y s t e m ) 算法1 3 ，a c l s 算法的主要改进是允许属性取任意的整数值。这种改进极大地扩展了决策树算法的应用范围，使决策2硕士学位论文第一章绪论树可以处理一些比较复杂的任务，比如图像识别等。1 9 8 4 年，l b r e i m a n 等人提出了分类及回退树( c a r t ；c l a s s i f i c a t i o na n dr e g r e s s i o n t r e e ) 算法【4 1 。这种方法选择具有最小g i n i 指数值的属性作为测试属性，生成最终二叉树，再利用重采样技术进行误差估计和剪枝，然后选择最优的作为最终构建的决策树。这些算法均要求训练集全部或一部分在分类过程中一直驻留在内存中。1 9 8 4 年，l b r e i m a n 和j f r e i d m a n 等人提出了决策树剪枝的概念，并提出了叫做误差复杂性剪枝( e c p ：e r r o r - c o m p l e x i t yp r u n i n g ) l 拘剪枝方法【4 】。因为用于生成决策树的训练集一般都存在噪声数据，而噪声数据会导致决策树过度复杂。决策树剪枝方法的出现极大地改善了决策树的性能。之后，不断有新的剪枝算法提出：1 9 8 6 年，t n i b l e t t 提出了最小错误率剪枝( m e p ：m i n i m u m - e r r o r p r u n i n g ) 的剪枝方法1 9 8 7 年j m i n g e r s 提出了临界值剪枝( c v p ：c r i t i c a lv a l u ep r u n i n g )的剪枝方法 6 1 ；同年，j r o u i n l a n 提出了减少错误剪枝( r e p ：r e d u c e d e r r o rp r u n i n g ) 的剪枝方法n1 9 9 2 年，k k i r a 和l r e n d e u 提出了基于属性问依赖性的r e l i e f 算法1 8 j 。r e l i e f 算法的提出是决策树算法发展史中的一座里程碑，因为它通过考虑“邻居”实例而把数据集中的局部信息引入到决策树算法中，局部信息的优势在于它能够在其它属性的背景下评估每一个属性，而此前的决策树算法都只能单独地评估每一个属性，忽略了属性间可能存在的关联f 9 1 。1 9 9 3 年，j r q u i n l a n 又提出了c 4 5 算法【1 0 】，旨在克服i d 3 算法在应用中的不足。c 4 5 算法对于i d 3 算法的重要改进是使用信息增益率来选择属性。c a 5算法能处理连续值属性的数据，这弥补了i d 3 算法只能处理离散值属性数据的缺陷。同时还可用于增量式学习，随着数据量的增加动态地调整决策树，克服了i d 3算法在这个方面的缺点，增量式学习对于在线任务非常有意义。1 9 9 4 年，i k o n o n e n k 把r e l i e f 算法扩展为属性间相关性过滤( r e l i e f f ：r e l i e ff i l t e r ) 算法1 1 1 】，r e l i e f f 算法对特征集中每一特征赋予一定的权重，它克服了r e l i e f 只能处理两类问题的缺点，可以处理多类问题。1 9 9 6 年，m m e h t a 和r a g r a w a l 等人提出了一种高速可伸缩的有监督的寻找学习( s l i q ：s u p e r v i s e dl e a r n i n gi nq u e s t ) 分类方法【1 2 l 。s l i q 针对数据量远大于内存容量的情况采用了类表、属性表以及类直方图三种数据结构，利用换入换出策略处理大数据量。在建树阶段，对连续属性采取预排序技术与广度优先相结合的策略生成树，对离散属性采取快速的求子集算法确定划分条件。3硕士学位论文第一章绪论1 9 9 6 年，j s h a r e r 和r a g r a w a i 等人提出可伸缩并行归纳决策树( s p r i n t ：s c a l a b l ep a r a l l e l i z a b l ei n d u c t i o no fd e c i s i o nn e c s l 分类方澍”l ，继s l i q 分类方法后提出的又一种规模可变的、支持并行计算的分类方法。s p r i n t 分类方法最大的优点就是可以避免内存空问的限制，利用多个并行处理器构造一个稳定的、分类准确率很高的决策树，具有很好的可伸缩性，扩容性，但该算法因使用属性列表，使得存储代价大大增加，并且节点分割处理的过程较为复杂，加大了系统的负担。1 9 9 7 年，1 k o n o n e n k o 和e s i m e c 把r e l i e f 进一步扩展为r r e l i e f f 算法1 1 4 ，r r e l i e f f 不但可以处理多类问题，而且可以处理连续类问题，即回归问题。1 9 9 7 年，g e o f f r e y1 w e b b 对生成的决策树进行了嫁接处理【1 5 】。所谓嫁接是剪枝的逆过程，是指在决策树构建完成之后，按照一定的策略适当的添加一些节点，来提高决策树的分类正确率。1 9 9 8 年，r r a s t o g i 等人提出一种将建树和修剪相结合( p u b l i c ：a d e c i s i o nt r e et h a ti n t e g r a t e sb u i l d i n ga n dp r u n i n g ) 分类算法【1 6 l ，该算法提出了节点代价的目标函数，其主要思想是在决策树建立阶段，计算每个节点相关的目标函数值，估计该节点在将来调整阶段是否被删除。如果该节点将被删除，则不对该节点迸行扩张，否则，扩展该节点。从而建树和修剪阶段结合成为一个阶段，而不是依次执行这两个阶段，提高了决策树的执行效率。1 9 9 8 年，j g e h r k e 和r r a m a k r i s h n a n 等人提出雨林( r a i n f 0 r e s t ) 分类方澍1 7 i ，它是一种针对大规模数据集，快速构造决策树的分类框架。r a i n f o r e s t 分类框架的核心思想是根据每一次计算所能使用的内存空间，合理地调整每次计算所处理的数据集的大小，使r a i n f o r e s t 框架内所使用的分类方法在每次计算的过程中，对内存资源的利用率达到最大，在有限的资源下，用最少的时间完成决策树的构建。2 0 0 2 年，s r u g g i e r i 提出了c 4 5 的改进算法一高效c 4 5 ( e c 4 5 ：e f f i c i e n tc 4 5 3算法【竭1 。e c 4 5 算法采用二分搜索取代线性搜索，还提出几种不同的寻找连续属性的局部阈值的改进策略。实验表明，在生成同样一棵决策树时，与c 4 5 相比，e c 4 5 可将效率提高5 倍，但e c 4 5 占用内存比c 4 5 多【1 9 1 。2 0 0 3 年，c o l a r u 提出一种新的模糊决策树分类方法一软决策树【2 0 1 。软决策树综合决策树的生成和修剪来决定其本身的结构，并利用重修和磨合来提高树的归纳能力，因此软决策树比一般决策树的正确率要高。国内的不少学者也在决策树算法上进行了深入的研究，并取得了不少的成4硕士学位论文第一章绪论果。从改进1 d 3 算法的角度：1 9 9 8 年，刘小虎博士和李生教授f 2 l j 提出，决策树优化是决策树学习算法中十分重要的分支。以i d 3 为基础，提出改进的递归信息增益优化算法。每当选择一个新的属性时，算法不仅仅是考虑该属性带来的信息增益，还需要考虑至0 该属性后选择的属性带来的信息增益，即同时考虑树的两层节点。2 0 0 1 年，郭茂祖博士和刘扬教授【2 2 时对i d 3 多值偏向的缺陷，提出了一种新的基于属性一值对为内节点的决策树归纳算法a v p i ，它所产生的决策树大小及测试速度均优于i d 3 。从构造机制的角度：1 9 9 9 年，吴菲和黄梯云教授f 2 3 1 提出利用二元决策树实现模型选择，并采用遗传算法构造二元决策树并提出了遗传算法基于二元决策树的模型选择方法，以趋势预测模型为例进行了验证，获得了较好的效果。2 0 0 5年，张拈等l 提出一种基于遗传算法的多重决策树组合分类方法，该算法与单个决策树相比，具有更高的分类精度。从多变量模糊决策树的角度：2 0 0 5 年，黄定轩等1 2 5 】提出一类加权连续属性的多变量决策树构造方法，首先利用粗糙集理论和模糊聚类理论确定连续多变量属性的选择问题，然后利用聚类中心算法建立等级标准中心以解决连续变量的区间划分问题，其次将等价关系相对泛化的概念用于决策树中多变量检验的构造。2 0 0 6 年，张曙红教授等2 6 】给出了一种面向连续值属性的模糊粗糙集决策树分析方法。该方法基于模糊聚类对连续属性进行离散化，并通过计算模糊隶属度矩阵中条件属性和类属性之间的模糊依赖性量度来确定属性的重要性和发现冗余属性。从新的决策树构造方法的角度：2 0 0 3 年，杨宏伟博士和王熙照教授等【2 7 悃基于层次分解的方法通过产生多层决策树来处理多类问题。2 0 0 6 ，阳东升博士等脚1 通过对组织协作网与决策树的描述分析提出了组织结构设计的新思路一基于决策个体在任务上的协作关系设计最佳的决策树。1 3 决策树算法研究的发展趋势通过仔细考察上述决策树算法研究的发展过程，可以发现决策树算法研究的发展呈现出以下趋势：1 提高决策树的分类精度决策树的分类精度一直是研究的重点，判断各种决策树的生成算法和剪枝算5硕士学位论文第章绪论法的优劣，精度是最重要的衡量指标。决策树剪枝是为了减小数据噪声对决策树的影响，构造多变量决策树是为了减小其规模，它们的最终目的都是为了提高决策树的精度；同时，嫁接技术正是基于提高决策树的分类精度而提出的。2 减少决策树算法对数据集的约束首先，对数据集中属性的取值约束逐渐减少。比如，在i d 3 算法中属性只能在有限集中取值，到a c l s 算法时属性可以在整数集中取值，到a s s i s t a n t 算法时属性可以在实数集中取值。其次，数据集中的类别数目逐渐增加。比如，r e l i e f 算法只能处理两类问题，其扩展算法r e l i e f f 算法就可以处理多类问题，到r r l i e f f 算法时就己经可以处理连续类问题了。对数据集的约束的减少会扩大决策树算法的应用范围。3 决策树技术与其他技术的结合在知识发现中，不可能用一种方法处理所有的数据集，完成各种数据挖掘任务，需要研究同其它方法相结合的问题。并且，决策树方法本身也可以和其它方法结合，如把决策树方法同神经网络技术、模糊集理论、遗传算法等相结合来进行研究，结果不同程度地提高了处理效率和精度。4 决策树技术的软件实现将决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术，一直是大家努力的方向。1 4 本文的主要工作本文研究工作源于上述的背景，主要目的是对决策树算法进行深入的研究，并在前人基础上对算法加以改进以更好的应用于实际工作中，主要工作归纳起来有以下几点：( 1 )介绍了课题背景和决策树算法的研究现状。对数据挖掘基本理论以及分类方法做了较深入的分析。在此基础上对决策树算法进行深入研究，通过吸取不同典型算法的优点，来对后面提出的组合优化算法提供理论基础。( 3 )总结决策树算法的缺点，通过对构造决策树过程中的预处理、属性选择和剪枝策略等主要环节进行组合优化，提出一种基于加权协调度的属性选择标6硕士学位论文第一章绪论准的决策树算法d t b a c 算法。( 4 )从面向对象的观点出发，在c + + b u i l d c r 6 0 平台上构建基于组合优化算法的决策树分类器系统。并通过相关的实验数据对改进的算法进行了模拟实验，从性能上对d t b a c 算法与i d 3 算法进行了比较。1 5 本文的结构本文韵组织结构如下：第一章为绪论部分。对选题的意义、国内外的研究历史及决策树算法发展趋势进行综合论述。第二章从宏观上介绍数据挖掘和分类技术的理论基础，为后面研究决策树算法奠定理论基础。第三章详细介绍决策树算法的内容。包括决策树算法中的基本概念、决策树算法中的主要过程、决策树算法主要研究的问题，并对典型的决策树生成算法进行了分析和比较。本文所提出的组合决策树优化算法也是通过提取这些典型算法的优点而成的。第四章分析了决策树算法的缺点，通过对构造决策树过程中的预处理、属性选择和剪枝策略等主要环节进行组合优化，重点在于提出一种基于加权协调度的属性选择标准。第五章介绍以d t b a c 算法为核心的组合优化决策树分类器系统的设计和实现过程，并将d t b a c 算法应用到医学领域中的病人分类中，与i d 3 算法进行了性能比较。接着以美国加利福尼亚大学l r v i n e 分校( u c i ) 提供的部分标准数据集1 2 9 1 进行大型数据集的实验。通过实验分析，组合优化决策树算法提高了算法的效率、预测精度和规则简明性，更适合于高维数据的处理。最后，概括了本文的主要研究结果，分析存在的问题，指出有待进一步解决的问题。7硕士学位论文第二章数据挖掘及其分类方法分析第二章数据挖掘及其分类方法分析随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及，人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类服务，业已成为广大信息科技工作者所重点关注的焦点之一。为有效解决这一问题，自二十世纪8 0 年代开始，数据挖掘技术逐步发展起来。而分类作为数据挖掘中的一个重要的方法，目前的研究在商业上应用最多。本章主要介绍数据挖掘和分类技术的基本理论。本文所研究的决策树算法是分类的一种重要方法，同时也是一种典型的数据挖掘技术，要更好的理解决策树算法，需要了解数据挖掘和分类的相关理论。2 1 数据挖掘的理论2 1 1 数据挖掘的概念数据挖掘，简单地讲就是从大量数据中挖掘或抽取出知识，它是- f l 交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从大量数据中提炼有价值的信息，为决燕提供支持。数据挖掘，又称为数据库中的知识发现，简称k d d ，是一个从大量数据中抽取出未知的、有价值的模式或规律的复杂过程。典型的k d d 过程包括：数据准备、数据清洗、数据集成、数据转换、数据挖掘、模式评估和知识表现六个环节。尽管数据挖掘只是整个知识发现过程的一个重要步骤，但是已经在工业界、媒体和数据库研究领域中，广义的表示为整个知识发掘过程。2 i 2 数据挖掘的功能数据挖掘的目标是从大量数据中，发现隐藏于其后的规律或数据问的关系，从而服务于决策。利用数据挖掘技术可以帮助获得决策所需的多种知识。在许多情况下，用户并不知道数据中存在着哪些有价值的知识，因此对于一个数据挖掘系统而言，它应该能够同时搜索发现多种模式的知识，以满足用户的期望和实际需要。数据挖掘的主要功能以及所能够挖掘出的知识类型描述如下。1 数据总结8硕十学位论文第二章数据挖掘及其分类方法分析数据总结目的是对数据进行浓缩，给出它的总体综合描述。通过数据总结，数据挖掘能够将数据库中的有关数据从较低的个体层次抽象总结到较高的总体层次上，从而实现对原始基本数据的总体把握。传统的也是最简单的数据总结方法利用统计学中的方法计算出数据库的各个数据项的总和、平均、方差、最大值、最小值等基本描述统计量。或者利用统计图形工具，对数据制作直方图、饼状图等。利用o l a p 技术实现数据的多维查询也是一种广泛使用的数据总结的方法。2 分类和预测分类的主要功能是通过构建并利用分类模型，该模型能够根据数据的属性将数据分派到不同的组中。预测的目的是从历史数据记录中自动推导出给定数据的推广描述，从而能对未来数据进行预测。分类可以用来预测数据对象的类别，也可以用来预测数据对象的某些未知的属性值。尽管预测可以涉及到属性值预测和类别预测，但通常预测仅限于数值预测，并因此不同于分类。在分类和预测之前可能需要进行相关分析，相关分析的作用是识别对于分类和预测无关的属性，并排除这些属性。本文的研究决策树算法就是一种最为典型的分类方法。3 关联分析关联分析的目的是找出数据库中隐藏的关联网，描述一组数据项目的密切度或关系。有时并不知道数据库中数据的关联是否存在精确的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有置信度，置信度级别度量了关联规则的强度。数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间存在某种规律性。这种关联关系有简单关联和时序关联两种。时序关联在简单关联中增加了时间属性。关联分析模型的一个典型例子是购物篮分析，通过对顾客购买偏好的分析，确定商品促销的目标客户，以此来设计各种商品促销的方案，并通过商品购买关联分析的结果，采用交叉销售和向上销售的方法，挖掘客户的购买力，实现准确的商品促销。4 聚类分析聚类是把物理或抽象对象的集合分成由类似的对象组成的多个类组的过程，即“物以类聚”。它的目的是使得属于同一类别的对象之间的具有较高的相似性，9硕十学位论文第二章数据挖掘及其分类方法分析而不同类别上的对象差别较大。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法等。聚类方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。在机器学习中，聚类称作无指导归纳。和分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。5 孤立点分析对孤立点数据的分析处理通常就称为孤立点挖掘。一个数据库中的数据一般不可能都符合分类预j 受j l 或聚类分析所获得的模型。那些不符合由大多数数据对象所构成的模型的数据对象就被称为孤立点。许多数据挖掘方法在正式进行数据挖掘之前，就将这些孤立点作为噪声或意外而排除在数据挖掘的分析处理范围之外。2 1 3 数据挖掘的步骤1 数据挖掘环境数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的，有效的，可实用的信息，并使用这些信息做出决策或丰富知识。数据挖掘环境可示意如图2 1 所示：廿恒丑翟一德图2 - 1 数据挖掘环境2 数据挖掘步骤数据挖掘的步骤可粗略的分为：问题的定义、数据收集与预处理、数据挖掘算法执行以及结果的解释和评估。数据挖掘过程是一个循环反复的螺旋处理过程，每一个步骤一旦与预期目标不符，都要回到前面的步骤，重新调整，重新执行。其主要步骤大致如下：( 1 )问题的定义。清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘1 0硕 学位论文第1 二章数据挖靠 f 及其分类方法分析的重要一步，也是最重要的一个阶段。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性，是不会成功的。所以在定义问题过程中，数据挖掘人员必须和领域专家以及最终用户紧密协作，对问题进行深入的分析，以确定可能的解决途径和对学习结果的评测方法。( 2 )数据准备。数据的准备又分为三个步骤：数据的选择、预处理和转换。数据的选择。搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的数据。在数据选择过程中可以利用数据库的查询功能以加快数据的选择速度。数据的预处理。研究数据的质量，为进一步的分析作准备。并确定将要进行的挖掘操作的类型。数据的转换。将转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立一个真正数据适合挖掘算法的分析模型是数据挖掘成功的关键。( 3 )数据挖掘。根据选定的知识发现算法对所得到的经过转换的数据进行挖掘，形成特点的知识形式。例如，分类的算法，本文在下节将重点讨论。( 4 )结果的解释和评估。解释并评估结果，其使用的分析方法一般根据数据挖掘操作而定，通常会用到可视化技术，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为：“i f t h e n ”规则。整个挖掘过程是一个不断反馈的过程，如果用户对挖掘结果评估不满意，需要重复先前的过程，甚至重新开始。2 2 分类的概念及算法描述2 2 1 分类概念分类和聚类不同，聚类是在特定的类标示下寻求新元素属于哪个类，而分类是已知现存的类别，要建立类别的描述规则，并对新例的观察值判别归类。在机器学习中聚类被称为无指导学习，分类被称为有指导学 - jr 3 0 l 。分类的目的是构建和利用分类函数或分类模型( 分类器) 。该模型能把数据库中的数据映射到给定类别中的某一个1 3 0 l 。而本文研究的决策树算法是通过构造一棵决策树分类器，并根据决策树生成的规则对新的实例进行分类，在第五章会详细介绍以本文提出的组合优化算法为核心的决策树分类器的设计和实现。为了更好的理解分类的概念，下面给出分类器的一般定义。硕十学位论文第二章数据挖掘及其分类方法分析定义2 1 给出一个数据库d = ，如， 和一组类c = c l ，c 2 ，q ，分类问题是去确定一个：d 斗c ，每个分组l ，被分配到一个类中a 一个类q 包含映射到该类中的所有元组，即q = i ( t ) = q ，l i n ，而且t 。d 。一般来说分类分为建模和分类两个步骤，如图2 - 2 所示：图2 - 2 用决策树算法进行分类的过程第一步：建模，构建分类器，找到合适的训练函数h ：f ( x ) - - , c 的表示模型来描述预定的数据类集或概念集。构造的主要方法有决策树、贝叶斯网、神经网络等。第二步：使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型，对数据集中的每一类别进行描述，形成分类预测。2 2 2 典型的分类算法描述目前，针对分类问题已有了若干不同领域方法的算法，如统计学、机器学习、神经网络和粗糙集理论等。按照各种算法的技术特点，将其分成决策树分类、贝叶斯分类、基于关联规则的分类以及基于数据库技术的分类等几类算法。本节除了简单介绍本文研究的决策树算法，同时也给出其他分类算法的介绍供比较分析。1 决策树算法决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则，通常用来形成分类器和预测模型，可以对未知数据进行分类或预测、数据挖掘等。它包括两个步骤：第1 2硕士学位论文第二章数据挖掘及其分类方法分析一步是利用训练样本集来建立并精化出一棵决策树，建立决策树模型。这个过程实际上是个从数据中获取知识，进行机器学习的过程。通常分为两个阶段：建树和剪枝。第二步是利用建好的决策树对新的数据进行分类。决策树算法不要求使用者掌握应用领域的知识，完全通过训练集自动构建分类器对未知数据进行分类或预测，并且决策树很容易转换为分类规则，原理简单容易理解。因此决策树算法在实际应用中最为广泛。关于决策树算法的研究在第三章中进行详细的介绍。2 遗传算法遗传算法是模拟生物进化过程的全局优化方法【3 ”，将较劣的初始解通过一组遗传算子，在求解空间按一定的随机规则迭代搜索，直到求得问题的最优解。遗传算法具有的隐含并行性、易于和其它模型结合等性质，使得它涉足于数据挖掘领域，表现在以下几个方面：用它和b p 算法结合训练神经网络，然后从网络提取规则；分类系统的设计，目前研究重点是一些基本的设计方法，如编码方式，信任分配函数的设计以及遗传算法的改进上。遗传算法存在的问题是算法较复杂，还有收敛于局部极小的过早收敛等难题未得到解决。3 神经网络算法神经网络1 3 2 是一种很好的函数逼近工具，在过去十几年里取得了飞速的发展，研究出了很多模型及其改进，如b p ，h o p f i e l d ，a r t ，r n n ，k b a n n ，r b f等。神经网络中的知识可解释为规则，其规则提取的第一步是网络剪枝，通过剪去对训练网络影响最小的加权链简化网络结构，剪枝简化后的网络可进行链、单元或活跃值的聚类。发现处于每个隐藏单元的共同活跃值的集合。分析每个隐藏单元的这些活跃值，导出涉及这些活跃值与对应输出单元值组合的规则。类似地导出输入和隐减单元层联系的规则，再结合这两个规则集合形成i f t h e n 规则。4 贝叶斯分类贝叶斯分类是统计学分类方法。它基于贝叶斯定理，可以预测类成员关系的可能性。通过对分类算法的比较发现，一种称作朴素贝叶斯分类3 3 1 的简单贝叶斯分类算法可以与判定树和神经网络算法相媲美。用于大型的数据库，贝叶斯分类表现出高准确率和高速度。5 基于概念格分类r w i l i e 等人根据二元关系建立的概念格是一种完备的层次结构p 4 j ，在本质上描述了对象与属性之间的联系，表明了概念之问泛化与例化的关系。硕十学位论文第二章数据挖掘及其分类方法分析概念格p 4 是基于二元关系构造的，作为知识的一种表示形式，有助于挖掘概念问的各种规则。概念是把所感知的事物的共同本质特点抽象出来，并加以概括。概念都具有内涵和外延。基于概念的这种理解，r w i l l e 在1 9 8 2 年首先提出根据二元关系柬构造相应概念格的思想，也称为形式概念分析，就是以概念格中的每个节点表示一个形式概念，其中概念的外延代表相应的一组对象，内涵则为这组对象所具有的公共特征；而概念格所对应的哈斯图则形象地揭示了概念i 日j 的泛化和例化关系，反映出一种概念层次结构，实现了对数据的可视化，非常适用于从数据库中进行知识挖掘，从而成为数据分析和规则提取的一种有效工具。6 其他分类方法其它的分类方法主要有以下三种方法：a r c s 方法是基于聚类挖掘关联规则，然后利用关联规则进行分类，其算法的准确率可以和c 4 5 相当，而其时间性能比c 4 5 更优【3 5 】。关联分类方法是根据有关的置信度条件寻找“精确的”规则，然后用这些规则排序，再利用这些规则来进行分类。c a e p ( 聚类显露模式分类) ，首先使用支持度挖掘显露模式，再用这些显露模式进行分类。2 3 评估分类模型准确性的尺度与方法2 3 1 评估分类模型准确性的尺度每种分类方法都需要通过一定的指标来对其进行评估，以确定其可用性。通常对分类模型准确性的评估，有以下几种分类器评价尺度3 6 】：( 1 ) 可伸缩性。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是海量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。( 2 )强壮性。涉及