决策树建模优秀课件.ppt

《决策树建模优秀课件.ppt》由会员分享，可在线阅读，更多相关《决策树建模优秀课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、决策树建模决策树建模第1页，本讲稿共44页4.1数据分类介绍数据分类介绍分类分类是是数据挖掘数据挖掘的一个重要课题的一个重要课题,它的目的是：它的目的是：构造一个分类函数或分类模型构造一个分类函数或分类模型,该模型能把数据库中的该模型能把数据库中的数据项映射到给定类别中的某一个。数据项映射到给定类别中的某一个。数据分类的过程一般来说主要包含两个步骤数据分类的过程一般来说主要包含两个步骤第一步第一步,建立一个描述已知数据集类别或概念的模型建立一个描述已知数据集类别或概念的模型第二步第二步,利用所获得的模型进行分类操作利用所获得的模型进行分类操作第2页，本讲稿共44页4.1数据分类介绍数据分类介绍

2、-2第一步第一步,建立一个描述已知数据集类别或概念的模型建立一个描述已知数据集类别或概念的模型该模型是通过对数据库中各数据进行内容的分析而获得该模型是通过对数据库中各数据进行内容的分析而获得的。的。分类学习方法所使用的数据集称为分类学习方法所使用的数据集称为训练样本集合训练样本集合，每一，每一数据行都属于一个确定的数据类别，其类别值是由一个属性数据行都属于一个确定的数据类别，其类别值是由一个属性来描述的来描述的(被称为被称为类别标记属性类别标记属性)。因此分类学习又可称为因此分类学习又可称为监督学习监督学习，它是在，它是在已知训练样本已知训练样本类别类别情况下，通过学习建立相应模型。而情况下，

3、通过学习建立相应模型。而无监督学习无监督学习则是在则是在训练样本的类别与类别个数均未知的情况下进行的，如聚类训练样本的类别与类别个数均未知的情况下进行的，如聚类分析。分析。第3页，本讲稿共44页4.1数据分类介绍数据分类介绍-2第二步第二步,利用所获得的模型进行分类操作利用所获得的模型进行分类操作首先对模型分类准确率进行估计。首先对模型分类准确率进行估计。模型的准确性可以通过由该模型所正确分类的测试样本模型的准确性可以通过由该模型所正确分类的测试样本个数所占总测试样本的比例得到。即对于每一个测试样本，个数所占总测试样本的比例得到。即对于每一个测试样本，比较其已知的类别与学习所获模型的预测类别。

4、比较其已知的类别与学习所获模型的预测类别。如果一个学习所获模型的准确率经测试被认为是可以如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未来数据行或对象接受的，那么就可以使用这一模型对未来数据行或对象(其类别未知其类别未知)进行分类，即利用学习所获得的模型进行分类，即利用学习所获得的模型进行预测进行预测，对未知类别的数据行或对象判断其，对未知类别的数据行或对象判断其类别类别(属性属性)取值。取值。第4页，本讲稿共44页由训练数据产生分类规则第5页，本讲稿共44页由分类规则对新的样本数据进行分类第6页，本讲稿共44页4.1决策树介绍决策树介绍-2常用的分类预测算法：

5、常用的分类预测算法：l决策树归纳分类决策树归纳分类l贝叶斯分类贝叶斯分类l基于规则的分类基于规则的分类l用后向传播分类用后向传播分类l遗传算法、粗糙集方法、模糊集方法遗传算法、粗糙集方法、模糊集方法第7页，本讲稿共44页4.1决策树介绍决策树介绍-24.1.1决策树的基本知识决策树的基本知识决策树方法最早产生于决策树方法最早产生于20世纪世纪60年代，是由年代，是由Hunt等人研究人类概念建模时建等人研究人类概念建模时建立的学习系统立的学习系统CLS(conceptlearningsystem)。到了。到了70年代末，年代末，J.RossQuinlan提出提出ID3算法，引进信息论中的有关思想

6、，提出用信息算法，引进信息论中的有关思想，提出用信息增益增益(informationgain)作为特征判别能力的度量，来选择属性作为决策树的节点，作为特征判别能力的度量，来选择属性作为决策树的节点，并将建树的方法嵌在一个迭代的程序之中。当时他的主要目的在于减少树的深度，并将建树的方法嵌在一个迭代的程序之中。当时他的主要目的在于减少树的深度，却忽略了叶子数目的研究。却忽略了叶子数目的研究。1975年和年和1984年，分别有人提出了年，分别有人提出了CHAID和和CART算法。算法。1986年，年，J.C.Schlinner提出提出ID4算法。算法。1988年，年，P.E.Utgoff提出提出ID

7、5R算法。算法。1993年，年，Quinlan本人以本人以ID3算法为基础研究出算法为基础研究出C4.5算法。新算法在对预测变量的缺失值处理、算法。新算法在对预测变量的缺失值处理、剪枝技术、派生规则等方面作了较大的改进，剪枝技术、派生规则等方面作了较大的改进，C5.0是是C4.5的商业改进版。的商业改进版。第8页，本讲稿共44页例子例子关于上mooc的例子第9页，本讲稿共44页例子例子第10页，本讲稿共44页例子例子第11页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识决策树技术发现数据模式和规则的核心是决策树技术发现数据模式和规则的核心是归纳算法归纳算法。归纳是从特殊到一般的过程

8、。归纳是从特殊到一般的过程。归纳推理从若干个事实表征出的特征、特性或属性中归纳推理从若干个事实表征出的特征、特性或属性中,通过比较、总结、概括而得出一个规律性的结论。通过比较、总结、概括而得出一个规律性的结论。归纳学习的过程就是寻找一般化描述归纳学习的过程就是寻找一般化描述(归纳断言归纳断言)的过程。的过程。这种一般化描述能够解释给定的输入数据，并可以用来这种一般化描述能够解释给定的输入数据，并可以用来预测预测新的数据。新的数据。归纳学习由于依赖于经验数据，因此又称作归纳学习由于依赖于经验数据，因此又称作经验学习经验学习。第12页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2归

9、纳学习存在一个基本假定归纳学习存在一个基本假定:任一模型如果能在足够大的任一模型如果能在足够大的训练样本集训练样本集中很好地逼近中很好地逼近目标函数，则它也能在目标函数，则它也能在未见样本未见样本中很好地逼近目标函数。中很好地逼近目标函数。这个假定是归纳学习这个假定是归纳学习有效性的前提条件有效性的前提条件。归纳过程就是在描述空间中进行搜索的过程。归纳过程就是在描述空间中进行搜索的过程。第13页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2归纳可以分为自下而上、自上而下和双向搜索三种方式归纳可以分为自下而上、自上而下和双向搜索三种方式自下而上法一次处理一个输入对象，将描述逐步自

10、下而上法一次处理一个输入对象，将描述逐步一般化，直到最终的一般化描述。一般化，直到最终的一般化描述。自上而下法则对可能的一般化描述集进行搜索，试图自上而下法则对可能的一般化描述集进行搜索，试图找到一些满足一定要求的最优的描述。找到一些满足一定要求的最优的描述。双向搜索方式则是这两者的结合。双向搜索方式则是这两者的结合。第14页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2先根据先根据训练子集训练子集(又称为窗口又称为窗口)形成决策树，如果该树不形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外能对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复该过程一

11、直到形成正确的决策集。加入到窗口中，重复该过程一直到形成正确的决策集。最终结果是最终结果是“一棵树一棵树”，其叶节点是，其叶节点是类名类名，中间节点是，中间节点是带有分枝的属性带有分枝的属性，该分枝对应，该分枝对应该属性的某一可能值。该属性的某一可能值。第15页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2决策树通常有两大类型，分别为决策树通常有两大类型，分别为分类决策树分类决策树和和回归决策树回归决策树。分类决策树用来实现对定类或定序目标变量的分类，分类决策树用来实现对定类或定序目标变量的分类，回归决策树则完成对定距目标变量取值的预测。回归决策树则完成对定距目标变量取值的预测

12、。根据决策树各种不同的属性，可分为以下几类根据决策树各种不同的属性，可分为以下几类:l决策树内节点的测试属性可能是单变量的，即每个内节点只包含一个决策树内节点的测试属性可能是单变量的，即每个内节点只包含一个属性属性;也可能是多变量的，既存在包含多个属性的内节点。也可能是多变量的，既存在包含多个属性的内节点。l测试属性的不同属性值的个数，可能使得每个内节点有两个或多个测试属性的不同属性值的个数，可能使得每个内节点有两个或多个分枝。如果一棵决策树每个内节点只有两个分枝则称之为二叉分枝。如果一棵决策树每个内节点只有两个分枝则称之为二叉决策树，如由决策树，如由CART算法生成的决策树。算法生成的决策树

13、。l每个属性可能是值类型每个属性可能是值类型(连续值连续值)，也可能是枚举类型，也可能是枚举类型(离散值离散值)。l分类结果既可能是两类也有可能是多类，如果二叉决策树的结果只有分类结果既可能是两类也有可能是多类，如果二叉决策树的结果只有两类，则称之为布尔决策树。两类，则称之为布尔决策树。第16页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2决策树学习是应用最广的归纳推理算法之一。它是一种决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散函数值的方法，分类精度高，操作简单，并且对逼近离散函数值的方法，分类精度高，操作简单，并且对噪噪声数据声数据有很好的稳健性，因而成为比较实

14、用且比较流行的数有很好的稳健性，因而成为比较实用且比较流行的数据挖掘算法。据挖掘算法。它的最大优点是，在学习过程中不需要使用者了解很多它的最大优点是，在学习过程中不需要使用者了解很多背景知识，只要训练样本集能够用背景知识，只要训练样本集能够用“属性属性-值值”的方式表达的方式表达出来就能使用决策树学习算法来分类。出来就能使用决策树学习算法来分类。第17页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2决策树方法的决策树方法的(相对相对)优点优点:l可以生成可理解的规则可以生成可理解的规则数据挖掘产生的模式的可理解度是判别数据挖掘算法的数据挖掘产生的模式的可理解度是判别数据挖掘算法

15、的主要指标之一，相比于一些数据挖掘算法，决策树算法主要指标之一，相比于一些数据挖掘算法，决策树算法产生的规则比较容易理解，并且决策树模型的建立过程产生的规则比较容易理解，并且决策树模型的建立过程也很直观。也很直观。l计算量较小。计算量较小。l可以处理连续和集合属性。可以处理连续和集合属性。l决策树的输出包含属性的排序决策树的输出包含属性的排序生成决策树时，按照最大信息增益选择测试属性，生成决策树时，按照最大信息增益选择测试属性，因此，在决策树中可以大致判断属性的相对重要性。因此，在决策树中可以大致判断属性的相对重要性。第18页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2决策树

16、方法的缺点决策树方法的缺点:l对于具有连续值的属性预测比较困难。对于具有连续值的属性预测比较困难。-l对于顺序相关的数据，需要很多预处理的工作。对于顺序相关的数据，需要很多预处理的工作。l当类别太多时，通常会增加误差当类别太多时，通常会增加误差l分枝间的拆分不够平滑，进行拆分时，不考虑其对将来拆分的影响。分枝间的拆分不够平滑，进行拆分时，不考虑其对将来拆分的影响。l缺值数据处理问题缺值数据处理问题:因为决策树进行分类预测时，完全基于数据的测试属因为决策树进行分类预测时，完全基于数据的测试属性，所以对于测试属性缺失的数据，决策树将无法处理。性，所以对于测试属性缺失的数据，决策树将无法处理。l通常

17、仅根据单个属性来分类通常仅根据单个属性来分类:决策树方法根据单个属性对数据进行决策树方法根据单个属性对数据进行分类，而在实际的分类系统中，类的划分不仅仅与单个属性有关，往往与一个属分类，而在实际的分类系统中，类的划分不仅仅与单个属性有关，往往与一个属性集有关。因此，将决策树算法推广到考虑多属性性集有关。因此，将决策树算法推广到考虑多属性是一个有待研究的课题。是一个有待研究的课题。第19页，本讲稿共44页4.1.1决策树的基本知识决策树的基本知识-2决策树学习算法适用的问题决策树学习算法适用的问题:l样本可以用样本可以用“属性属性-值值”的方式来描述的方式来描述l目标函数的输出值为离散值目标函数

18、的输出值为离散值l训练数据中允许包含有错误训练数据中允许包含有错误:样本的分类错误或属性值错误都允许样本的分类错误或属性值错误都允许l训练数据中有样本属性值缺失训练数据中有样本属性值缺失第20页，本讲稿共44页4.1决策树介绍决策树介绍-24.1.2决策树的应用和发展趋势决策树的应用和发展趋势决策树由于结构简单、效率高等优点而获得了广泛的应用。在国外，决策决策树由于结构简单、效率高等优点而获得了广泛的应用。在国外，决策树在商业、工业、天文、医学、风险分析、社会科学和分类学等领域的应用已经树在商业、工业、天文、医学、风险分析、社会科学和分类学等领域的应用已经取得了很好的经济和社会效益。取得了很好

19、的经济和社会效益。国内目前有关决策树的研究多是围绕算法的改进以及决策树在商业、工业等领域国内目前有关决策树的研究多是围绕算法的改进以及决策树在商业、工业等领域的运用。的运用。l在商业领域，决策树方法所能解决的典型商业问题有在商业领域，决策树方法所能解决的典型商业问题有:客户关系客户关系管理、数据库营销、客户群体划分、交叉销售等市场分析管理、数据库营销、客户群体划分、交叉销售等市场分析行为，以及客户流失分析、客户信用计分及欺诈发现，等等。行为，以及客户流失分析、客户信用计分及欺诈发现，等等。l在工业领域，决策树可以用于故障诊断、工业生产过程控制等。在工业领域，决策树可以用于故障诊断、工业生产过程

20、控制等。l在医学领域，决策树方法可用于疾病诊断治疔、在医学领域，决策树方法可用于疾病诊断治疔、基因与高分子序列分析、医院信息系统挖掘及医疗政策分析等。基因与高分子序列分析、医院信息系统挖掘及医疗政策分析等。第21页，本讲稿共44页4.2树的建模过程树的建模过程第22页，本讲稿共44页4.2树的建模过程树的建模过程决策树算法通过构造决策树来发现数据中蕴涵的分类规决策树算法通过构造决策树来发现数据中蕴涵的分类规则，包含许多种不同的算法，主要可以分为三类则，包含许多种不同的算法，主要可以分为三类:(1)基于统计学理论的方法，以基于统计学理论的方法，以CART为代表，在这类算法中，为代表，在这类算法中

21、，对于非终端节点来说，有两个分枝对于非终端节点来说，有两个分枝;(2)基于信息理论的方法，以基于信息理论的方法，以ID3算法为代表，此类算法中，算法为代表，此类算法中，非终端的节点的分枝由样本类别个数决定非终端的节点的分枝由样本类别个数决定;(3)以以AID，CHAD为代表的算法，在此类算法中，非终端节为代表的算法，在此类算法中，非终端节点的分枝数在点的分枝数在2至样本类别个数范围内分布。至样本类别个数范围内分布。这些算法在分类中应用的过程与思想基本上是一致的。这些算法在分类中应用的过程与思想基本上是一致的。如何构造如何构造精度高、规模小的决策树精度高、规模小的决策树是决策树算法的是决策树算法

22、的核心内容核心内容第23页，本讲稿共44页4.2树的建模过程树的建模过程总体步骤总体步骤决策树的构造基本可以分为如下两步决策树的构造基本可以分为如下两步:l决策树的生成决策树的生成决策树的生成是指由决策树的生成是指由训练样本数据集训练样本数据集生成决策树的过程。生成决策树的过程。一般情况下，训练样本数据集是根据实际需要由实际的历史一般情况下，训练样本数据集是根据实际需要由实际的历史数据生成的、有一定综合程度的、用于数据分析处理的数据生成的、有一定综合程度的、用于数据分析处理的数据集。数据集。l决策树的剪枝决策树的剪枝决策树剪枝是对上一阶段所生成的决策树进行检验、决策树剪枝是对上一阶段所生成的决

23、策树进行检验、校正和修正的过程，主要是采用新的样本数据集校正和修正的过程，主要是采用新的样本数据集(称为称为测试数据集测试数据集)中的数据检验决策树生成过程中产生的初步中的数据检验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。一般情况下，根规则，将那些影响预测准确性的分枝剪除。一般情况下，根据测试数据集中的每一元组对生成的规则进行预测准确性的据测试数据集中的每一元组对生成的规则进行预测准确性的检验，如果预测准确性过低，则将该分枝剪除。检验，如果预测准确性过低，则将该分枝剪除。第24页，本讲稿共44页4.2树的建模过程树的建模过程4.2.1数据要求数据要求(数据准备数据准备)在

24、进行分类和预测挖掘之前，首先必须准备好有关挖掘在进行分类和预测挖掘之前，首先必须准备好有关挖掘数据。一般需要对数据进行以下预处理，以帮助提高分类和数据。一般需要对数据进行以下预处理，以帮助提高分类和预测过程的准确性、有效性和可伸缩性。主要的工作包括：预测过程的准确性、有效性和可伸缩性。主要的工作包括：n数据清洗数据清洗n相关分析相关分析n数据转换数据转换第25页，本讲稿共44页4.2.1数据准备数据准备数据清洗数据清洗这一数据预处理步骤，主要是帮助除去数据中的噪声，这一数据预处理步骤，主要是帮助除去数据中的噪声，并妥善解决缺失数据问题，尽管大多数分类算法都包含一些并妥善解决缺失数据问题，尽管大

25、多数分类算法都包含一些处理噪声和缺失数据的方法，但这一预处理步骤可以有效处理噪声和缺失数据的方法，但这一预处理步骤可以有效减少学习过程可能出现相互矛盾情况的问题。减少学习过程可能出现相互矛盾情况的问题。第26页，本讲稿共44页4.2.1数据准备数据准备相关分析相关分析由于数据集中的许多属性与挖掘任务本身可能是无关的，由于数据集中的许多属性与挖掘任务本身可能是无关的，例如记录银行贷款申请例如记录银行贷款申请(单单)填写时的星期数填写时的星期数(属性属性)，就可能与，就可能与申请成功与否的描述无关。此外，有些属性也可能是冗余的。申请成功与否的描述无关。此外，有些属性也可能是冗余的。因此需要对数据进

26、行相关分析，以使在学习阶段之前就消除因此需要对数据进行相关分析，以使在学习阶段之前就消除无关或冗余属性。在机器学习中，这一相关分析步骤被称为无关或冗余属性。在机器学习中，这一相关分析步骤被称为属性选择属性选择(featureselection)，包含与挖掘任务无关的属性可，包含与挖掘任务无关的属性可能会减缓甚至误导整个学习过程。在理想情况下，相关分析能会减缓甚至误导整个学习过程。在理想情况下，相关分析所花费的时间加上对削减后属性所花费的时间加上对削减后属性(子子)集进行归纳集进行归纳学习所花费的时间之和，应小于从初始属性集进行学习所花学习所花费的时间之和，应小于从初始属性集进行学习所花费的时间

27、，从而达到帮助改善分类效率和可扩展性的目的。费的时间，从而达到帮助改善分类效率和可扩展性的目的。第27页，本讲稿共44页4.2.1数据准备数据准备数据转换数据转换利用概念层次树，数据能够被泛化到更高的层次。概念利用概念层次树，数据能够被泛化到更高的层次。概念层次树对连续数值的转换非常有效。例如，属性层次树对连续数值的转换非常有效。例如，属性“收入收入”的的数值就可以被泛化为若干离散区间，诸如低、中和高。类似数值就可以被泛化为若干离散区间，诸如低、中和高。类似地，像地，像“街道街道”这样的属性也可以被泛化到更高的抽象层次，这样的属性也可以被泛化到更高的抽象层次，如泛化到城市。由于泛化操作压缩了原

28、来的数据集，从而可如泛化到城市。由于泛化操作压缩了原来的数据集，从而可以帮助有效减少学习过程所涉及的输入输出操作。此外，初以帮助有效减少学习过程所涉及的输入输出操作。此外，初始数据可能还需要规格化，特别是在利用距离计算方法实施始数据可能还需要规格化，特别是在利用距离计算方法实施各种学习方法时，如在基于示例学习方法中，规格化处理是各种学习方法时，如在基于示例学习方法中，规格化处理是不可或缺的重要处理操作。不可或缺的重要处理操作。第28页，本讲稿共44页4.2树的建模过程树的建模过程4.2.2树的生长树的生长决策树算法是一种常用的数据挖掘算法，它是从决策树算法是一种常用的数据挖掘算法，它是从机器学

29、习领域中逐渐发展起来的一种分类函数逼近方法。机器学习领域中逐渐发展起来的一种分类函数逼近方法。决策树学习的基本算法是贪心算法，采用自上而下的递归决策树学习的基本算法是贪心算法，采用自上而下的递归方式构造决策树。方式构造决策树。Hunt等人于等人于1966年提出的概念学习系统年提出的概念学习系统(conceptlearningsystem，CLS)是最早的决策树算法，以后是最早的决策树算法，以后的许多决策树算法都是对的许多决策树算法都是对CLS算法的改进或由算法的改进或由CLS衍生而来。衍生而来。目前，利用决策树进行数据分类的方法已经被深入研究，并目前，利用决策树进行数据分类的方法已经被深入研究

30、，并且形成了许多决策树算法。且形成了许多决策树算法。第29页，本讲稿共44页4.2树的建模过程树的建模过程决策树算法的分类模型是一棵决策树算法的分类模型是一棵有向无环树有向无环树，下面将以下面将以二叉树为例二叉树为例说明说明基本的决策树算法。基本的决策树算法。决策树的每个节点有决策树的每个节点有0或或2个子节点，除了根节点以外，个子节点，除了根节点以外，每个节点有且仅有一个父节点。如果节点没有子节点，则称每个节点有且仅有一个父节点。如果节点没有子节点，则称它为它为叶节点叶节点，否则称为，否则称为内部节点内部节点。第30页，本讲稿共44页4.2树的建模过程树的建模过程每个叶节点对应每个叶节点对应

31、一个类标号一个类标号，使用决策树对未知样本，使用决策树对未知样本分类的类标号的值即为叶节点的值。每个内部节点都对应分类的类标号的值即为叶节点的值。每个内部节点都对应一个分枝方案，它包括用于节点分裂的属性一个分枝方案，它包括用于节点分裂的属性A和分枝的和分枝的判断规则判断规则q。训练样本的属性分为数值属性和分类属性，数值属性的训练样本的属性分为数值属性和分类属性，数值属性的取值范围是一个连续的区间，比如实数集取值范围是一个连续的区间，比如实数集R;而分类属性的取而分类属性的取值范围则是离散值的集合值范围则是离散值的集合S(A)，比如性别属性的取值范围就，比如性别属性的取值范围就是集合是集合男，女

32、男，女。如果属性如果属性A是数值属性，那么是数值属性，那么q 的形式是的形式是Av，其中其中v是是属于属于A的取值范围的一个常量的取值范围的一个常量;如果如果A是分类属性，那么是分类属性，那么q 的形式是的形式是AS,其中其中S是是S(A)的子集。的子集。第31页，本讲稿共44页4.2.2树的生长树的生长决策树是决策树是“一棵树一棵树”，它的根节点是整个数据集合空间，它的根节点是整个数据集合空间，每个分节点是对一个每个分节点是对一个单一变量单一变量(属性属性)的测试，该测试将数据的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于集合空间分割成两个或更多块。每个叶节点是属于单一类别

33、单一类别的记录。的记录。首先，通过首先，通过训练集训练集生成决策树，再通过生成决策树，再通过测试集测试集对决策树对决策树进行修剪。进行修剪。决策树的决策树的功能功能是是预测一个新的记录属于哪一类预测一个新的记录属于哪一类。第32页，本讲稿共44页4.2.2树的生长树的生长通常通常,通过通过自上而下递归分割自上而下递归分割的过程来构建决策树的过程来构建决策树,分为分为三个步骤三个步骤:(1)寻找初始分裂。整个寻找初始分裂。整个训练集训练集作为产生决策树的集合，作为产生决策树的集合，训练集每个记录必须是已经分好类的。决定哪个属性训练集每个记录必须是已经分好类的。决定哪个属性(field)域作为目前

34、最好的分类指标。一般的做法是穷尽所有域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。的一个分裂。(2)树增长到一棵完整的树。重复第一步，直至每个叶节点树增长到一棵完整的树。重复第一步，直至每个叶节点内的记录都属于同一类，或达到其他停止准则。内的记录都属于同一类，或达到其他停止准则。(3)数据的修剪。去掉一些可能是噪音或者异常的数据或节点数据的修剪。去掉一些可能是噪音或者异常的数据或节点第33页，本讲稿共44页4.2.2树的生长树的生长其通用的基本算法其通用的基本算法(贪心算法贪心算

35、法)为为:以自上而下分而治之的方法，开始时，所有的数据都在以自上而下分而治之的方法，开始时，所有的数据都在根节点根节点;属性都是种类字段属性都是种类字段(如果是连续的，将其离散化如果是连续的，将其离散化);所所有记录用所选属性递归地进行分割有记录用所选属性递归地进行分割;属性的选择是基于一个属性的选择是基于一个启发式规则或者一个统计的度量启发式规则或者一个统计的度量(如如informationgain)。停止分割的条件停止分割的条件:一个节点上的数据都是属于同一个一个节点上的数据都是属于同一个类别或没有属性可以再用于对数据进行分割。类别或没有属性可以再用于对数据进行分割。第34页，本讲稿共44

36、页4.2.2树的生长树的生长算法的形式描述算法的形式描述ProcedureBuildTree(S)用数据集用数据集S初始化根节点初始化根节点R用根节点用根节点R初始化队列初始化队列QWhi1eQisnotEmpty,do取出队列取出队列Q中的第一个节点中的第一个节点NifN不纯不纯(impure)for每一个属性每一个属性A估计该节点在估计该节点在A上的信息增益上的信息增益选出最佳的属性选出最佳的属性,将将N分裂为分裂为N1,N2第35页，本讲稿共44页4.2树的建模过程树的建模过程-34.2.3有效性和风险性有效性和风险性基本的决策树算法没有考虑噪声基本的决策树算法没有考虑噪声,生成的决策树

37、完全与生成的决策树完全与训练例子拟合。训练例子拟合。这样虽然能降低算法的时间复杂度，但也使算法在这样虽然能降低算法的时间复杂度，但也使算法在较深层次的样本划分中，专注于训练样本集某个子集的统计较深层次的样本划分中，专注于训练样本集某个子集的统计信息，而忽视各类样本的整体分布情况，造成了对噪声敏感。信息，而忽视各类样本的整体分布情况，造成了对噪声敏感。所以，虽然一棵完整的决策树能够非常准确地反映所以，虽然一棵完整的决策树能够非常准确地反映训练样本集训练样本集中数据的特征，但因失去了一般代表性而无法中数据的特征，但因失去了一般代表性而无法对新数据进行准确的分类或预测，出现了过匹配现象。对新数据进行

38、准确的分类或预测，出现了过匹配现象。第36页，本讲稿共44页4.2.3有效性和风险性有效性和风险性过匹配过匹配指的是模型由于过度训练，导致其记住的不是指的是模型由于过度训练，导致其记住的不是训练数据的一般特性，而是训练集的局部特性。训练数据的一般特性，而是训练集的局部特性。当将这个模型应用到新的测试集上时就导致预测结果的当将这个模型应用到新的测试集上时就导致预测结果的不准确。不准确。因此，一个完整的决策树构造过程将包含因此，一个完整的决策树构造过程将包含决策树的创建决策树的创建和和决策树的剪枝决策树的剪枝这两方面。这两方面。剪枝是一种克服噪声的技术，用于解决过匹配问题，剪枝是一种克服噪声的技术

39、，用于解决过匹配问题，同时它也能使树得到简化而变得更容易理解。同时它也能使树得到简化而变得更容易理解。第37页，本讲稿共44页4.2.3有效性和风险性有效性和风险性剪枝的原则包括剪枝的原则包括:l奥卡姆剃刀原则奥卡姆剃刀原则“如无必要，勿增实体如无必要，勿增实体”。即在与。即在与观察相容的情况下，应当选择最简单的一棵决策树。观察相容的情况下，应当选择最简单的一棵决策树。l决策树越小就越容易理解，其存储与传输的代价也就决策树越小就越容易理解，其存储与传输的代价也就越小。越小。l决策树越复杂，节点越多，每个节点包含的训练样本个决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点的

40、假设的样本个数就越少，可数越少，则支持每个节点的假设的样本个数就越少，可能导致决策树在测试集上的能导致决策树在测试集上的分类错误率就会增大分类错误率就会增大。但决策树过小也会导致错误率较大。因此，但决策树过小也会导致错误率较大。因此，需要在树的大小与正确率之间寻找均衡点需要在树的大小与正确率之间寻找均衡点第38页，本讲稿共44页4.2.3有效性和风险性有效性和风险性常用的剪枝技术有预剪枝常用的剪枝技术有预剪枝(pre-pruning)和后剪枝和后剪枝(post-pruning)两种。两种。l预剪枝预剪枝：在构造决策树时，决定不再对：在构造决策树时，决定不再对不纯的训练子集不纯的训练子集进行进一

41、步划分的剪枝方法进行进一步划分的剪枝方法预剪枝技术限制了决策树的过度生长预剪枝技术限制了决策树的过度生长如如CHAID,ID3系列的系列的ID3、C4.5算法等算法等l后剪枝后剪枝：在树完全生成之后的剪枝策略：在树完全生成之后的剪枝策略如如CART算法等算法等剪枝的目的就是删除由于噪声数据而引起的分枝，从而剪枝的目的就是删除由于噪声数据而引起的分枝，从而避免决策树的过匹配。避免决策树的过匹配。第39页，本讲稿共44页4.2.3有效性和风险性有效性和风险性预剪枝中最直接而简单的方法是事先指定决策树生长的预剪枝中最直接而简单的方法是事先指定决策树生长的最大深度，使决策树不能得到充分生长。这种停止标

42、准一般最大深度，使决策树不能得到充分生长。这种停止标准一般能够取得比较好的效果。不过指定树的高度的方法要求用户能够取得比较好的效果。不过指定树的高度的方法要求用户对数据的取值分布有较为清晰的把握，而且须对参数值进行对数据的取值分布有较为清晰的把握，而且须对参数值进行反复尝试，否则无法给出一个较为合理的树高度阈值。反复尝试，否则无法给出一个较为合理的树高度阈值。第40页，本讲稿共44页4.2.3有效性和风险性有效性和风险性后剪枝技术允许决策树过度生长，然后根据一定的后剪枝技术允许决策树过度生长，然后根据一定的规则，剪去决策树中那些不具有规则，剪去决策树中那些不具有一般代表性一般代表性的叶节点或分

43、枝。的叶节点或分枝。后剪枝算法有自上而下和自下而上两种剪枝策略。后剪枝算法有自上而下和自下而上两种剪枝策略。自下而上的算法首先从最底层的内节点开始，剪去满足自下而上的算法首先从最底层的内节点开始，剪去满足一定条件的内节点，在生成的新决策树上递归调用这个算法，一定条件的内节点，在生成的新决策树上递归调用这个算法，直到没有可以剪枝的节点为止。直到没有可以剪枝的节点为止。自上而下的算法是从根节点开始向下逐个考虑节点的剪自上而下的算法是从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就进行剪枝。枝问题，只要节点满足剪枝的条件就进行剪枝。第41页，本讲稿共44页4.2.3有效性和风险性有效

44、性和风险性目前，决策树修剪策略主要有三种目前，决策树修剪策略主要有三种:悲观修剪悲观修剪(pessimisticpruning)，代价复杂度修剪，代价复杂度修剪(cost-complexitypruning)和基于最小描述长度和基于最小描述长度(minimumdescriptionlength，MDL)原理的修剪。原理的修剪。悲观修剪是悲观修剪是Quinlan在在1987年提出的，该方法将所有的年提出的，该方法将所有的样本用于树的构建和修剪，但是这种方法产生的树太大，并样本用于树的构建和修剪，但是这种方法产生的树太大，并且有时候精度不高。代价复杂度修剪使用了独立的样本用于且有时候精度不高。代价

45、复杂度修剪使用了独立的样本用于修剪，这种策略适用于训练样本比较多的情况。在训练样本修剪，这种策略适用于训练样本比较多的情况。在训练样本数目较少的情况下，需要将所有的样本既用于树的构建，又数目较少的情况下，需要将所有的样本既用于树的构建，又用于树的修剪。基于用于树的修剪。基于MDL原理的修剪是使用较多并且效果较原理的修剪是使用较多并且效果较好的方法。好的方法。第42页，本讲稿共44页4.2树的建模过程树的建模过程4.2.4属性选择属性选择属性选择的统计度量属性选择的统计度量(又称为又称为分枝指标分枝指标splittingindex，SI)的计算是决策树构建算法的的计算是决策树构建算法的关键关键。不同的决策树算法采用不同的统计度量，主要有不同的决策树算法采用不同的统计度量，主要有:l信息增益信息增益InformationGain(ID3和和C4.5算法使用算法使用)，所有属性假设都是所有属性假设都是种类字段种类字段，经过修改之后可以适用于，经过修改之后可以适用于数值字段数值字段;l基尼指数基尼指数Giniindex(即即Gini指标指标)CART算法、算法、CHAID算法和算法和SLIQ算法使用算法使用适用于种类和数值字段等等。适用于种类和数值字段等等。第43页，本讲稿共44页TOBECONTINUED第44页，本讲稿共44页