2-dtree-决策树

2019/8/28Guilin1决策树分类器朱晓峰[e-mail]数据库知识发现技术数据预处理：属性约简，缺失值填充…关联规则分类或预测聚类可视化分析2019/8/28Guilin3什么叫分类？分类是一个古老的方法、现代热门的课题已知数据的集合D：数据被标记学习：从数据集合中归纳出规则、规律等，通常称为分类器，或模型预测：用分类器预测新数据的类这种从有标记的数据种归纳分类器的方法叫监督学习决策树、回归是最常用的分类器分类任务图例ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetLearningalgorithmTrainingSet分类任务例子PredictingtumorcellsasbenignormalignantClassifyingcreditcardtransactionsaslegitimateorfraudulentClassifyingsecondarystructuresofproteinasalpha-helix,beta-sheet,orrandomcoilCategorizingnewsstoriesasfinance,weather,entertainment,sports,etc分类技术DecisionTreebasedMethodsRule-basedMethodsMemorybasedreasoningNeuralNetworksNaïveBayesandBayesianBeliefNetworksSupportVectorMachines2019/8/28Guilin7决策树分类器/模型学习将已知数据集合分成训练数据集合测试集合学习：从一个训练数据集合归纳出一棵决策树：从完全空间搜索一棵最佳树的过程预测：用决策树分类新数据决策树是最常用的分类器之一不要求任何知识或参数设定它是一种监督学习方法一棵决策树可以表示成一组规则2019/8/28Guilin8决策树的结构决策树是层次的树结构由一些节点和枝（边）组成，一棵决策树至少有一个节点枝的两端是节点一棵决策树通常是从左到右，或从上到下画图树的第一个节点称为根节点，“根-枝-节点-...–节点”的最后一个节点是叶节点，其它节点叫中间节点非叶节点至少有一条枝2019/8/28Guilin9决策树分类器的解释一棵决策树是训练数据的一个划分树的一个非叶节点是对一个属性上的测试一个属性的一条枝是测试该属性的一个结果一个叶节点是一个类标记在每个非叶节点，一个属性被选中，它将训练数据分裂成尽可能不同类的子集合（划分）对于一个新数据，根据它的每个属性值从根节点一直匹配到叶节点，这个叶节点的标记就用来预测新数据的类2019/8/28Guilin10构造决策树分类器的原则目标：最大化预测新数据的精度（实现困难）通常将给定的已知数据随机分成训练集合和测试集合。训练数据用于归纳分类器，测试数据用来评估分类器训练分类器时的目标是最大化预测测试数据的精度，即，该分类器基本上体现两个（训练和测试）集合的共同结构过度拟合（overfitting）问题：拟合训练数据的效果很好，拟合测试数据的效果很差2019/8/28Guilin11举例说明（训练数据）AttributesClassesGenderCarownershipTravelCost($)/kmIncomeLevelTransportationmodeMale0CheapLowBusMale1CheapMediumBusFemale1CheapMediumTrainFemale0CheapLowBusMale1CheapMediumBusMale0StandardMediumTrainFemale1StandardMediumTrainFemale1ExpensiveHighCarMale2ExpensiveMediumCarFemale2ExpensiveHighCar2019/8/28Guilin12举例说明（决策树）2019/8/28Guilin13举例说明（测试数据）决策树是用于预测一个数据的类问题：Alex,BuddyandCheery使用哪种交通工具？GenderCarownershipTravelCost($)/kmIncomeLevelTransportationmodeAlexMale1StandardHigh?BuddyMale0CheapMedium?CherryFemale1CheapHigh?2019/8/28Guilin14举例说明（决策树的运用）从根节点Travelcostperkm开始如果TravelCost=expensive，Transportationmode=car如果TravelCost=standard，Transportationmode=train如果TravelCost=cheap，决策树需要检查下一个节点Gender如果Gender=male，Transportationmode=bus如果Gender=female，决策树需要检查下一个节点Carownership如果Carownership=0，Transportationmode=bus，否则Transportationmode=train2019/8/28Guilin15举例说明（决策树）2019/8/28Guilin16举例说明（决策树产生的规则）每个叶节点产生一条规则Rule1：IfTravelcost=expensivethenMode=carRule2：IfTravelcost=standardthenMode=trainRule3：IfTravelcost=cheapGender=malethenMode=busRule4：IfTravelcost=cheapGender=femaleCarownership=0thenMode=busRule5：IfTravelcost=cheapGender=femaleCarownership=1thenMode=train2019/8/28Guilin17举例说明（预测）根据上面的决策树或者规则，回答前面的问题就很简单、直接Alex：Travelcost=standard，所以，无论其它属性取什么值，可以预测他的交通工具是trainBuddy：Travelcost=cheap并且Gender=male，则可以预测他的交通工具是busCherry：Travelcost=cheap并且Gender=female并且Carownership=1，则可以预测他的交通工具是train2019/8/28Guilin18决策树的缺点多数决策树算法采用贪心策略：按照设定的启发式信息搜索最佳树无回溯非穷近搜索，但可能剪枝2019/8/28Guilin19如何建构决策树？决策树很简单，但实现建构一棵好的树是很困难的在上面的例子中，属性Incomelevel没有用于交通工具的分类建构一棵树通常的办法（启发式信息）是度量数据集的不纯度（impurity）EntropyGiniindexClassificationerror2019/8/28Guilin20不纯度的定义给定一个训练数据集（决策表），我们能根据类属性度量它的同构性（或异构性heterogeneity）如果一个训练数据集的类属性只取一个类值，它是纯的或者同构的如果一个训练数据集的类属性取多个类值，它是不纯的或者异构的2019/8/28Guilin21如何度量不纯度有多种量化方法度量不纯度最常用的三种方法如下上面所有的度量方法都含有类j的概率pjjjjppEntropy2logjjpIndexGini21_}max{1_jperrortionClassifica2019/8/28Guilin22举例说明（训练数据）AttributesClassesGenderCarownershipTravelCost($)/kmIncomeLevelTransportationmodeMale0CheapLowBusMale1CheapMediumBusFemale1CheapMediumTrainFemale0CheapLowBusMale1CheapMediumBusMale0StandardMediumTrainFemale1StandardMediumTrainFemale1ExpensiveHighCarMale2ExpensiveMediumCarFemale2ExpensiveHighCar2019/8/28Guilin23举例说明（类的频率）在训练数据集合中，类属性Transportationmode有三个类值Bus、Car和Train我们的例子中，每个值出现的次数如下4buses3cars3trains简单记为4B,3C,3T总数据量是10个标记的例子2019/8/28Guilin24举例说明（计算概率）根据上面的数据，每个类的概率如下：p(Bus)=4/10=0.4p(Car)=3/10=0.3p(Train)=3/10=0.3注意，在上面的概率计算中，我们只考虑了类属性Transportationmode，其它属性都不考虑有了每个类的概率，我们就可以用前面的方法计算训练数据集合的不纯度2019/8/28Guilin25举例说明（用熵计算概率）计算训练数据集合的不纯度的一个方法就是采用熵（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jjjppEntropy2log2019/8/28Guilin26熵的性质一个纯的训练数据集合（只有一个类）的熵是0，这是因为概率1的对数log(1)=0在多个类的情况下，熵在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的熵的最大值，这里，p=1/n熵的最大值是-n*p*logp注意：当类个数n2时，熵12019/8/28Guilin27图示熵的性质2019/8/28Guilin28举例说明（用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jjpIndexGini21_2019/8/28Guilin29Gini索引的性质一个纯的训练数据集合（只有一个类）的Gini索引值是0，这是因为概率1的Gini索引值是1-(1)^2=0与熵一样，Gini索引在每个类的概率相等时达到最大值下面的图描出了不同的类个数n的Gini索引的最大值，这里，p=1/n注意：无论有多少个类值，Gini索引值总是在0和1