第5章-数据分类-决策树解析课件.ppt

1、2023-5-231数据仓库与数据挖掘技术数据仓库与数据挖掘技术2023-5-232 第5章章 决策树和决策规则决策树和决策规则 5.1 引例引例 n分类的定义n分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。2023-5-233AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1描述属性描述属性类别属性类别属性分类问题使用的数据集格式：分类问题使用的数据集格式：2023-5-2345.1 引例n分类问题使用的数据集格式n描述属性可以是连续型属性，也可以是

2、离散型属性；而类别属性必须是离散型属性。n连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的，例如属性“Age”n离散型属性是指该属性的取值是不连续的，例如属性“Salary”和“Class”2023-5-2355.1 引例n分类问题使用的数据集格式n分 类 问 题 中 使 用 的 数 据 集 可 以 表 示 为X=(xi,yi)|i=1,2,totalnxi=(xi1,xi2,xid)，其中xi1,xi2,xid分别对应d个描述属性A1,A2,Ad的具体取值nyi表示数据样本xi的类标号，假设给定数据集包含m个类别，则yic1,c2,cm，其中c1,c2,cm是类别属性C的具体取值

3、n未知类标号的数据样本x用d维特征向量x=(x1,x2,xd)来表示2023-5-2365.2 分类问题概述n5.2.1 分类的过程n5.2.2 分类的评价准则2023-5-2375.2.1 分类的过程获取数据获取数据预处理预处理分类器设计分类器设计分类决策分类决策2023-5-2385.2.1 分类的过程n获取数据n输入数据、对数据进行量化n预处理n去除噪声数据、对空缺值进行处理n数据集成或者变换 n分类器设计n划分数据集、分类器构造、分类器测试n分类决策n对未知类标号的数据样本进行分类2023-5-2395.2.2 分类的评价准则n给定测试集Xtest=(xi,yi)|i=1,2,NnN表

4、示测试集中的样本个数nxi表示测试集中的数据样本nyi表示数据样本xi的类标号n对于测试集的第j个类别，假设n被正确分类的样本数量为TPjn被错误分类的样本数量为FNjn其他类别被错误分类为该类的样本数据量为FPj2023-5-23105.2.2 分类的评价准则n精确度：代表测试集中被正确分类的数据样本所占的比例 NTPAccuracym1jj2023-5-23115.2.2 分类的评价准则n查全率：表示在本类样本中被正确分类的样本所占的比例 n查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例 mj1,FNTPTPRecalljjjjmj1,FPTPTPPrecisionjjjj

5、2023-5-23125.2.2 分类的评价准则nF-measure(加权调合平均数加权调合平均数)：是查全率和查准率的组合表达式 n是可以调节的，通常取值为1 mj1,PrecisionRecallPrecisionRecall)1(measureFjj2jj2j2023-5-23135.2.2 分类的评价准则n几何均值：是各个类别的查全率的平方根 m1jjcallRemeanG2023-5-2314 决策树方法的起源是亨特（决策树方法的起源是亨特（HuntHunt，19661966）的）的概念学习系统概念学习系统CLSCLS方法，然后发展到由方法，然后发展到由QuinlanQuinlan研

6、制研制ID3ID3方法，然后到著名的方法，然后到著名的C4.5C4.5算法，算法，C4.5C4.5算算法的一个优点是它能够处理连续属性。还有法的一个优点是它能够处理连续属性。还有CARTCART算法和算法和AssistantAssistant算法也是比较有名的决策算法也是比较有名的决策树方法。树方法。5.3 5.3 决策树决策树2023-5-2315n决策树的优点：n进行分类器设计时，决策树分类方法所需时间相对较少n决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式n可以将决策树中到达每个叶节点的路径转换为IFTHEN形式的分类规则，这种形式更有利于理解2023-5-23161.1.

7、什么是决策树什么是决策树q 决策树（决策树（Decision TreeDecision Tree）又称为判定树，是运）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点用于分类的一种树结构。其中的每个内部结点（internal nodeinternal node）代表对某个属性的一次测试）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（，每条边代表一个测试结果，叶结点（leafleaf）代表某个类（代表某个类（classclass）或者类的分布（）或者类的分布（class class distributiondistribution），最上面的结点是根结点。），最上面的结点是

8、根结点。q 决策树提供了一种展示类似在什么条件下会得决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结策树的基本组成部分：决策结点、分支和叶结点。点。2023-5-2317例图例图5-2 给出了一个商业上使用的决策树的例子。它表给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个）

9、的知识，用它可以预测某条记录（某个人）的购买意向。人）的购买意向。Age?Credit_rating?student?yes no yes yes no 40 3040 yes no fair excellent 图图5-2 buys_computer的决策树的决策树 2023-5-2318这棵决策树对销售记录进行分类，指出一个电子产品消费者这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机是否会购买一台计算机“buys_computerbuys_computer”。每个内部结点。每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆（方形框）代表对某个属性的一

10、次检测。每个叶结点（椭圆框）代表一个类：框）代表一个类：buys_computers=yes buys_computers=yes 或者或者 buys_computers=nobuys_computers=no在这个例子中，样本向量为：在这个例子中，样本向量为：（age,student,credit_rating;buys_computersage,student,credit_rating;buys_computers）被决策数据的格式为被决策数据的格式为:（age,student,credit_ratingage,student,credit_rating）输入新的被决策的记录，可以预测该

11、记录隶属于哪个类。输入新的被决策的记录，可以预测该记录隶属于哪个类。2023-5-23192.2.使用决策树进行分类使用决策树进行分类 构造决策树是采用自上而下的递归构造方法。以多叉树构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入

12、是决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为结点）一般表示为一个逻辑判断，如形式为(a=b)的逻辑判的逻辑判断，其中断，其中a 是属性，是属性，b是该属性的某个属性值；树的边是逻是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（辑判断的分支结果。多叉树（ID3）的内部结点是属性，边）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。叶结点都是类别标记。202

13、3-5-2320使用决策树进行分类分为两步：使用决策树进行分类分为两步：q 第第1 1步：利用训练集建立并精化一棵决策树，建立决策步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。进行机器学习的过程。q 第第2 2步：利用生成完毕的决策树对输入数据进行分类。步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。到到达某个叶结点，从而找到该记录所在的类。2023-5-2

14、321问题的关键是建立一棵决策树。这个过程通常分为两个阶问题的关键是建立一棵决策树。这个过程通常分为两个阶段：段：q建树（建树（Tree BuildingTree Building）：决策树建树算法见下，这）：决策树建树算法见下，这是一个递归的过程，最终将得到一棵树。是一个递归的过程，最终将得到一棵树。q剪枝（剪枝（Tree PruningTree Pruning）：剪枝的目的是降低由于训）：剪枝的目的是降低由于训练集存在噪声而产生的起伏。练集存在噪声而产生的起伏。2023-5-2322 由由Quinlan在在80年代中期提出的年代中期提出的ID3算法是分类规则算法是分类规则挖掘算法中最有影响

15、的算法。挖掘算法中最有影响的算法。ID3即决策树归纳（即决策树归纳（Induction of Decision Tree）。早期的）。早期的ID算法只能就两类算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在必须是唯一的。在ID3算法挖掘后，分类规则由决策树来算法挖掘后，分类规则由决策树来表示。表示。5.4 5.4 分类规

16、则挖掘的分类规则挖掘的ID3ID3算法算法2023-5-23231.ID31.ID3算法的基本思想算法的基本思想 由训练数据集中全体属性值生成的所有决策树的集合由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树。系统根据某个评价函数决定搜索空间中的哪一个决策树是是“最好最好”的。评价函数一般依据分类的准确度和树的大的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测小来决定决策树的质量。如果两棵决策树都能准确地在

17、测试集进行分类，则选择较简单的那棵。相对而言，决策树试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵越简单，则它对未知数据的预测性能越佳。寻找一棵“最最好好”的决策树是一个的决策树是一个NP完全问题。完全问题。NPNP完全问题是这样的问题：用确定性的算法在多项式时间完全问题是这样的问题：用确定性的算法在多项式时间内无法解决的问题。实际之中，解决这样的问题，往往是内无法解决的问题。实际之中，解决这样的问题，往往是根据用启发式算法，求出近似的解。根据用启发式算法，求出近似的解。2023-5-2324ID3ID3使用一种自顶向下的方法在部分搜索空间创建

18、决策使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树树，同时保证找到一棵简单的决策树可能不是最简单的。可能不是最简单的。ID3ID3算法的基本思想描述如下：算法的基本思想描述如下：step 1step 1任意选取一个属性作为决策树的根结点，然后任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；就这个属性所有的取值创建树的分支；step 2step 2用这棵树来对训练数据集进行分类，如果一个用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所

19、有的叶结点都有类标记，则算法终止；结点；如果所有的叶结点都有类标记，则算法终止；step 3step 3否则，选取一个从该结点到根路径中没有出现否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤续创建树的分支；重复算法步骤step 2step 2；agestudentcredit_ratingbuys_computers25YESexcellantYES35NOfairYES2023-5-2325这个算法一定可以创建一棵基于训练数据集的正确的这个算法一定可以创建一棵基于训练

20、数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。属性将生成一棵简单的决策树。在在ID3算法中，采用了一种基于信息的启发式的方法算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息量的来决定如何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分支决策树的那个属性。属性，也就是说，生成最少分支决策树的那个属性。2023-5-2326算法：算法：Generat

21、e_decision_treeGenerate_decision_tree由给定的训练数据产生一棵决策树由给定的训练数据产生一棵决策树输入：训练数据集输入：训练数据集samplessamples，用离散值属性表示；候选属性的集合，用离散值属性表示；候选属性的集合attribute_listattribute_list。输出：一棵决策树输出：一棵决策树方法：方法：（1 1）创建结点）创建结点N N；（2 2）if samples if samples 都在同一个类都在同一个类C thenC then（3 3）返回）返回N N作为叶结点，用类作为叶结点，用类C C标记；标记；（4 4）if att

22、ribute_list if attribute_list 为空为空 then then（5 5）返回）返回N N作为叶结点，标记作为叶结点，标记samplessamples中最普通的类；中最普通的类；/多数表决多数表决（6 6）选择）选择attribute_listattribute_list中具有最高信息增益的属性中具有最高信息增益的属性test_attributetest_attribute；/用信息增益作为属性选择度量用信息增益作为属性选择度量（7 7）标记结点）标记结点N N为为test_attributetest_attribute；（8 8）for each test_attri

23、butefor each test_attribute中的已知值中的已知值aiai /划分划分samplessamples（9 9）由结点）由结点N N生长出一个条件为生长出一个条件为test_attributetest_attributeaiai的分枝；的分枝；（1010）设）设sisi为为samplessamples中中test_attributetest_attributeaiai的样本集合；的样本集合；/一个划分一个划分（1111）if siif si为空为空 thenthen（1212）加上一个叶结点，标记为标记）加上一个叶结点，标记为标记samplessamples中最普通的类；中

24、最普通的类；/多数表决多数表决（1313）else else 加上一个由加上一个由Generate_decision_treeGenerate_decision_tree（sisi,attribute_list-test_attribute,attribute_list-test_attribute）返回的结点；）返回的结点；2023-5-23272.2.属性选择度量属性选择度量在在Generate_decision_treeGenerate_decision_tree算法的算法的Step 6Step 6，算法需选择，算法需选择a t t r i b u t e _ l i s ta t t

25、r i b u t e _ l i s t 中 具 有 最 高 信 息 增 益 的 属 性中 具 有 最 高 信 息 增 益 的 属 性test_attributetest_attribute。ID3ID3算法在树的每个结点上以信息增益（算法在树的每个结点上以信息增益（information gaininformation gain）作为度量来选择测试属性。这种度量称）作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增为属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属益（或最大熵压缩）的属性作为当前结点的

26、测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。保找到一棵简单的（但不一定是最简单的）决策树。2023-5-2328Information GainInformation Gain指标的原理来自于信息论。指标的原理来自于信息论。19481948年，年，香农（香农（C.E.ShannonC.E.Shannon）提出了信息论。其中给出了关于）提出了信息论。其中给出了关于信息量（信息量（InformationInformation）和熵（）和熵（EntropyEntropy）的定义，熵

27、实际）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。上是系统信息量的加权平均，也就是系统的平均信息量。2023-5-2329假设要选择有假设要选择有n n个输出（所给属性的个输出（所给属性的n n个值）的检验，个值）的检验，把训练样本集把训练样本集T T分区成子集分区成子集T T1 1，T T2 2，T Tn n。仅有的指导信。仅有的指导信息是在息是在T T和它的子集和它的子集T Ti i中的类的分布。如果中的类的分布。如果S S是任意样本集，是任意样本集，设设freq(freq(C Ci i,S,S)代表代表S S中属于类中属于类C Ci i （k k个可能的类中的一个）个

28、可能的类中的一个）的样本数量，的样本数量，|S|S|表示集合表示集合S S中的样本数量。下面给出了中的样本数量。下面给出了集合集合S S（单位为比特）的熵计算：（单位为比特）的熵计算：kInfo(S)i=1 (freq(freq(C Ci i,S,S)/|S|).log2(freq(freq(C Ci i,S),S)/|S|)以以2 2为底的原因是：信息按二进制位编码为底的原因是：信息按二进制位编码2023-5-2330熵是一个衡量系统混乱程度的统计量。熵越大，表熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、分类的目的是提取

29、系统信息，使系统向更加有序、有规则组织的方向发展。所以最佳的分裂方案是使熵减有规则组织的方向发展。所以最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是少量最大的分裂方案。熵减少量就是Information GainInformation Gain（信息增益信息增益），所以，最佳分裂就是使，所以，最佳分裂就是使Gain(A)Gain(A)最大的分最大的分裂方案。通常，这个最佳方案是用裂方案。通常，这个最佳方案是用“贪心算法贪心算法+深度优先深度优先搜索搜索”得到的。得到的。2023-5-2331现在考虑现在考虑T T被分区之后的一个相似度量标准，被分区之后的一个相似度量标准，T T按照一按

30、照一个属性检验个属性检验X X的几个输出进行分区。所需信息可通过这些的几个输出进行分区。所需信息可通过这些子集的熵的加权和求得：子集的熵的加权和求得：n nInfo x(T)i=1 (|T|Ti i|/|T|).info(Ti)信息增益的计算公式：信息增益的计算公式：Gain(X)=Info(T)-Gain(X)=Info(T)-Info x(T)通过计算求出具有最高增益的属性。通过计算求出具有最高增益的属性。2023-5-2332以下分析有关度量标准的应用和创建决策树的一个以下分析有关度量标准的应用和创建决策树的一个简单例子，假设以平面文件形式给出的数据集简单例子，假设以平面文件形式给出的数

31、据集T T，其中有，其中有1414个样本，通过个样本，通过3 3个输入属性描述且属于所给的两个类之个输入属性描述且属于所给的两个类之一：类一：类1 1或类或类2 2。2023-5-2333训练例子的简单平面数据库训练例子的简单平面数据库数据库T：属性1属性2属性3属性4A70真类1A90真类2A85假类2A95假类2A70假类1B90真类1B78假类1B65真类1B75假类1C80真类2C70真类2C80假类1C80假类1C96假类12023-5-2334其中：其中：9 9个样本属于类个样本属于类1 1，5 5个样本属于类个样本属于类2 2，因此分区前，因此分区前的熵为：的熵为：info(T)

32、-9/14.log2(9/149/14)-5/14.log2(5/145/14)=0.940比特根据属性根据属性1 1把初始样本集分区成把初始样本集分区成3 3个子集（检验个子集（检验x x1 1表示从表示从3 3个值个值A A，B B或或C C中选择其一）后，得出结果：中选择其一）后，得出结果：Info x1(T)5/14（-2/5 log2(2/52/5)-3/5 log2(3/53/5)）+4/14（-4/4 log2(4/44/4)-0/4 log2(0/4/4)）+5/14（-3/5 log2(3/53/5)-2/5 log2(2/5/5)）=0.694比特通过检验通过检验x x1

33、1获得的信息增益是：获得的信息增益是：Gain(Gain(x x1 1)=0.940 0.694=0.246)=0.940 0.694=0.246比特比特2023-5-2335如果该检验和分区是基于属性如果该检验和分区是基于属性3 3的（检验的（检验x x2 2表示从真或假表示从真或假两个值选择其一），类似地有：两个值选择其一），类似地有：Info x2(T)6/14（-3/6 log2(3/63/6)-3/6 log2(3/63/6)）+8/14（-6/8 log2(6/86/8)-2/8 log2(2/8/8)）=0.892比特通过检验通过检验x x2 2获得的增益是：获得的增益是：Gai

34、n(Gain(x x2 2)=0.940 0.892=0.048)=0.940 0.892=0.048比特比特按照增益准则，将选择按照增益准则，将选择x x1 1作为分区数据库作为分区数据库T T的最初检验。的最初检验。为了求得最优检验还必须分析关于属性为了求得最优检验还必须分析关于属性2 2的检验，的检验，它是连续取值的数值型属性。它是连续取值的数值型属性。2023-5-23363.ID33.ID3算法的改进算法的改进（1 1）离散化）离散化 为了解决该问题，在用为了解决该问题，在用ID3ID3算法挖掘具有连续性属性算法挖掘具有连续性属性的知识时，应该首先把该连续性属性离散化。最简单的的知识

35、时，应该首先把该连续性属性离散化。最简单的方法就是把属性值分成方法就是把属性值分成 和和 两段。如身高可以分两段。如身高可以分为为1 1米以下，米以下，1 1米以上或者分为米以上或者分为1.51.5米以下，米以下，1.51.5米以上。米以上。如何选择最佳的分段值呢？对任何一个属性，其所有的如何选择最佳的分段值呢？对任何一个属性，其所有的取值在一个数据集中是有限的。假设该属性取值为取值在一个数据集中是有限的。假设该属性取值为，则在这个集合中，一共存在，则在这个集合中，一共存在m-1m-1个分段值，个分段值，ID3ID3算法采算法采用计算信息量的方法计算最佳的分段值，然后进一步构用计算信息量的方法

36、计算最佳的分段值，然后进一步构建决策树。建决策树。ID3ID3算法的扩展是算法的扩展是C4.5算法，算法，C4.5算法把分类范围算法把分类范围从分类属性扩展到数字属性。从分类属性扩展到数字属性。NAiNAimvvv,212023-5-23371.C4.51.C4.5算法概述算法概述C4.5C4.5算法是算法是ID3ID3算法的扩展，它的改进部分是：算法的扩展，它的改进部分是：q 能够处理连续型的属性。首先将连续型属性离散化，能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个把连续型属性的值分成不同的区间，依据是比较各个属性属性GianGian值的大小。

37、值的大小。q 缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据的考虑：在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记缺失数据，即在计算增益时，仅考虑具有属性值的记录。录。q 提供两种基本的剪枝策略：提供两种基本的剪枝策略：子树替代法：用叶结点替代子树。子树替代法：用叶结点替代子树。子树上升法：用一棵子树中最常用的子树来代替这棵子树上升法：用一棵子树中最常用的子树来代替这棵子树。子树。5.5 5.5 分类规则挖掘的分类规则挖掘的C4.5 C4.5 算法算法剪枝目的是降低由于训练集存在噪声而产生的起伏。剪枝目的是降低由于训练集存在噪声而产生的起伏。2023-5-

38、23382.2.离散化离散化 的方法的方法把连续型属性值把连续型属性值 离散化离散化 的具体方法是：的具体方法是：1 1）寻找该连续型属性的最小值，并把它赋值给寻找该连续型属性的最小值，并把它赋值给MINMIN，寻找该连续型属性的最大值，并把它赋值给寻找该连续型属性的最大值，并把它赋值给MAXMAX；2 2）设置区间设置区间 MINMIN，MAX MAX 中的中的N N个等分断点个等分断点AiAi，它们分别，它们分别是是 Ai=MIN+（MAX MIN）/N）*i其中，其中，i=1,2,.,N3）分别计算把分别计算把MIN，Ai和（和（Ai，MAX）（）（i=1,2,.,N）作为区间值时的）作

39、为区间值时的Gain值，并进行比较。值，并进行比较。4）选取）选取Gain值最大的值最大的Ak做为该连续型属性的断点，把属性做为该连续型属性的断点，把属性值设置为值设置为MIN，Ak和（和（Ak，MAX）两个区间值。）两个区间值。2023-5-2339对于前面例子中的数据库对于前面例子中的数据库T T，分析属性，分析属性2 2分区的可能结分区的可能结果，分类后得出属性果，分类后得出属性2 2的值的集合是：的值的集合是：65,70,75,78,80,85,90,95,9665,70,75,78,80,85,90,95,96按照按照C4.5C4.5算法，选择每个区间的最小值作为阈值，即：算法，选择

40、每个区间的最小值作为阈值，即：65,70,75,78,80,85,90,95共共8个值，从中选取最优的阈个值，从中选取最优的阈值。值。按照前述方法选取两区间，并分别计算其按照前述方法选取两区间，并分别计算其Gain值：值：6570757880859095如以第二种分段为例计算，计算其如以第二种分段为例计算，计算其Gain值：值：2023-5-2340属性属性2化简后的平面数据库化简后的平面数据库数据库T：属性1属性2属性3属性4A1真类1A2真类2A2假类2A2假类2A1假类1B2真类1B2假类1B1真类1B2假类1C2真类2C1真类2C2假类1C2假类1C2假类12023-5-2341Inf

41、o x2(T)4/14（-3/4 log2(3/4)-1/4 log2(1/4)）+10/14（-6/10 log2(6/10)-4/10 log2(4/10)）=比特Gain(x2)=0.940 Info x2(T)=比特比特2023-5-2342找到最优的阈值（具有最高信息增益）找到最优的阈值（具有最高信息增益）Z=80Z=80相应的检验相应的检验3 3（属性（属性2=80280)280)的信息增益计算的信息增益计算为：为：Info x3(T)9/14（-7/9 log2(7/97/9)-2/9 log2(2/92/9)）+5/14（-2/5 log2(2/52/5)-3/5 log2(3

42、/5/5)）=0.837比特通过检验通过检验x x3 3获得的增益是：获得的增益是：Gain(Gain(x x3 3)=0.940 0.837=0.103)=0.940 0.837=0.103比特比特比较本例中比较本例中3个属性的信息增益，可以看出属性个属性的信息增益，可以看出属性1具有具有最高增益，选择该属性对决策树的结构进行首次分区。最高增益，选择该属性对决策树的结构进行首次分区。2023-5-2343T1检验检验X1:属性属性1=？属性2属性3类70真类190真类285假类295假类270假类1属性2属性3类90真类178假类165真类175假类1属性2属性3类80真类270真类280假

43、类180假类196假类1T2T3ABC叶结点叶结点2023-5-2344对于剩下的子结点对于剩下的子结点T T1 1、T T3 3进行分析：进行分析：对对T T1 1的属性进行检验：最优检验（具有最高的信息增益）的属性进行检验：最优检验（具有最高的信息增益）有两个选择：属性有两个选择：属性2=70270270，定义为，定义为x x4 4。Info(T T1 1)-2/14 log2(2/52/5)-3/14 log2(3/53/5)=0.940比特用属性2把T T1 1分成两个子集（检验分成两个子集（检验x x4 4），结果信息是：），结果信息是：Info x4(T)2/5（-2/2 log2

44、(2/22/2)-0/2 log2(0/20/2)）+3/5（-0/3 log2(0/30/3)-3/3 log2(3/3/3)）=0比特该检验的信息增益最大：该检验的信息增益最大：Gain(Gain(x x4 4)=0.940 0=0.940)=0.940 0=0.940比特比特这两个分枝将生成最终叶结点。这两个分枝将生成最终叶结点。2023-5-2345对于剩下的子结点对于剩下的子结点T T3 3进行分析：进行分析：对对T T3 3的属性进行检验：选择的最优检验为的属性进行检验：选择的最优检验为x x5 5对属性对属性3 3的的值进行检验，树的分枝是属性值进行检验，树的分枝是属性3=3=真

45、和属性真和属性3=3=假。假。最终决策树为：最终决策树为：X1:属性1X4:属性2X5:属性3类1类2类1类2类1检验结点ABC70真假叶结点叶结点2023-5-2346决策树可以用伪代码的形式表示，这种伪代码用决策树可以用伪代码的形式表示，这种伪代码用IF-IF-THENTHEN结构对决策树进行分枝。结构对决策树进行分枝。If 属性属性1=Athen if 属性属性2=70then 类别类别=类类1;else 类别类别=类类2;Else if 属性属性1=B then类别类别=类类1;else if 属性属性1=C thenif 属性属性3=真真 then类别类别=类类2;else类别类别=

46、类类1.2023-5-2347增益标准对紧凑型决策树的构造有很好的效果，但也增益标准对紧凑型决策树的构造有很好的效果，但也存在一个严重缺陷：存在一个严重缺陷：q对具有多输出的检验有严重的偏差。对具有多输出的检验有严重的偏差。q解决方法：根据解决方法：根据info(S)info(S)的定义，指定一个附加的参数：的定义，指定一个附加的参数：n nSplit_Info(X)i=1 (|T|Ti i|/|T|).log2(|T|Ti i|/|T|)含义：含义：q通过把集通过把集T T分区成分区成n n个子集个子集T Ti i而生成的潜在信息。而生成的潜在信息。新的增益标准新的增益标准-增益率：增益率：

47、Gain_ratio(X)=Gain(X)/Split_Info(X)Gain_ratio(X)=Gain(X)/Split_Info(X)新的增益标准表示分区所生成的有用信息的比例新的增益标准表示分区所生成的有用信息的比例2023-5-2348根据前面实例，求检验根据前面实例，求检验X X1 1的增益比例。的增益比例。q计算计算Split_Info(XSplit_Info(X1 1)Split_Info(X X1 1)-5/14 log2(5/145/14)-4/14 log2(4/144/14)-5/14 log2(5/145/14)=1.577比特q计算计算Gain_ratio(XGai

48、n_ratio(X1 1)Gain_ratio(XGain_ratio(X1 1)=0.246/1.577=0.156)=0.246/1.577=0.156q检验过程，将采用最大增益率代替增益标准值检验过程，将采用最大增益率代替增益标准值2023-5-2349在实际应用过程中，大量的现实世界中的数据都不在实际应用过程中，大量的现实世界中的数据都不是以人的意愿来定的，可能某些字段上缺值（是以人的意愿来定的，可能某些字段上缺值（missing values）；可能数据不准确含有噪声或者是错误的；可）；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。能是缺少必须的数据造成

49、了数据的不完整。解决丢失值问题有两种选择：解决丢失值问题有两种选择：q抛弃数据库中有丢失数据的样本。抛弃数据库中有丢失数据的样本。q定义一个新的算法或改进现有的算法来处理。定义一个新的算法或改进现有的算法来处理。3.3.未知属性值问题未知属性值问题如存在大量丢失数据如存在大量丢失数据?2023-5-2350按照第二种选择，必须回答几个问题：按照第二种选择，必须回答几个问题：q怎样比较具有不同数目未知值的两个样本？怎样比较具有不同数目未知值的两个样本？q具有未知值的训练样本和检验的具体值之间没有联具有未知值的训练样本和检验的具体值之间没有联系，它们不能被分配给任何子集，该如何处理这些系，它们不能

50、被分配给任何子集，该如何处理这些样本？样本？q在分类的检验阶段，如果检验有丢失值的属性时，在分类的检验阶段，如果检验有丢失值的属性时，该怎样处理丢失值？该怎样处理丢失值？通过一些方法补充数据？通过一些方法补充数据？2023-5-2351新的增益标准：新的增益标准：Gain(X)=FGain(X)=F*(info(T)info(info(T)infox x(T(T)通过把具有未知值的样本看作分区的一个附通过把具有未知值的样本看作分区的一个附加组来修改加组来修改Split_Info(X X)。如果检验如果检验x有有n个输出，个输出，Split_Info(X X)按照检验把数按照检验把数据集分区成据