（计算机应用技术专业论文）数据挖掘中的决策树方法及其在客户分类中的应用.pdf

摘要 摘要 针对性地收集客户资源，对客户资源的有效维护和使用，是直销企业管理中的 核心问题。我国加入； i t o 后，开放直销市场的日期日益临近，2 0 0 4 年1 0 月1 日我 国的直销法即将出台，外资直销企业和国外的直销产品将陆续进入中国，对我国的 直销市场形成强烈冲击。在这种情况下，我国的直销企业如何快速构建完善的管理 基础，特别是客户资源管理体系是当务之急。 本文以典型的直销企业大连理工领先生物工程有限公司业务中的客户资源管 理为对象，利用决策树方法对客户资源进行客户分类，挖掘出理想客户。 决策树方法的核心算法是i d 3 算法。它的缺陷是易偏向于取值较多的属性，而 取值较多的属性却不总是最优的属性。本文在利用i d 3 算法建立决策树的过程中， 提出了信息增益度优化算法，在定程度上克服了i d 3 算法取值偏向问题，得到了 较为理想的决策树分类模型。 另外在对数值连续型数据离散化，即对数据进行二元分裂时，本文用分类准确 率替代了原来的信息增益，使计算大大简化。 关键字：数据挖掘：决策树：客户分类：信息熵；信息增益；信息增益度 盔鎏堡三查堂婴主望壅一一 a b s t r a c t e f f e c t i v e c o l l e c t i n g , m a i n t a i n i n ga n du s i n g e l l s t o m e fr e s o u r c e si so n eo f t h ek e y q u e s t i o n s i nt h ed i r e c t - s a l ee n t e r p r i s e s w i t ht h ec o m i n go f o p e n i n gt h ed i r e c t - s a l em a r k e t i no u r c o u n t r y a f t e rc h i n a se n t e r i n gw t o t h el a wo f d i r e c t - s a l ew mb ei ne f f e c to i l1 “o c t2 0 0 4 f r o mt h e no n , m o r ea n dm o r e f o r e i g nc o m p a n i e sa n dp r o d u c t so f d i r e c t - s a l ew i l le n t e r c h i n a sn 韭i r ! 敞w h i c hw i l lb ei n t e n s i v e l yi m p a c t e d s oh o wt oc o n s t r u c tc o m p l e t e m a n a g e m e n ts y s t e m , e s p e c i a l l yc u s t o m e rs e n , i c em a n a g e m e n ts y s t e m i s au r g e n t p r o b l e m t h i sp a p e rs t u d y0 1 3t h eo b j e c t i v eo fa 瞒t o m 钉r e s o l z r e em a n a g e m e n ti nt h ed a l i a n s h e n g y u a nb i o t e c h n o l o g yc o m p a n y , o n eo f t h et y p i c a ld i r e c t - s a l ee n t e r p r i s e ，e x p l o i t i n g d e c i s i o nt r e et oc l a s s i f yt h ec u s t o m e r r e s o u r c e ，a n dh a v i n gm i n e d t h ei d e a lc u s t o m e r t h ec o r ea l g o r i t h mo fd e c i s i o nt r e ei si d 3 ，w h i c h d i s a d v a n t a g eo f i se a s yt os e l e c tt h o s e a t l r i b u t e sw h o s ev a l u e si sm o r c w h i l ea t t r i b u t e sw h o s ev a l u e si sm o r ea r en o ta l w a y st h e b e s t t h i sp a p e r p r e s e n ta n e w a p p r o a c h o ni d 3a l g o r i t h m - - t h ei n f o r m a t i o ng a i nd e g r e e o f a t t r i b u t e 一- t oo p t i n l i z e t h ed e c i s i o nt r e e ，a n do b t a i nr a t h e ri d e a lc l a s s i f i c a t i o nm o d e lo f d e c i s i o nt r e e i na d d i t i o n a l 1 h i sp a p e rs u w r c e a et h ei n f o r m a t i o ng a i nw i t hc l a s s i f i c a t i o nc o r r e c tr a t i o d u r i n gt h ed i s c r e t i n gt h ec o n t i n u o u sa t t r i b u t e s ，t w o e l e m e n ts p l i 伍n g ，a n ds i m p l i f y i n gt h e c a l c u l a t i o n k e yw o r d s ：d m ( d a t am i n i n g ) ；d e c i s i o nt r e e ；c u s t o m e rc l a s s i f i c a t i o n ；i n f o r m a t i o n e n t r o p y ；i n f o r m a t i o nc r a i n ；i n f o r m a t i o ng a i nd e g r e e 前言 0 前言 数据挖掘，又称数据库中的知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ，k d d ) ， 是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值 的信息或模式，它是数据处理技术研究中的一个很有应用价值的新领域，融合了数 据库、人工智能、机器学习、统计学等多个领域的理论和技术。它不仅能从历史数 据中建立描述型( 回顾型) 模型，而且还能够建立预测型模型，为我们从大规模的 数据库中提取有用信息提供了强有力的解决工具。数据挖掘不但能够学习已有的知 识，而且能够发现未知的知识。通过数据挖掘得到的知识是“显式”的，既能为人 所理解，又便于存储和应用，因此一出现就得至咿泛的重视。目前，数据挖掘技术 己广泛地应用于零售、营销、银行、保险、交通、电信、医疗及故障诊断等许多领 域，在市场预测、股票分析、客户行为分析及决策支持等许多方面取得了可喜的成 果。随着c r m 经营理念的迅速发展和应用，数据挖掘技术所带来的经济效益越来 越受到企业的关注，其应用前景也越来越广阔。 本文利用i d 3 算法对大连理工领先生物工程有限公司的客户资源进行了尝试 性的数据挖掘，建立了决策树分类模型，对客户进行了分类。同时针对1 3 9 3 算法的 取值偏向问题以及在实际应用中所带来的误差，对i d 3 算法进行了改进，提出了信 息增益度优化算法。该优化算法选取信息增益度最大的属性作为分支属性，取代了 i d 3 算法中的信息增益标准，由于引入了取值数n ，在一定程度上克服了1 1 ) 3 易偏 向于取值较多的属性这缺陷，最终得到了较为理想的决策树，其结点个数明显减 少，而分类精度保持不变。 该算法改变了i d 3 算法的启发式函数，时间复杂性与i d 3 算法相同，其计算 比信息增益率简单。同时，如果各属性的取值个数相同，则又回归为i d 3 算法。 另外在对数值连续型数据离散化，即对数据进行二元分裂时，本文用分类准确 率替代了原来的信息增益，使计算大大简化。 l 绪论 1 绪论 1 1 课题的来源、研究背景及意义 本课题来源于大连理工领先生物工程有限公司客户服务中心研究课题。 大连理工领先生物工程有限公司成立于2 0 0 1 年1 0 月，主要从事生物技术的开 发和应用，技术主要依托是中国医学科学院、中国农业科学院以及大连理工大学生 物科学研究院安利佳教授及其科研团队。公司目前的主要产品是百岁健蓝莓口服 液。产品采取的营销模式是服务营销( 直销的延伸) ，这种营销模式的核心是对客 户资源的有效管理和使用。受大连理工领先生物工程有限公司的委托，作者于2 0 0 3 年6 月开始了本文的工作。工作的主要内容是通过对数据挖掘方法的研究和改进， 探索出一种有效、简便的分类方法，挖掘出公司客户资源管理系统中的理想客户， 提高业务人员的服务对象的针对性，进而提升公司的销售业绩。 随着各种现代生产管理手段和技术的发展，各企业产品之间的差别越来越难以 区分，产品同质化的趋势越来越明显，通过产品差别来细分市场从而创造企业的竞 争优势也就交得越来越困难。与此同时，随着市场态势从卖方市场向买方市场的转 变，客户的消费行为越来越成熟，期望也越来越高。企业与客户之间的交互方式发 生了显著的变化，谁也不能保证客户会从一而终。因此，研究客户的需求和提高对 客户的服务水平也就变得异常重要。企业要想与客户建立持久的关系，从每个客户 身上获取最大利润，降低市场营销费用，减少由于客户离去和无效的经营策略产生 的浪费。要做到这些，就必须对客户在与企业交互过程中的各种客户数据进行收集、 分析，挖掘出隐含在数据中的有用的信息。这要求企业能够快速、有效地从庞大的 数据库中抽取有效的、未知的和能理解的信息，用来提高效益。而要做到这一点， 需要完成以下步骤：( 1 ) 用全局的观点来获取和集成来自企业内部和外部的数据； ( 2 ) 分析集成的数据来获取信息；( 3 ) 用能加速复杂的决策过程的方式来组织和 表示这些信息和知识。 在现实中许多企业搜集和存储了与客户相关的宝贵数据。但是，由于传统的 信息技术以实时事务处理为目标，缺乏发现隐含在数据中的有用的信息的能力，所 以这些企业无法将数据转化为知识。数据挖掘技术就是帮助我们解决客户交互过程 中遇到的各种问题的最重要的技术。它是通过信息技术手段来实现其管理目标，已 经在西方获得了较大的成功。要想在竞争中立于不败之地，就必须结合自身的情况， 采用先进的管理思想和技术手段，因此关于数据挖掘技术的研究对我国企业的决策 支持水平有着重要的意义。 1 2 数据挖掘的研究方面 从2 0 世纪9 0 年代起，出现了一种全新的技术数据挖掘( d a t am i n i r t q g , d m ) 【1 】【2 。数据挖掘是从数据中发现隐含着的有用的信息或知识的技术，它是随着人类 大连理工大学硬士论文 进入信息社会以来对信息的价值认识不断提高而不断发展的，是为满足和解决当前 “数据太多，信息不足”问题的技术。数据挖掘目前一种比较公认的定义是 w j f r a w l e y ，0 p l a m s k ys h a p i r o 等人提出的：数据挖掘就是从大型数据库的数据 中提取人们感兴趣的知识，这些知识或信息是隐含的、事先未知而潜在有用的，提 取的知识表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。1 1 3 1 1 3 0 1 1 w h ( 1 9 9 3 ) 提出了数据仓库( d a t aw a r c h o u s e , d w ) 的概念1 3 ，解 决了数据挖掘的前期数据准备问题；f r i e d m a n ( 1 9 9 7 ) 列出了支持数据挖掘的四个 主要技术；j i a w e ih a n 等( 2 0 0 0 ) 全面介绍了数据挖掘的相关内容【4 】。 数据挖掘作为知识发现过程的个特定步骤，它是一系列技术及应用，或者说 是对大容量数据及数据间关系进行考察和建模的方法集。它的目标是将大容量数据 转化为有用的知识和信息。 一般情况下，数据挖掘的对象定义为数据库，而更广义的说法是，数据挖掘意 味着从一些事实或观察数据的集合中寻找模式。数据挖掘的对象不仅是数据库，也 可以是文件系统或其 瞧任何组织在_ 起的数据集合，侈l 如w w w 信息资源，最新 的对象是数据仓库。 与数据挖掘和知识发现关系密切的研究领域包括归纳学习( i n d u c t i v e l e , a m i n g ) 、机器学习( m a c h i n el e a r n i n g ) 和统计( s t a t i s t i c s ) 分析，特别是机器学 习被认为和数据挖掘的关系最密切。二者的主要区别在于；数据挖掘的任务是发现 可以理解的知识，而机器学习关心的是提高系统的性能，因此训练神经网络来控制 一根倒立棒是一种机器学习过程但不是数据挖掘；数据挖掘的对象是大型的数据 库，一般来说机器学习处理的数据集要小得多，因此效率问题对数据挖掘是至关重 要的。 数据挖掘的技术基础就是人工智能，它利用了人工智能中的诸多算法进行挖 掘，为用户提供有用信息。在很大程度上，数据挖掘是人工智能的某些成熟的技术 ( 人工神经网络、遗传算法、决策树) 在特定的应用系统中具体而微小的应用，但 是其问题的规模和难度大大降低。 除了人工智能之外，数据挖掘还结合了传统的统计分析方法、模糊数学方法以 及科学计算可视化技术，以数据库和数据仓库为研究对象，形成了数据挖掘方法和 技术。 在现实生活中，数据挖掘技术被广泛应用，尤其是在决策支持系统中，常常利 用数据挖掘技术从数据库系统中获得有用信息，让更高一级的用户根据挖掘结果做 出更明智、更正确的决策。 国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究进一步发 展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传统 的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括： k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立 的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多计算 机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行 2 1 绪论 这方面的工作。许多著名的计算机公司开始尝试k d d 软件的开发，比较典型的s a s 公司的e n t e q m s e m i n e r , i b m 公司的i n t e l l i g e n t m i n e r , s g i 公司的s e t m i n e r , s p s s 公 司的c l e m e n l i n e 。还有k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d bm i n e r 、q u e s t 等aw e b 数据挖掘产品有n e tp e 哪哟n s ，a e e m e 埘g h t 和a e e m e h i tl i s t , c o m m e r e e t r e n d s 等。 同时，数据挖掘在国内也成为了讨论的热点。这些讨论主要集中于对数据挖掘 相关算法的介绍和修正。以及数据挖掘在一些具体行业部门的实施购架。郑泽芝 ( 2 0 0 0 ) 、高峰( 2 0 0 0 ) 等修正了经典的a p f i o f i 算法，提高了关联规则挖掘的效率 口】；熊肖华( 2 0 0 2 ) 讨论了模糊理论在关联规则挖掘中的应用；刘夫涛等( 2 0 0 0 ) 将变量聚类和样本聚类结合起来，使分类性有了较大提高；中国人民大学统计学系 数据挖掘中心( 2 0 0 2 ) 则集中讨论了决策树技术的概念和应用【6 】。在数据挖掘领域 同样也有一些专业的国内网站，如h t t p ：d m g r o u p o r g c d 。国内的数据挖掘研究一般 是计算机领域的专业研究，专门面向c r m 的数据挖掘研究还远远不够。 1 3 数据挖掘的主要任务 ( 1 ) 数据总结 数据总结的目的是对数据进行浓缩，给出它的紧凑描述。数据挖掘主要关心从 数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次 抽象到高层次上的过程。数据泛化目前主要有两种技术：多维数据分析方法和面向 属性的归纳方法。 ( 2 ) 概念描述 概念描述是对数据库的整体信息进行全面概括，从数据库中归纳抽象的信息。 概念描述有两种典型的描述：特征描述和判别描述。 ( 3 ) 分类 分类是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的 是提出一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中数据 项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从历史数 据记录中自动推导出给定数据的推广描述，从而能对未来数据进行预测。和回归方 法不同的是，分类的输出是离散的类别值，而回归的输出则是连续数值。 分类器的典型构造方法有决策树法、贝叶斯法，神经网络方法、近邻学习或基于事 例的学习等方法。不同的分类器有不同的特点。 ( 4 ) 聚类 聚类是根据数据的不同特征，将其划分为不同的数据类。它的目的是使得属于 同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的 大。聚类方法包括：统计方法、机器学习方法和神经网络方法。 3 大连理工大学硕士论文 ( 5 ) 相关性分析 相关性分析的目的是发现特征之间或数据之间的相互依赖性。数据相关性关系 代表一类重要的可发现的知识。若两个或多个数据项的取值重复出现且概率很高 时，它就存在着某种关联。可以建立起这些数据项的关联规则。 最著名、最重要的关联规则发现算法是r a g r a w a l 等人提出的a p r i o r i 算法。 ( 6 ) 偏差分析 偏差分析包括分类中的反常实例、例外模式、观测结果对期望值的偏离以及量 值随时间的变化等，其基本思想是寻找观察结果与参照量之间的有意义的差别。数 据库中的数据能反映许多异常情况，从数据分析中发现这些异常情况是很重要的， 能引起人们对它更多的注意。 ( 7 ) 预测 预测是预测新事物的特征，它利用现有的数据找出变化规律，即建立模型，并 用此模型来预测未来数据的种类、特征等。 1 4 论文的主要内容 论文首先介绍了数据挖掘以及决策树的含义，然后详细阐述了决策树的核心算 法i d 3 算法，最后将i d 3 算法应用到大连理工领先生物工程有限公司的客户资源 管理中，建立了决策树分类模型，进行了客户分类。其中针对i d 3 算法所存在的属 性取值偏向问题本文提出了一种新的优化算法信息增益度算法，其中引入了取 值数n ，在一定程度上克服了i d 3 算法易偏向于取值较多的属性这一缺陷，得到了 较为理想的决策树，其结构更简洁。另外在对数值连续型数据离散化，即对数据进 行二元分裂时，用分类准确率替代了原来的信息增益，使计算大大简化。 1 5 论文的组织结构 第一章，绪论。阐述了论文的课题来源、研究背景及意义，国内外在相关领域的研 究和应用状况以及论文的结构。 第二章，数据挖掘中的决策树方法。简要介绍了决策树方法的含义、核心算法、特 点、简化等概念。 第三章，客户分类的问题定义。本章介绍了系统需求分析、问题定义和客户分类的 概念，然后介绍了数据预处理的流程，最终得到了数据训练模型。 4 l 绪论 第四章，决策树分类模型的建立。本章首先用 d 3 算法对客户资源建立了决策树分 类模型，然后针对 d 3 算法的取值偏向问题以及由此带来的在实际应用中的误差。 本文对 d 3 算法进行了改进，提出了信息增益度优化算法，在一定程度上克服了 d 3 算法取值偏向问题，并得到了较为理想的决策树。 第五章，总结与展望。对本文工作进行了总结，并且对今后的工作进行了展望。 大连理工大学硕士论文 2 数据挖掘中的决策树方法 2 1 决策树方法介绍 数据挖掘有着广泛的应用，如数据库营销、客户群体划分、客户流失性预测、 欺诈检测和客户信用记分等。根据所挖掘的知识的不同对应羞不同的实现方法。其 中，提取同类事物共同性质的特征型知识和不同事物之间的差异特征型知识一般采 用分类法。分类法是数据挖掘中的一个非常重要的技术q 在指导式的学习环境下， 分类作为人工智能里知识获取或知识抽取的一个可行解决方案而被广泛研究。 分类的目标是要根据属性的值为每个类推导出一个简洁的模型或描述。这个模 型用于对那些类未知的记录进行分类，赋予每个记录相应的类标签。常见的分类方 法有贝叶斯分类( b a y e s ) 、神经网络( n e u r a ln e t w o r k s ) 、遗传算法( g e n e t i c a l g o r i t h m s ) 和决策树分类器( d e c i s i o nt r e e s ) ，在这些分类方法中，决策树分类器 在大规模的数据挖掘环境中已经获得了最为广泛的应用 s , g a 0 。 决策树有几大优点： 第一，与神经网络和贝叶斯分类器相比，决策树提供非常直观的描述，这种描 述易于被吸收，转化为标准的数据库查询。 第二。训练神经网络模型时要花费大量的时间，要进行大量的重复操作，与之 相比，决策树效率要高得多，适合于大的训练集。 第三，决策树生成算法除了训练集中包含的信息外不需要附加的信息( 即领域 知识或类标签以前的分布情况) 。 第四，决策树有着可比的或更高的准确率。 在所要建立的客户分类预测模型中，因为预测的结果为理想客户或非理想客户 两种情况，适合于决策树进行分类。针对决策树难以处理连续型属性的特点，本文 采用了分类准确率算法对属性离散化处理，很好地解决了这一问题。基于上述考虑， 客户分类预测模型的核心部分预测分类将采用决策树算法，本章介绍决策树分类涉 及到的基础理论知识。 2 2i d 3 学习算法 决策树的核心算法是d 3 算法，其他的许多算法如c 4 5 、c a r t 算法等都是 在d 3 算法基础上的改进队1 2 1 。 l 、信息增益 19 4 8 年，香农( c e s h a n n o n ) 提出了信息论。其中对信息量( i n f o r m a t i o n ) 和熵( e n t r o p y ) 的定义为f 1 3 】： 抽f o m 越o i f - l 0 9 2 p i e n 血d p ) ，；e p i l o ( p i ) 一数据集s 划分前的熵： 6 2 数据挖掘中的决策树方法 设数据集s 有a 1 ，a ：，a 。，c 共有珂十1 个属性。其中分类属性c 有1 1 3 个不同的 离散属性值q ，c ：，c 。即数据集s 中的记录要分成m 个类别。设数据集s 中全 部的记录数为s ，分类属性值为c 】，c ：，f 。的记录数分别为j 。，s ：，s 。那么划分 之前，数据集s 的总熵为： 三 e ( 丑，是，) = 一艺bl 0 9 2 ( b ) 其中p ；是任意一个记录属于类别q 的概率，用墨s 估计。容易看出，数据集s 的总熵在划分之前是属于不同类别的记录的信息量的加权平均。 数据集s 划分后的熵： 假设属性a 具有v 个不同的离散属性值，可使用属性a 把数据集s 划分成v 个 子集 墨，s ：，s ，) 设子集s ，中全部的记录数为s ，其中分类属性值为c 1c ：，c 。 的记录数分别为5 护s 2 ，子集q 的熵为 e ( j j 2 ，s j ) = 一p l 0 9 2 ( p f ) t - 1 其中岛是墨中任意一个记录属于类别c i 的概率，用勺s 估计。 使用属性a 把数据集s 划分成v 个子集( 墨，s ：，鼠) 后，数据集s 的总熵为v 个子集的熵的加权平均。数据集s 划分后的熵为： e ( 爿) = e e o l ，s 2 ，j 。) 其中，是第j 个子集的权。用s ，s 估计。 数据集s 划分前与划分后的熵差： 信息增益：表示系统由于分类获得的信息量。由系统熵的减少值定量描述。数 据集s 用属性a 划分后的信息增益为数据集s 划分前后的熵差： g a i n ( a ) = e ( 曲，5 2 ，s 。) 一e ( 4 ) 选择属性对结点进行划分的标准：划分属性应该具有最高信息增益。熵是系统 混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系 统向更加有序、有规则组织的方向发展。所以最佳的划分方案是使熵减少量最大的 划分方案。划分后熵的减少量就是信息增益，所以，选择属性对结点进行划分的标 准就是选取信息增益最大的属性。通常，决策树是用“贪心算法+ 深度优先搜索” 得到的。 2 、d 3 算法的基本思想 d 3 算法是& q l i n l a n 于1 9 8 6 年提出的，其前身是c l s i ”】。c l s 的工作过程 为：首先找出最有判别力的因素，把数据分成多个子集，每个子集又选择最有判别 力的因素进行划分，一直进行到所有子集仅包含同卅型的数据为止，最后得到一 7 太连理工大学硕士论文 棵决策树，可以用它来对新的样例进行分癸。 0 u i i l l a 的工作主要是引进了信息论中的互信息，他将其称为信息增益，作为 特征判别能力的度量，并且将建树的方法嵌在一个迭代的外壳之中。 i d 3 是基于信息熵的决策树分类算法，根据属性集的取值来判断实例的类别。 i d 3 的算法核心是在决策树中各级结点上选择属性时，用信息增益作为属性选择的 标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息， 使用该属性将例子集分成子集后，系统的熵值最小。期望该非叶结点到达各后代叶 结点的平均路径最短，使生成的决策树平均深度较小，提高分类速度和准确率 1 5 , 1 6 。 i d 3 的基本原理【1 日：设日= e e e 是n 维有穷向量空间，其中f j 是有 穷离散符号集，h 中的元素e = 叫做例子，其中v ，e ，= 1 , 2 ， 。 设p e 和n e 是e 的两个例子集，分别叫做正例集和反例集。 假设向量空间h 中的正例集p e 和反例集n e 的大小分别为p 和n ，i d 3 基于 下列两个假设：( 1 ) 在向量空间h 上的一棵正确决策树对任意例子的分类概率同h 中正反例的概率一致；( 2 ) 一棵决策树能对一例子作出正确类另q 判断所需的信息量 为 1 9 j ： 1 ( p ，n ) = 一圭1 0 9 2 圭一旦1 0 9 2 上 p np np np + n 如果以属性a 作为决策树的根，a 具有v 个值 v 1 ，v ：，v ， ，它将h 分为v 个子集 蜀，：，h ，) ，假设e 中含有个正例和珥个反例，子集e 的信息熵为 ( p ；，) ，以属性a 为根分类后的信息熵为何( 4 ) = 窆l 导，( p 。，) 。因此， 百p 十一 以a 为根的信息增益是g a i n ( d ) = ，( p ，呻一h 叫) 。i d 3 选择使g a i n ( d ) 最大( 即 日( 爿) 最小) 的属性爿作为根结点，砌的不同取值对应的h 的v 个子集日递归 调用上述过程，生成一的子结点马，b 2 ，且。 i d 3 方法检验所有的特征，选择信息增益( 互信息) 最大的特征a 产生决策 树结点，由该特征的不同取值建立分枝，对各分枝的实例子集递归调用该方法建立 决策树的各个结点和分枝，直到某一子集中的例子属于同一类为止。 i d 3 方法利用信息增益最大的特征建立决策树，使决策树结点数最少，识别例 子准确率高。 3 、d 3 算法的特点 ( 1 ) 优点【1 9 , 2 0 1 i d 3 算法在选择重要特征时利用了信息增益的概念，算法的基础理论清晰，使 得算法较简单，是一个很有实用价值的示例学习算法。 该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。有人曾 8 2 鼓据挖掘中的决策树方法 用4 7 6 1 个关于苯的质谱例子做了试验，其中正例2 3 6 1 个，反例2 4 0 0 个，每个例 子由5 0 0 个特征描述，每个特征取值数日为6 ，得到一棵1 5 1 4 个结点的决策树， 对正、反例各1 0 0 个测试例作了测试，正例判对8 2 个，反例判对8 0 个，总预测正 确率8 1 ，效果是令人满意的。 ( 2 ) 缺点 ( a ) 信息增益的计算依赖于取值较多的特征，这样不太合理。比较理想的改 进是采用信息增益率作为选取属性的标准。 ( b ) 用信息增益作为特征选择量存在一个假设，即训练例子集中的正、反例 的比例应与实际问题领域里正、反例比例相同。但是一般情况不能保证相同，因而 计算训练集的信息增益就有偏差。 ( c ) i d 3 算法在建树时，每个结点仅含一个特征，是种单变元的算法，特 征间的相关性强调不够虽然它将多个特征用一棵树连在一起，但联系还是松散的 口1 1 。 ( d ) i d 3 算法对噪声较为敏感。关于什么是噪声，q u i l 出a 的定义是训练例子 中的错误就是噪声。它包含两方面，一是特征取值错，二是类别给错。 ( e ) 当训练集增加时，1 1 9 3 算法的决策树会随之变化。在建树过程中，各特 征的信息增益会随例予的增加而改变，从而使决策树也变化，这对渐进学习( 即训 练例子不断增加) 是不方便的。 总的来说，d 3 算法由于其理论清晰，方法简单，学习能力较强，适于处理太 规模的学习问题，得到了广泛的应用与极大的关注，是数据挖掘和机器学习领域中 的一个极好范例，也不失为一种知识获取的有用工具。 4 、i i ) 3 算法的发展 m 3 算法在实际应用中解决了许多问题，对于非增量式学习任务，i d 3 算法常 常是建立决策树的很好的选择，但对于增量式学习任务来说，由于i d 3 不能增量地 接受训练例，这就使得每增加一次实例都必须抛弃原有决策树，重新构造新的决策 树，造成了极大的开销于是i ) 3 算法被q u i n l a n 自己扩充为c 4 5 算法吲，c 4 5 算法每接受一个新的训练例就更新一次决策树。在c 4 5 算法的决策树中，每个结 点都保存了可用于计算e 值的属性的信息，这些信息由属性的每个取值所对应的 正例、反例计数组成。根据放在结点的信息，就可以判断出哪个属性的信息熵e 值最小，从而确定当前用哪一个属性来进行划分田】。 c 4 5 算法使用了一个适合小数据量的方法：基于训练例自身的性能估计。当 然训练例进行估计很可能产生偏向于规则的结果，为了克服这一点，c 4 5 算法采 用了保守估计，它采用的具体方法是：计算规则对其使用的各个训练例分类的精度 a ，然后计算这个精度的二项分布的标准差s ，最后对给定信任度( 9 5 ) ，取下界 ( a - 1 9 6 ) 为该规则的性能度量p i 在有大量数据的情况下，s 接近于o ，p a 接近于 a ；随着数据量的减少，p 。与a 的差别将会增大。c 4 5 算法使用更复杂的方法是为 属性a 的各种取值赋以概率，具有未知属性a 值的实例x 按概率值分为大小不等 的碎片，沿相应属性a 值的分支向树的下方分布，实例的碎片将用于及计算信息 大连理工大学硕士论文 增益 1 5 1 。这个实例碎片在学习后，还可以用来对属性值不全的新实例进行分类。 另外，c 4 5 算法采用信息增益率作为选择属性的标准，解决了i d 3 算法中的 属性取值偏向问题。 然而，现有的决策树归纳学习算法都把注意力集中在属性的选择标准上，这种 思想方法已开始受到人们的怀疑，j o h n m i n g e r s 等人曾经用各秘试验来对各种属性 的选择标准进行了比较，最后的结果是属性的选择对精度的影响不大【2 4 j 。 理想的决策树分为3 种圈：( 1 ) 叶结点数最少；( 2 ) 叶子结点深度最小；( 3 ) 叶结点数最少且叶子结点深度最小。决策树的好坏，不仅影响了分类的效率，而且 影响了分类的准确率。因此，许多学者致力于寻找更优的启发式函数和评价函数。 洪家荣【2 6 j 、p e i - l e i1 俨”等入分别证明了要找到这种最优的决策树是非常困难的， 它是一个n p 难题1 2 m 。因此，人们为寻找较优的解，不得不寻求各种启发式方法。 1 9 9 2 年a h ad 科冽和k i r ak t 划等人对属性集的选择进行了细致的研究。同 年p e i 1 e i _ t 1 u f3 1 垛用了基于属性相关性的启发式函数。1 9 9 7 年j e n s e nd 【3 习对生成 的决策树进行剪枝处理，另外1 9 9 2 年o l i v e r j 。网扩充了决策树，形成决策图。 1 9 9 1 年w 缸c h a nj l g p 4 1 等人采用的优化算法很简单，其基本思相是：首先用 i d 3 算法选择属性f l ，建立树t l ，左右子树的属性分别为f 2 ，f 3 ；再以f 2 ，f 3 为 根，重建树t 2 ，t 3 ；比较t l ，t 2 ，b 的结点个数，选定结点最少的树。对于选取 树的儿子结点采用同样的方法，递归建树。尽管作者用一个实验证明能够建立理想 的决策树，但算法有较大的弱点：时间开销太大，因为每选择一个新的属性，算法 需要建立3 棵决策树，从中选优。 2 3 决策树的简化 在决策树学习算法中，除去分类的正确性应当放在第一位给予考虑之外，决策 树的复杂程度是另外一个需要考虑的重要因素。我们的目标是构造颗结构简单的 决策树，这也是我们对学习系统的一个偏置。前面我们已经给出了许多决策树学习 的改进算法，这里我们将给出改进算法的概括性讨论，这些算法不仅能够简化决策 树，而且能够改进决策树分类的正确性。 很明显，如果决策树构造的过于复杂，那么对于用户来说这个决策树是难以理 解的，这将在很大程度上使得分类树的构造没有意义，所以应该在保证正确率的前 提下尽量构造简单的决策树网。但是也要注意不能使得决策树过小，因为决策树过 小会导致错误率上升。例如一棵空树( 即只包含根结点的树) 是不能提供任何有关 根据测试属性进行分类的信息。所以简化决策树需要在树的大小与正确率之间寻找 平衡点。 2 3 1 决策树过大的原因 ( 1 ) 表示不当。很明显，决策树的大小与描述语言有关。有一些概念的表示 1 0 2 数据挖掘中的决策树方法 语言能简洁明了地表示目标概念，而另外一些则没有这个能力。因此，选择正确的 描述语言可以大大减小决策树的复杂程度。 ( 2 ) 数据有噪音。数据的噪音包括属性噪音( 即包括了不j 晗当的属性) 和属 性值噪音( 即数据的属性值有错误) 。因为决策树无法区分正确的数据与错误的数 据，它既对正确的数据建模又对错误的数据建模，而正确数据本身的规律有可能被 噪音所淹没，所以决策树将会随着噪音的存在而变大1 3 6 】。 ( 3 ) 重复的子树。产生i 立y f f 大的诀策树的另外一种可能是因为有完全相同的 子树。 虽然我们的目标是寻找尽可能小的决策树，但是因为寻找最小决策树问题是 n p 困难问题，所以在现实中不可能寻找到绝对最小决策树。我们只能通过分析上 面所有这些使得决策树变得过于庞大的原因，借助某种技术来简化决策树。简化决 策树的方法很多，这里我们主要讨论从控制树的大小来简化决策树的方法。 2 3 2 控制树的大小 这是最常用的简化决策树的方法。它主要通过在训练过程中明确地控制树的大 小来简化决策树。它主要包括预剪枝( p r e - p n m i n g ) 和后剪枝( p o s t p r t m i n g ) 两种 方法，以及其他的后处理( p o s t - p r o c e s s i n g ) 方法。 l 、预剪枝 在前面的算法中，所有的算法都要求以每个叶结点中的训练实例都属于同一个 类作为算法停止条件。在以此为标准的情况下，决策树的错误率为0 。然而在预剪 枝算法当中，并不使用这个标准，而是在这个标准得到满足之前就停止继续扩展决 策树。具体在什么时候停止决策树的扩展就成为这个方法的主要研究内容。 一种最为简单的方法就是在决策树达到一定高度的情况下就停止决策树的扩 展，这种停止标准在一定情况下能取得比较好的效果。然而，更为普遍的做法是计 算每次扩展对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。如果 在最好情况下的扩展增益都小于阈值，则即使有些叶结点的实例集不属于同一类， 算法也停止。一般情况下，所谓判断是否停止扩展决策树的增益的选择标准，与每 次扩展时选择测试属性的标准相同。 但是，q u 讪t n 发现将选择测试属性的标准和是否停止扩展决策树的标准相同 的时候是存在问题的如果将这些选择的标准用在叶结点，则进行判断的时候也是 存在问题的，因为这些标准大都是与训练实例集的大小有关的对于这个问题有以 下三个解决办法j ： ( 1 ) 选择测试属性的标准。使得这个标准与训练实例集的大小无关。 ( 2 ) 选择一个全局性的标准，而不是只对叶结点应用的标准。 ( 3 ) 将两个标准分开，使用不同的标准。 预剪枝还有另外一个缺点，即视野效果问题。也就是说在相同标准下，也许当 大连理工大学硕士论文 前的扩展不能满足要求，但是更进一步的扩展能够满足要求。而预剪枝将会因为过 早地停止决策树的构造导致很大的误差，后剪枝将克服这些缺点。但是由于预剪枝 不必生成整棵决策树，使得其算法效率很高，适合解决大规模问题，所以这种方法 仍然得到广泛的应用。 2 后剪枝 后剪枝算法已经得到了广泛的讨论。在这个算法中输入为一个未经剪枝的决策 树t ，输出为对它剪枝之后的决策树t7 ，t 是算法将t 的某一个或某几个子树 删除后所得到的结果。剪枝过程中，将一些子树删除而用叶结点来代替，这个叶结 点所属的类用这棵子树中大多数训练实例所属的类代替，并且在相应叶子上标记出 所属这个类的训练实例所占的比例。 明显经过剪枝的决策树t 对于训练实例集的错误率已经不为0 ，但是由于在 这种剪枝算法当中位于底层的子树将被优先剪枝，而这些结点都是只包含很少实例 的，所以这种方法将减少噪声对决策树构造的影响。所以经过剪枝的决策树一般情 况下会提高决策树对整个实例空间分类的正确性。 在后剪枝算法当中，我们将算法氛围增长集用来生成决策树t 以及可能的对 决策树的修剪，而修剪集则用来选择最优的一个子树。 后剪枝算法的另外一个优点是，它能够产生一组而不是一棵决策树，这将使得 专家有可能在其中作出自己的选择而不是由计算机武断地作出选择，因为专家往往 有可能不同意计算机所作出的选择。 后剪枝算法有两种可能的剪枝策略，一种是自上而下( t o p - d o w n ) 的，一种是 自下而上( b o t t o m - u p ) 的郾】。自下而上的算法是首先在最底层的内结点( 即所有 予结点都为叶结点的内结点) 开始剪枝，剪去那些满足一定标准的内结点，生成新 的决策树，之后在新的决策树上递归调用这个算法，直至没有新的结点可以剪枝为 止。而与之相反的是，自上而下的算法是从根结点开始向下逐个考虑每个结点是否 应被剪枝。直到某结点满足剪枝的标准而被修剪为止。 如果一棵子树的任何个子结点都不满足剪枝标准，那么自上而下剪枝方法可 以避免将这个结点修剪掉，也就是可以避免视野效果的问题。而对于自下而上的算 法，则不能避免这个问题，而会产生与预剪枝相同的问题。 根据剪枝标准的不同，或根据自上而下，自下而上的不同，或根据其他一些技 术的引入不同，主要有六种方法剪枝，它们的详细评述见文献【3 9 】。这些主要包括 m c c p ( m i n i m a l c o s t - c o m p l e x i t y p r u n i n g ) 方法，用于c a r t 系统，r e p ( p e d u c e de r r o r p r u i n g ) , m e p ( m i n i m a l e r r o r p r u n i n g ) 方法，p e p ( p e s s i m i s t i c e r r o r p r u n i n g ) 方法也 用于1 1 ) 3 系统和e b p ( e r r o rb a s e dp r u n i n g ) 方法用于c 4 5 系统【4 0 】，另有一些其他 方法，如b o o t s t m p 方法等，但对它们缺少系统的测试与评价。 3 、增量树学习 在一般情况下，为了解决内存空间的问题，利用增量树学习( i n c r e m e n t a l t r e _ e s i z i n g ) 的方法，通过逐步增加训练实例增量式地构造决策树。在递归谣用剪枝 算法的过程中，因为大的实例集对于剪枝是有好处的，所以如果增加训练实例的时 1 2 2 数据挖掘中的决策捉方法 候重新考虑以前进行剪枝的决定是有一定好处的。 另一种增量式学习方法是动态剪枝( d y n a m i cp r u n i n g ) 或者叫做虚剪枝( v i r t u a l p r u n i n g ) 。在这种方法中，也是根据前面的方法以统计的方法建立树。不同的是并 不是整个树的所有结点都用来分类。而是有一部分叶结点作为虚结点，不对实例进 行分类，而只有实结点对实例进行分类。虚结点可以被看作已经被修剪的结点。而 叶结点在虚结点与实结点之间的转换是在决策树积累实例的过程中动态决定的，所 以当将一个叶结点剪枝时只是将它变为虚结点，而不会带来不可修复的变化。 可以看出增量式