决策树分类器培训知识

决策树分类器培训知识2023/6/29Guilin2数据库知识发现技术数据预处理：属性约简，缺失值填充…分类或预测聚类可视化分析2023/6/29Guilin3什么叫分类？分类是一个古老的方法、现代热门的课题已知数据的集合D：数据被标记学习：从数据集合中归纳出规则、规律等，通常称为分类器，或模型预测：用分类器预测新数据的类这种从有标记的数据种归纳分类器的方法叫监督学习决策树、回归是最常用的分类器分类任务图例分类任务例子PredictingtumorcellsasbenignormalignantClassifyingcreditcardtransactions

aslegitimateorfraudulentClassifyingsecondarystructuresofprotein

asalpha-helix,beta-sheet,orrandom

coilCategorizingnewsstoriesasfinance,

weather,entertainment,sports,etc分类技术DecisionTreebasedMethodsRule-basedMethodsMemorybasedreasoningNeuralNetworksNaïveBayesandBayesianBeliefNetworksSupportVectorMachines2023/6/29Guilin7决策树分类器/模型学习将已知数据集合分成训练数据集合测试集合学习：从一个训练数据集合归纳出一棵决策树：从完全空间搜索一棵最佳树的过程预测：用决策树分类新数据决策树是最常用的分类器之一不要求任何知识或参数设定它是一种监督学习方法一棵决策树可以表示成一组规则2023/6/29Guilin8决策树的结构决策树是层次的树结构由一些节点和枝（边）组成，一棵决策树至少有一个节点枝的两端是节点一棵决策树通常是从左到右，或从上到下画图树的第一个节点称为根节点，“根-枝-节点-...–节点”的最后一个节点是叶节点，其它节点叫中间节点非叶节点至少有一条枝2023/6/29Guilin9决策树分类器的解释一棵决策树是训练数据的一个划分树的一个非叶节点是对一个属性上的测试一个属性的一条枝是测试该属性的一个结果一个叶节点是一个类标记在每个非叶节点，一个属性被选中，它将训练数据分裂成尽可能不同类的子集合（划分）对于一个新数据，根据它的每个属性值从根节点一直匹配到叶节点，这个叶节点的标记就用来预测新数据的类2023/6/29Guilin10构造决策树分类器的原则目标：最大化预测新数据的精度（实现困难）通常将给定的已知数据随机分成训练集合和测试集合。训练数据用于归纳分类器，测试数据用来评估分类器训练分类器时的目标是最大化预测测试数据的精度，即，该分类器基本上体现两个（训练和测试）集合的共同结构过度拟合（overfitting）问题：拟合训练数据的效果很好，拟合测试数据的效果很差2023/6/29Guilin11举例说明（训练数据）2023/6/29Guilin12举例说明（决策树）2023/6/29Guilin13举例说明（测试数据）决策树是用于预测一个数据的类问题：Alex,BuddyandCheery使用哪种交通工具？2023/6/29Guilin14举例说明（决策树的运用）从根节点Travelcostperkm开始如果TravelCost=expensive，Transportationmode=car如果TravelCost=standard，Transportationmode=train如果TravelCost=cheap，决策树需要检查下一个节点Gender如果Gender=male，Transportationmode=bus如果Gender=female，决策树需要检查下一个节点Carownership如果Carownership=0，Transportationmode=bus，否则Transportationmode=train2023/6/29Guilin15举例说明（决策树）2023/6/29Guilin16举例说明（决策树产生的规则）每个叶节点产生一条规则Rule1：IfTravelcost=expensivethenMode=carRule2：IfTravelcost=standardthenMode=trainRule3：IfTravelcost=cheapGender=malethenMode=busRule4：IfTravelcost=cheapGender=femaleCarownership=0thenMode=busRule5：IfTravelcost=cheapGender=femaleCarownership=1thenMode=train2023/6/29Guilin17举例说明（预测）根据上面的决策树或者规则，回答前面的问题就很简单、直接Alex：Travelcost=standard，所以，无论其它属性取什么值，可以预测他的交通工具是trainBuddy：Travelcost=cheap并且Gender=male，则可以预测他的交通工具是busCherry：Travelcost=cheap并且Gender=female并且Carownership=1，则可以预测他的交通工具是train2023/6/29Guilin18决策树的缺点多数决策树算法采用贪心策略：按照设定的启发式信息搜索最佳树无回溯非穷近搜索，但可能剪枝2023/6/29Guilin19如何建构决策树？决策树很简单，但实现建构一棵好的树是很困难的在上面的例子中，属性Incomelevel没有用于交通工具的分类建构一棵树通常的办法（启发式信息）是度量数据集的不纯度（impurity）EntropyGiniindexClassificationerror2023/6/29Guilin20不纯度的定义给定一个训练数据集（决策表），我们能根据类属性度量它的同构性（或异构性heterogeneity）如果一个训练数据集的类属性只取一个类值，它是纯的或者同构的如果一个训练数据集的类属性取多个类值，它是不纯的或者异构的2023/6/29Guilin21如何度量不纯度有多种量化方法度量不纯度最常用的三种方法如下

上面所有的度量方法都含有类j的概率pj2023/6/29Guilin22举例说明（训练数据）2023/6/29Guilin23举例说明（类的频率）在训练数据集合中，类属性Transportationmode有三个类值Bus、Car和Train我们的例子中，每个值出现的次数如下4buses3cars3trains简单记为4B,3C,3T总数据量是10个标记的例子

2023/6/29Guilin24举例说明（计算概率）根据上面的数据，每个类的概率如下：p(Bus)=4/10=0.4p(Car)=3/10=0.3p(Train)=3/10=0.3注意，在上面的概率计算中，我们只考虑了类属性Transportationmode，其它属性都不考虑有了每个类的概率，我们就可以用前面的方法计算训练数据集合的不纯度2023/6/29Guilin25举例说明（用熵计算概率）

计算训练数据集合的不纯度的一个方法就是采用熵（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对数的底是22023/6/29Guilin26熵的性质一个纯的训练数据集合（只有一个类）的熵是0，这是因为概率1的对数log(1)=0在多个类的情况下，熵在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的熵的最大值，这里，p=1/n熵的最大值是-n*p*logp注意：当类个数n>2时，熵>12023/6/29Guilin27图示熵的性质2023/6/29Guilin28举例说明（用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.6602023/6/29Guilin29Gini索引的性质一个纯的训练数据集合（只有一个类）的Gini索引值是0，这是因为概率1的Gini索引值是1-(1)^2=0与熵一样，Gini索引在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的Gini索引的最大值，这里，p=1/n注意：无论有多少个类值，Gini索引值总是在0和1之间2023/6/29Guilin30图示Gini索引的性质2023/6/29Guilin31举例说明（用分类误差计算概率）计算训练数据集合的不纯度的第三个方法是采用分类误差（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.602023/6/29Guilin32分类误差的性质与熵和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/n2023/6/29Guilin33决策树算法的运行方式这里解释决策树算法的运行方式设一个训练数据集合D有多个属性和一个类属性对于D，取出每个属性和类属性形成一个子集合如果有m个属性，我们就从D构造出m个子集合设第i个属性的子集合为Si

这里，D是Si的父亲2023/6/29Guilin34举例说明（训练数据）2023/6/29Guilin35举例说明（训练数据的子集合）S1S2S3S42023/6/29Guilin36取多值的属性对于属性i的Si表（子集合），我们需要分别计算每个属性i的不纯度例如，属性Travelcost有三个值：Cheap,Standard和Expensive它应该分成三个表（子集合）2023/6/29Guilin37属性Travelcost与三个表TravelCosts:CheapStandardExpensive2023/6/29Guilin38信息增益（informationgain）

选择分裂数据集D的属性，需要比较D和各个子集合Si之间的不纯度差异数据集D和子集合Si的不纯度之差异被称为信息增益（informationgain）所以，需要计算每个属性的信息增益值2023/6/29Guilin39信息增益计算方法一个属性的信息增益是它产生的子集合的父集合的不纯度与该子集合的不纯度之差该子集合的不纯度是它分解的表的不纯度的加权之和，权值一般是每个表所占的比例对于熵方法，属性i的信息增益计算如下Informationgain(i)=i的父集合的熵–(ki/n*

Si产生的表ki的熵)2023/6/29Guilin40属性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.2102023/6/29Guilin41属性TravelCost按三种方法计算的信息增益同样，我们也可以用Gini索引和分类误差计算属性TravelCost的信息增益采用三种方法计算出属性TravelCost的信息增益如下Entropy:1.210GiniIndex:0.500ClassificationError:0.5002023/6/29Guilin42属性Gender按三种方法计算的信息增益采用三种方法计算出属性Gender的信息增益如下Entropy:0.125GiniIndex:0.060ClassificationError:0.1002023/6/29Guilin43属性CarOwnership按三种方法计算的信息增益采用三种方法计算出属性CarOwnership的信息增益如下Entropy: 0.534GiniIndex: 0.207ClassificationError: 0.2002023/6/29Guilin44属性IncomeLevel按三种方法计算的信息增益采用三种方法计算出属性IncomeLevel的信息增益如下Entropy: 0.695GiniIndex: 0.293ClassificationError: 0.3002023/6/29Guilin45分裂属性选择的标准在决策树构建中，哪个属性是目前最好的？产生最小树的属性启发式:选择产生最纯的属性常用的度量：信息增益策略：选择信息增益最大的属性为分裂数据集合的属性2023/6/29Guilin46选择第一个分裂属性有了所有属性的信息增益后，我们就可以找出信息增益最大的那个属性：i*=argmax{informationgainofattributei}在我们的例子中，属性TravelCost产生的信息增益最大该属性作为决策树的当前节点因为它是第一个节点，它就是决策树的根节点一棵决策树可以只有一个节点2023/6/29Guilin47用属性TravelCost分裂训练数据集

一个分裂属性选定后，我们可以根据该属性将当前的数据集合分裂成多个子集合在我们的例子中，我们根据TravelCost的取值分列D训练数据集合D被分裂成三个子集合2023/6/29Guilin48用属性TravelCost分裂训练数据集的结果数据被分裂后，我们有TravelCost=Expensive只有一个类CarTravelCost=Standard只有一个类TrainTravelCost=Cheap需要进一步分裂产生纯类（只含一个类）的属性值总是作为决策树的叶节点这样就完成了决策树构造的第一个循环

2023/6/29Guilin49训练数据集的三个子集合2023/6/29Guilin50用属性TravelCost产生的树2023/6/29Guilin51第二次循环属性值Expensive和Standard是纯类，不再需要分裂当TravelCost=Cheap，它有多个类，需要继续分裂将相应的表中的数据作为待分裂的数据，开始第二次循环2023/6/29Guilin52为第二次循环产生数据集合2023/6/29Guilin53Cheap连接的节点的数据集合的不纯度现在只有三个属性Gender、carownership、IncomelevelCheap连接的节点的数据集合的不纯度如下2023/6/29Guilin54属性Gender按三种方法计算的信息增益采用三种方法计算出属性Gender的信息增益如下Entropy: 0.322GiniIndex: 0.120ClassificationError: 0.0002023/6/29Guilin55其它属性按三种方法计算的信息增益采用三种方法计算出属性CarOwnership的信息增益如下Entropy: 0.171GiniIndex: 0.053ClassificationError: 0.000采用三种方法计算出属性IncomeLevel的信息增益如下Entropy: 0.171GiniIndex: 0.053ClassificationError: 0.0002023/6/29Guilin56为第二次循环选择分裂属性通过比较属性Gender的信息增益最大当前的数据集合将按照属性Gender的取值分裂在我们的例子中，属性值Male

只有一个类Bus，属性值Female有多个类，需要继续分裂2023/6/29Guilin57第二次循环的数据集合分裂2023/6/29Guilin58第二次循环产生的树2023/6/29Guilin59用属性Gender分裂子数据集的结果节点Gender有两个值MaleFemale属性值Male是纯的类，是叶节点属性值Female有多个类，需要在下一个循环继续分裂2023/6/29Guilin60第三次循环第三次循环的数据是第二次循环留待分的数据集合属性值Female的数据剩下可以考虑的属性只有两个CarownershipIncomelevel2023/6/29Guilin61为第三次循环产生数据集合2023/6/29Guilin62Female连接的节点的数据集合的不纯度只有两个记录两个记录有不同的类如果选用属性carownership作为分裂属性，我们将得到两个纯类的子集合同样，如果选用属性incomelevel作为分裂属性，我们也将得到两个纯类的子集合所以，任意选一个即可，不需要计算信息增益值假设我们选用属性carownership，我们得到一颗决策树，循环结束2023/6/29Guilin63建立的决策树2023/6/29Guilin64评估技术Holdout:训练集合/测试集合

数据集合很大时较好k-fold交叉验证:将数据集合分成k子集合在每次建树时，使用一个子集合作为测试集合，其它k-1子集合一起作为训练集合

用这k次结果的均值作为参照它消除了训练集合/测试集合方法的随机性2023/6/29Guilin6565

交叉验证图解数据集合分成k段

一个做测试，其它的用来训练分类器

重复到Testiteration2023/6/29Guilin66增益率增益率（Gainratio）：是信息增益的一个改良版，它可以减少信息增益偏好于取值较多的属性增益率考虑分支数目和分枝的大小它通过内在信息改良信息增益值也称为分裂率内在信息：分支里的记录分布的熵2023/6/29Guilin67增益率的定义增益率一般是数据均匀分布时很大数据集中于某个枝时很小增益率（Quinlan’86)）标准化信息增益2023/6/29Guilin68有关决策树分类器的研究问题分裂属性选择标准过度拟合（Overfitting）低度