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

摘要 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知识的过程。 在这一过程中，对数据的分类是数据挖掘领域研究的重要课题。 本文阐述了数据挖掘和分类技术的理论基础，主要介绍如何利用决策树方 法对数据进行分类挖掘，详细的描述了决策树的基本知识和相关算法，并对几 种典型的决策树算法进行了分析和比较。主要研究工作如下： 1 在分析x m l 技术和决策树的基础上，提出了一种决策树在x m l 数据库挖 掘中的分析模型，为解决不同数据接口问题进行了有益的尝试； 2 针对i d 3 算法倾向于取值较多属性的缺点，引入概率影响因子对i d 3 算 法作了修正，使决策树减少了对取值较多的属性的依赖性，并通过使用学生信息 训练集对两种算法建立的决策树进行比较，取得了良好的效果； 3 利用修正后的决策树算法，使用c + + 语言，在兰州气象局气象技术保障 网络管理信息系统中进行数据挖掘，为决策部门提供了合理、科学的决策根据。 关键词：数据挖掘，决策树，x m l ，i d 3 算法，信息熵，概率影响因子 a b s t r a c t d a t am i n i n gm e a n st h ep r o c e s so fi n c o m p l e t e ，n o i s y , f u z z ya n dr a n d o md a t a ， e x t r a c t i o no fi m p l i d t ，i nw h i c hp e o p l ed o n tk n o wi na d v a n c e ，b u tp o t e n t i a l l yu s e f u l i n f o r m a t i o na n dk n o w l e d g e i nt h i sp r o c e s s ，t h ec l a s s i f i c a t i o no fd a t ai nd a t am i n i n g i sa l li m p o r t a n ts u b j e c to fs t u d y t h i sp a p e re x p o u n d st h et e c h n i c a ld a t am i n i n ga n dt h ec l a s s i f i c a t i o no fb a s i c t h e o r y , m a i n l yi n t r o d u c e sh o wt ou s et h ed e c i s i o nt r e et o d a t am i n i n gm e t h o do f c l a s s i f i c a t i o n ，d e c i s i o nt r e ei sd e s c r i b e di nd e t a i lt h eb a s i ck n o w l e d g ea n dr e l a t e d a l g o r i t h m s ，a n ds e v e r a lt y p i c a la l g o r i t h m so fd e c i s i o nt r e ea n a l y s i sa n dc o m p a r e d t h em a i nr e s e a r c hw o r ka sf o l l o w s ： 1 a n a l y s i so fx m lt e c h n o l o g ya n dt h eb a s i so ft h ed e c i s i o nt r e e ，at r e ei nt h e x m ld a t a b a s em i n i n gi nt h ea n a l y s i sm o d e l ，w h i c hc a ne f f e c t i v e l ys o l v et h e p r o b l e mo fd i f f e r e n td a t ai n t e r f a c e 2 i d 3a l g o r i t h mb a s e do nt h ea t t r i b u t ev a l u e st e n dt ob em o r ed i s a d v a n t a g e s ， i n t r o d u c i n gt h ep r o b a b i l i t yo fi n f l u e n c i n gf a c t o r so fi d 3a l g o r i t h mc o r r e c t e d ，m a k e t h ed e c i s i o nt r e et or e d u c et h ed e p e n d e n c eo ft h ea t t r i b u t ev a l u e s ，a n dt h r o u g ht h e u s eo fs t u d e n t s i n f o r m a t i o nc o l l e c t i o no ft w ok i n d so fd e c i s i o nt r e ea l g o r i t h mo f c o m p a r i s o n ，a c h i e v e dg o o de f f e c t 3 u s i n gt h e m o d i f i e dd e c i s i o nt r e ea l g o r i t h m ，u s i n gc + + l a n g u a g e ，i n m e t e o r o l o g i c a lt e c h n i c a lg u a r a n t e ei n f o r m a t i o ns y s t e m i nd a t am i n i n g , a n dt o p r o v i d e ar a t i o n a ld e c i s i o n m a k i n gd e p a r t m e n t s ，t h es c i e n t i f i cd e c i s i o n - m a k i n g b a s i s k e y w o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，x m l , i d 3 ，i n f o r m a t i o ne n t r o p y , p r o b a b i l i s t i ci n f l u e n c ef a c t o r 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行 研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数 据、观点等，均己明确注明出处。除文中已经注明引用的内容外，不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做 出重要贡献的个人和集体，均己在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 淞 日 期：垒与垃 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该论文直接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：2 ：訇丝墅! 缨导师签名： 日期 2 q 兰州大学硕士学位论文基于决策树分类算法研究 1 1 研究背景和意义 第一章引言 随着信息技术的快速发展，人们收集、存储和访问的数据急剧增加，各行 各业拥有大量的数据信息，对这些快速增长的海量数据进行分析和知识的理解 已经远远超出了人们的能力。大量的数据被描述为“数据丰富，但信息贫乏 。 目前的数据库系统，如o r a d e l l g 、s q l s e r v e r 2 0 0 5 等虽然可以高效的实现数据 库的录入、查询、统计等功能，但无法准确发现数据中隐含存在的关系、规则、 论断以及根据现有的数据预测未来的发展趋势，远远不能满足现实的需要。而 大量激增的数据中往往又隐藏着许多重要的信息，如果能把这些信息从数据库 中提取出来，就能为用户创造很多潜在的价值。这就需要有新的、更为有效的 手段来对各种数据源进行整理并挖掘，以发现新的知识规则并发挥这些数据的 潜能。8 0 年代末兴起的数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， k d d ) 及其核心技术数据挖掘( d a t am i n i n g ，d m ) 1 1 2 l 正是在这样的应用需求下产 生并迅速发展起来的一门技术。数据挖掘技术为解决这一问题而被提出并迅速 发展起来，近年来成为研究的热点。 数据库中的知识发现是从数据库中识别出有效的、新颖的、潜在有用的， 以及最终可理解的模式的非平凡过程。数据挖掘是知识发现的一个核心步骤。 知识的发现过程一般包括：数据准备、数据挖掘阶段、选择合适的工具、挖掘 知识的操作以及结果的解释和评价。 目前知识发现和数据挖掘技术己经成为计算机界新的研究热点之一，引起 数据库、机器学习、统计等领域专家的广泛关注。数据挖掘的方法有多种，包 括分类、预测、聚类、关联规则挖掘、序列模式挖掘等，其中分类问题是被广 泛研究的课题之一。分类是指把数据项映射到一个事先定义的类中的学习过程， 即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。 分类学习的目标是构建一个分类模型，它在构造模型时需要知道训练集中每个 样本所属的类，因此是有指导的学习方法。 数据挖掘中广泛使用的分类方法有决策树、贝叶斯分类、规则推理、遗传 兰州大学硕士学位论文 基于决策树分类算法研究 算法以及神经网络等；其中决策树方法是一种较为通用并深入研究的分类函数 逼近法，它是一种常用于预测模型的算法，通过将大量数据有目的地分类，从 中找到一些具有价值的、潜在的信息。相对于其它分类方法，决策树算法应用 最为广泛，其独特的优点包括： 1 学习过程中使用者不需要了解很多背景知识，只要训练事例能够用属性 结论的方式表达出来，就能用该算法进行学习； 2 决策树的训练时间相对较少，其它的分类方法如神经网络，即使对小数 据集也要花费很多的训练时间； 3 与神经网络或贝叶斯分类等其他分类模型相比，决策树的分类原理简单 易懂，很容易被使用人员理解和接受； 4 决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式； 5 可以将决策树中到达每个叶子结点的路径转换为“i f - t h e n 形式的分 类规则，这种形式更有利于理解。 但决策树方法也存在着缺点： 1 随着数据复杂性的提高，其分支也增多，增加了管理上的困难； 2 分类数据的预处理工作，不仅增加了算法的额外开销，而且降低了分类 的准确性； 3 存在缺值处理问题。 目前，已有多种决策树算法，如c l s ，i d 3 ，c h a i d ，c a 5 ，c a r t , s l i q ，s p r i n t 等。各种决策树算法的主要区别在于测试属性的选择、决策树的 结构及剪枝策略的不同。 1 2 国内外研究现状及进展 目前决策树算法被广泛应用于多个领域，它经历了一个由浅到深、由简单 到复杂的过程。下面是国内外决策树算法发展过程中的一些重要进展1 3 7 l ： 1 9 6 6 年，h u n i 等人研制了一个概念学习系统( c l s ：c o n c e p tl e a r n i n g s 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 e r 3 ) 算法是 2 兰州大学硕士学位论文基于决策树分类算法研究 决策树算法的代表【9 | 。i d 3 采用分治策略，在节点处选择属性时，用信息熵作为 属性的选择标准。它的贡献是把信息论中的信息熵概念引入了决策树算法中。 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 d r e g r e s s i o nt r e e ) 算、法t 3 8 1 。这种方法选择具有最小g i n i 指数值的属性作为测试属 性，生成最终二叉树，再利用重采样技术进行误差估计和剪枝，然后选择最优 的作为最终构建的决策树。算法要训练集全部或一部分在分类过程中一直驻留 在内存中。 1 9 9 3 年，j r q u i n l a n 又提出了c 4 5 算法m ，目的在于克服i d 3 算法在应用 中的不足。c a 5 算法对于i d 3 算法的重要改进是使用信息增益率来选择属性。 c a 5 算法能处理连续值属性的数据，弥补了i d 3 算法只能处理离散值属性数据 的缺陷。c 4 5 算法还可用于增量式学习，随着数据量的增加动态地调整决策树， 克服了i d 3 算法在这个方面的缺点。 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 ) 分类方法【剐。s l i o 针对数据量远大 于内存容量的情况采用了三种数据结构：类表、属性表以及类直方图，采用换 入换出的策略处理大数据量。在建树阶段，对连续属性采取预排序技术与广度 优先相结合的策略生成决策树，对离散属性采取快速的求子集算法确定划分条 件。同年，j s h a f e r 和r a g r a w a l 等人提出可伸缩并行归纳决策树( 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 nt r e e s ) 分类方法，它是一种规模可变 的、支持并行计算的分类方法。s p r i n t 分类方法最大的优点就是可以避免内 存空间的限制，利用多个并行处理器构造一个稳定的、分类准确率很高的决策 树，具有很好的可伸缩性，扩容性；但是该算法的节点分割处理过程复杂，并 且存储能力要就较高。 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 n t r e et h a ti n t e g r a t e sb u i l d i n ga n dp n l n i n g ) 分类算法【4 1 ，p u b l i c 算法提出了节点代 价的目标函数，其主要思想是在决策树建立阶段，计算每个节点相关的目标函 数值，然后估计该节点在将来调整阶段是否被删除；如果该节点将被删除，则 不对该节点进行扩张，否则，扩展该节点。从而建树和修剪阶段结合成为一个 阶段，而不是依次执行这两个阶段，提高了决策树的执行效率。同年，j g e h r k e 3 兰州大学硕士学位论文 基丁决策树分类算法研究 和r r a m a k r i s h n a n 等人提出雨林( 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 ) 算法【删。高效c 4 5 算法采用二分搜索取代线性搜索，还提出几种不同的寻找连 续属性的局部阈值的改进策略。实验表明，在生成同样一棵决策树时，与c 4 5 相比，e c 4 5 可将效率提高5 倍，但e c 4 5 占用内存比较多。 国内的许多学者也在决策树算法上进行了深入的研究，并取得了一些成果。 1 9 9 8 年，刘小虎博士和李生教授提出，决策树优化【4 1 j 是决策树学习算法中 十分重要的分支。以i d 3 为基础，提出改进的递归信息增益优化算法。每当选 择一个新的属性时，算法不仅仅是考虑该属性带来的信息增益，还需要考虑到 该属性后选择的属性带来的信息增益，即同时考虑树的两层节点。 2 0 0 1 年，郭茂祖博士和刘扬教授针对i d 3 多值偏向的缺陷，提出了一种新 的基于属性一值对为内节点的决策树归纳算法a v p i ，它所产生的决策树大小及 测试速度均优于i d 3 。 2 0 0 3 年，杨宏伟博士和王熙照教授【4 2 l 等用基于层次分解的方法通过产生多 层决策树来处理多类问题。 2 0 0 6 ，阳东升博士等通过对组织协作网与决策树的描述分析提出了组织结 构设计的新思路基于决策个体在任务上的协作关系设计最佳的决策树。 1 3 决策树发展方向 随着数据挖掘技术的兴起，决策树技术将会得到更广泛的应用。目前决策 树技术的主要研究方向有以下几点： 1 决策树的精度 决策树的预测精度一直是研究的重点，判断各种决策树的生成算法和剪枝 算法的优劣，精度是最重要的衡量指标。 2 决策树技术与其他技术的结合 4 兰州大学硕士学位论文 基于决策树分类算法研究 如何将决策树技术和其他新兴的技术相结合以便取长补短一直是决策树技 术研究的热点。现在已经有人把决策树方法同神经网络技术、模糊集理论、遗 传算法等相结合来进行研究，结果不同程度地提高了处理效率和精度。 3 寻找新的构造决策树的方法 从q u i n l a n 提出i d 3 和c 4 5 方法后，虽然有不少专家提出了其它构造决策 树的方法。但仍然很难找到一种适合于所有情况的高效算法，这是今后决策树 研究的难点。 4 寻找更好的简化决策树方法 简化决策树的研究工作主要有两个方面，一是对比各种不同的简化决策树 方法，分析它们各自的特性、优点和缺点；另外一个就是寻找更好的与传统方 法不同的简化决策树的方法。 5 决策树的训练和检验数据的大小及特性与决策树特性之间的关系 训练数据的增加经常造成决策树大小的线性增加，而这种增加并没有都带 来决策树准确性的提高，在产生决策树前尽量减少数据量比在决策树产生后再 简化决策树更加有效，这就是数据预处理技术。 6 不确定环境下决策树研究 实际的数据集中存在着一些缺值数据，最简单的方案是删除带有未知属性 值的例子或是将未知属性值用最常用的值代替，j r q u i n l a n 提出的一种解决方 案是依据对象的其它属性值和类信息来预测未知属性的属性值。 7 决策树技术中时间复杂度与准确性之间的矛盾 决策树技术中如何处理时间复杂度和分类准确性之间的矛盾是一个令人感 兴趣的问题。随着微处理器速度越来越快、价钱越来越便宜，以及并行计算的运 用，使人们在做决定时拥有比以前更大的自由。 8 决策树技术的软件实现 如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决 策树技术，一直是大家努力的方向。 5 兰州大学硕士学位论文基于决策树分类算法研究 1 4x m l 在数据挖掘中的应用 1 4 1 】l 知识 x m l 是e x t e n s i b l em a r k u pl a n g u a g e 的缩写，扩展标记语言x m l 是一种 简单的数据存储语言，使用一系列简单的标记描述数据【2 2 期。 x m l 数据库是一种支持对x m l 格式文档进行存储和查询等操作的数据管 理系统。x m l 数据库有良好的扩展性、出色的性能、管理x m l 文档版本的能 力和链接内容中各部分的能力等。它具有两个高级功能：一是连续修改内容； 二是将已存储的x m l 信息与关键业务流程联系起来，并且得到了大多数数据 库厂商的支持，微软公司的s q ls e r v e r2 0 0 5 可以存储和处理x m l 数据，且无 须将这些数据转换为关系列和行，更不需要将其存储为二进制大型对象；i b m 的d b 2v i p e r 可以存储传统的关系数据和x m l 数据；o r a c l el l g 中加入了对于 二进制的x m l 文件存储，以提高数据库提取文件的速度。 1 4 2x m l 的特点 1 简单。x m l 由若干规则组成，这些规则可用于创建标记语言，并能用一 种常称作分析程序的简明程序处理所有新创建的标记语言。x m l 能创建一种任 何人都能读出和写入的世界语，这种创建世界语的功能叫做统一性功能； 2 开放。x m l 是s g m l 在市场上有许多成熟的软件可用来帮助编写、管理 等，开放式标准x m l 的基础是经过验证的标准技术，并针对网络做最佳化： 3 高效且可扩充。x m l 提供了一个独立的运用程序的方法来共享数据，使 用d t d 可以来交换数据； 4 国际化。标准国际化，且支持世界上大多数文字。这源于依靠它的统一 代码的新的编码标准，这种编码标准支持世界上所有以主要语言编写的混合文 本。因此，x m l 不仅能在不同的计算机系统之间交换信息，而且能跨国界和超 越不同文化疆界交换信息； 5 易移植。x m l 语言可以定义各种数据，文本、图像、声音等格式都可以 采用x m l 来表述。 6 兰州大学硕士学位论文 基于决策树分类算法研究 1 4 3x m l 在数据挖掘中的应用 x m l 已经成为正式的规范，开发人员能够用x m l 的格式标记和交换数据。 x m l 在三层架构上为数据处理提供了良好的方法，使用可升级的三层模型， x m l 可以从已有的数据中产生出来，使用x m l 结构化的数据可以从商业规范 和表现形式中分离出来。数据的集成、发送、处理和显示的步骤如下1 3 1 】： 用标准的h t m l 无法完成的w e b 应用极大地促进了x m l 应用。这些应用 主要分成以下四类：需要w e b 客户端在两个或更多异质数据库之间进行通信的 应用；试图将大部分处理负载从w e b 服务器转到w e b 客户端的应用；需要w e b 客户端将同样的数据以不同的浏览形式提供给不同的用户的应用；需要智能 w e b 代理根据个人用户的需要裁减信息内容的应用。 x m l 给基于w e b 的应用软件赋予了强大的功能和灵活性，能给开发者和 用户带来了许多好处。x m l 能够使不同来源的结构化的数据很容易地结合在一 起，允许它描述不同种类应用软件中的数据。同时，由于基于x m l 的数据是 自我描述的，数据不需要有内部描述就能被交换和处理。x m l 文档对象模式 ( d o m ) 允许用脚本或其他编程语言处理数据，数据计算不需要回到服务器就能 进行。 x m l 可以通过以简单开放扩展的方式描述结构化的数据，x m l 补充了 h t m l ，被广泛地用来描述使用者界面。h t m l 描述数据的外观，而x m l 描 述数据本身。由于数据显示与内容分开，x m l 定义的数据允许指定不同的显示 方式，使数据更合理地表现出来。本地的数据能够以客户配置、使用者选择或 其他标准决定的方式动态地表现出来。在这类应用中，x m l 解决了数据的统一 接口问题。 x m l 还被应用于网络代理，以便对所取得的信息进行编辑、增减以适应用 户的需要。x m l 的出现给数据交换带来了一场革命，将成为下一代网络发展的 基石。 1 5 本文组织结构 数据挖掘在很多领域得到了广泛的应用，但其研究是非常大的课题，在数 7 兰州大学硕士学位论文 基于决策树分类算法研究 据挖掘领域的研究里有许多方面等待着我们去研究。本章主要介绍了数据挖掘 中用于分类的决策树方法的产生背景及研究意义，同时还介绍了国内外的研究 现状以及x m l 相关知识。全文的具体组织如下： 第一章为引言部分，介绍了知识发现的基本概念，并对选题的意义、国内 外的研究现状、x m l 的基础知识等进行了综合论述并给出了全文的组织结构。 第二章介绍了数据挖掘理论知识，数据挖掘的定义、分类、功能、常用技 术、过程以及应用等。 第三章介绍了决策树的概念，基本原理以及常见的决策树算法。 第四章着重介绍了i d 3 算法以及引入概率影响因子后的i d 3 算法，并结合 实例进行了分析。 第五章将决策树算法应用于一个气象技术保障网络管理信息系统，为系统 的决策支持做出了有力的保障，有效地发挥了决策树算法的实际应用价值。 最后，概括了本文的主要研究结果，说明本文工作的意义，指出有待进一 步解决的问题。 8 兰州大学硕士学位论文基于决策树分类算法研究 第二章数据挖掘理论知识 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的原始数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用、 可信、新颖的信息和知识的过程。它是一门广义的交叉学科，它的发展和应用 涉及到不同的领域，尤其是数据库、人工智能、数理统计、可视化、并行计算 等。 数据挖掘也被称为数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ， k d d ) ，它研究主要基于三大技术支柱，包括数据库、人工智能和数理统计。图 2 - 1 简要描述了数据挖掘技术的形成过程【1 7 】：数据库理论的发展促成了数据仓 库的形成，人工智能的发展促进了机器学习的进步，同时这些技术与传统的数 理统计理论的结合，最终促成了数据挖掘的产生。 2 2 数据挖掘的分类 图2 1 数据挖掘的形 由于数据挖掘本身涉及到不同的学科领域，其分类方法也有很多：根据开 采对象分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本 数据库、多媒体数据库、异质数据库及网络数据库等；根据开采方法可粗略地 分为：机器学习方法、统计方法、神经网络方法和数据库方法，在机器学习中 可细分为：归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等； 根据开采目标可分为：数据处理、预测、回归、分类、关联分析、模型可视化、 探索性数据分析等。 9 兰州大学硕士学位论文 基于决策树分类算法研究 2 3 数据挖掘的功能 数据挖掘的功能是从数据库中发现隐含的、有意义的知识，主要有以下五 类功能： 1 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分 析的问题如今可以迅速直接由数据本身得出结论。 2 关联分析 若两个或多个变量的取值之间存在某种规律性，就称为关联。关联分析的 目的是找出数据库中隐藏的关联网。 3 聚类 聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。 聚类技术主要包括传统的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提 出了概念聚类技术，该方法在划分对象时不仅考虑对象之间的距离，还要求划 分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。 4 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述。生成一个类的特征性描述只涉及该类 对象中所有对象的共性；生成区别性描述的方法很多，如决策树方法、遗传算 法等。 5 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 偏差包括很多潜在的知识。偏差检测的基本方法是，寻找观测结果与参照值之 间有意义的差别。 2 4 数据挖掘常用技术 1 神经网络 神经网络是仿照生理神经网络结构的非线性预测模型，通过学习进行模式 识别。它基于人脑的组织模式，将众多结构和功能极其简单的神经元通过各种 1 0 兰州大学硕士学位论文 基于决策树分类算法研究 方式联接成一个复杂的网络结构，以实现复杂的智能行为。它具有很强的自学 习能力和自适应能力，而且神经网络的智能活动表现为一种并行的联想方式， 能够像人脑一样实现快速的“推理。 2 遗传算法 遗传算法( g e n e t i c a l g o r i t h m ) 是一类借鉴生物界的进化规律演化而来的随 机化搜索方法，其主要特点是群体搜索策略和群体中个体之间的信息交换，比 较适用于处理传统搜索算法难以解决的复杂的非线性问题。它是由美国的 j h o l l a n d 教授1 9 7 5 年首先提出，其主要特点是直接对结构对象进行操作，不存 在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采 用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索 方向，不需要确定的规则。遗传算法已经广泛地应用于组合优化、机器学习、 信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技 术之一。 3 决策树方法 基于决策树的方法是从实例集中构造决策树，是一种有指导的学习方法。 一般都是自上而下生成的，选择分类的方法有很多种，但是目的一致，就是对 目标类尝试最佳的分类。最为典型的决策树学习算法是i i ：) 3 算法，它采用自项 向下不回溯策略，保证找到一个简单的树，算法c 4 5 是i d 3 算法的扩展，将分 类领域从类别属性扩展到数值型属性。 4 近邻算法 将数据集合中每一个记录进行分类的方法。它的基本思想是在给定数据后， 考虑在训练数据集中与该新数据距离最近( 最相似) 的所有数据，根据这些数据 所属的类别判定新数据所属的类别。 5 规则推导 从统计意义上对数据中的“i f t h e n 规则进行寻找和推导。采用上述技 术的某些专门的分析工具己经发展了大约十多年的历史，不过这些工具所面对 的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工业标准的 数据仓库和联机分析系统中去了。 兰州大学硕士学位论文 基于决策树分类算法研究 2 5 数据挖掘的过程 数据挖掘过程是一个多次的循环反复的过程，每一个步骤一旦与预期目标 不符，都要回到前面的步骤，重新调整，重新执行。其主要步骤如下： 1 确定业务对象。清晰地定义出业务问题，认清数据挖掘的目的是数据挖 掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的， 为了数据挖掘而数据挖掘则带有盲目性，是不会成功的。 2 数据准备。主要分为三个方面：数据的选择、数据的预处理以及数据的 转换。 3 数据挖掘。对所得到的经过转换的数据进行挖掘。除了完善从选择合适 的挖掘算法外，其余一切工作都能自动地完成。 4 结果分析。解释并评估结果，其使用的分析方法一般应作数据挖掘操作 而定，通常会用到可视化技术。 5 知识的同化。将分析所得到的知识集成到业务信息系统的组织结构中去。 2 6 数据挖掘的应用 数据挖掘技术已经运用于社会的多个领域【3 5 l ，为决策部门提供可靠、科学 的决策依据。在金融领域中，通过特征选择和属性相关性计算，识别关键因素， 进行贷款偿付预测和客户信用分析；利用分类和聚集的方法对用户群体进行识 别和目标市场分析；利用数据挖掘技术来帮助电信公司理解商业行为、确定电 信模式、捕捉盗用行为，更好的利用资源和提高服务质量是非常有必要的。在 零售业中，利用客户的购买信息，可以发现顾客购买模式和趋势，进行关联分 析，以便更好地进行货架摆设；改进服务质量，获得更好的顾客忠诚度和满意 程度；提高货品的销量比率，设计更好的货品运输与分销策略，减少商业成本； 寻找描述性的模式，以便更好地进行市场分析等等。医学领域也是近年来应用 的比较多的地方，由于数据挖掘中已经有许多有意义的序列模式分析和相似检 索技术，因此数据挖掘成为d n a 分析中的强有力工具。利用数据挖掘技术在 d n a 数据的分析研究中可以进行d n a 序列问的相似搜索和比较，对同时出现 的基因序列的相关分析，遗传研究中的路径分析等。 1 2 兰州大学硕士学位论文基于决策树分类算法研究 3 1 决策树分类 第三章决策树分类算法 决策树方法是目前应用最广泛的归纳推理算法之一，是一种逼近离散值函 数的方法。分类在数据挖掘中是一项非常重要的任务，目前在商业中应用最多。 它是以实例为基础的归纳学习算法，通常用来形成分类器和预测模型，着眼于 从一组无次序、无规则的事例中推理出决策树表示形成的分类规则。 要构造分类器，需要有一个训练样本数据集( 训练集) 作为输入。训练集 是一条条数据记录组成的。每一条记录是一个由有关字段值组成的特征向量， 我们把这些字段称作属性，此外，训练集的每条记录还有一个特定的类标签与 之对应，类标签也就是训练集的类别标记。 一般来说分类分为两个步骤： 第一步，构建分类器，即建立一个模型，描述规定的数据类集或概念集。 构造的主要方法有决策树、贝叶斯网、神经网络等； 第二步，利用模型进行分类。不同的分类器有不同的特点，主要从预测准 确度、计算复杂度、模型描述的简洁度等三个方面对分类器进行评价和比较。 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值，有的 分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值。 目前普遍认为不存在某种方法能适合于各种特点的数据。 3 2 决策树方法的介绍 3 2 1 决策树 决策树学习是以实例为基础的归纳学习算法【1 3 ，2 6 1 ，它着眼于从一组无次 序、无规则的事例中推理出决策树表示形式的分类规则，通常用来形成分类器 和预测模型，可以对未知数据进行分类或预测、数据挖掘等。自2 0 世纪6 0 年 代以来，决策树在分类、预测、规则提取等领域有着广泛应用，特别是在q u i n l a n jr 于1 9 8 6 年提出i d 3 算法以后，决策树方法在机器学习、知识发现领域得到 1 3 兰州大学硕+ 学位论文 基于决策树分类算法研究 了进一步应用及巨大的发展，在人工智能领域有着相当重要的理论意义与实用 价值。 一棵决策树的内部结点是属性或属性的集合，叶结点是所要学习划分的类， 内部结点的属性称为测试属性。用决策树进行分类分两步走：第一步是利用训 练集建立一棵决策树，建立决策树模型；第二步是利用生成完毕的决策树模型 对未知的数据样本进行分类。 决策树分类方法首先要利用训练集建立决策树模型，然后根据这个决策树 模型对输入数据进行分类。其中，关键问题在于决策树的构建过程，这一过程 包括建树和剪枝两个步骤：第一个步骤为建树阶段；第二个步骤为剪枝阶段。 决策树的建树算法是通过递归过程，最终得到一棵决策树，而剪枝则是为了降 低噪声数据对分类正确率的影响。 3 2 2 决策树的基本思想 1 信息论原理 信息论是c e s h a n n o n 为解决信息传递( 通信) 过程问题而建立的理论h 1 ， 也称为统计通信理论。一个传递信息的系统是由发送端( 信源) 和接收端( 信 宿) 以及连接两者的通道( 信道) 三者组成。信息论把通信过程看作是在随机 干扰的环境中传递信息的过程。 2 互信息的计算 ( 1 ) 定义 设s 为训练集，训练集中每个训练样本有n 个特征( 属性) ，表示为 ( 4 ，4 ，4 ) ，i s i 表示例子总数；s 中有u ，两类，i qi 表示阢类例子总 数；特征4 处有m 个取值，分别为“，v ：，) ； ( 2 ) 概率计算公式 阢类出现的概率为：p ( q ) 一斜 ( 3 1 ) q 类出现在特征4 处，l 敦f f i v ，的例子集合的条件概率为： 酬吩黼 1 4 ( 3 2 ) 兰州大学硕士学位论文 基于决策树分类算法研究 在特征4 处取值v 的例子集合的概率为： p ( v j ) ；斜 ( 3 - 3 ) 在特征4 处取值 ，的例子，属于q 类的例子集合的条件概率 粕m _ ) = 谢 ( 3 ) 信息熵 ( 3 4 ) 信息熵是信源输出后，每个信息所提供的信息量，也反映了信源输出前的 平均确定型。定义为： ) 罩p “) l o g k 瓦南2 一；p “) l o g t p ( u a ( 3 - 5 ) 信息熵h ) 是信源输出前的平均不确定性，也称为先验熵。 ( 4 ) 互信息 互信息才是接收端所获得的信息量。 3 2 3 决策树的生长过程 决策树的生长是构造决策树的首要问题。构造决策树通常分为两个步骤： 一是决策树的生长：由训练集生成一棵决策树；二是决策树的修剪：用非训练 集的事例检验，剪去影响预测精度的树枝。 决策树建立的过程就是其各个分支形成的过程。构造决策树有多种算法， 国际上最早也最有影响力的决策树算法是上世纪7 0 年代末q u i n l a n 提出的i d 3 算法。后来q u i n l a n 提出了c 4 5 的算法，对i d 3 进行了改进，另外还有m i d 3 算法等，后面将着重介绍i d 3 算法。 3 2 4 决策树的剪枝技术 在创建决策树时，由于训练样本太少或数据中存在噪声和孤立点，许多分 枝反映的是训练数据中的异常现象。剪枝【5 , 3 6 】是一种克服噪声的技术，同时它也 能使得到的决策树得到简化而变得更容易理解。 两种剪枝策略，先剪枝和后剪枝。前者限制决策树的过度生长，常用的方 1 5 兰州大学硕士学位论文 基于决策树分类算法研究 法是采用统计意义下的x 2 检验、信息增益等度量，评估每次节点分裂对系统性 能的增量，如果节点分裂的增量小于预先给定的阈值，则对该节点进行扩展。 如果在最好的情况下的扩展增益都大于阈值，则不对该节点进行扩展。后者是 允许决策树过度生长，然后根据一定的规则，剪去那些不具有一般代表性的节 点和分枝。 先剪枝算法有可能过早停止树的生长而存在视野效果问题，但该算法效率 高，适合于规模大的问题；后剪枝所需的计算比先剪枝多，但能产生更可靠的 树。 3 2 5 决策树的性能评价 在决策树的学习算法当中，决策树的复杂度和分类精度是需要考虑的两个 最重要的因素，下面是决策树的性能评价标准： 1 预测准确性：该指标描述分类模型准确预测新的或未知的数据类的能力。 经分类发现模型处理后，从数据中得到的信息的准确程度不同在很大程度上将 会影响决策人员决策制定的准确性。 2 描述的简洁性：这是针对分类发现模型对问题的描述方式以及该描述方 式的可理解水平提出的。分类发现模型的最终目的是方便决策人员的使用，所 以，对于决策人员来说，模型描述越简洁，也就越易于理解，同时也就越受欢 迎。 3 计算复杂性：计算复杂性依赖于具体的实现细节，在数据挖掘中，由于 某种操作对象是巨量的数据库，因此空间和时间的复杂性问题将是非常重要的 一个环节，将直接影响生成与使用模型的计算成本。 4 模型强健性：强健性是对模型预测准确性的一个补充，是在存在噪声及 数据缺损的情况下，准确对未知其类的数据进行分类的能力。 5 处理规模性：处理规模性是指在巨量数据的情况下构造模型的能力以及 构造分类模型的精确度。数据挖掘所处理的对象数量是巨大的，那么就要求所 构建的挖掘模型可以适用于各种不同规模的数据量情况。 1 6 兰州大学硕士学位论文基于决策树分类算法研究 3 3 常见决策树算法 3 3 1i d 3 算法 i d 3 算法是决策树算法中最为典型的算法f 强矧。i i ) 3 算法是q u i n l a n 1 l 提出 的一种基于信息熵的决策树学习算法，它是决策树算法的代表，绝大数决策树 算法都是在它的基础上加以改进而实现的。他把s h a n n o n 信息论引入到了决策 树算法中，采用分治策略，在决策树各级节点上选择属性时，检测所有的属性， 选择信息增益最大的属性产生决策树节点，由该属性的不同取值建立分支，再 对各分支的子集递归调用该方法建立决策树节点的分支，直到所有子集仅包含 同一类别的数据为止。最后得到一棵决策树，它可以对新的样本进行分类。 i d 3 由于其理论比较清晰，方法简单，学习能力较强，适于处理大规模的 学习问题，是数据挖掘和机器学习领域中的一个较好的范例，也不失为一种知 识获取的有用工具。 3 3 2c l s 算法 c l s 学习算法是1 9 6 6 年由h u n t 、m a r t i n e 和s t o n e 提出的早期的决策树学 习算法，后来的许多决策树学习算法都是它的改进与更新。其主要思想是从一 个空的决策树出发，通过添加新的判定结点来改进原来的决策树，直至该决策 树能够正确地将训练实例分类为止。 3 3 3c 4 5 算法 c 4 5 算法【2 】是q u i n l a n 在1 9 9 3 年针对i d 3 存在的一些缺点提出的，它是i d 3 算法的后继，同时也成为后面诸多决策树算法的基础。 c 4 5 算法在i d 3 的基础上融入了对连续型属性、属性值空缺情况的处理， 对树剪枝也有了比较成熟的方法。c 4 5 采用基于信息增益率( i n f o r m a t i o ng a i n r a t i o ) 的方法选择测试属性，信息增益率等于信息增益对分割信息量( s p l i t i n f o r m a t i o n ) 的比值。对样本集丁，假设，是有s 个不同取值的离散属性，用，分 割样本集所得信息增益的算法同i d 3 ，分割信息量由公式 洲耻砉谢l o g ：( p 鹦i t i 绌刖t 愀据集t 的例子数i 啪燃 1 7 兰州大学硕士学位论文 基于决策树分类算法研究 的例子数。 c 4 5 算法比i d 3 算法在效率上有了很大的提高，不仅可以直接处理连续型 属性，还可以允许训练样本集中出现属性空缺的样本，生成的决策树的分枝也 较少。但是，c 4 5 算法在选择测试属性，分割样本集上所采用的技术仍然没有 脱离信息熵原理，因此生成的决策树仍然是多叉树；如果想生成结构更为简洁 的二叉树，