（计算机应用技术专业论文）基于粗糙集的大数据集挖掘算法研究与实现.pdf

江苏大学硕士学位论文 摘要 随着计算机技术、传感器技术和i n t e m e t 的快速发展，产生了很多有效的工具 用于生成、传播、存储和检索数据。因此，随着我们获取数据的速度和规模的不 断增长，各种形式的数据流被记录在各种类型的存储介质中。数据在实例数量、 属性数量和分类数量等方面都出现激增，高维大数据集随之出现。大数据集的出 现给包括决策树分类挖掘算法在内的许多机器学习算法在健壮性和可伸缩性等 方面带来了巨大的挑战。 本文首先阐述了课题的研究背景和意义，然后综述了决策树分类和卡r 糙集的 相关原理和理论。本文在训练集准备与决策树分类模型构造两个阶段引入料糙集 理论，从缩减大数据集规模和改良决策树节点属性选择测度入手，围绕粗糙集理 论与大数据集规模的缩减和决策树分类模型构造优化的交义融合进行了深入研 究和积极创新，主要内容和创新包括： 1 针对已有数据集规模压缩算法的计算复杂和对实例规模删减的关注不足 等缺点，给出一种大数据集空间分割算法，主要考虑从空间上对数据集进行分害4 ， 所以引入聚类思想将信息熵的大小作为属性纯度的度量标准来分割数据集，优先 选择具有最小熵值的属性，熵值越小，分割后的子集越纯净，即子集划分内的相 似性( 同质性) 越大。 2 一般来说，分割后一部分信息会丢失，因此如何使重要的信息保留下来 就成为需要主要考虑的问题之一。给出一种大数据集约简算法，利用欧式距离度 量找出每个子集划分的中心实例，它是对挖掘任务来说最重要的信息，然后利用 k 近邻算法查找中心实例的k 个最近邻实例并且与中心实例共同组成代表性实 例，进而形成优化的训练集约简集。另外，给出算法的复杂度分析和信息论基础 分析，证明算法计算时间复杂度远远小于经典粗糙集约简算法，可以在短时问内 找到原始大数据集的一个近似最优约简集。 3 给出一种基于粗糙集理论的节点属性选择新测度属性分类价值量， 并结合已取得的大数据集约简算法的研究成果给出新的决策树模型构造算法 a c v s 。该算法将分类相同但条件属性值不同的情况作为补偿因子可分辨矩阵， 并提出属性分类价值量度量函数，它更能全面表征属性对分类的价值，并用于节 江苏大学硕士学位论文 点属性的选择。同时，将r l d s 作为训练集优化的核心算法。 4 实现a c v s 决策树分类算法，设计一个分类模型。在来自于u c i 的数 据集上进行对比试验评估算法性能，总结实验，分析存在的问题，提出下一步的 研究目标和方向。 关键词：大数据集挖掘，粗糙集，决策树，属性纯度，可分辨矩阵， 属性分类价值量 江苏大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y ，s e n s o rt e c h n o l o g ya n dt h e i n t e r n e t ，t h e r ea r eal o to fe f f e c t i v ed a t at o o l sf o rg e n e r a t i o n ，t r a n s m i s s i o n ，s t o r a g ea n d r e t r i e v a l t h e r e f o r e ，a st h ei n c r e a s eo fd a t ar a t ea n ds i z et h a tw ec a p t u r e d ，av a r i e t yo f d a t as t r e a m sw e r er e c o r d e di nt h ev a r i o u st y p e so fs t o r a g em e d i a b e c a u s eo ft h er a p i d g r o w t ho fd a t ai nt h en u m b e ro fi n s t a n c e s ，p r o p e r t i e sa n dc l a s s i f i c a t i o n ，i ta p p e a r s h i g h d i m e n s i o n a ld a t as e t s ，w h i c hb r i n gs o m et r e m e n d o u sc h a l l e n g e si nr o b u s t n e s s a n d s c a l a b i l i t y t om a n ym a c h i n el e a r n i n g a l g o r i t h m si n c l u d i n gd e c i s i o n t r e e c l a s s i f i c a t i o nm i n i n ga l g o r i t h m i nt h i st h e s i s ，w ef i r s t l ye x p l a i nt h eb a c k g r o u n da n ds i g n i f i c a n c e ，t h e nd i s c u s st h e r e l a t e dp r i n c i p l e sa n dt h e o r i e so fd e c i s i o nt r e ec l a s s i f i c a t i o na n dr o u g hs e t w e i n t r o d u c er o u g hs e tt h e o r yi n t ot h ep r e p a r a t i o no ft r a i n i n gs e ta n dt h em o d e l c o n s t r u c t i o no fd e c i s i o nt r e e ，a n ds t a r tw i t hr e d u c i n gs i z eo fl a r g ed a t as e t sa n d i m p r o v i n gn o d ea t t r i b u t es e l e c t i o nm e a s u r eo fd e c i s i o nt r e e w ep e r p e t r a t es e v e r a l i n d e p t hr e s e a r c h e sa n df r u i t f u li n n o v a t i o n s ，t h em a i nc o n t e n ta n di n n o v a t i o n a r e d e s c r i b e da sf o l l o w ： 1 t h ed a t as e ts i z ec o m p r e s s i n ga l g o r i t h mi st o oc o m p l e xa n dc u t t i n gi n s t a n c e s s i z ei sn o tt a k e ni n t oa c c o u ts e r i o u s l y w ep r o p o s et h es p a c ep a r t i t i o na l g o r i t h mf o r l a r g ed a t as e t sb a s e da t t r i b u t ep u r i t yp a r t i t i o n i n g ，w h i c hi n t r o d u c ec l u s t e r i n gn o t i o n a n du s ee n t r o p yt op a r t i t i o nd a t as e t sa sm e a s u r e m e n to fa t t r i b u t ep u r i t y t h es m a l l e r e n t r o p y , t h em o r ep u r es u b s e ts e g m e n t e d ，i no t h e rw o r d st h eg r e a t e rs i m i l a r i t y ( o r h o m o g e n e i t y ) o fi n t e r n a ls u b s e t 2 i ng e n e r a l ，s o m ei n f o r m a t i o nm a yl o s ea f t e rp a r t i t i o n i n g t h e r e f o r e ，o n e m a j o rc o n s i d e r a t i o ni sh o wt ok e e pi m p o r t a n ti n f o r m a t i o n t h er l d s ( r l d s ， r e d u c t i o na l g o r i t h mf o rl a r g ed a t as e t s ) b a s e da t t r i b u t ep u r i t y p a r t i t i o n i n ga n d r e p r e s e n t a t i v ei n s t a n c e se x t r a c t i n gi sp r o p o s e d w h i c hc a ns e a r c hc e n t r a li n s t a n c eo f e a c hs u b s e tb ye u c l i d e a nd i s t a n c ea n df i n dkn e a r e s tn e i g h b o r so fc e n t r a li n s t a n c e ， t h e nt h et w oc o m p o n e n t sc o m p o s er e d u c t i o no ft r a i n i n gs e t s t h ec o m p l e x i t ya n d i n f o r m a t i o nt h e o r ya n a l y s i so fa l g o r i t h mi l l u m i n a t et h a tt i m ec o m p l e x i t yi sm u c hl e s s t h a nc l a s s i c a lr o u g hs e ta n da l g o r i t h mc a nr a p i d l yf i n dar e d u c t i o nw h i c hi sa n a p p r o x i m a t e l ys i m p l e s ts e to fo r i g i n a ll a r g ed a t as e t s 江苏大学硕士学位论文 3 w ep r o p o s ean o v e lm e a s u r e m e n t - - - a t t r i b u t ec l a s s i f i c a t i o nv a l u ef o rs e l e c t i n g a t t r i b u t ei ne a c hn o d eb a s e do nr o u g hs e ta n dan e wd e c i s i o nt r e em o d e lc o n s t r u c t i o n a l g o r i t h m ( a c v s ，a t t r i b u t e c l a s s i f i c a t i o nv a l u ef o rs e l e c t i n g ) s y n t h e s i z e dw i t h r e d u c t i o na l g o r i t h m ( r l d s ) f o rl a r g ed a t as e t s t h ea c v sm a k ec o n d i t i o nt h a t d i f f e r e n tc o n d i t i o na t t r i b u t eb u ts a m ec l a s sa sc o m p e n s a t i v ef a c t o rt oe x p a n d d i s c e m i b i l i t ym a t r i x t h em e a s u r ef u n c t i o no fa t t r i b u t ec l a s s i f i c a t i o nv a l u ei sp r o p o s e d b a s e do nn e w d i s c e r n i b i l i t ym a t r i x ，w h i c hc o u l db eu s e dt os e l e c ta t t r i b u t ei nn o d ea n d m o r es y n t h e t i c a l l ym e a s u r e sc o n t r i b u t i o no fa na t t r i b u t ef o rc l a s s i f i c a t i o n r l d si s t h ec o r em e t h o do fo p t i m i z a t i o no ft h et r a i n i n gs e t s 4 ad e c i s i o nt r e ec l a s s i f i c a t i o nm o d e li s d e s i g n e da n di m p l e m e n t e d w e i m p l e m e n t et h ee v a l u a t i o nt e s to fa l g o r i t h mp e r f o r m a n c ei ns o m eu c id a t as e t s ， s u m m a r i z et h ee x p e r i m e n ta n da n a l y z et h ee x i s t i n gp r o b l e m s ，a n dp r o p o s ef u t u r e r e s e a r c hg o a l sa n dd i r e c t i o n k e yw o r d s ：l a r g ed a t as e t sm i n i n g ，r o u g hs e t ，d e c i s i o nt r e e ，a t t r i b u t ep u r i t y , d i s c e r n i b i l i t ym a t r i x ，a t t r i b u t ec l a s s i f i t i o nv a l u e l v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 捕等复制手段保存和汇编本学位论文。 本学位论文属于 学位沦文作者签名： 么| 年七月b 日 保密口，在年解密后适用本授权书。 不保密酣 闽南 指导教师签名： 乙厶年月哆e 1 绦l 独创性申明 本人郑重声明：所呈交的学位沦文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 1 司，毛 矽f 年6 月岱日 江苏大学硕士学位论文 1 1 概述 第一章绪论弟一早三百t 匕 数据采集技术和数据存储介质的稳定进步、数据库技术的发展和成熟以及因 特网技术的出现和普及使得各存储媒介中积累了海量的数据。这些丰富的信息数 据资源中隐藏着许多未知的、非常重要的、具有潜在利用价值的知识，但是人们 却无法很有效地使用这些数据，造成了所谓“数据丰富但知识贫乏”的局面。要 想在浩如炯海的数据中找到自己所需的信息，传统的数据分析工具和技术已经无 法满足我们的数据处理要求。另外，即使数据集相对较小，由于数据本身存储的 非线性特点，也不能使用传统的方法处理。这样，就迫切需要一些新的方法和工 具用于从大量的数据中智能的、主动的发现有价值的知识或信息。决策树分类就 是一种重要的数据挖掘方法，它将传统的数据分析方法与处理大量数据的复杂算 法相结合用于数据分析与规则抽取。本章将阐述论文的研究背景以及意义，然后 从粗糙集与决策树相结合的角度对目前的研究现状作出概述，并在此基础上给出 全文的研究内容和组织结构。 1 2 课题研究背景及意义 分类足数据挖掘中一种重要的分析方法，可以应用于实例预测，规则归纳， 它通过训练集学习构造一个分类函数或分类模型，该函数或模型能够把数据记录 映射到给定类别中的某一个。用于分类挖掘的方法有很多，例如决策树、贝叶斯 网络、遗传算法、神经网络、k 一最近邻算法等。其中，决策树分类法是一种通过 构造决策树米归纳数据集中分类知识的数据挖掘方法，具有速度快、精度高、易 理解和生成模式简单等优点受到人们的广泛重视和应用。各研究机构与学者对决 策树算法的研究与改进一直是一个热点。目前，分类己被广泛应用于医疗诊断、 气象预测、信用审核、顾客区分、案件侦破等许多领域。 粗糙集理论是二十世纪八十年代出现的一种软计算方法，它将知识理解为对 数据的划分，每一个划分的集合称为概念，将不精确或不确定的知识利用已知知 识库中的知识米近似刻画处理，是分析和处理不精确、不确定和信息不完备的主 江苏大学硕士学位论文 动数据分析决策工具。粗糙集的研究也是目前非常活跃的信息科学领域热点之 一，它与模糊集方法、证据理论方法和概率方法等其他处理不确定性问题理论的 显著区别在于无须提供所处理数据之外的任何先验信息。 随着计算机技术的迅速发展，企业信息化程度的提高，信息化事务处理技术 的运用，数据收集工具和技术的多样化以及互联网的发展为我们带来了海量的数 据和信息，在国土资源、空间气象、生物制药、医学影像、金融和商业等领域尤 其明显。如何从大量的，杂乱无章的，噪音干扰的数据中挖掘隐藏在数据背后的 信息如概念( c o n c e p t ) 、规贝l j ( r u l e ) 、模式( p a t t e r ) 及相关性( r e l a t i o n s h i p ) 等，给信 息挖掘处理提出了前所末有的挑战。目前，信息化的重点已经从自动化办公和搭 建企业局域网转到利用海量数据帮助企业进行决策支蒯。但是，如此大量的数 据给包括决策树分类算法在内的许多机器学习算法在健壮性和学习性能方面带 来了严重的问题。例如，高维大数据集可能包含大量的不相关和冗余的信息，其 中大部分属性与挖掘任务不相关，足冗余的。不相关属性的存在和相关属性的遗 漏都是有害的，这l 】能导致决策树挖掘算法性能大幅下降、发现的模式质量不高， 甚至预测出错。此外，不桐天或冗余的属性增加了数据量，会大大增加挖掘所需 的时空开销。 综上所述，大数据集的规模缩减和决策树的构造过程优化已经成为决策树挖 掘过程中的两大关键| 、u j 题。研究人员已经发展出很多形式的决策树构造方法。但 是在训练集准备与决策树构造阶段引入粗糙集理论来解决大数据集挖掘| u j 题却 是一个崭新的课题。结合粗糙集理论与决策树理论，取长补短、充分发挥决策树 和粗糙集理论的优点以寻求更好的决策树分类模型，使其可以有效地处理大规模 数据集，并真正的为电信、保险、银行、故障诊断、零售、空间数据库和医疗等 很多行业实际问题提供有力的决策支持，对未来的商业行为和人们的生活方式也 将产生深远的影响。 1 3 课题研究现状 1 3 1 决策树的研究现状 决策树方法起始于人工智能，从其出现以来先后出现了许多算法，包括i d 3 、 江苏大学硕士学位论文 c 4 5 、c 5 0 、c a r t 、c h a i d 、s l i q 和s p i n t 等。它们都采用自顶向下的递归方 式进行属性值的比较并根据不同值从该节点向下进行分裂，在决策树的叶子结点 得到结论。决策树从根到叶子节点的一条路径对应着一条合取规则，整棵树对应 着一组析耿表达式形式的规则，一棵决策树能够方便地转化为若干条分类规贝l j 。 近十几年来国内外的研究人员逐步提出和改进了各种决策树算法，例如决策树与 神经网络技术相结合，决策树与模糊集合理论相结合等等。 i b ma l m a d e n 研究所开发的s l i q 分类方法1 2 1 和j o h ns h a f e r 等人提出的 s p r i n t 算法1 3 j 在算法中首次使用了一些特殊的数据结构，如属性表和类表，具有 良好的伸缩性和并行性，并且改善了经典i d 3 分类方法【4 1 及其改进版本c 4 5 1 5 1 和 c 5 0 方法不适合大型数据集的问题。但是，在算法执行过程中需要随时修改类表， 因此类表常驻内存，而类表的大小会随着训练样本集的增大而增大，导致输入数 据受到主存容量的限制，依然没有很好的解决大数据集挖掘这个| 、u j 题。 r a j e e v 等提出了将决策树建树和剪枝集成在一起的p u b l i c ( ad e c i s i o nt r e e t 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 ) 5 - 类算法【6 l ，在建树阶段通过计算r 标函数决 定节点是否会在将来被删除，从而决定是否扩展。p u b l i c 算法提高了决策树的 执行效率。 c o l a m 在2 0 0 3 年提出了一种新的模糊决策树分类方法软决策树【7 1 。软 决策树综合了决策树的生成和修剪来决定其本身的结构，并利用重修和磨合来提 高树的归纳能力，因此软决策树比一般的决策树正确率要高。 m a n k e r s t 等提出了基于多维可视化的交互式决策树构造方法1 8 l 。该方法将 专家知谚 加入到决策树构造阶段，便于用户更深地理解产生决策树的数据以及最 终产生的决策树。 吴强、李金龙等在2 0 0 6 年提出了一种用拟合回归建立决策树的算法1 9 1 。该算 法根据数据属性间存在的线性相关和非线性相关会影响决策树性能的特性，选择 了一个较优的属性子集，对此子集中的属性进行加权组合，用于构造决策树节点， 采用二次多项式来拟合两个属性间可能存在的相关性，从而构造出分类能力更强 的决策树。 3 江苏大学硕士学位论文 1 3 2 决策树与粗糙集交叉研究的现状 籽l 糙集是一种处理含糊和不精确性问题的数学工具，是由波兰数学家 z p a w l a k 在1 9 8 2 年首先提“ 的f l o l 。自问世以来，它在知识发现、机器学习、故 障诊断、医疗数据分析、专家系统、决策分析系统、归纳推理、模式识别和主动 控制等许多领域取得了令人鼓舞的成就，近年来受到国际上越来越多的学者广泛 关注。经典粗糙集( 即，z p a w l a k 创立的料糙集) 的理论研究包括公理化问题、拓 扑空f h j 、代数结构和算子代数等，已取得了较完善的成测1 1 , 1 2 j 。 w e ij i n m a o 于2 0 0 3 年提出在决策树的构造过程中引入粗糙集的相关理论 1 3 , 1 4 1 ，他根据粗糙集理论中近似区问的概念，以能明确被分类的实例个数最多或 者不能被明确地分类实例个数最少作为当前分支节点的属性选择标准，可以快速 地生成高精度的决策树分类模型。 m b e y n o n 在2 0 0 1 年提出一种基+ j ：籽l 糙集理论的属性约简原理来作分类【1 5 】。 首先根据粗糙集理论进行属性约简，然后在约简后的决策表中提取决策规则，依 据决策规则进行分类。 m z b l e y b e r g 和a e l u m a l a i 在2 0 0 1 年提出了基于粗糙集理论的决策树算法 f i 引。算法利用粗糙集的j f 区域( 或下近似集) 以及分类精度等作为选择节点属性 的度量标准，这些标准刻画了属性可答别对象集的大小。f h 足，并未考虑属性对 样本的划分状况影响后继分类的其他因素，从而影向了算法的性能和规则集的质 量。另外，这些基于粗糙集的分类算法对噪音数据和不相容数据也未能提供较为 有效可行的处理方法。 c e b r o d l e y 在1 9 9 5 年提出一种基于组合的决策树构造方法1 1 7 l 。该方法分别构 造属性的b o o l e a n 组合和线性组合，然后建立多变量归纳学习系统。优势在于在 度量准则上考虑了多个属性，所以能够产生相关度高的的属性。 1 4 论文研究内容 为了克服现有决策树分类算法在大数据集上有效性和_ 町伸缩性的局限，论文 以决策树分类模型为主要研究对象，从优化训练集以适应大数据集的处理和提出 新节点属性选择测度以改进决策树建树过程两方面对基于粗糙集的决策树分类 模型进行了深入的研究和创新，并且对新方法的复杂度、准确性、简洁性以及高 4 江苏大学硕士学位论文 效性进行精确分析与计算。具体研究工作集中在如下几个方面： ( 1 ) 研究基于属性纯度的数据空间分割算法 分析训练集质量和规模与决策树规模和泛化能力之间的关系，根据聚类思想 给出一种基于属性纯度的大数据集空间分割算法。该算法利用信息熵作为属性纯 度的衡量标准，信息熵值越小，子集越纯净。采用自底向上逐步细分数据空间的 策略，每一次分割都用当前子集中属性纯度最小的属性根据其分类分割集合，直 到满足一定条件为止，可以使子集内的实例具有某种共同特征或者性质。 ( 2 ) 研究基于中心实例的大数据集约简算法r l d s 针对大部分算法不能适用于大数据集数据处理的要求。本文给出一种基于属 性纯度和中心实例的大数据集约简算法r l d s ( r e d u c t i o no fl a r g ed a t as e t s ， r l d s ) 。该算法首先给出中心实例的概念，它是对挖掘任务来说最重要的信息。 然后利用欧式距离度量找出每个子集划分的中心实例，利用k 近邻算法查找中 心实例的后个最近邻实例与中心实例共同组成代表性实例，并且给出删除属性和 实例的条件，进而形成近似最优的约简集。最后，给出算法的复杂度分析和信息 论基础分析，从理沦上证明诿确性和优越性。 ( 3 ) 研究基于r l d s 和属性分类价值量的决策树分类模型构造算法 对常用的属性选择标准进行研究分析，给出一种基于属性分类价值量的节点 属性选择新测度，并且将r l d s 大数据集约筒算法作为训练集优化的核心算法， 给出新的决策树分类模型构造算法a c v s ( a t t r i b u t ec l a s s i f i c a t i o nv a l u es e l e c t ， a c v s ) 。该算法将分类相同但条件属性值不同的情况作为补偿因子扩展m ( s ) 为 新的可分辨矩阵m ( s ) ，给出总属性分类价值量度量函数并用于节点属性的选 择。训练出的决策树分类模型包含更多的可用分类知识并且考虑了相同分类中的 实例之间的关系。 ( 4 ) a c v s 决策树分类模型构造算法的实现与评估 以r l d s 大数据集约简算法和属性分类价值量测度为核心实现a c v s 决策 树分类算法，并设计一个分类模型。在来自于u c i 的数据集上进行对比试验评 估算法性能。 5 江苏大学硕士学位论文 1 5 论文组织结构 全文共分6 章，各部分章节组织结构安排如下： 第一章：绪论。首先分析了论文的研究背景和意义，其次阐明了决策树分类 以及与；f i i 糙集交叉研究领域的发展现状，最后总结了论文的主要研究内容和组织 结构。 第二章：决策树年h s t i 糙集的相天理论研究。分别综述了决策树分类和粗糙集 的基础理沦，分析了决策树的构造过程并对典型的决策树算法进行分析比较，总 结其优缺点。 第三章：面向大数据集的数据约简算法。首先阐述了大数据集的特性和规模 控制的必要性，指出训练集规模与决策树规模之问存在单调递增的近似线性关 系。然后提出蚪j 属性纯度分割数据集，并在分割后的子集上用k n n 方法基于中 心实例抽取出代表性实例进而形成近似最优约简集。最后对算法的复杂度和信息 论基础进行分析并举例既明约简原理和过程。 笫四章：基于属性分类价值黾的决策树模型。首先介绍了常用的决策树节点 属性选择标准并且总结存在的l 、u j 题，然后将町分辨矩阵m ( s ) 扩展定义为m ( s ) ， 并且用扩展的町分辨矩阵m7 ( s ) 和属性分类价值量函数代替熵函数来选择属性， 给出一种新颖的基于r l d s 大数据集约简算法和属性分类价值量的决策树模型 构造算法。最后给出算法描述并举例说明建树原理和过程。 第五章：实验结果与性能评估。简述实验环境和实验数据的特征。设计实验 步骤，通过理沦证明、实例分析和对比实验证明r l d s 大数据集约简算法的高效 和计算快速与a c v s 决策树模型构造算法的准确性、简洁性和高效性。 第六章：总结与展望。系统地总结本文研究工作，并提出下一步需要研究的 内容。 6 江苏大学硕士学位论文 第二章决策树和粗糙集的相关理论研究 数据挖掘( d a t am i n i n g ) 就是从人量的、不完全的、有噪声的和模糊的数据中 发现隐含在其中的先前末知的、潜住有益的模式的过程。分析复杂的、不完整的 数据以发现数据之间的关系，归纳有益的模式以简化信息处理，确定不精确、不 完备知识的表达，这些是数据挖掘的首要任务。决策树( d e c i s i o nt r e e ) 技术就是 这样一种典型的数据挖掘技术，具有速度快、精度高和生成模式简单等优点。同 时，粗糙集( r o u g hs e t ) 理论也是一种新的分析和处理不精确、不一致、不完整信 息和知识的数学工具，两者的结合正好可以满足数据挖掘中数据特征的需求。 2 1 分类模型概述 2 1 1 分类的定义 分类足数据挖掘最荤要的研究领域之一。分类的目的是通过训练具有类别标 记的实例( 数据) ，得出一个能够预测新实例类别的模型。分类任务的输入数据是 记录的集合。每条记录称为实例或者样例，用元组( x ，y ) 表示，其中x 是属性的 集合，而y 是一个特殊的属性，代表实例的类标一弓- ( c l a s sl a b e l ，也称为分类属性 或者目标属性) 。分类问题足一个普遍存在的问题，有许多不同的应用。例如： 根据电予邮件的标题和内容检查垃圾邮件，根据核磁共振扫描的结果区分肿瘤是 恶性的还是良性的，根据星系的形状对它们进行分类等等。 定义2 1 分类分类任务就足通过学习得到一个目标函数( t a r g e t f u n c t i o n ) 厂，把每个属性集x 映射到一个预先定义的类标号y 。一般地，目标函 数也称为分类模型( c l a s s i f i c a t i o nm o d e l ) 。 分类模型的作用有： ( 1 ) 描述性建模分类模型作为解释性工具，用于区分不同分类中的对象。 ( 2 ) 预测性建模分类模型还可以用于预测未知实例的类标号。 分类模型可以看作是一个对应用透明的块，当给定未知实例的属性集上的值 时，它自动地赋予未知样本类标号，如图2 1 所示。 7 江苏大学硕士学位论文 图2 1 分类模型的工作原理 分类方法是一种根据输入数据集构造分类模型系统的方法。常用构造方法有 决策树( d e c i s i o nt r e e ) 分类法、基于规则的分类法、神经网络( n e u r a ln e t w o r k ) 、 支持向量机( s u p p o r tv e c t o rm a c h i n e s ) $ 1 j 卡l 素贝叶斯( b a y e s ) 分类法等。图2 2 展示 了建立和应用分类模型的一般步骤。 2 1 2 分类模型的评价标准 图2 2 分类模型建立过程 分类模型的评价主要基于以下五项标准： ( 1 ) 预测准确度它是描述分类模型准确地预测新的或先前未知的样本的 类标号的能力，这将对决策产生巨大的影响。 ( 2 ) 计算的速度产生模型和使用模型进行分类的时问代价。 ( 3 ) 健壮性正确预测含有噪声和空缺值的数据集的能力。 ( 4 ) 伸缩性对大数据集有效地构建模型的能力。 ( 5 ) 模型描述的简洁度 因为大多数的决策者并不是领域专家，所以模型描 述越简洁，越容易理解，便于进行决策。 8 江苏大学硕士学位论文 2 1 3 分类模型的评估方法 常用的分类方法性能评估方法有下面4 种： ( 1 ) 保持法( h o l d o u t )将被标记的原始数据集划分成两个独立的集合，用 训练集建立模型，再用测试集评估模型。它们的划分比例通常是取三分之二的数 据作为训练集，其余作为测试集。为保证评估的准确性，每次随机地将原数据集 划分成不同的训练集和测试集共进行k 次评估，总的准确率取k 次准确率的平 均值。保持法最大的问题是不同的测试集之间有重叠的数据。 ( 2 ) 随机二次抽样( r a n d o ms u b s a m p l i n g ) 多次重复保持法来改进对分类 方法性能的评估，这种方法称为随机二次抽样。 ( 3 ) k 一折交叉验证( k c r o s s v a l i d a t i o n )在k 一折交叉验证方法中，每个记 录用于训练的次数相同，并且用于检验恰好一次。将k 次评估的正确分类数除 以数据集的记录总数可得到模型的总体准确率，通常取k = 1 0 。k 折交叉验证法 j 以避免不同的测试数据集之问数据重叠的问题。 ( 4 ) 自助法( b o o t s t r a p i n g ) 在自助法中用于训练的实例采用有放回抽样， 即已经选作训练的实例将放回原来的训练集中，使得它等几率地被重新抽取。 2 2 决策树方法概述 2 2 1 决策树概述 自2 0 世纪6 0 年代以来，决策树在分类、预测以及规则提取等领域有着广泛应 用，特别是在j r q u l u l a n 于1 9 8 6 年提出i d 3 算法以后，决策树方法在机器学习、 知识发现领域得到了进一步应用及巨大的发展，在人工智能领域也有着相当重要 的理沦意义与实用价值。决策树分类方法足以实例为基础的归纳学习算法，它着 眼于从一组无序、无规则的训练样本实例集中推理出决策树表示形式的分类规 则，通常用来形成分类器和预测模型，可以对未知数据进行预测、分类或挖掘等。 决策树是一种树状结构，它的每一个树结点可以是叶节点，对应着某一类， 也可以对应着一个划分，将该节点对应的样本集划分成若干个子集，每个子集对 应一个节点。对个分类问题或规则学习问题，决策树的生成是一个从上至下、 分而治之的过程。决策树从根节点开始，对数据样本进行测试，根据不同的结果 9 江苏大学硕士学位论文 将数据样本划分成不同的数据样本子集，每个数据样本子集构成_ 个子节点。对 每个子节点再进行划分，生成新的子节点。重复这个过程，直至达到特定的终止 条件，生成的决策树每个叶节点对应一个分类。对一个样本进行分类时，从树的 根：i 了点开始，根据每个节点对应的划分将其归到相应的子节点，直至叶节点。叶 节点所对应的类别就是该样本对应的分类。 2 2 2 决策树的构造过程 理论上，对于给定的属性集，可以构造出指数级的决策树。尽管某些决策树 比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树实际上 是不可行的。但仍然有学者开发了一些有效的算法，能够在可接受的时间内构造 出具有一定准确率的次最优决策树。这些算法通常采用贪心策略，在选择分裂数 据的属性时，采取一系列局部最优策略来构造决策树。 决策树的构造包括两个步骤：树构造( t r e eb u i l d i n g ) 和树剪枝( t r e ep r u n i n g ) 。 1 树构造阶段 决策树构造采用自顶向下的递归方式，从根节点开始在每个节点上按照给定 标准选择测试属性向下建立分枝，直到节点上的所有样本被划分到同一个类。 a l g o r i t h m ：通用决策树生成算法 i n p u t ：t s ，训练数据集；r e s ta t t r i b u t e ，候选属性集合 p r o c e d u r e ： s t e p l ：创建节点； s t e p 2 ：如果界在同一个类c 中 则返f , i n n 为叶节点，并标记为c ； s t e p 3 ：如果r e s ta t t r i b u t e 为空 则返l i , i n - f l s 为叶节点，标记为t s 中最普遍的类； s t e p 4 ：选择r e s ta t t r i b u t e 中具有最高信息增益的属幽作为t e s ta t t r i b u t e ； s t e p 5 j 标记节点为测试属性； s t e p 6 7f o r j ! ) ! l j 试属性的每一个已知值西 由节点k 出一个分支，满足t e s ta t t r i b u t e = a i ； s t e p 7 ；设s ，是嬲中t e s t s t e p 8 ；如果s ，为空 加上一个树叶，标记为峦中最普遍的类； 否则，转s t e p 9 ： s t e p 9 ：加上一个i 扫b u i l d i n g t r e e ( s ；，r e s t a t t r i b u t e - w e e _ a t t r i b u t e ) 返同的节点。 图2 3 通用决策树生成算法 l o 江苏大学硕士学位论文 决策树的通用生成算法如图2 3 所示。这一阶段最关键的操作是在树的节点 上选择最佳测试属性，该属性对当次分裂来说足最好的。选择测试属性的标准有 信息增益、信息增益率、基尼指数( g i n ii n d e x ) 以及基于距离的划分等。此外，测 试属性的取值可以是连续的( c o n t i n u o u s ) ，电可以足离散的( d i s c r e t e ) ，而样本的分 类属性必须是离散的。 2 树剪枝阶段 构造过程得到的，。般并不是最简洁的决策树，因为许多分枝反映的可能是i f i l 练数据中的孤立点或噪声。而f j l ，决策树舰模越小，所需存储空间也越小，对它 的某些操作相对来说也就简单省时。树剪枝过程就是试图在保证正确率的前提 下，尽量检测和去掉这种分枝，并构造简洁的决策树，以提高对未知数据集进行 分类的准确性。 树剪技主要通过在训练过程中明确地控制树的火小来简化决策树，主要方法 有先剪枝和后剪枝。 ( 1 ) p e p l l8 1 ( p e s s i m i s t i ce r r o rp r u n i n g ，悲观错误剪枝) p e p l - l - i q u i n l a n 在1 9 8 7 年提出，引入二项分布中的连续修正对训练集巾的错误 率加以修i f ，以得到更符合实际的错误率。修讵后的错误率与修正前相比增加了 不少，因此被认为对错误率的判断是“悲观”的。 ( 2 ) m e p 19 1 ( m i n i m u me r r o rp r u n i n g ，最小错误剪枝) n i b l e t t 币l b r a t k o 提出的m e p 方法埘于树巾每个非叶节点，首先计算该节点的 误差e r ( t ) 。然后，计算该节点每个分枝的误筹e r ( t i ) ，并且加权相加，权为每个分 枝拥有的训练样本比例。如果e r ( t ) 大于e r ( t i ) l ! j ! l j 保留该子树；否则，剪裁它。 ( 3 ) m c c p 2 0 1 ( m i n i m u mc o s t c o m p l e x i t yp r u n i n g ，最小代价复杂性剪枝) b r e i m a n 等人提出的m c c p 是一种后剪枝方法，在c a r t 系统中有所应用。首 先按照某种启发规则，得到从大到小的一系列决策树；然后，按照树的错误率的 估计，在决策树系列中选择具有最小期望错误率的最佳树。 ( 4 ) m d l i z l l ( m i n i m u md e s c r i p t i o nl e n g t h ，最小描述长度) m m e h t a ，j r i s s a n e n 和r a g r a w a l 等人提出的m d l 方法将构造的决策树中所 包含的信息量以二进制编码的形式来表示，利用编码的长度代表决策树某一分枝 的错误分类率的大小，进而决定是否需要剪枝，它的目的在于生成一棵描述长度 最小的决策树。 江苏大学硕士学位论文 2 2 3 经典决策树算法的分析与比较 c l s 是由h u n t 于1 9 6 6 年提出的完全搜索决策树方法，是决策树家族中最早提 出的算法，自此出现了多种决策树构造算法。其中，q u i n l a n 于1 9 8 6 年提出的i d 3 和1 9 9 3 年提出的c 4 5 是最有影响的决策树算法。 1 i d 3 算法 。 i d 3 算法是一种非递增算法，把信息熵的下降速度作为选取测试属性的标准。 设训练数据集为丁，其所分类有c l ，c 2 ，e ，将数据集丁划分到各分类中的概率 分别为丑，最，只，要确定数据集的分类所需要的信息量为： ，( 丁) = ，( e ，只) = 一只l o g ( p , ) ( 2 1 ) 假设根据条件属性x 将数据集丁划分为巧，砭，t o ，此时，确定数据集下各分类 所需的信息量