第5章 数据分类-决策树

2019/8/301数据仓库与数据挖掘技术五邑大学信息学院2009.06何国辉教授2019/8/302第5章决策树和决策规则5.1引例分类的定义分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。2019/8/303AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1………描述属性类别属性分类问题使用的数据集格式：2019/8/3045.1引例分类问题使用的数据集格式描述属性可以是连续型属性，也可以是离散型属性；而类别属性必须是离散型属性。连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的，例如属性“Age”离散型属性是指该属性的取值是不连续的，例如属性“Salary”和“Class”2019/8/3055.1引例分类问题使用的数据集格式分类问题中使用的数据集可以表示为X={(xi,yi)|i=1,2,…,total}xi=(xi1,xi2,…,xid)，其中xi1,xi2,…,xid分别对应d个描述属性A1,A2,…,Ad的具体取值yi表示数据样本xi的类标号，假设给定数据集包含m个类别，则yi∈{c1,c2,…,cm}，其中c1,c2,…,cm是类别属性C的具体取值未知类标号的数据样本x用d维特征向量x=(x1,x2,…,xd)来表示2019/8/3065.2分类问题概述5.2.1分类的过程5.2.2分类的评价准则2019/8/3075.2.1分类的过程获取数据预处理分类器设计分类决策2019/8/3085.2.1分类的过程获取数据输入数据、对数据进行量化预处理去除噪声数据、对空缺值进行处理数据集成或者变换分类器设计划分数据集、分类器构造、分类器测试分类决策对未知类标号的数据样本进行分类2019/8/3095.2.2分类的评价准则给定测试集Xtest={(xi,yi)|i=1,2,…,N}N表示测试集中的样本个数xi表示测试集中的数据样本yi表示数据样本xi的类标号对于测试集的第j个类别，假设被正确分类的样本数量为TPj被错误分类的样本数量为FNj其他类别被错误分类为该类的样本数据量为FPj2019/8/30105.2.2分类的评价准则精确度：代表测试集中被正确分类的数据样本所占的比例NTPAccuracym1jj2019/8/30115.2.2分类的评价准则查全率：表示在本类样本中被正确分类的样本所占的比例查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例mj1,FNTPTPRecalljjjjmj1,FPTPTPPrecisionjjjj2019/8/30125.2.2分类的评价准则F-measure(加权调合平均数)：是查全率和查准率的组合表达式β是可以调节的，通常取值为1mj1,PrecisionRecallPrecisionRecall)1(measureFjj2jj2j2019/8/30135.2.2分类的评价准则几何均值：是各个类别的查全率的平方根m1jjcallRemeanG2019/8/3014决策树方法的起源是亨特（Hunt，1966）的概念学习系统CLS方法，然后发展到由Quinlan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。5.3决策树2019/8/3015决策树的优点：进行分类器设计时，决策树分类方法所需时间相对较少决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式可以将决策树中到达每个叶节点的路径转换为IF—THEN形式的分类规则，这种形式更有利于理解2019/8/30161.什么是决策树决策树（DecisionTree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internalnode）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（classdistribution），最上面的结点是根结点。决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。2019/8/3017〖例〗图5-2给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向。Age?Credit_rating?student?yesnoyesyesno=30?4030…40yesnofairexcellent图5-2buys_computer的决策树2019/8/3018这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：buys_computers=yes或者buys_computers=no在这个例子中，样本向量为：（age,student,credit_rating;buys_computers）被决策数据的格式为:（age,student,credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。2019/8/30192.使用决策树进行分类构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a=b)的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。2019/8/3020使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。2019/8/3021问题的关键是建立一棵决策树。这个过程通常分为两个阶段：建树（TreeBuilding）：决策树建树算法见下，这是一个递归的过程，最终将得到一棵树。剪枝（TreePruning）：剪枝的目的是降低由于训练集存在噪声而产生的起伏。2019/8/3022由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树归纳（InductionofDecisionTree）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。5.4分类规则挖掘的ID3算法2019/8/30231.ID3算法的基本思想由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最好”的决策树是一个NP完全问题。NP完全问题是这样的问题：用确定性的算法在多项式时间内无法解决的问题。实际之中，解决这样的问题，往往是根据用启发式算法，求出近似的解。2019/8/3024ID3使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树—可能不是最简单的。ID3算法的基本思想描述如下：step1．任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；step2．用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结点都有类标记，则算法终止；step3．否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤step2；agestudentcredit_ratingbuys_computers25YESexcellantYES35NOfairYES2019/8/3025这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分支决策树的那个属性。2019/8/3026算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树方法：（1）创建结点N；（2）ifsamples都在同一个类Cthen（3）返回N作为叶结点，用类C标记；（4）ifattribute_list为空then（5）返回N作为叶结点，标记samples中最普通的类；//多数表决（6）选择attribute_list中具有最高信息增益的属性test_attribute；//用信息增益作为属性选择度量（7）标记结点N为test_attribute；（8）foreachtest_attribute中的已知值ai//划分samples（9）由结点N生长出一个条件为test_attribute＝ai的分枝；（10）设si为samples中test_attribute＝ai的样本集合；//一个划分（11）ifsi为空then（12）加上一个叶结点，标记为标记samples中最普通的类；//多数表决（13）else加上一个由Generate_decision_tree（si,attribute_list-test_attribute）返回的结点；2019/8/30272.属性选择度量在Generate_decision_tree算法的Step6，算法需选择attribute_list中具有最高信息增益的属性test_attribute。ID3算法在树的每个结点上以信息增益（informationgain）作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。2019/8/3028InformationGain指标的原理来自于信息论。1948年，香农（C.E.Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。2019/8/3029假设要选择有n个输出（所给属性的n个值）的检验，把训练样本集T分区成子集T1，T2，…，Tn。仅有的指导信息是在T和它的子集Ti中的类的分布。如果S是任意样本集，设freq(Ci,S)代表S中属于类Ci（k个可能的类中的一个）的样本数量，|S|表示集合S中的样本数量。下面给出了集合S（单位为比特）的熵计算：kInfo(S)＝－Σi=1((fre