决策树分类器教学课件

1、2022/8/3Guilin1决策树分类器朱晓峰2022/8/3Guilin2数据库知识发现技术数据预处理：属性约简，缺失值填充关联规则分类或预测聚类可视化分析2022/8/3Guilin3什么叫分类？分类是一个古老的方法、现代热门的课题已知数据的集合D：数据被标记学习：从数据集合中归纳出规则、规律等，通常称为分类器，或模型预测：用分类器预测新数据的类这种从有标记的数据种归纳分类器的方法叫监督学习决策树、回归是最常用的分类器分类任务图例分类任务例子Predicting tumor cells as benign or malignantClassifying credit card trans

2、actions as legitimate or fraudulentClassifying secondary structures of protein as alpha-helix, beta-sheet, or random coilCategorizing news stories as finance, weather, entertainment, sports, etc分类技术Decision Tree based MethodsRule-based MethodsMemory based reasoningNeural NetworksNave Bayes and Bayes

3、ian Belief NetworksSupport Vector Machines2022/8/3Guilin7决策树分类器/模型学习将已知数据集合分成训练数据集合测试集合学习：从一个训练数据集合归纳出一棵决策树：从完全空间搜索一棵最佳树的过程预测：用决策树分类新数据决策树是最常用的分类器之一不要求任何知识或参数设定它是一种监督学习方法一棵决策树可以表示成一组规则2022/8/3Guilin8决策树的结构决策树是层次的树结构由一些节点和枝（边）组成，一棵决策树至少有一个节点枝的两端是节点一棵决策树通常是从左到右，或从上到下画图树的第一个节点称为根节点，“根-枝-节点-.节点”的最后一个节点是

4、叶节点，其它节点叫中间节点非叶节点至少有一条枝2022/8/3Guilin9决策树分类器的解释一棵决策树是训练数据的一个划分树的一个非叶节点是对一个属性上的测试一个属性的一条枝是测试该属性的一个结果一个叶节点是一个类标记在每个非叶节点，一个属性被选中，它将训练数据分裂成尽可能不同类的子集合（划分）对于一个新数据，根据它的每个属性值从根节点一直匹配到叶节点，这个叶节点的标记就用来预测新数据的类2022/8/3Guilin10构造决策树分类器的原则目标：最大化预测新数据的精度（实现困难）通常将给定的已知数据随机分成训练集合和测试集合。训练数据用于归纳分类器，测试数据用来评估分类器训练分类器时的目标

5、是最大化预测测试数据的精度，即，该分类器基本上体现两个（训练和测试）集合的共同结构过度拟合（overfitting）问题：拟合训练数据的效果很好，拟合测试数据的效果很差2022/8/3Guilin11举例说明（训练数据）2022/8/3Guilin12举例说明（决策树）2022/8/3Guilin13举例说明（测试数据）决策树是用于预测一个数据的类问题：Alex, Buddy and Cheery使用哪种交通工具？2022/8/3Guilin14举例说明（决策树的运用）从根节点Travel cost per km开始如果Travel Cost = expensive，Transportatio

6、n mode = car如果Travel Cost = standard，Transportation mode = train如果Travel Cost = cheap，决策树需要检查下一个节点Gender如果Gender = male，Transportation mode = bus如果Gender = female，决策树需要检查下一个节点Car ownership如果Car ownership = 0，Transportation mode = bus，否则Transportation mode = train 2022/8/3Guilin15举例说明（决策树）2022/8/3Gui

7、lin16举例说明（决策树产生的规则）每个叶节点产生一条规则Rule 1：If Travel cost = expensive then Mode = car Rule 2：If Travel cost = standard then Mode = train Rule 3：If Travel cost = cheap Gender = male then Mode = bus Rule 4：If Travel cost = cheap Gender = female Car ownership = 0 then Mode = bus Rule 5：If Travel cost = cheap

8、 Gender = female Car ownership = 1 then Mode = train2022/8/3Guilin17举例说明（预测）根据上面的决策树或者规则，回答前面的问题就很简单、直接Alex：Travel cost = standard，所以，无论其它属性取什么值，可以预测他的交通工具是trainBuddy：Travel cost = cheap并且Gender = male，则可以预测他的交通工具是bus Cherry：Travel cost = cheap并且Gender = female 并且Car ownership = 1，则可以预测他的交通工具是train2

9、022/8/3Guilin18决策树的缺点多数决策树算法采用贪心策略：按照设定的启发式信息搜索最佳树无回溯非穷近搜索，但可能剪枝2022/8/3Guilin19如何建构决策树？决策树很简单，但实现建构一棵好的树是很困难的在上面的例子中，属性Income level没有用于交通工具的分类建构一棵树通常的办法（启发式信息）是度量数据集的不纯度（impurity）EntropyGini indexClassification error 2022/8/3Guilin20不纯度的定义给定一个训练数据集（决策表），我们能根据类属性度量它的同构性（或异构性heterogeneity）如果一个训练数据集的类

10、属性只取一个类值，它是纯的或者同构的如果一个训练数据集的类属性取多个类值，它是不纯的或者异构的2022/8/3Guilin21如何度量不纯度有多种量化方法度量不纯度最常用的三种方法如下 上面所有的度量方法都含有类j的概率pj2022/8/3Guilin22举例说明（训练数据）2022/8/3Guilin23举例说明（类的频率）在训练数据集合中，类属性Transportation mode有三个类值Bus、Car和Train我们的例子中，每个值出现的次数如下 4 buses3 cars 3 trains 简单记为4B, 3C, 3T总数据量是10个标记的例子 2022/8/3Guilin24举例

11、说明（计算概率）根据上面的数据，每个类的概率如下：p(Bus) = 4 / 10 = 0.4 p(Car) = 3 / 10 = 0.3 p(Train) = 3 / 10 = 0.3注意，在上面的概率计算中，我们只考虑了类属性Transportation mode，其它属性都不考虑有了每个类的概率，我们就可以用前面的方法计算训练数据集合的不纯度2022/8/3Guilin25举例说明（用熵计算概率） 计算训练数据集合的不纯度的一个方法就是采用熵（entropy）已知p(Bus) = 0.4, p(Car) = 0.3和p(Train) = 0.3，熵的计算如下：Entropy = 0.4 l

12、og (0.4) 0.3 log (0.3) 0.3 log (0.3) = 1.571 对数的底是22022/8/3Guilin26熵的性质一个纯的训练数据集合（只有一个类）的熵是0，这是因为概率1的对数log (1) = 0在多个类的情况下，熵在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的熵的最大值，这里，p=1/n熵的最大值是-n*p*log p注意：当类个数n2时，熵12022/8/3Guilin27图示熵的性质2022/8/3Guilin28举例说明（用Gini索引计算概率）计算训练数据集合的不纯度的第二个方法是采用Gini索引（Gini index） 已知p(Bus)

13、 = 0.4, p(Car) = 0.3和p(Train) = 0.3， Gini索引值的计算如下：Gini Index = 1 (0.42 + 0.32 + 0.32) = 0.660 2022/8/3Guilin29Gini索引的性质一个纯的训练数据集合（只有一个类）的Gini索引值是0，这是因为概率1的Gini索引值是1-(1)2 = 0与熵一样， Gini索引在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的Gini索引的最大值，这里，p=1/n注意：无论有多少个类值，Gini索引值总是在0和1之间2022/8/3Guilin30图示Gini索引的性质2022/8/3Guil

14、in31举例说明（用分类误差计算概率）计算训练数据集合的不纯度的第三个方法是采用分类误差（classification error）已知p(Bus) = 0.4, p(Car) = 0.3和p(Train) = 0.3，分类误差值的计算如下：Classification_Error = 1 Max0.4, 0.3, 0.3 = 1 - 0.4 = 0.60 2022/8/3Guilin32分类误差的性质与熵和Gini索引一样，一个纯的训练数据集合（只有一个类）的分类误差值是0，这是因为概率1的分类误差值是1-max(1) = 0分类误差值总是在0和1之间对于给定类的个数， Gini索引的最大值

15、总是与分类误差的最大值相等设每个类的概率为p=1/n，Gini索引的最大值是1-n*(1/n)2 = 1-1/n，而分类误差的最大值也是1-max1/n =1-1/n 2022/8/3Guilin33决策树算法的运行方式这里解释决策树算法的运行方式设一个训练数据集合D有多个属性和一个类属性对于D，取出每个属性和类属性形成一个子集合如果有m个属性，我们就从D构造出m个子集合 设第i个属性的子集合为Si 这里，D 是Si的父亲2022/8/3Guilin34举例说明（训练数据）2022/8/3Guilin35举例说明（训练数据的子集合）S1 S2 S3 S42022/8/3Guilin36取多值的

16、属性对于属性i的 Si表（子集合），我们需要分别计算每个属性i的不纯度 例如，属性Travel cost有三个值：Cheap, Standard和Expensive 它应该分成三个表（子集合）2022/8/3Guilin37属性Travel cost与三个表Travel Costs: Cheap Standard Expensive 2022/8/3Guilin38信息增益（information gain） 选择分裂数据集D的属性，需要比较D和各个子集合Si之间的不纯度差异数据集D和子集合Si的不纯度之差异被称为信息增益（information gain）所以，需要计算每个属性的信息增益值2

17、022/8/3Guilin39信息增益计算方法一个属性的信息增益是它产生的子集合的父集合的不纯度与该子集合的不纯度之差该子集合的不纯度是它分解的表的不纯度的加权之和，权值一般是每个表所占的比例对于熵方法，属性i的信息增益计算如下Information gain(i) = i的父集合的熵 (ki/n * Si产生的表ki的熵) 2022/8/3Guilin40属性Travel Cost的信息增益对于训练数据集D，我们有三个类4B、3C、3T，D的熵是1.571对于属性Travel Cost，它产生的子集合可以分成如下三个表 值Cheap有两个类4B, 1T，它的熵是0.722值Standard有

18、一个类2T，它的熵是0值Expensive有一个类，它的熵是0属性Travel Cost的信息增益是1.571 (5/10 * 0.722+2/10*0+3/10*0) = 1.210 2022/8/3Guilin41属性Travel Cost按三种方法计算的信息增益同样，我们也可以用Gini索引和分类误差计算属性Travel Cost的信息增益采用三种方法计算出属性Travel Cost的信息增益如下Entropy: 1.210Gini Index: 0.500Classification Error: 0.500 2022/8/3Guilin42属性Gender按三种方法计算的信息增益采用

19、三种方法计算出属性Gender的信息增益如下Entropy: 0.125Gini Index: 0.060Classification Error: 0.100 2022/8/3Guilin43属性Car Ownership按三种方法计算的信息增益采用三种方法计算出属性Car Ownership的信息增益如下Entropy:0.534Gini Index:0.207Classification Error:0.200 2022/8/3Guilin44属性Income Level按三种方法计算的信息增益采用三种方法计算出属性Income Level的信息增益如下Entropy:0.695Gini

20、 Index:0.293Classification Error:0.300 2022/8/3Guilin45分裂属性选择的标准在决策树构建中，哪个属性是目前最好的？产生最小树的属性启发式: 选择产生最纯的属性常用的度量：信息增益策略：选择信息增益最大的属性为分裂数据集合的属性2022/8/3Guilin46选择第一个分裂属性有了所有属性的信息增益后，我们就可以找出信息增益最大的那个属性：i* = argmax information gain of attribute i在我们的例子中，属性Travel Cost产生的信息增益最大该属性作为决策树的当前节点因为它是第一个节点，它就是决策树的根

21、节点一棵决策树可以只有一个节点 2022/8/3Guilin47用属性Travel Cost分裂训练数据集 一个分裂属性选定后，我们可以根据该属性将当前的数据集合分裂成多个子集合在我们的例子中，我们根据Travel Cost的取值分列D训练数据集合D被分裂成三个子集合2022/8/3Guilin48用属性Travel Cost分裂训练数据集的结果数据被分裂后，我们有 Travel Cost = Expensive只有一个类CarTravel Cost = Standard只有一个类TrainTravel Cost = Cheap需要进一步分裂产生纯类（只含一个类）的属性值总是作为决策树的叶节点

22、这样就完成了决策树构造的第一个循环 2022/8/3Guilin49训练数据集的三个子集合2022/8/3Guilin50用属性Travel Cost产生的树2022/8/3Guilin51第二次循环属性值Expensive和Standard是纯类，不再需要分裂当Travel Cost = Cheap，它有多个类，需要继续分裂将相应的表中的数据作为待分裂的数据，开始第二次循环 2022/8/3Guilin52为第二次循环产生数据集合2022/8/3Guilin53Cheap连接的节点的数据集合的不纯度现在只有三个属性 Gender、car ownership、Income levelCheap

23、连接的节点的数据集合的不纯度如下2022/8/3Guilin54属性Gender按三种方法计算的信息增益采用三种方法计算出属性Gender的信息增益如下Entropy:0.322Gini Index:0.120Classification Error:0.0002022/8/3Guilin55其它属性按三种方法计算的信息增益采用三种方法计算出属性Car Ownership的信息增益如下Entropy:0.171Gini Index:0.053Classification Error:0.000采用三种方法计算出属性Income Level的信息增益如下Entropy:0.171Gini Ind

24、ex:0.053Classification Error:0.0002022/8/3Guilin56为第二次循环选择分裂属性通过比较属性Gender的信息增益最大当前的数据集合将按照属性Gender的取值分裂在我们的例子中，属性值Male 只有一个类Bus，属性值Female有多个类，需要继续分裂 2022/8/3Guilin57第二次循环的数据集合分裂2022/8/3Guilin58第二次循环产生的树2022/8/3Guilin59用属性Gender分裂子数据集的结果节点Gender有两个值 MaleFemale属性值Male是纯的类，是叶节点属性值Female有多个类，需要在下一个循环继续

25、分裂2022/8/3Guilin60第三次循环第三次循环的数据是第二次循环留待分的数据集合属性值Female的数据剩下可以考虑的属性只有两个 Car ownership Income level 2022/8/3Guilin61为第三次循环产生数据集合2022/8/3Guilin62Female连接的节点的数据集合的不纯度只有两个记录两个记录有不同的类如果选用属性car ownership作为分裂属性，我们将得到两个纯类的子集合同样，如果选用属性income level作为分裂属性，我们也将得到两个纯类的子集合所以，任意选一个即可，不需要计算信息增益值假设我们选用属性car ownership

26、，我们得到一颗决策树，循环结束 2022/8/3Guilin63建立的决策树2022/8/3Guilin64评估技术Holdout: 训练集合/测试集合 数据集合很大时较好k-fold交叉验证: 将数据集合分成k子集合在每次建树时，使用一个子集合作为测试集合，其它k-1子集合一起作为训练集合 用这k次结果的均值作为参照它消除了训练集合/测试集合方法的随机性2022/8/3Guilin6565 交叉验证图解数据集合分成k段 一个做测试，其它的用来训练分类器 重复到Testiteration2022/8/3Guilin66增益率增益率（Gain ratio）：是信息增益的一个改良版，它可以减少信息

27、增益偏好于取值较多的属性增益率考虑分支数目和分枝的大小它通过内在信息改良信息增益值也称为分裂率内在信息：分支里的记录分布的熵2022/8/3Guilin67增益率的定义增益率一般是数据均匀分布时很大数据集中于某个枝时很小增益率（Quinlan86)）标准化信息增益2022/8/3Guilin68有关决策树分类器的研究问题分裂属性选择标准过度拟合（Overfitting）低度拟合（Underfitting）评估技术非均匀数据/类（Imbalanced data/classes）多标记学习半监督分类2022/8/3Guilin69Summary决策树的定义决策树的使用如何建树分裂属性选择不纯度信息

28、增益评估技术相关的研究问题2022/8/3Guilin70参考目录D. LU and Q. WENG，（2007），A survey of image classification methods and techniques for improving classification performance，International Journal of Remote Sensing，Vol. 28, No. 5, 10 March 2007, 823870。F. Zeng and Z. Qiu (2004) A survey of classification learning algor

29、ithm, ICSP 04. Thair Nu Phyu （2009）Survey of Classification Techniques in Data Mining，IMECS 2009, C. Aggarwal and C. Zhai （2012） A Survey of Text Classification Algorithms，Mining Text Data，2012, pp 163-222Zhengzheng Xing, Jian Pei, Eamonn J. Keogh: A brief survey on sequence classification. SIGKDD Explorations 12(1): 40-48 (2010)Shehroz S. Khan,