dtree决策树.ppt

2019 12 27 Guilin 1 决策树分类器 朱晓峰seanzhuxf 2019 12 27 Guilin 2 数据库知识发现技术 数据预处理 属性约简 缺失值填充 关联规则分类或预测聚类可视化分析 2019 12 27 Guilin 3 什么叫分类 分类是一个古老的方法 现代热门的课题已知数据的集合D 数据被标记学习 从数据集合中归纳出规则 规律等 通常称为分类器 或模型预测 用分类器预测新数据的类这种从有标记的数据种归纳分类器的方法叫监督学习决策树 回归是最常用的分类器 分类任务图例 分类任务例子 PredictingtumorcellsasbenignormalignantClassifyingcreditcardtransactionsaslegitimateorfraudulentClassifyingsecondarystructuresofproteinasalpha helix beta sheet orrandomcoilCategorizingnewsstoriesasfinance weather entertainment sports etc 分类技术 DecisionTreebasedMethodsRule basedMethodsMemorybasedreasoningNeuralNetworksNa veBayesandBayesianBeliefNetworksSupportVectorMachines 2019 12 27 Guilin 7 决策树分类器 模型学习 将已知数据集合分成训练数据集合测试集合学习 从一个训练数据集合归纳出一棵决策树 从完全空间搜索一棵最佳树的过程预测 用决策树分类新数据决策树是最常用的分类器之一不要求任何知识或参数设定它是一种监督学习方法一棵决策树可以表示成一组规则 2019 12 27 Guilin 8 决策树的结构 决策树是层次的树结构由一些节点和枝 边 组成 一棵决策树至少有一个节点枝的两端是节点一棵决策树通常是从左到右 或从上到下画图树的第一个节点称为根节点 根 枝 节点 节点 的最后一个节点是叶节点 其它节点叫中间节点非叶节点至少有一条枝 2019 12 27 Guilin 9 决策树分类器的解释 一棵决策树是训练数据的一个划分树的一个非叶节点是对一个属性上的测试一个属性的一条枝是测试该属性的一个结果一个叶节点是一个类标记在每个非叶节点 一个属性被选中 它将训练数据分裂成尽可能不同类的子集合 划分 对于一个新数据 根据它的每个属性值从根节点一直匹配到叶节点 这个叶节点的标记就用来预测新数据的类 2019 12 27 Guilin 10 构造决策树分类器的原则 目标 最大化预测新数据的精度 实现困难 通常将给定的已知数据随机分成训练集合和测试集合 训练数据用于归纳分类器 测试数据用来评估分类器训练分类器时的目标是最大化预测测试数据的精度 即 该分类器基本上体现两个 训练和测试 集合的共同结构过度拟合 overfitting 问题 拟合训练数据的效果很好 拟合测试数据的效果很差 2019 12 27 Guilin 11 举例说明 训练数据 2019 12 27 Guilin 12 举例说明 决策树 2019 12 27 Guilin 13 举例说明 测试数据 决策树是用于预测一个数据的类问题 Alex BuddyandCheery使用哪种交通工具 2019 12 27 Guilin 14 举例说明 决策树的运用 从根节点Travelcostperkm开始如果TravelCost expensive Transportationmode car如果TravelCost standard Transportationmode train如果TravelCost cheap 决策树需要检查下一个节点Gender如果Gender male Transportationmode bus如果Gender female 决策树需要检查下一个节点Carownership如果Carownership 0 Transportationmode bus 否则Transportationmode train 2019 12 27 Guilin 15 举例说明 决策树 2019 12 27 Guilin 16 举例说明 决策树产生的规则 每个叶节点产生一条规则Rule1 IfTravelcost expensivethenMode carRule2 IfTravelcost standardthenMode trainRule3 IfTravelcost cheap Gender malethenMode busRule4 IfTravelcost cheap Gender female Carownership 0thenMode busRule5 IfTravelcost cheap Gender female Carownership 1thenMode train 2019 12 27 Guilin 17 举例说明 预测 根据上面的决策树或者规则 回答前面的问题就很简单 直接Alex Travelcost standard 所以 无论其它属性取什么值 可以预测他的交通工具是trainBuddy Travelcost cheap并且Gender male 则可以预测他的交通工具是busCherry Travelcost cheap并且Gender female并且Carownership 1 则可以预测他的交通工具是train 2019 12 27 Guilin 18 决策树的缺点 多数决策树算法采用贪心策略 按照设定的启发式信息搜索最佳树无回溯非穷近搜索 但可能剪枝 2019 12 27 Guilin 19 如何建构决策树 决策树很简单 但实现建构一棵好的树是很困难的在上面的例子中 属性Incomelevel没有用于交通工具的分类建构一棵树通常的办法 启发式信息 是度量数据集的不纯度 impurity EntropyGiniindexClassificationerror 2019 12 27 Guilin 20 不纯度的定义 给定一个训练数据集 决策表 我们能根据类属性度量它的同构性 或异构性heterogeneity 如果一个训练数据集的类属性只取一个类值 它是纯的或者同构的如果一个训练数据集的类属性取多个类值 它是不纯的或者异构的 2019 12 27 Guilin 21 如何度量不纯度 有多种量化方法度量不纯度最常用的三种方法如下上面所有的度量方法都含有类j的概率pj 2019 12 27 Guilin 22 举例说明 训练数据 2019 12 27 Guilin 23 举例说明 类的频率 在训练数据集合中 类属性Transportationmode有三个类值Bus Car和Train我们的例子中 每个值出现的次数如下4buses3cars3trains简单记为4B 3C 3T总数据量是10个标记的例子 2019 12 27 Guilin 24 举例说明 计算概率 根据上面的数据 每个类的概率如下 p Bus 4 10 0 4p Car 3 10 0 3p Train 3 10 0 3注意 在上面的概率计算中 我们只考虑了类属性Transportationmode 其它属性都不考虑有了每个类的概率 我们就可以用前面的方法计算训练数据集合的不纯度 2019 12 27 Guilin 25 举例说明 用熵计算概率 计算训练数据集合的不纯度的一个方法就是采用熵 entropy 已知p Bus 0 4 p Car 0 3和p Train 0 3 熵的计算如下 Entropy 0 4log 0 4 0 3log 0 3 0 3log 0 3 1 571对数的底是2 2019 12 27 Guilin 26 熵的性质 一个纯的训练数据集合 只有一个类 的熵是0 这是因为概率1的对数log 1 0在多个类的情况下 熵在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的熵的最大值 这里 p 1 n熵的最大值是 n p logp注意 当类个数n 2时 熵 1 2019 12 27 Guilin 27 图示熵的性质 2019 12 27 Guilin 28 举例说明 用Gini索引计算概率 计算训练数据集合的不纯度的第二个方法是采用Gini索引 Giniindex 已知p Bus 0 4 p Car 0 3和p Train 0 3 Gini索引值的计算如下 GiniIndex 1 0 4 2 0 3 2 0 3 2 0 660 2019 12 27 Guilin 29 Gini索引的性质 一个纯的训练数据集合 只有一个类 的Gini索引值是0 这是因为概率1的Gini索引值是1 1 2 0与熵一样 Gini索引在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的Gini索引的最大值 这里 p 1 n注意 无论有多少个类值 Gini索引值总是在0和1之间 2019 12 27 Guilin 30 图示Gini索引的性质 2019 12 27 Guilin 31 举例说明 用分类误差计算概率 计算训练数据集合的不纯度的第三个方法是采用分类误差 classificationerror 已知p Bus 0 4 p Car 0 3和p Train 0 3 分类误差值的计算如下 Classification Error 1 Max 0 4 0 3 0 3 1 0 4 0 60 2019 12 27 Guilin 32 分类误差的性质 与熵和Gini索引一样 一个纯的训练数据集合 只有一个类 的分类误差值是0 这是因为概率1的分类误差值是1 max 1 0分类误差值总是在0和1之间对于给定类的个数 Gini索引的最大值总是与分类误差的最大值相等设每个类的概率为p 1 n Gini索引的最大值是1 n 1 n 2 1 1 n 而分类误差的最大值也是1 max 1 n 1 1 n 2019 12 27 Guilin 33 决策树算法的运行方式 这里解释决策树算法的运行方式设一个训练数据集合D有多个属性和一个类属性对于D 取出每个属性和类属性形成一个子集合如果有m个属性 我们就从D构造出m个子集合设第i个属性的子集合为Si这里 D是Si的父亲 2019 12 27 Guilin 34 举例说明 训练数据 2019 12 27 Guilin 35 举例说明 训练数据的子集合 S1S2S3S4 2019 12 27 Guilin 36 取多值的属性 对于属性i的Si表 子集合 我们需要分别计算每个属性i的不纯度例如 属性Travelcost有三个值 Cheap Standard和Expensive它应该分成三个表 子集合 2019 12 27 Guilin 37 属性Travelcost与三个表 TravelCosts CheapStandardExpensive 2019 12 27 Guilin 38 信息增益 informationgain 选择分裂数据集D的属性 需要比较D和各个子集合Si之间的不纯度差异数据集D和子集合Si的不纯度之差异被称为信息增益 informationgain 所以 需要计算每个属性的信息增益值 2019 12 27 Guilin 39 信息增益计算方法 一个属性的信息增益是它产生的子集合的父集合的不纯度与该子集合的不纯度之差该子集合的不纯度是它分解的表的不纯度的加权之和 权值一般是每个表所占的比例对于熵方法 属性i的信息增益计算如下Informationgain i i的父集合的熵 ki n Si产生的表ki的熵 2019 12 27 Guilin 40 属性TravelCost的信息增益 对于训练数据集D 我们有三个类4B 3C 3T D的熵是1 571对于属性TravelCost 它产生的子集合可以分成如下三个表值Cheap有两个类4B 1T 它的熵是0 722值Standard有一个类2T 它的熵是0值Expensive有一个类 它的熵是0属性TravelCost的信息增益是1 571 5 10 0 722 2 10 0 3 10 0 1 210 2019 12 27 Guilin 41 属性TravelCost按三种方法计算的信息增益 同样 我们也可以用Gini索引和分类误差计算属性TravelCost的信息增益采用三种方法计算出属性TravelCost的信息增益如下Entropy 1 210GiniIndex 0 500ClassificationError 0 500 2019 12 27 Guilin 42 属性Gender按三种方法计算的信息增益 采用三种方法计算出属性Gender的信息增益如下Entropy 0 125GiniIndex 0 060ClassificationError 0 100 2019 12 27 Guilin 43 属性CarOwnership按三种方法计算的信息增益 采用三种方法计算出属性CarOwnership的信息增益如下Entropy 0 534GiniIndex 0 207ClassificationError 0 200 2019 12 27 Guilin 44 属性IncomeLevel按三种方法计算的信息增益 采用三种方法计算出属性IncomeLevel的信息增益如下Entropy 0 695GiniIndex 0 293ClassificationError 0 300 2019 12 27 Guilin 45 分裂属性选择的标准 在决策树构建中 哪个属性是目前最好的 产生最小树的属性启发式 选择产生最纯的属性常用的度量 信息增益策略 选择信息增益最大的属性为分裂数据集合的属性 2019 12 27 Guilin 46 选择第一个分裂属性 有了所有属性的信息增益后 我们就可以找出信息增益最大的那个属性 i argmax informationgainofattributei 在我们的例子中 属性TravelCost产生的信息增益最大该属性作为决策树的当前节点因为它是第一个节点 它就是决策树的根节点一棵决策树可以只有一个节点 2019 12 27 Guilin 47 用属性TravelCost分裂训练数据集 一个分裂属性选定后 我们可以根据该属性将当前的数据集合分裂成多个子集合在我们的例子中 我们根据TravelCost的取值分列D训练数据集合D被分裂成三个子集合 2019 12 27 Guilin 48 用属性TravelCost分裂训练数据集的结果 数据被分裂后 我们有TravelCost Expensive只有一个类CarTravelCost Standard只有一个类TrainTravelCost Cheap需要进一步分裂产生纯类 只含一个类 的属性值总是作为决策树的叶节点这样就完成了决策树构造的第一个循环 2019 12 27 Guilin 49 训练数据集的三个子集合 2019 12 27 Guilin 50 用属性TravelCost产生的树 2019 12 27 Guilin 51 第二次循环 属性值Expensive和Standard是纯类 不再需要分裂当TravelCost Cheap 它有多个类 需要继续分裂将相应的表中的数据作为待分裂的数据 开始第二次循环 2019 12 27 Guilin 52 为第二次循环产生数据集合 2019 12 27 Guilin 53 Cheap连接的节点的数据集合的不纯度 现在只有三个属性Gender carownership IncomelevelCheap连接的节点的数据集合的不纯度如下 2019 12 27 Guilin 54 属性Gender按三种方法计算的信息增益 采用三种方法计算出属性Gender的信息增益如下Entropy 0 322GiniIndex 0 120ClassificationError 0 000 2019 12 27 Guilin 55 其它属性按三种方法计算的信息增益 采用三种方法计算出属性CarOwnership的信息增益如下Entropy 0 171GiniIndex 0 053ClassificationError 0 000采用三种方法计算出属性IncomeLevel的信息增益如下Entropy 0 171GiniIndex 0 053ClassificationError 0 000 2019 12 27 Guilin 56 为第二次循环选择分裂属性 通过比较属性Gender的信息增益最大当前的数据集合将按照属性Gender的取值分裂在我们的例子中 属性值Male只有一个类Bus 属性值Female有多个类 需要继续分裂 2019 12 27 Guilin 57 第二次循环的数据集合分裂 2019 12 27 Guilin 58 第二次循环产生的树 2019 12 27 Guilin 59 用属性Gender分裂子数据集的结果 节点Gender有两个值MaleFemale属性值Male是纯的类 是叶节点属性值Female有多个类 需要在下一个循环继续分裂 2019 12 27 Guilin 60 第三次循环 第三次循环的数据是第二次循环留待分的数据集合属性值Female的数据剩下可以考虑的属性只有两个CarownershipIncomelevel 2019 12 27 Guilin 61 为第三次循环产生数据集合 2019 12 27 Guilin 62 Female连接的节点的数据集合的不纯度 只有两个记录两个记录有不同的类如果选用属性carownership作为分裂属性 我们将得到两个纯类的子集合同样 如果选用属性incomelevel作为分裂属性 我们也将得到两个纯类的子集合所以 任意选一个即可 不需要计算信息增益值假设我们选用属性carownership 我们得到一颗决策树 循环结束 2019 12 27 Guilin 63 建立的决策树 2019 12 27 Guilin 64 评估技术 Holdout 训练集合 测试集合数据集合很大时较好k fold交叉验证 将数据集合分成k子集合在每次建树时 使用一个子集合作为测试集合 其它k 1子集合一起作为训练集合用这k次结果的均值作为参照它消除了训练集合 测试集合方法的随机性 2019 12 27 Guilin 65 65 交叉验证图解 数据集合分成k段一个做测试 其它的用来训练分类器重复到 Test iteration 2019 12 27 Guilin 66 增益率 增益率 Gainratio 是信息增益的一个改良版 它可以减少信息增益偏好于取值较多的属性增益率考虑分支数目和分枝的大小它通过内在信息改良信息增益值也称为分裂率内在信息 分支里的记录分布的熵 2019 12 27 Guilin 67 增益率的定义 增益率一般是数据均匀分布时很大数据集中于某个枝时很小增益率 Quinlan 86 标准化信息增益 2019 12 27 Guilin 68 有关决策树分类器的研究问题 分裂属性选择标准过度拟