（应用数学专业论文）基于兴趣度的判定树算法快速分类的优化.pdf

摘要 摘要 数据挖掘在科研和商业应用中正发挥着越来越重要的作用。随着数据量的增 加，数据挖掘工具处理海量数据的能力问题显得日益突出。数据挖掘通常又称数 据库知识发现。为了系统的将数据挖掘技术应用与企业的决策，将企业的数据资 源转换为企业的核心竞争力，一个有效的方法就是将数据挖掘技术与企业知识库 技术有机地结合起来，形成分析研究和应用需求相互促进、知识与规则提取方法 的专业化的应用体系。 数据挖掘的基本任务是从海量数据中获取隐含在数据背后的有用的知识。数 据挖掘应用基本过程是集成历史数据，在此基础上建立挖掘模型，挖掘出有价值 的商业运作规律和模式，再将这些挖掘模型、规律和模式表示成易理解的规则集 成到企业知识库中，最后是将知识库知识应用于企业的商业活动。不同的数据挖 掘任务会产生出不同类型的知识。通过对这些知识类型结构和性质的研究，可以 得到相应的数据挖掘过程需要完成的任务集合，从而定义出规范的、完整的数据 挖掘算法流程。 决策树学习有很多算法，本文着重研究了对引入用户兴趣度参数的i d 3 算法 在面对多值属性时的快速分类的优化，在避免了多值弱相关属性覆盖少值强相关 属性的基础上，通过数学工具简化原算法的复杂度和编码代价，从而提高使用该 算法时的运算速度，尽量多的节约计算时间，从而达到降低成本的，提高效率的 目的。 关键词：决策树，归纳学习，i d 3 算法，机器学习 a b s n u c t a b s t r a c t t h ed a t am i l l i n gp l a ya n 血p o r t a n tr 0 1 ei n s c i c n t i f i cr e s e a r c ha i l db u s i n e s s a p p l i c a t i o n w i t l lt 1 1 ei n c r e a s eo fd a t aq u 趾t i t y 1 1 1 ep r o b l e mo fa b i l i 哆t od e a lw i mm c d a t ao fi n s 慨e n tw l l i c hu s e df o rd a t am i n i n gs e e m so u t s t a n d i n gd a yb yd a yt h ed a t a m i i l i n ga n du s u a l l yh a v ea 1 1 0 m e rn a m ec a l l e dm ek n o w l e d g eo f m ed 北m a s e t of i n d f o r s y s t 锄a t i cm i n j n gm ed e c i s i o no ft e c h n i c a l 印p l i c a t i o n 趾de 玎止e r p r i s eo ft l l ed a t a ， c h a n g et 1 1 ed a t ar e s o u r c e so fc n t e r p r i s e si n t ot h ek e yc o m p c t i t i v e n e s so fe n t e r p r i s e s ，a l l e 丘b c t i v em e t h o di st oc o m b i n em 访i i l gt e c h n o i o g ya n de n t e r p r i s e sk n o w l e d g eb a s e t e c h n o l o g yt o g e t l l e ro 唱a i l i c a l l y ，f o n nas y s t e mw h i c hi n c l u d er e s e a f c ho fa n a l w ea n d d e m a l l do fa p p l i c a t i o np r o m o t em u n j a l ly ，m em e t h o dt od r a w i n gt h em l ea dk n o w l e d g e p m f e s s i o n a l l y _ i t 曲p i i e s 也eu s e m lk n o w l e d g eb e h i n dd a l at h a tm ed a t am i n i l l gi so b t a i n e d 丘o m t h ed a t a t h ed a t am i n j n gu s e dt oi n t e 铲a t et h e1 l i s t o r i c a ld a t a ，s e tu pm em o d e lo f m i n i n go nm i sb a s i s ，m i n i n go u tv a l u a b l eb u s m e s sn 1 1 ea i l dm o d e t h e ns h o w st h e r n i n t oa 1 1i n t e l l i 百b l em l e ，a l l di n t e 铲a t e di n 铷t e r p r i s e sk n o w l e d g eb a s e t h e1 a s tt a s ki s a p p l ym ek n o w l e d g eb a s ei nm eb u s i n e s sa c t i “t yo fe n t e r p r i s e s w i l lp r o d u c ed i 疏r e n t k i n do f k n o w i c d g ei nd i 饪矗e n td a t ai i l i n i n gt a s kt 1 l r o u 曲l er e s e a r c ho ns 咖c t l l r ea n d n a m r eo f 也e s ek n o w l e d g e ，c a ng e tm ec o r r e s p o n d i n gi n f o m a i i o ni no m e rt a s ko fd a t a m i i l i n gw h i c hh a v es 锄em l e t h u sd e f i n et 1 1 en o mi nt h ep m c e d l l r eo fa l g o r i t h m so f d a t a m i n i n 晷 。 1 1 1 ed e c i s i o nt r e eh a da1 0 to fa l g o r i 恤n s ，t h i sp a p c rf o c u so nt 1 1 eo p 廿m i z a t i o no f 缸td a s s i 丘c a t i o ni nt h ef 犯eo f n - v a l u ea n r f b u t eo f i d 3a l g o r i t h mw h i c hh a dp a r a m e t e r s o f u s 目sm c r e s t o nt h eb a s i so f a v o i d i n gt l l ew e a kr e l e v a n t 砌b u t eo f n v a l u ec o v e r e d t h ew o n l ls 仃o n gr e l e v 柚ta t 砸b u t e ，s i m p l i 母c o m p l e x i t yo ft 1 1 eo r i g i n a la l g o r i t h 趴d c o d ec o s t 1 1 o u 曲t h em a m e i l l a t i c st 0 0 1 ，l u sr a i s et h es p e e do fo p e r a t i o nw h i l el l s i n g m i sa l g o r i t l l l t l ，a 1 1 d1 0 w e rc o s t si nt m ra sm u c ha sp o s s i b l e ，t or a i s em ee 伍c i e n c y k e y w o r d s ： t h ed e c i s i o n 仃e e ，i n d u c t i v el e a r n i n g ，a l g o r i t l l mo fi d 3 ，t h em a c h i n c l e a m i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：邑耋 日期：乃6 ( 年厂月易曰 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：至差导师签名：重雠 j 日期：跏6 够月2 珀 第一章绪论 1 1 数据挖掘的由来 第一章绪论 一切新事物的产生都是由需求驱动的。希望能让计算机自动智能分析数据库 中的大量数据以获取信息，是推动挖掘型工具产生并发展的强大动力。从数据管 理的角度来看，历史的数据是一笔宝贵的财富，而且这些数据正以几何级数或指 数级数增长。伴随着数据库技术的飞速发展以及人们获取数据手段的多样化，人 类所拥有的数据急剧增加，可是目前用于对这些数据进行分析的工具却非常之少， 所以人类通过这些数据所得到的信息量仅仅是整个数据库包含的信息量的很少的 一部分，隐藏在这些数据之后的更加重要的的信息是关于这些数据的整体特征的 描述以及对其发展趋势的预测，这些信息在决策制定的过程中起着非常重要的指 导作用。 例如，文献【1 】提到超级市场的经理人员希望能够从过去几年的销售记录中分 析出顾客的消费习惯和行为，以便及时变换营销策略；地质学家想通过分析地球 资源卫星发回的大量数据和照片来发现有开采价值的矿物资源等等。有一个很普 通却很能说明数据挖掘如何产生效益的例子：文献 2 】列举了美国加州某个超级连 锁店通过数据挖掘，从记录着每天销售信息和顾客基本情况的数据库中发现，在 下班后来购买婴儿尿布的顾客多数是男性，而且往往也同时购买啤酒。于是该店 的经理当机立断，重新布置了货架，把啤酒类商品布置在婴儿尿布货架附近，并 在二者之间放上土豆之类的佐酒小食品，同时把男士们需要的日常生活用品也就 近布置。这样一来，上述几种商品的销量大增。 通过上述的例子可以看出，数据挖掘能为决策者提供重要的、极有价值的信 息或知识，从而产生不可估量的效益。因此，虽然数据挖掘产品尚不成熟，但其 市场份额却正日益扩大，越来越多的大中型企业开始利用数据挖掘来分析公司的 数据以便帮助决策，数据挖掘正逐渐成为在市场竞争中立于不败之地的法宝。 在经过十几年的技术发展之后，国外在数据挖掘技术上取得了丰富的经验。 不但在研究方面使各个学科的经验向该领域集中，而且出现了大量的软件产品， 在社会的各个领域的应用也取得了丰硕的成果。 电子科技大学硕士学位论文 在国内，数据挖掘已经从单纯的研究走向产品的开发及技术的应用，随着市 场经济不断完善，数据挖掘的市场需求正在高速的增长。数据挖掘与其他软件不 同，由于需要不断地实验与评估，不懂原理或没有核心软件技术，其应用效果将 大打折扣。因此，在数据挖掘领域飞速的出现越来越多的专业学习和专业研究， 将数据挖掘推向又一个高峰。 1 2 什么是数据挖掘 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过程。这 些数据就是原始数据，它可以是结构化的，如关系数据库中的数据，也可以是半 结构化的，如文本、图形、图象数据，甚至是分布在网络上的异构型数据。发现 知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等等，还可以 用于数据自身的维护。因此数据挖掘是一门很广义的交叉学科，它汇集了不同领 域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的 学者和工程技术人员。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检 索查询调用，而且要对这些数据进行微观或宏观的统计、分析、综合和推理，以 指导实际问题的求解，企图发现事件之间的相互联系，甚至利用已有的数据对未 来的活动进行预测。例如，加拿大的某电话公司要求一个大学的数据挖掘研究组， 根据其拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法， 制定既有利于公司又有利于客户的优惠政策。文献【3 】列举了美国n b a 的著名篮球 队的教练，利用m m 公司提供的数据挖掘技术，临场决定替换队员，一度在数据 库界被传为佳话。这样一来，就把人们对数据的应用，从低层的末端查询操作， 提高到为各级经营决策者提供决策的支持。需要指出的是，我们所说的知识发现， 不是要去寻找一个放之四海而皆准的真理，也不是要崭新的自然科学定理和数学 公式，更不是什么机器的定理证明。所有发现的知识都是相对的，是有特定的前 提和约束条件的、面向特定领域的，同时还要易于被用户所理解和使用。 数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据之间关系的 过程，这些模型和关系可以用来做出预测或决策支持。 2 第一章绪论 数据挖掘的第一步是描述数据计算统计变量( 比如平均值、均方差等等) ， 再利用图表或图片直观地表现出来，进而可以看出一些变量之间的相关性( 比如 有一些值经常同时出现) 。选择正确的数据源对整个数据挖掘项目的成败至关重 要，在后面的数据挖掘的过程中将体现出其重要性。 单单是数据描述并不能为人们制定行动计划提供足够的依据，必须用这些历 史数据建立一个预言模型，然后再用另外一些数据对这个模型进行测试，一个好 的模型没必要与数据库中的所有数据都一一吻合，但它在做决策时是一个很好的 指南和依据。 最后一步是验证模型。比如用所有对产品推广计划做出回应的人的数据库做 了一个模型，来预测什么样的人会对产品感兴趣。是在得到这个模型后就直接利 用这个模型做出决定呢? 还是更稳妥一点先对一小部分客户做一个测试，然后再 决定? 数据挖掘是一个工具，它不能一直对数据库处于监视状态，随时在发现有 意义的模型时发出一个提示信息。它仍然需要了解业务，理解数据，确定分析方 法。数据挖掘只是帮助商业人士更深入、更容易的分析数据，它无法告诉某个模 型对企业的实际价值，而且数据挖掘中得到的模型必须要在现实生活中进行验证。 需要特别注意的是数据挖掘中得到的预言模型并不会告诉一个人为什么会做 一件事情或为什么采取一个行动，数据挖掘只能告诉使用者它可能会这样做，至 于为什么这样做就需要使用者去考虑。比如，数据挖掘可能会告诉你，如果这个 人是男的、年收入在5 万到6 万之间，那么他可能会买你的商品或服务。你能利 用这条规则，集中向这类人推销商品并从中获利，但是购买的原因还是要靠你自 己来探讨。 为了保证数据挖掘结果的价值，必须了解数据，这一点至关重要。输入数据 库中的异常数据、不相关数据、不相关的字段或有冲突的字段、数据的编码方式 等都会对数据挖掘输出结果的质量产生影响。 数据挖掘不会在缺乏指导的情况下自动地发现模型。不能让数据挖掘工具帮 我们提高直接邮件推销的响应率，而是应该让数据挖掘工具找对推销有回应的人， 或既回应又做了大量定单的人的特征。在数据挖掘中，寻找这两种模型是有很大 区别的。 虽然数据挖掘工具可让使用者不必再掌握高深的统计分析技术，但使用者仍 然需要知道所选用的数据挖掘工具是如何工作的，它所采用的是什么样的算法， 其原理是怎样的。所选用的技术和优化方法会对模型的准确度和生成速度产生很 大影响。 电子科技大学硕士学位论文 数据挖掘永远不能代替有经验的商业分析师或管理人员所起的作用，它只提 供一个强大的工具。每个成熟的、了解市场的公司都已经具有一些重要的、能产 生高回报的模型，这些模型可能是管理人员花了很长时间，作了很多调查，甚至 是经过很多失误之后得到的。数据挖掘工具要做的就是使模型得到的更容易、更 方便，而且有确实的依据。 1 3 数据挖掘的分类 数据挖掘系统利用的技术越多，得出的结果精确性就越高。原因很简单，对 于某一种技术不适用的问题，其他方法却可能很奏效。这主要取决于问题的类型 以及数据的类型和规模。 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务，可以 分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依 赖关系或依赖模型发现、异常和趋势发现等。根据挖掘对象分，有关系数据库、 面向对象数据库、空间数据库、时态数据库、文本数据库、多媒体数据库、异构 数据库、遗产数据库以及w 曲。根据挖掘方法，可分为机器学习方法、统计方法、 神经网络方法和数据库方法。机器学习包含归纳学习方法、基于案例学习、遗传 算法等。统计方法包含回归分析、判别分析、聚类分析、探索性分析等。神经网 络方法包含了前向神经网络、自组织神经网络等。数据库方法主要是多维数据分 析方法，另外还有面向属性的归纳方法。 数据挖掘所能够发现的知识有如下几种：广义型知识，反映同类事物共同性 质的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事 物之间属性差别的知识；关联型知识，反映事物之间依赖或关联关系的知识；预 测模型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏 离常规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念 树的提升，从微观到宏观，以满足不同用户、不同层次决策的需要。 1 3 1 分类分析 文献 4 】指出预言模型以通过数据库中的某些数据得到另外的数据为目标。若 预测的变量是离散的，这类问题就称为分类；如果预测的变量是连续的，这种问 题称为回归。分类一直为人们所关注。数据挖掘广泛使用的方法有决策树、神经 网络、径向基础函数等。 d 第一章绪论 基于债务水平、收入水平和工作情况，可对给定用户进行信用风险分析。分 类算法通过判断以上属性与已知训练数据中风险程度的关系给出语言结果。决策 树是一种常见且有用的预言模型。表1 1b 】是一个可用与判断信用风险的训练数据 集。客户的债务情况、收入情况、工作情况及信用情况被收集其中。 表1 1 判断信用风险的训练数据表 c u s t o mi dd e b t s a l a r y e m p l o y m e n t c r e d i tr i s k h l f o m a t i o ni n f j 肌a t i o n 聊e l h i 曲h i 曲s e l f e 1 p l o y e d b a d 2 h i 曲h i 班 s a l a r i e db a d 3 h i 曲 l o ws a l a r i e db a d 4l o wl o ws a l a r i e dg o o d 5l 0 wl o w s d f e m p i o y e d b a d 在这个普通的例子中，一个决策树算法对于信用风险预测来说，最重要的属 性是债务情况。因此决策树中的第一个分支点设在债务情况。叶子“d e b 仁h i 曲” 包含了三条“c r e d i tr j s k _ b a d ”而没有“c r e d i t 融s k _ g 0 0 d ”的记录。在这个例子 中，客户的高负债记录是他的信用风险大的充分条件。叶子“d e b t _ l o w ”仍然是 混合的其中一条“c r e d i t 砒s k _ b a d ”和一条“c r e d i t m s k = g o o d ”。在这种情况 下，决策树算法将用“e m p l o y m e n t 聊e ”作为第二判断条件。e i n p l o y m e n t 聊e 处分支得到两个叶子。它显示了受雇于自己的人有较高的信用风险。当然这只是 一个理想状况下的例子，事实上，对于每个信用申请者有远多过如此的属性，并 且申请者的数量是庞大的。当一个实用问题的规模发展到如此地步，再用人力去 寻找判断好坏的标准将是非常困难的。然而分类算法将可以判断成百的属性及数 百万的记录以建立描述规则的决策树。 1 3 2 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组。与预测模型不同，聚 类中没有明显的目标变量作为数据的属性存在。聚类算法通过检测数据判断“隐 藏属性”。这些案例将客户数据库分成若干相似的组，每组包含若干相似的客户， 针对每个不同的组可制定不同的销售策略。有很多方法可使数据分类，公认的常 用方法包括k - m e a m s 算、分层凝聚法以及采用估算最大值法使适应数据可能的混 合模型。一条记录有可能属于若干不同的分类。 电子科技大学硕士学位论文 参照如下例子【6 j ，雇员数据库中雇员有三个属性年龄、工资、公司退休金 计划中既定的数量。用户有可能提出查询，要求生成一张交叉表：求雇员的平均 年龄，要求这些雇员的退休金数在1 0 0 1 0 也0 0 k 、2 0 0 k 4 0 0 k 、4 0 0 k 1 0 0 0 k ，并且 工资分别在5 0 k 1 0 0 k 、1 0 0 k 2 0 0 k 、2 0 0 k 3 0 0 k 。在传统方法中，上述查询的层 次在每个维中是动态的、不可预测的。 多维数据记录可看作多维空间中的点。举例来说，记录如( a g e ，s a l a r y ) 可看作二维空间中的点，其维度是a g e 和s a l a r y 。表1 2 为上例的数据，图l 一1 为二维空间坐标图。 表1 2二维数据表 a g es a l a r y 2 5 5 0 0 0 0 2 75 5 0 0 0 2 65 8 0 0 0 4 0 8 5 5 0 0 5 0l 0 0 0 0 0 5 51 3 0 0 0 0 5 71 2 0 0 0 0 a g e 图l - 1 二维示例图 现在假设某人将以某种形式对上述查询结果加以展示。他可提供平均年龄和 平均工资以及它们的的标准方差。这将表示为这群雇员平均工资为8 5 5 k ( + ，一3 5 5 k ) 其年龄为4 0 ( 十- 1 5 5 ) 。进一步想象，所有员工分为两类，如表1 3 数据所示。 6 第一章绪论 表1 3 分类表 g r o u pa g es a l a r y 平均年龄标准方差平均收入标准方差 s e 鲫肌t l 2 6 v e a r s1 o5 4 3 k4 s e g m e n t 2 5 4 v e a r s3 61 1 6 6 k1 5 2 如表1 3 所示，数据不仅被指明比较两个独立的组织问的不同，并且其平均值 在每一个组中都更有意义。 如何表明上述表述正是聚类算法所要做的。当维数为2 时，组的划分可能比 较简单；但是维数更大的情况下，用人工来分类是非常困难的，因为数据简单的 划分已经没有意义了，并且划分数据因为数据点极多而变得非常复杂。但是聚类 算法能够自动对数据分类，每一段有自己的分布表示。本例使用了最少的维数， 但是更多的维数也可用多维分布来表示和判断。聚类算法可处理各种分布形式， 并且生成有用的聚合值的组。 1 3 3 关联分析 关联分析描述了这样一种方法，它的目的在于生成部分数据的概要，例如寻 找数据子集间的关联关系或者一些数据与其数据之间的派生关系。本领域最常见 的技术是利用关联规则。有些时候如商场销售分析，关系规则的计算以来于识别 在相关数据中频繁出现的数据集。频繁出现的数据由在某事务中同时出现的数据 组成。 频繁出现的数据组可用于描述在超级商场中客户有意同时购买的商品名称。 例如，文献【7 】列举了如想了解清楚某网站被用户访问的情况，经常出现的数据组 也可表示为在某次站点访问时间中被访问的页面集。这样，零售商可通过关联技 术将相关商品摆在一起进行组合销售。通过规定一个最小支持度，数据挖掘算法 能够从数据集中找出同时销售的商品。假设有一组销售数据并有与之相对应的支 持度的关联数据。其中需要注意的是：随着支持度的减小，关联数据组的数量急 剧增长。通常情况下，在实际的业务数据库中，不管是销售数据库、网站访问行 为分析，还是客户服务记录，有较高支持度的关联数据量是非常小的，随着支持 度的减小，其数量将呈指数级增长。 一旦关联数据被推导出，即可用于生成关联规则。关联规则是这样产生的： 选定关联数据中的某一类为预测目标，给其他类赋值作为预测规则的条件。举例 7 电子科技大学硕士学位论文 来说，文献 8 列举了如果有“牛奶和黄油的支持度均为3 ”则可以导出如下规则： 如果一客户购买牛奶，则他也会购买黄油。 但是，实际上，这一规则的有效性并不如想象的那么高，因为这仅仅是一种 可能，与实际上还是有所区别的。 1 3 4 序列分析及时问序列 序列分析和时间序列说明数据中的序列信息和与时间相关的序列分析。 在分类与回归模型、聚类和关联分析中，时间产生的序列信息被忽略或简单 的被作为一条记录对待。举例来说，文献 9 】列举了在一组统计用户访问网站信息的 数据中，假设用户u 7 7 4 访问网页顺序如下： p 0 一p 2 一p 1 3 一p 1 7 。这一事件简单的被记录如下： u s c ru 7 7 4 ：v i s i t c d p a g c o ，p a g e 2 ，p a g e l 3 ，p a g e l 7 另外一种做法，它可以很好的被表示为序列信息，这意味着其他用户依照不 同顺序访问同样的网页，将与u 7 7 4 区别开来。 这类方法关注于下述几个方面之一： 总结数据的序列或者事件； 检测数据随时间变化的变化； 检测知识随时间变化的变化。 对于第一种情况来说，假设用户访问站点顺序的习惯如图1 2 。 图1 2 访问顺序图 从数据中得到的序列可能表明对给定的站点，有9 0 的用户访问过p a g eo ， 第一章绪论 2 的用户是从p a g e l 0 进入的。这序列也可能表明有p a g e 6 0 的用户从p a g e 0 到 了p a g e1 5 ，4 0 到了p a g e1 。图1 2 总结了经排序的联系并给出有关流程。确实 在p a g e1 5 p a g e1 7 之间有可能有无序的访问，但只有有序的访问才被报告。 1 3 5 孤立点分析 孤立点是实际生活中的反常行为的写照。用距离的观点来定义，孤立点就是 那些离密度较高的大部分点较远的点。例如，税务稽查机关在选案的过程中，先 从数据仓库中根据企业的规模、行业、地区等维度查找出若干企业，将这些数据 再用数据挖掘软件查找纳税额明显偏低的企业，可以将这些企业作为有逃税嫌疑 的企业进行稽查。 1 4 数据挖掘的体系结构 数据挖掘的核心技术是人工智能、机器学习、统计学等等，但一个数据挖掘 系统不是多项技术的简单组合，而是一个完整的整体，它还需要辅助技术的支持 才能完成数据的采集、预处理、数据分析、结果表述这一系列任务，最后将分析 结果呈现在用户面前。 根据数据挖掘与数据库以及数据仓库的耦合程度可以分为零耦合、松散耦合、 半紧密耦合以及紧密耦合四种机构。文献【1 0 定义零耦合是指数据挖掘与数据仓库 及数据库没有任何关系，输入数据是从文件中取出的，存放结果也是存放在文件 中，这种结构一般很少使用。松散耦合是指利用数据仓库或数据库为数据挖掘的 数据源，其结果写入文件、数据库或数据仓库中，但不使用数据库以及数据仓库 提供的数据结构以及查询优化方法。半耦合是指部分数据挖掘原语出现在数据仓 库或数据库中。紧密耦合是将数据挖掘集成到数据库或数据仓库中，作为其中的 一个组成部分。目前的发展趋势是紧密耦合的系统结构。 第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法设计用来 挖掘向量数据，这些数据模型在挖掘时，一般一次性调进内存进行处理。许多这 样的系统已经商业化。这些系统的成功依赖于数据的质量。 第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具 有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集合，以 及高维数据。这一代系统通过支持数据挖掘模式和数据挖掘查询语言增加系统的 灵活性。文献 1 1 指出第二代数据挖掘系统提供数据仓库和数据挖掘系统之间的有 电子科技大学硕士学位论文 效的接口。在实施策略方面，如果数据足够大，并且频繁的变化，这就需要利用 数据库或者是数据仓库技术进行管理和优化，这就是说第二代数据挖掘系统是必 不可少的。不过其兼容缺陷也是明显的，因为目前的数据仓库设计是方便o l a p 操 作的，而不是数据挖掘应用，这就表明第二代数据挖掘系统必须使用自己的专门 的数据管理系统。 第三代的特征是能够挖掘i n t e m e t e x h 锄e t 的分布式和高度异质的数据，并且 能够有效地和操作型系统继承。这一代数据挖掘系统关键的技术之一是提供对建 立在异质系统上的多个预言模型以及管理这些模型的元数据提供第一级别的支 持。第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口。第 三代数据挖掘系统和预言模型系统的一个重要的优点是由数据挖掘系统产生的预 言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模块相联合提 供决策支持的功能。 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统和普遍存在计算设备产 生的各种类型的数据，这是当前一个很有潜力的研究领域。 1 5 研究内容以及主要创新 决策树方法自使用以来，在机器学习、知识挖掘等领域得到了广泛应用，其 可用于知识的自动获取过程，其中表现为在对一个分类型问题或建立规则型问题 的处理，是被采用最多、研究最多的一种方法。决策树方法顾名思义是一种树状 它采用贪心算法，从根节点开始，以一种倒树状结构进行建立，其建立的依据是 对数据样本进行测试所得到的信息熵，根据得到的熵按判定标准将数据样本划分 成不同的数据样本子集，每个子集即构成一个节点，再对该子集进一步划分，生 成新的子节点，往复循环直至达到用户设定的标准时停止。 决策树学习有很多算法，本文着重研究了对引入用户兴趣度参数的i d 3 算法 在面对多值属性时的快速分类的优化，主要目的是提高使用该算法时的运算速度， 尽量多的节约计算时间，从而达到降低成本的，提高效率的目的。 1 0 第二章预备知识 2 1 数据分类 第二章预备知识 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的 目的是学会一个分类函数或分类模型，该模型能把数据库中的数据项映射到给定 类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据记录 中自动推导出给定数据的推广描述，从而能对未来数据进行预测。 要构造一个分类器，需要一个训练样本数据集来作为输入。文献 1 2 定义训练 样本数据集亦称训练集，是由数据库记录组成的。每一条记录包含若干条属性， 组成一个特征向量。训练集的每条记录还有一个特定的类标签与之对应。该类标 签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为向量： ( k ，；c ) 。在这里_ 表示字段值，c 表示类标签属性的值。 分类的目的是”：分析输入数据，通过在训练集中的数据表现出来的特性， 为每一个类找到一种准确的描述或者是模型。这种描述用来对未来的测试数据进 行分类。尽管这些未来的测试数据的标签是未定的，但仍然可以由此预测这些新 数据所属的类。注意这些预测并不是肯定会发生的。 定义2 1 4 j 设置，x ：，x 。，c 是随机变量，其中x ，的域为d d m ( 五) ；在不失 一般性的前提下，设d 伽( c ) = 1 ，2 ，七 。一个分类器就是函数： d ：d 伽啤1 ) d 伽啤2 ) d d m ( x 。) 斗d 叫( c ) 。 设p 忸，c ) 是在d o m e 。) d o 吖：) d o 时伍。) d d m ( c ) 上的概率分 布，定义f = ( z 。，t 盖：，f z 。) 是一个随机地从尸中得到的记录， 即f 有概率p 僻，c j ，其中( f 一1 ，f z 2 ，f 。) x ，r c c 。 定义分类器d 的误分类率为：尸p “f 五，f 互，f 邑，) ) f c ) 。 与使用的数据库术语结合起来，以尸分布的随机样本集就是训练数据库d ，工， 为对应属性，称为非类别属性，c 称为类标签属性。 分类描述为u5 j ；给定一训练数据的集合丁，丁中的元素记录由若干个属性描 述。在所有属性中有且仅有一个属性作为类别属性。属性集合用矢量 电子科技大学硕士学位论文 x = ( 蜀，x 。) 表示，其中工；( 1 f h ) 对应各非类别属性，可以具有不同的值域， 即对于任一属性x ：= k ，x 。 ，m ；随属性的不同而变化。当一属性的值域为连 续域时，该属性称为连续属性，否则称为离散属性；用c 表示类别属性， c = c ，c 。 ，即数据集有置个不同的类别。那么，r 就隐含地确定了一个矢量x 到类别属性c 的映射函数：日：厂( 工) 斗c ，分类的目的就是采用某种方法将该映 射函数日表示出来。 不同的分类器有不同的特点。文献 1 6 提出有三种分类器评价或比较尺度：预 测准确度；计算复杂度；模型描述的简洁度。预测准确度是用得最多的一种比较 尺度，特别是对于预测型分类任务，目前公认的方法是1 0 折分层交叉验证法。计 算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨 量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述 型的分类任务，模型描述越简洁越好。 另外需要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大， 有的有缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而 有的是连续值或混合式的。目前不存在一种可以适应各种类型数据的方法。 2 1 1 决策树的基本算法 2 1 1 1 决策树生成算法 数据分类操作通常有以下两个步骤u 7j ： 第一步，根据给定的训练数据集，找到合适的映射函数日：厂( z ) _ c 的表示 模型。这一步称为模型训练阶段。 第二步，使用上一步训练完成的函数模型预测数据的类别，或利用该函数模 型，对数据集中的每一类别进行描述，形成分类规则。 作为分类器，决策树是一棵有向、无环树。这里以二叉决策树为例给出相关 概念的描述u 8 j ：树中的根节点没有父节点，所有其他节点都有且只有1 个父节点； 1 个节点可以有l 2 个或没有子节点。如果节点没有子节点，称其为叶节点；其 他的称为内部节点。文献【1 9 规定每个叶节点都对应于一个类别标识c 的值；每个 内部节点都对应于一个用于分割数据集的属性z 。，称为分割属性；每个内部节点 都有一个分割判断规则g ，： 如果置是连续属性的，那么g ，的形式为j 。x ，其中x 。d 侧；) ，_ 就 第二章预备知识 是节点n 的分割点； 如果墨是离散属性，那么g 的形式为一i ，其中誓c d d m 伍；) ，e 就成为 节点”的分割子集。节点 的分割属性和分割判断规则组成了节点n 的分割标准。 决策树分类算法通常分为两个阶段：决策树构建和决策树修剪。表2 一工 2 0 】是通 用的t o p d o w n 决策树构建算法。 由算法可知，分割方法嬲m 是决策树的算法的关键。 一个决策树就是一个类别分辨器，它递归地对训练集进行划分，直至每个子 集的记录全属于一个类或某一类占压倒性的多数。图2 1 给出了基于表2 2 的一 个决策树分类器。 表2 _ 2 决策树分类结果表 记录年龄汽车类型风险 o2 3 f 锄i l yh i 曲 11 7 s p o r t sh i 曲 24 3 s p o r t sh i 曲 36 8f a m i l vl o w 4 3 2t m c k l o w 52 0f a m i l v h i 曲 电子科技大学硕士学位论文 a g e ( 2 5 h l g h l o w 图2 1 树型结构图 ( a g e 2 5 ) 和( c a 订卯e s p o r t s ) ) 是两个分割点，它们将记录划分为高、低风险 两类。这个决策树可用于鉴别未来保险申请人的类别：申请是高风险还是低风险。 在构建树的阶段，通过递归地将数据划分成子集，并保证每个子集要么是“纯” 的( 所有记录都属于同一类) ，要么足够小( 由用户设定某一参数来界定) ，依次 来构建一棵树，其过程由图2 1 给出。文献【2 2 】中规定用于划分数据的分割形式取 决于属性的类型：对连续属性a 而言，其分割形式为v 砒u c ( a ) x ，其中x 为a 域 中的某一值；对离散属性，其分割形式为v a l u e ( a ) x ，其中x d o m ( a ) 。我们 只考虑二叉分割的情况，因为这样生成的树的准确度更高。但是，树一旦生成后， 便进入第二阶段修剪阶段。这个阶段主要是通过消除由于统计噪声或数据波 动对决策树的影响来达到净化树的目的。 通常，建树阶段的耗时往往比修剪阶段的要大，因为在建树阶段要对数据进 行多次扫描，而修剪阶段只需访问生成的决策树而已。而且，依据在s l i q 上的经 验，修剪的耗时一般只占建树的1 。 在建树阶段，要特别关注以下两个方面： ( 1 ) 如何找出用于定义节点测试的分割点。 ( 2 ) 若已选定某分割点，如何将数据进行划分。 2 1 1 2 决策树的修剪 目前决策树修剪的策略有三种：基于代价复杂度的修剪，悲观修剪和m d l 修 剪。基于代价复杂度的修剪使用了独立的样本集用于修剪，即与用于树的构建过 程中使用的样本集不同，称为修剪样本。在很多情况下，特别是当训练集很小时， 更期望所有的样本既用于树的构建也用于树的修剪。文献 2 3 】提到悲观修剪是 q u i l l l a l l 在1 9 8 7 年提出的，将所有的训练样本都用于树的构建与修剪，经验表明， 该方法产生的树太大并且有时精度不高。在实际使用中用的较多并且效果较好的 1 4 第二章预备知识 是m d l 修剪。 ( 1 ) 修剪的基本算法 修剪树的基本算法如下表2 3 在算法中c ) 、c 舢( ) 分别以s 、节点的记录创建树的代价，其计算公 式为： ) 2 渺蚓+ 孚崦料崦2 l 南j 陋， 式中，聆为s 中的总记录数；c 为数据集s 的类别数；n 为j 中属于类别f 的记录数。 算法中，q 。p ) 的求解分为以下两种情况。 当分割属性为连续属性时： c ) = 1 0 9 2n + l 0 9 2 ( v 一1 ) ( 2 2 ) 当分割属性为离散属性时： c o f i f ( s ) = 1 0 9 2d + 1 0 9 ：( 2 ”一2 ) ( 2 - 3 ) 式中，d 为决策树可用的属性个数；v 为某分割属性可能取值的个数。 ( 2 ) m d l 修剪算法 m d l 原理口4 】即最小长度描述原理，类似于m m l 原理即最小消息原理，早已 成功地应用于机器学习，该方法主要用于归纳决策树。决策树生成后面i 临的问题 是树的过度细化，特别是存在噪声数据或不规范属性时更加突出，决策树的修剪 就是对过度细化的模型进行调整。应用m d l 原理对规则集的精确度及精简程度是 电子科技大学硕士学位论文 一种可行的解决方案，长度的概念是所需编码的比特长度。一个规则集即模型的 消息长度定义如下： 总的消息长度= 描述模型的消息长度+ 给定模型后描述数据的消息长度。 对于这种方法的一种解释是： 文献 2 5 借助一个通信模型，在该模型中，发送者给接受者发送一个描述，该 描述是由一个模式丁及数据d 组成的，由r 和d 可推导出正确的描述。因为r 是双 方事先约定好的，描述的长度首先与丁的编码大小有关，其次与给定丁之后的数据 d 相关。这种方法的特点是，模型越复杂，对模型编码的比特长度就越长，这时 就可以使用较少的数据来表示描述；但数据越多反而越节省模型编码的比特长度。 即m d l 使两个方面达到平衡：若模型越通用，编码越小，则对数据的误分类率就 越高，就需要多的信息对其更正；反之，模型对数据描述得非常精确，但模型的 使用量就越少，因此，需要更多的编码信息，故需要二者之间达到平衡。 这种方法的另一种解释口】是：基于统计学的解释，即利用贝叶斯推理。对于 给定的数据。，可以选择一个假设h ，使p ( 芸) 最大。可以从最大似然度原理推 导出m d l 原理。设日是一个假设，h 4 ，爿= 扫i ) ，d 是一个观察的数据集， 则由贝叶斯法则有： p 盼p 2 嚣鬻 p 4 ， 希望找到假设日+ ，使得p p ，d ) 最大，则有： 日= a r s 叫鲁 且日 c z 卸 对( 2 4 ) 两边取对数得： 山g ：删叫如) _ l p ( 珈删 ( 2 _ s ) 使得尸( 告 最大化等价于使一l 。g ：攻鲁 最小。由于1 。g ：p ( d ) 是常数，则等价于使 1 6 第二章预备知识 f 式( 2 - 7 ) 最小： 一l o g ：p 呱) 一l o g ：p 仁) 垦) 若将一l o g ：，喊) 看作从假设日中得到的信息量，记为，( h ) 同理可得： 尸m ) 记为仨 ， 则式( 2 4 ) 与( 2 5 ) 可改写为： 儿a r g 叫删+ ，卜日爿 ( 2 7 ) ( 2 8 ) 式( 2 8 ) 证明概率最大的假设使在假设及样本中的信息量之和最小，即等价于m d l 原理。 2 2 决策树i d 3 i d 3 是为了从数据中归纳分类模型而构造的算法，也称为决策树。