（计算机软件与理论专业论文）决策树算法在贴片机生产数据挖掘中的应用研究.pdf

摘要 摘要 随着数据库技术的迅速发展，数据库中存储的数据已经远远超越了人类理 解力所能达到的范围。对这些数据进行全面系统的分析，挖掘出这些数据中蕴 藏着的知识已经成为一项极具挑战性的任务，我们迫切地需要一种新技术来帮 助我们智能的从这些数据中提取出蕴藏在其中的知识。数据挖掘技术就是在这 样的背景下产生并发展起来的。 本文首先介绍了数据库技术的发展和数据挖掘技术的产生，之后对数据挖 掘技术进行了详细的阐述，包括数据挖掘的起源，发展，定义等，同时对数据 挖掘中的主要技术如决策树，关联规则，聚类分析，粗糙集理论，贝叶斯分类， 人工神经网络等进行了介绍。 本课题是实验室与日本s o r u n 公司合作的国际合作项目，我们所用数据 是由s o r u n 公司提供的贴片机生产数据。贴片机在长期生产电子芯片过程中 积累了大量的数据，在这些数据的背后往往存在着一些不易被发现的知识， s o r u n 公司希望我们把这些数据利用起来，通过对这些数据全面系统地挖掘， 得到一些能够帮助提高生产效率的知识。 s o r u n 公司希望我们可以提供易于理解的挖掘结果。在数据挖掘领域的 众多技术当中，由于决策树技术具有可以生成比较直观易懂的规则并且计算量 相对不是很大的特点，我们决定采用决策树技术对贴片机生产数据进行应用研 究。在阐述了贴片机生产数据的预处理过程和决策树技术的基本思想之后，我 们详细地介绍了三种应用最为广泛的决策树算法叫d 3 算法，c 4 5 算法，分 类回归树c a r t 算法。然后我们设计了对比实验，在贴片机生产数据中对比这 三种决策树算法的准确性，以帮助我们选取一种最为适合在贴片机生产数据中 应用的算法。 通过i d 3 算法，c 4 5 算法和分类回归树c a r t 算法的对比实验，我们得到 如下结论： 首先，这三种决策树算法在贴片机生产数据上的准确性分布基本一致。 其次，这三种决策树算法的准确性随着测试训练比的增加先增加后减小。 北京t 业大学t 学硕- ：学位论文 准确性在达到最大值以前迅速增加。在达到最大值以后缓慢下降。测试训练比 值为1 1 6 7 时，准确性达到最大值。 最后，这三种算法构造的决策树在构造过程的准确性要比在测试过程的准 确性高六到七个百分点。 由于本课题是实际课题，贴片机生产数据量很大，分类回归树c a r t 算法 除了与i d 3 算法和c 4 5 算法的准确性基本一致以外，它还是商品化最为成熟的 算法，能够可靠地处理数据量很大的真实数据。它也是三种决策树算法中，唯 一能够在给出规则的同时给出其准确性概率的算法，这对于厂方认识规则的准 确性也是很有帮助的，所以我们选取分类回归树c a r t 算法作为我们的挖掘算 法。 我们使用分类回归树c a r t 算法对贴片机生产数据进行了全面系统的数据 挖掘，得到了一些能够帮助用户提高贴片机生产效率降低生产成本的知识，并 将这些知识以树型结构简明易懂地呈现给用户，使用户可以更好的理解这些知 识。 最后，我们对本课题所做的工作进行了总结，并对将来我们可以继续研究 的内容进行了展望。 关键词数据挖掘；决策树；分类回归树c a r t 算法 a b s t r a c t a b s tr a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g y , t h ed a t as t o r e di nt h e d a t a b a s eh a sf a rb e y o n dt h es c o p eo fh u m a nc o m p r e h e n s i o n i th a sb e c o m ea c h a l l e n g i n gt a s kt os y s t e m a t i c a l l ya n dr o u n d l ya n a l y z et h ed a t a ，a n dm i n eo u tt h e k n o w l e d g ec o n t a i n e di nt h ed a t a d a t am i n i n gt e c h n o l o g ye m e r g e n c ea n dd e v e l o p u n d e rt h i sk i n do fb a c k g r o u n d i nt h i sp a p e r , f i r s t l y , w ei n t r o d u c et h ed e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n d t h ea p p e a r a n c eo fd a t am i n i n g a f t e r t h a t ，w ei n t r o d u c et h ed a t am i n i n gt e c h n o l o g y i nd e t a i l ，s u c ha st h eo r i g i n ，t h ed e v e l o p m e n t ，a n dt h ed e f i n i t i o n i nt h es a m et i m e ， w ed e s c r i b et h em a i nt e c h n o l o g yi nd a t am i n i n ga r e a ，f o ri n s t a n c ed e c i s i o nt r e e ， a s s o c i a t i o nr u l e ，c l u s t e ra n a l y s i s ，f u z z yt h e o r y , b a y e s i a nc l a s s i f i c a t i o n ，n e u r a l n e t w o r k t h i si sa ni n t e r n a t i o n a lc o o p e r a t ep r o je c tb yo u rl a b o r a t o r ya n daj a p a n e s e c o m p a n yn a m e ds o r u n t h ed a t au s e di no u rp r o j e c ti st h ep r o d u c t i o nd a t ao f m o u n t e r s u p p l i e db ys o r u n m o u n t e r m a c h i n ea c c u m u l a t eag r e a td e a lo f d a t ai nt h ec o u r s eo fp r o d u c t i o nc h i p i tt e n dt oh i d es o m ek n o w l e d g eb e h i n dt h e d a t a s o r u nh o p ew ec a r lu s et h ed a t a , a n dg e ts o m ek n o w l e d g ew h i c hc a nh e l p i m p r o v et h ep r o d u c t i o ne f f i c i e n c yb ym i n i n gt h i sd a t as y s t e m a t i c a l l ya n dr o u n d l y s o r u nh o p ew ec a ns u p p l yc o m p r e h e n s i b l er e s u l t d u r i n gt h et e c h n o l o g i e s i nd a t am i n i n gw ed e c i d et oc h o o s ed e c i s i o nt r e et e c h n o l o g yt od os o m ea p p l y i n g r e s e a r c hi nt h ep r o d u c t i o nd a t ao fm o u n t e r b e c a u s ed e c i s i o nt r e et e c h n o l o g yc a n g e n e r a t et h ec o m p r e h e n s i b l ea n di n t u i t i o n i s t i cr u l ea n dn e e dr e l a t i v el e s sc a l c u l a t i o n a f t e re x p o u n d e dt h ep r e p r o c e s s i n gp r o c e d u r ea n dt h eb a s i ci d e ao fd e c i s i o nt r e e t e c h n o l o g y , w ei n t r o d u c et h r e ek i n d so fw i d e l yu s e dd e c i s i o nt r e ea l g o r i t h m si n d e t a i l - 一i d 3 ，c 4 5 ，c a r t a f t e rt h a t ，w ed e s i g nt h ec o m p a r ee x p e r i m e n tt oc o n t r a s t t h ev e r a c i t yo ft h e s ea l g o r i t h m s ，i no r d e rt oh e l pu ss e l e c tt h em o s ts u i t a b l ea l g o r i t h m t ob eu s e di nt h ep r o d u c t i o nd a t ao fm o u n t e r i i i 北京t 业大学t 学硕十学位论文 鼍皇皇曼曼曼量量璺皇曼曼曼苎mm m 曼曼皇曼皇曼曼量 b yt h ec o m p a r ee x p e r i m e n t , w ef o u n dt h a t ： f i r s t l y , i ng e n e r a lt h ev e r a c i t yd i s t r i b u t i o no ft h e s et h r e ek i n d so fd e c i s i o nt r e e a l g o r i t h m si sc o n s i s t e n t s e c o n d l y ，州t ht h ei n c r e a s eo ft h e ，m 之，t h ev e r a c i t yd i s t r i b u t i o no ft h e s et h r e e k i n d so fd e c i s i o nt r e ea l g o r i t h m si n c r e a s e ，a n dt h e nd e c r e a s e b e f o r et h ev e r a c i t y r e a c h e st h em a x ，i ti n c r e a s e ss h a r p l y a f t e rt h ev e r a c i t yr e a c h e st h em a x ，i td e c r e a s e s s l o w l y a tl a s t ，t h ev e r a c i t yo ft h et h e s et h r e ek i n d so fd e c i s i o nt r e ea l g o r i t h m si nt h e c o l l r s eo fc o n s t r u c t i o ne x c e e d 6t o7c e n t i g r a d et h a ni nt h ec o u r s eo ft e s t a st h i si sap r a c t i c a lp r o j e c t ，t h ea m o u n to fp r o d u c t i o nd a t ai sv e r yl a r g e i n t e r m so ft h ee x p e r i m e n tr e s u l t ，c a r ta l g o r i t h mh a sc o n s i s t e n ta c c u r a c yw i t hi d 3 a n dc 4 5 i na d d i t i o n ，c a r ti st h em o s tm a t u r ea l g o r i t h mu s e di nb u s i n e s s i tc a n d e a l 、i mt h er e a ld a t ar e l i a b l y i nt h e s et h r e ek i n d so fa l g o r i t h m c a r ti st h eo n l y w h i c hc a ng e n e r a t et h er u l e sw i t ht h ea c c u r a t ep r o b a b i l i t y t h i si sa l s oh e l p f u lf o r s o r u nt or e a l i z et h er u l e sv e r a c i t y f i n a l l y , w ec h o o s ec a r ta l g o r i t h m 嬲o u r m i n i n ga l g o r i t h m 。w ea p p l yc a r ta l g o r i t h mt o m i n et h ep r o d u c t i o nd a t ao f m o u n t e rr o u n d l ya n ds y s t e m a t i c a l l y , a n dg e ts o m ek n o w l e d g ew h i c hc a l lh e l p n s e rt oi m p r o v et h ep r o d u c t i o ne f f i c i e n c yo fm o u n t e ra n dd e c r e a s et h ec o s t w e u s eat r e es t r u c t u r et or e p r e s e n tt h ek n o w l e d g ec o m p r e h e n s i b l ya n dc o n c i s e l y , i n o r d e rt om a k et h eu s e rc o m p r e h e n dt h ek n o w l e d g eb e t t e r a tl a s t ，w es u m m a r i z eo u rw o r ki nt h i sp a p e r , a n dp r o s p e c tt h ec o n t e n tt h a tw e c a nc o n t i n u eo u rr e s e a r c h k e y w o r d sd a t am i n i n g ；d e c i s i o nt r e e ；c l a s s i f i c a t i o na n dr e g r e s s i o nt r e ea l g o r i t h m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鲻日期：坦星笸：，主 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：奎疆 导师签名： 第1 章绪论 1 1 研究背景 第1 章绪论 2 0 世纪6 0 年代以来，随着数据库技术的出现，数据信息技术已经从主文 件处理系统转变为先进强大的数据库系统。7 0 年代以后，数据库系统已经从早 期的网格结构发展成为全新的关系结构，数据以数据表的形式存储在关系数据 库中，用户可以通过使用查询语言和用户接口等途径方便灵活的访问数据库中 的数据【l 。随后出现的在线交易处理( o n l i n et r a n s a c t i o np r o c e s so l t p ) 技术将 对数据库的一次查询操作看作一次只读交易，从而使关系数据库成为一种高效 存储检索大型数据库的技术而被大众认可。8 0 年代中期以后，数据库以关系结 构为主要特征已经为大众所广泛接受【4 1 4 2 1 。 随着数据库技术的不断发展与进步，面向应用的数据库系统也应运而生， 主要包括：空间数据库，时间数据库，多媒体数据库，流数据库，科学工程数 据库等。在这些面向应用的数据库迅速发展的同时，数据库科研工作者对数据 库中的数据分布，数据共享等基本问题也都进行了全面充分的研究。基于w w w 的因特网全球信息系统经过2 0 多年的迅速发展，已经成为了信息产业中十分重 要的一部分【4 3 】。 在过去的3 0 年中，计算机硬件技术一直在迅速稳定地向前发展着，这使得 计算机的成本不断下降，并为数据库提供了强大的存储介质和存储设备。这些 功能强大的数据库为我们进行交易管理，信息检索，数据分析等提供了强有力 的技术支持。随着数据库技术的不断发展，出现了一种新的数据存储形势一 数据仓库。由于数据仓库的出现，使得多种异类数据源能够以一致图表的形式 存储在数据仓库中。通过数据仓库和在线处理分析技术，我们可以从不同的角 度观察数据。这为我们更好地观察理解数据，并由此做出决策提供了极大的方 便【l l 】。 尽管如此，随着数据库数据仓库技术的飞速发展，存储在其中的数据量的 迅速增长，数据库数据仓库中存储的数据已经远远超过了我们人类理解力所能 北京丁业大学1 = 学硕一 ：学位论文 达到的范围【3 8 】，如w o r l dw i d ew ，e b 中的数据在以指数速度增长着【l o l 。这些数据 的不断积累，导致了数据库和数据仓库中存储了海量的数据，这样大量的数据 存储在巨大数据库数据仓库中却很少被访问。这就造成了重要决策的做出是基 于决策者个人的直觉，而不是基于存储在数据库中蕴含着丰富有价值信息的数 据。在这种数据丰富而知识贫乏的矛盾中，对这些数据进行高效的分析，挖掘 出这些数据中蕴藏着的有价值的知识和信息已经成为一项极具挑战性的任务， 我们迫切地需要一种新技术来帮助我们智能的从这些海量数据中提取出蕴藏在 其中的有价值的知识和信息。数据挖掘技术就是在这种情况下应运而生的【1 2 】。 经过2 0 多年的发展，数据挖掘技术已经有了长足的进步，成为了一个极具活力 的研究领域，我们可以利用数据挖掘中的各种技术帮助我们从数据库的数据中 高效自动的分析提取出隐藏在数据背后的不易被发现的知识和信息，来帮助我 们进行正确决策避免在实际工作和生产中受到损失【1 3 】。 1 2 课题的主要研究内容 本文主要针对贴片机生产数据挖掘进行了应用研究，通过对比实验，研究 了三种应用最为广泛的决策树算法i d 3 ( i t e r 撕v ed i c h o t o m i s e r ) 算法，c 4 5 算 法( i d 3 算法的变体) ，分类回归树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 nt r e e s ) 算法 在贴片机生产数据中的准确性关系。我们希望可以通过对这些算法在贴片机生 产数据中准确性的比较，最适合于在贴片机生产数据中应用的决策树算法。对 贴片机生产数据进行全面系统的数据挖掘。提取出隐藏在这些生产数据背后的 对生产有帮助的知识，以直观易懂的树型结构呈现给用户，帮助用户优化生产 过程，提高贴片机的生产的效率降低生产成本。 1 3 本文的组织 本文在绪论中首先介绍了课题的研究背景，数据库技术的演变和数据挖掘 技术等，然后介绍了本文主要的研究内容以及本文的组织结构。本文共分为五 章，分别是：第一章绪论；第二章数据挖掘综述；第三章贴片机生产数 据的预处理；第四章决策树算法在贴片机生产数据分析中的应用研究；第五 章分类回归树算法在贴片机生产数据分析中的应用。 第1 章绪论 第二章是数据挖掘综述。我们对数据挖掘技术进行了详细的介绍，主要包 括数据挖掘的起源，发展，定义等，并对数据挖掘中的主要技术如：决策树， 关联规则，聚类，粗糙集理论，贝叶斯分类，神经网络进行了介绍。 第三章是贴片机生产数据的预处理。我们首先介绍了数据预处理的原因和 一般步骤，主要包括：数据描述，数据清洁，数据约减和数据离散化等等。本 课题所采用的数据是贴片机生产电子芯片过程中积累的数据，在本章的后半部 分，我们重点介绍了针对于贴片机生产数据的预处理过程，主要包括：数据表 选取，确定分类属性，分类属性离散化，目标数据提取，预测属性选择，缺失 值处理，噪音数据处理等。 第四章是决策树算法在贴片机生产数据分析中的应用研究。它是本文的重 点内容之一。本章在介绍了研究目的和研究思路以后，我们通过决策树基本算 法说明了决策树技术的基本思想，即采用分治策略，通过对属性的测试来将含 有类标识的数据集分割成若干个小的子集，通过一次一次的迭代分割最终达到 将数据记录分类的目的。之后我们详细介绍了三种最为常用的决策树算法 i d 3 算法，c 4 5 算法，c a r t 算法。最后是本章的重点内容，三种常用决策树 算法的对比实验，在这部分中我们定义了测试训练比，介绍了测试集的选取策 略，并通过流程图，清楚地说明了我们对比实验的流程，进行了全面完整的对 比实验。最后根据我们的实验结果得到了如下结论：首先，这三种决策树算法 在贴片机生产数据上的准确性分布基本一致。其次，这三种决策树算法的准确 性随着测试训练比的增加先增加后减小。准确性在达到最大值以前准确性增加 迅速，准确性在达到最大值以后缓慢下降。测试训练比值为1 1 6 7 时准确性达 到最大值。最后，这三种算法构造的决策树在构造过程的准确性要比在测试过 程的准确性高六到七个百分点。 第五章是分类回归树算法在贴片机生产数据分析中的应用。它也是本文的 一个重点内容。本章根据三种决策树算法的对比实验结果，实际课题的要求以 及算法自身的特点综合考虑，最终选取了分类回归树c a r t 算法作为贴片机生 产数据挖掘的算法，在选定了记录错误信息的属性作为分类属性，并通过对贴 片机生产过程的学习确定了预测属性以后，我们使用分类回归树c a r t 算法对 北京t 业大学下学硕1 ：学位论文 贴片机生产数据进行了全面系统的数据挖掘，得到了很多反映错误产生原因的 规则。我们通过知识提取过程，以准确性概率0 8 0 为阈值，对这些规则进行了 过滤，最后我们将挖掘到的知识以知识的树型结构直观易懂的表示出来，并呈 现给用户，使得用户可以更好的理解我们的知识。 最后我们是对本次课题所做的工作进行了系统地总结，并对未来我们可以 进一步深入研究的方向进行了展望。 第2 章数据挖捅综述 2 1 数据挖掘 第2 章数据挖掘综述 数据挖掘技术产生于2 0 世纪8 0 年代末，在2 0 世纪9 0 年代得到了长足的 发展，并且成为了数据库信息系统中最重要最有前途的研究领域之一“5 1 。数 据挖掘是一个多学科交叉领域，包含了多个学科的知识，如数据库数据仓库技 术，统计学，机器学习，高性能计算，模式识别，神经网络，数据视觉，信息 检索，图像信号处理，空间时间数据库分析等【4 6 1 。数据挖掘是由各种分类技术 组成的，主要包括：决策树，关联规则，聚类分析，贝叶斯网络，粗糙集理论， 人工神经网络等。通过数据挖掘，我们可以从数据库中提取出隐藏在数据背后 的极具实用价值的知识，我们可以利用这些知识来做决策，进行过程控制，信 息管理，和过程查询等等【2 3 1 。近年来，数据挖掘技术已经在国内外许多行业中 得到了广泛的应用如：零售，生产，金融，电信等领域。许多企业纷纷利用数 据挖掘技术作为他们在竞争中获取战略优势的重要工具，典型的数据挖掘应用 包括：故障诊断，营销管理和信用分析等【_ 7 1 。 数据挖掘的目的是从数据库数据仓库或其它巨大的信息存储中心挖掘出隐 藏在数据背后的不易被人发现的有价值的知识。数据挖掘主要由问题分析，数 据预处理，数据挖掘，模式评估，知识表示等几个步骤组成。总的来说，数据 挖掘可以应用在各种数据源和数据流上，包括：关系数据库，事物数据库，数 据仓库，数据流和高级数据库等【4 7 “钔。高级数据库分为面向对象数据库和面向 特定应用的数据库，主要包括：空间数据库，时间序列数据库，文本数据库和 多媒体数据库等。由于现实世界中的数据库和数据仓库等数据源都普遍存在着 不完整的，有噪音的不一致的数据，这些数据是不能直接用于数据挖掘的，数 据预处理阶段是必不可少的一个环节，是挖掘出有价值信息的必要前提。为了 对数据进行恰当的预处理，对数据有一个全面地了解是必不可少的，对数据整 体分布特点的了解，是我们深入理解数据特性的前提。在数据集中有许多属性 是与数据挖掘任务不相关的，我们可以通过数据约减的方法找出这些与数据挖 北京丁业大学t 学硕i j 学位论文 掘工作不相关的属性子集，并将其移除来减小数据集的规模，提高数据挖掘的 效率。有些数据挖掘算法要求某些属性必须是离散型属性，如决策树算法就要 求类属性必须是离散型属性，所以有些时候需要对数据进行离散化，以符合数 据挖掘算法的要求。在完成以上数据预处理以后就可以对数据构建分类模型， 如构建决策树，产生关联规则，构造人工神经网络等1 9 1 ，这是数据挖掘整个过 程的核心部分，我们可以通过分类模型对数据的分类，将隐藏在数据背后的知 识以数据模式的形式提取出来，这些被提取出来的数据模式的数量是很大的， 并且有很大一部分是无用的，我们需要对这些数据模式进行评估，分辨出哪些 数据模式是我们所感兴趣的对我们有价值的，这就是模式评估所要做的工作， 最后当我们得到了这些有价值知识以后，我们通过知识表示将这些知识以规则 图表等形式，简明易懂的呈现在用户面前【2 4 1 。 2 2 数据挖掘的主要技术 数据挖掘这一领域是由若干种挖掘技术组成的，每种技术代表一个研究方 向，每个研究方向都有其经典的算法作为支撑，一般我们可以将这些技术分为 两类：分类技术和聚类技术【】 分类技术指的是构造分类模型的过程中，用于构造模型的数据记录是含有 类属性的，要划分的类是事先已知的。在构造分类模型的时候你可以清楚地识 别，你的模型将数据所分的类与数据实际的类属性是否一致，如果一致则证明 对这条记录的分类是正确的，不一致则是错误的。数据记录中的类属性就是一 个对你分类结果的指导，从机器学习的观点来看，分类技术是一种有指导的学 习方法。通过学习可以形成数据记录对象与类属性间的对应关系。如决策树就 是一种典型的分类技术。 聚类技术指的是构造分类模型的过程中，用于构造模型的数据记录不含有 类属性，在构造分类模型的时候我们只能依靠统计方法，根据数据的总体分布 情况和数据之间的相互关系以及紧密程度等因素将数据记录分成几类。与分类 技术最主要的不同点是：聚类技术中要划分的类是事先未知的，类的形成完全 是数据驱动的。从机器学习的观点来看，聚类技术是一种无指导的学习方法。 聚类主要依靠统计方法进行如聚类分析，回归分析等来描述这个数据集的主要 第2 章数据挖掘综述 特征。 一从某种意义上说，数据挖掘的目标就是根据训练集数据构造分类模型对数 据源进行分类，进而利用这个模型可以对未来数据进行预测分类。下面我们将 对数据挖掘中的各种基本技术做一个简要的介绍【4 9 5 0 1 。 2 2 1 决策树 决策树是一种应用最为广泛的归纳推理算法之一。它是一种逼近离散值目 标函数的方法，从一组无次序无规则的训练数据集中推理出由决策树表示的分 类规则的过程。决策树技术对噪声数据具有很好的健壮性【5 0 】。 通过决策树学习得到的函数被表示为一种类似于流图的树型结构，这种树 型结构称为决策数。其中每一个内部节点表示一个在数据记录属性上的测试， 该节点的每一个后续分支表示测试的一个结果对应于该属性的一个可能值，每 个叶子节点都有一个类标识，表示决策树对数据记录的分类结果。决策树分类 方法采用自顶项向下的递归方式，从树的根节点开始测试节点指定的属性，按 照给定实例在该属性上的值向对应的树枝移动。决策树内部节点按以上方法迭 代进行，直到到达叶子节点得到决策结论【3 4 3 5 t3 9 1 。大多决策树算法采用自顶向 下的贪婪搜索策略遍历可能的决策空间。最为常有的决策树算法有i d 3 算法， c 4 5 算法，和分类回归树c a r t 算法。i d 3 算法使用了信息赢取( i n f o r m a t i o n g a i n ) 作为属性选择的标准，这种方法是基于信息理论的，它是数据挖掘领域 中最为典型的决策树算法。c 4 5 是i d 3 的变体算法，i d 3 所采用的信息赢取方 法往往倾向于选择有大量不同属性值的离散属性，c 4 5 采用了赢取率的方法来 修正这种倾向。c 4 5 算法已经成为其它新的决策树算法的比对标准。分类回归 树c a r t 算法采用的是基尼系数( g i n ii n d e x ) 作为属性选择的标准，在决策树 技术中与i d 3 算法具有同等重要的地位。 2 2 2 关联规则 关联规则反映的是事件和事件之间的依赖关系。数据库中的数据关联是现 实世界中事物联系的表现。数据库作为一种结构化的数据组织形式，利用其依 北京t 业大学丁学硕士学位论文 量皇皇曼曼曼i _ii m ! _ 曼皇皇麓 附的数据模型描述了一些数据间的关联关系。但是，客观世界的复杂性决定了 数据之间的关系不仅仅依是附在数据模型之中的关联，许多关系是蕴含在数据 背后的。关联规则挖掘的任务就是提取隐藏在数据库中的关联信息。关联关系 可以分为简单关联，因果关联，时序关联等等。这些关联大多是蕴藏在数据之 中的，需要通过关联规则挖掘将这些关联关系揭示出来m2 引。 从广义上讲，数据挖掘的本质就是关联分析。数据挖掘的目的是发现蕴藏 在数据之中的知识，所以这种知识一定是反映不同对象之间的关联关系的。关 联规则挖掘是数据挖掘中最为活跃的研究方向之一。关联规则最初是这对购物 篮问题提出的，目的是为了发现交易数据库( t r a n s a c t i o nd a t a b a s e ) 中不同商品 之间的联系规则。在超市中顾客往往一次购买自己所需要的所有商品，因此商 家可以收集大量的销售数据，并将这些数据存储在交易数据库中。通过对这些 数据的分析，我们可以获得有关顾客购买模式的一般性规则。这些规则刻画了 顾客购买行为的模式可以指导商家科学的安排进货库存以及货架设计等。 最早也是最为著名的关联规则挖掘算法是由a g r a w a l 等人于1 9 9 3 年提出的 a p f i o f i 算法。这种算法使用最小支持度( m i n i m u ms u p p o r t ) 和最小可信度 ( m i n i m u mc o n f i d e n c e ) 两个阈值作为衡量关联规则的标准。挖掘出的关联规 则必须满足用户规定的最小支持度，他表示一组项目关联在一起需要满足的最 低联系程度，它反映了这条规则的适用性。挖掘出的关联规则也必须满足用户 规定的最小可信度，它反映了一个关联规则的最低可靠度。从这个意义上讲， 关联规则挖掘的目的就是从原数据中挖掘出满足最小支持度和最小可信度的关 联规则【1 4 15 1 。 2 2 3 聚类分析 聚类分析指的是将数据集中的数据记录根据数据的特征进行分类，使得每 个类中的数据具有很高的相似性，任意两个不同的类之间的数据具有很高的相 异性。到目前为止，已经涌现出大量的聚类分析算法如k _ 平均，艮中心点等等。 采用不同的聚类分析方法对同一数据进行聚类分析时，可能会得到不同的聚类 划分结果【3 一。按聚类分析算法的思路来分，我们可以将聚类分析算法划分为以 第2 覃数据挖掘综述 下几类【5 0 1 ： a ) 基于密度的方法( d e n s i t y b a s e dm e t h o d s ) ：基于密度的方法与其他方法 的一个本质区别是这种方法考察的是数据对象是否属于相连的密度域，而不是 采用各式各样的距离作为分类统计量的。 b ) 基于模型的方法( m o d e l b a s e dm e t h o d s ) ：基于模型的方法给每一个簇 假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型 可能是数据点在空间中的密度分布函数。它的一个潜在假定是：目标数据集是 有一系列的概率分布所决定的。这种方法通常有两种方案，即统计的方案和神 经网络方案。 c ) 划分法( p a r t i t i o n i n gm e t h o d s ) ：给定一个n 条记录的数据表，划分法构 建数据的k ( k n ) 个划分，每个划分表示一个簇，即这种方法将数据划分为k 个组，同时满足每个组至少包含一个对象，每个对象必须属于且只能属于一个 组。 d ) 基于网格的方法( g r i d b a s e dm e t h o d s ) ：这种方法首先将数据空间划分 成为有限个单元的网格结构，所有的处理都是以单元为对象的。这样处理的优 点是处理速度快，通常与目标数据库中的记录个数无关，只与把数据空间分为 多少个单元有关。但是这种处理方法较粗糙，往往影响聚类的质量。 e ) 层次法( h i e r a r c h i c a lm e t h o d s ) ：层次法对给定数据集进行层次的分解。 根据层次的分解方法，层次法又分为凝聚的和分裂的。凝聚的层次法是一种自 底向上的方法，开始时每个对象作为单独的一个簇，然后相继合并相近的簇， 直到所有的簇合并成为一个，或者达到中止条件为止。分裂的层次法与凝聚法 相反，是一种自顶向下方法，开始时将所有对象置于一个簇中。然后在迭代的 每一步中，一个簇被分裂成更小的簇，直到每个对象在一个单独的簇中，或达 到中止条件为止。 2 2 4 粗糙集方法 粗糙集方法是由波兰科学家z p a w l a k 在19 8 2 年首先提出的一种研究不精 确不确定性知识的数学工具。粗糙集一经提出就立刻引起数据挖掘研究人员的 北京- 1 业大字i ：掌坝i j 学位论又 曼m !_ 一! ii 曼皇曼曼曼皇量皇皇曼曼曼皇皇曼曼曼曼皇量曼曼曼曼舅曼曼曼曼曼量曼曼曼曼皇曼曼曼曼曼曼曼曼曼曼曼曼曼鼍曼曼皇曼曼曼曼曼曼曼舅舅曼皇 注意。粗糙集的思想可以概括为：一种类别对应于一个概念，知识由概念组成； 如果某种知识中含有不精确概念，则该种知识不精确。粗糙集对于不精确概念 的描述方法是通过下近似( d w e ra p p r o x i m a t i o n ) 和上近似( u p p e r a p p r o x i m a t i o n ) 概念来表示。一个概念或集合的下近似概念或集合中的元素肯 定属于该概念或集合，而一个概念或集合的上近似概念或集合只是可能属于该 概念【5 0 1 。 粗糙集理论把客观世界抽象为一个信息系统，一个信息系统s 是一个四元 组，s = ： u 是对象的有限集，记为u = 而，j c 2 ， ； a 是属性的有限集，记为a = 4 ，鸣，4 ，| ； v 是属性值域集，记为v = k ，k ，匕) ，其中k 是属性4 的值域： f 是信息函数( i n f o r m a t i o n f u n c t i o n ) ，即f ：u x a 寸矿，厂( 一，4 ) 巧。 属性集a 常常又划分为两个集合c 和d ，即a = c u d ，c id = f 2 j ，c 表 示条件属性集，d 表示决策属性集。d 一般只有一个属性。对应于一个数据库 系统，f ( a ，p ) 的值确定记录e 关于属性a 的取值。对于属性集a 中的任意一个 属性a ，如果纪录乞和记录巳对于属性a 的取值相同，我们称q 和巳基于属性集 相等。基于某个属性集a 的所有等价纪录的集合，被定义为等价类。属于同一 等价类的记录归为一类，此分类成为r 基于属性集a 的划分，常被表示为 r = r i ，r 2 ”，r ) 。 粗糙集刻画了由一个二元组 给出的近似空间( a p p r o x i m a t i o n s p a c e ) ： u 是对象的有限集合，记为u = x i ，而，毛) ； b 是a 的属性子集，r ( 动是u 上的二元等价关系， 即 r ( 研= ( 而，x 2 ) lf ( x 。，b ) = f ( x 2 ，6 ) ，6 研。畏( 回把u 划分为k 个等价类 五，x 2 ，黾，记尺( b ) = ，三条 北京- e 业大学_ t 学硕十学位论文 否) 。对于 中年) 有4 条 是 ，0 条 否) ， 老年) 3 条 是) 2 条( 否) 。使用公式 ( 4 2 ) 可以计算出数据表4 1 中的记录根据属性年龄分割以后，将所有元组完 全分类还需要的平均分类信息是： 州驴爿i i d i d jl i n f o ( d j ) = i n f o o g , ( d ) - 云( _ 沁9 0 9 2 争 + 彳( 一4 1 0 9 ：三一詈一。g ：i 0 ) + i 5 孑( 一3 5 1 。g ：；一詈- 。g ：；2 ) = o 6 9 4 这样，在知道属性年龄的信息以后得到的信息赢取是： g a i n ( a g e ) = i n f o ( d ) 一i n f o o , , ( d ) = 0 9 4 0 0 6 9 4 = 0 2 4 6 同样的，我们可以计算出其它属性可以带来的信息赢取： g a i n ( i n c o m e ) = 0 0 2 9g a i n ( s t u d e n t ) = 0 15 1 g a i n ( c r e d i t r a t i n g ) = o 0 4 8 。由于在 所有的属性中属性年龄具有最高的信息赢取，所以选取属性年龄作为分割属性， 标识节点n 为属性年龄，并为属性年龄的每个属性值构建分支，数据记录按照 属性年龄的值被相应的分割。当一个分支中的元组都属于同一类时，为这一分 支构造叶子，并将其标识为这些元组所属的类，如属性值 中年) 分支中所有记 录都属于类 是 所以为其生长一个树叶标识为 是) 。迭代执行以上操作，直到 所有属性都被选取。如果这时还有分支中的类属性购买计算机不属于同一类， 则根据多数投票原则将其标识为整个数据集中类属性所含纪录最多的属性值， 数据表4 1 中类属性值为 是 的数据记录有9 个多于属性值为 否 的5 个所以 标识为 是 【1 1 】。 4 4 20 4 5 算法 c 4 5 算法是i d 3 算法的改进算法，i d 3 算法所采用的信息赢取标准往往倾 向于选择有大量不同属性值的离散属性作为分割标准，c 4 5 采用了可以将信息 赢取标准化的赢取率来修正这种倾向【2 1 。首先定义分割信息： 聊岷c 咖 篙灿g ：唰， 件3 ， 赢取率的定义如下： 第4 章决策树算法在贴片机生产数据分析中的戍用研究 曼皇量皇曼皇曼量曼量曼曼鼍m m；i 。 一一 i ii | 曼曼曼鼍曼皇量曼曼曼曼曼曼曼曼曼曼皇曼曼曼皇曼曼曼皇曼皇曼曼曼曼皇曼皇曼皇曼曼曼曼量 g a i 以r a t f d ( 彳) ：剑一( 4 4 ) 、7 s p l i t l n f o ( a ) 赢取率指的是根据属性a 的v 个不同的属性值将数据集d 分成v 个子集以 后，对于每个子集我们都考虑这个子集中包含的记录数量在整个数据集中的比 重，这与信息赢取的不同点在于i d 3 算法所采用的信息赢取只是以一种平均权 重的方式来衡量的每个属性所带来的信息赢取的。在c 4 5 算法中产生最大赢取 率的属性被选为分割属性。这种方法的缺点是当分割信息接近0 时，赢取率会 变得很不稳定【3 1 3 2 1 。 表4 - 1 中的属性收入将整个数据集分成三个部分，即 低) ， 中) ， 高) ， 分别包含4 ，6 ，4 条记录。计算属性收入的赢取率首先使用公式( 4 3 ) 计算分 割信息： s p l i t l n f o a ( d 卜喜剖灿以舒 ：一4 g 一 一 ： 2 46 a 9 264 4 0926x l o gl o gx l o g 。一1 4百一百1 4 一1 42 酉2 由于g a i n ( i n c o m e ) = 0 0 2 9 ，所以，g a i n r a t i o ( i n c o m e ) = 0 0 2 9 0 9 2 6 = 0 0 31 。 4 4 3 分类回归树c a r t 算法 分类回归树c a r t 算法采用基尼系数( g i n ii n d e x ) 作为属性选择的标准， 基尼系数测量数据集d 的混乱度【3 3 t3 7 1 ，定义如下： g i n i ( d ) = l -