数据挖掘方法：决策树

LOGO数据挖掘方法：决策树DecisionTree组2成员：黄婉婧王佩09物流管理组2Contents决策树应用前景决策树典型算法案例决策树典型算法决策树的特点与意义决策树定义介绍数据挖掘方法：决策树09物流管理组2决策树定义介绍什么是决策树？决策树(Decisiontree)由一个决策图和可能的结果(包括资源成本和风险)组成，用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的树结构。--------维基百科决策树一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。----------百度百科数据挖掘方法：决策树09物流管理组2决策树的定义介绍原理：利用几个变量判断所属类别决策节点：1.最上面的节点称为根节点，是整个决策树的开始。2.每个节点子节点的个数与决策树在用的算法有关。（二叉树、多叉树）分支：判断过程，要么是新的决策节点，要么是叶子树叶:树的结尾，每个叶子代表一个类别概率分支概率分支数据挖掘方法：决策树根节点决策节点树叶树叶树叶决策节点状态节点状态节点09物流管理组2决策树的特点归纳用于决策的类似于流程图的树结构每个节点表示在一个属性上的测试每个分枝代表一个测试输出从树根到树叶的每一条路径对应一组属性测试的合取数据挖掘方法：决策树YESNONONO属性测试可能值分析树根树叶09物流管理组2决策树的意义条理清晰程序严谨定量、定性分析相结合应用性强总结：在企业面临着许多可供选择的方案时能快速挑选出是用最少的资源，赢得最大的利润以及最大限度地降低企业的经营风险的最优决策数据挖掘方法：决策树09物流管理组2决策树算法•决策树算法通过构造决策树来发现数据中蕴含的分类规则。•核心：构造精度高、规模小的决策树•步骤：1.决策树的生成：由训练样本数据集（根据历史数据生成、有一定综合程度的用于数据分析处理的数据集）生成2.决策树的剪枝：采用新的样本数据集（测试数据集）检验决策树生成过程中产生的初步规则，将影响预测准确性的分支剪除。数据挖掘方法：决策树决策树算法准备条件决策树归纳的设计问题如何分裂训练记录•怎样为不同类型的属性指定测试条件?•怎样评估每种测试条件?如何停止分裂过程指定测试条件依赖于属性的类型标称序数连续依赖于划分的路数2路划分多路划分基于标称属性的划分多路划分:划分数（输出数）取决于该属性不同属性值的个数.二元划分:划分数为2，这种划分要考虑创建k个属性值的二元划分的所有2k-1-1种方法.CarTypeFamilySportsLuxuryCarType{Family,Luxury}{Sports}CarType{Sports,Luxury}{Family}ORCarType{Family,Sports}{Luxury}多路划分:划分数（输出数）取决于该属性不同属性值的个数.二元划分:划分数为2，需要保持序数属性值的有序性.基于序数属性的划分SizeSmallMediumLargeSize{Medium,Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}基于连续属性的划分多路划分:vi≤A＜vi+1（i=1,…,k)二元划分:(Av)or(Av)考虑所有的划分点，选择一个最佳划分点vTaxableIncome80K?YesNoTaxableIncome?(i)Binarysplit(ii)Multi-waysplit10K[10K,25K)[25K,50K)[50K,80K)80K决策树算法准备条件决策树归纳的设计问题如何分裂训练记录•怎样为不同类型的属性指定测试条件?•怎样评估每种测试条件?如何停止分裂过程09物流管理组2评估测试条件GiniEntropy（熵）Classificationerror数据挖掘方法：决策树09物流管理组2评估测试条件：GINI公式数据挖掘方法：决策树jtjptGINI2)]|([1)(C10C26C12C24C11C25P(C1)=0/6=0P(C2)=6/6=1Gini=1–P(C1)2–P(C2)2=1–0–1=0P(C1)=1/6P(C2)=5/6Gini=1–(1/6)2–(5/6)2=0.278P(C1)=2/6P(C2)=4/6Gini=1–(2/6)2–(4/6)2=0.444(p(j|t)是在结点t中，类j发生的概率).得到的GINI值越小，样本纯度越高，划分越可行！09物流管理组2评估测试条件：Entropy公式数据挖掘方法：决策树jtjptjptEntropy)|(log)|()(2C10C26C12C24C11C25P(C1)=0/6=0P(C2)=6/6=1Entropy=–0log20–1log21=–0–0=0P(C1)=1/6P(C2)=5/6Entropy=–(1/6)log2(1/6)–(5/6)log2(1/6)=0.65P(C1)=2/6P(C2)=4/6Entropy=–(2/6)log2(2/6)–(4/6)log2(4/6)=0.92与GINI算法相似，得到的值越小，划分越可行！09物流管理组2评估测试条件：ClassificationError公式数据挖掘方法：决策树)|(max1)(tiPtErroriC10C26C12C24C11C25P(C1)=0/6=0P(C2)=6/6=1Error=1–max(0,1)=1–1=0P(C1)=1/6P(C2)=5/6Error=1–max(1/6,5/6)=1–5/6=1/6P(C1)=2/6P(C2)=4/6Error=1–max(2/6,4/6)=1–4/6=1/3得到的值越小，划分越可行！决策树算法准备条件决策树归纳的设计问题如何分裂训练记录•怎样为不同类型的属性指定测试条件?•怎样评估每种测试条件?如何停止分裂过程决策树算法准备条件当所有的记录属于同一类时，停止分裂当所有的记录都有相同的属性时，停止分裂提前终止树的生长09物流管理组2决策树的典型算法Hunt算法ID3（信息增益Informationgain）C4.5(增益比率Gainratio)Cart（GINIindex）数据挖掘方法：决策树决策树典型算法：HuntDon’tCheatRefundDon’tCheatCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat80K=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10Hunt算法采用贪心策略构建决策树.在选择划分数据的属性时，采取一系列局部最优决策来构造决策树.09物流管理组2决策树典型算法：Cart数据挖掘方法：决策树CART（classificationandregression）算法中采用了二元划分，在分支节点上进行Gini值的测试，如果满足一定纯度则划分到左子树，否则划分到右子树，最终生成一棵二叉决策树。在只有二元分裂的时候，对于训练数据集D中的属性A将D分成的D1和D2，则给定划分D的Gini指标如下公式所示：)()()(2211DGiniDDDGiniDDDGiniA09物流管理组2决策树典型算法：Cart数据挖掘方法：决策树CART算法在满足下列条件之一，即视为叶节点不再进行分支操作：（1）所有叶节点的样本数为1、样本数小于某个给定的最小值或者样本都属于同一类的时候；（2）决策树的高度达到用户设置的阈值，或者分支后的叶节点中的样本属性都属于同一个类的时候；（3）当训练数据集中不再有属性向量作为分支选择的时候。09物流管理组2决策树典型算法：ID3数据挖掘方法：决策树任意样本分类的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)•其中，数据集为S，m为S的分类数目，Pi•Ci为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数由A划分为子集的熵：•E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)•A为属性，具有V个不同的取值•信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)||||SSi09物流管理组2ID3应用实例数据挖掘方法：决策树OutlookTemperatureHumidityWindClasssunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweaknoraincoolnormalstrongnosunnymildhighweaknoovercastcoolnormalstrongyesovercastmildhighstrongyesraincoolnormalstrongnorainmildnormalweakyessunnycoolnormalweakyessunnymildnormalstrongyesovercasthotnormalweakyesrainmildhighstrongyes09物流管理组2ID3应用实例数据挖掘方法：决策树ID3算法过程：（1）类别属性信息熵的计算由于未分区前，训练数据集中共有14个实例，其中有9个实例属于p类（适合打网球的），5个实例属于n类（不适合打网球），因此分区前类别属性的熵为：（2）非类别属性信息熵的计算若选择Outlook为测试属性。bitnpI940.0145log145149log149),(22bitOutlookE694.0)52log5253log53(145)40log4044log44(144)53log5352log52(145)(22222209物流管理组2决策树典型算法：ID3数据挖掘方法：决策树因此，这种划分的信息增益是：同理可以求出其他三个增益：由上可知，属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支：（3）递归地创建决策树的树枝和叶子选择作为测试属性后，将训练实例集分为三个子集，生成三个子节点，对每个子节点递归采用上述过程进行分类直至每个节点都成为叶节点而已。bitOutlookEnpIOutlookGain246.0694.0940.0)(),()(biteTemperaturGain029.0)(bitHumidityGain151.0)(bitWindGain048.0)(09物流管理组2决策树典型算法：ID3数据挖掘方法：决策树属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支：09物流管理组2决策树典型算法：ID3数据挖掘方法：决策树A．分析图中的sunny分支，计算其子属性的信息增益值来决定子分裂属性形成子分支之一。针对sunny中的子训练数据集分支，有两个类别，该分支中有3个实例属于n类，有2个实例属于p类，因此针对分支的信息熵为：若以：sunny分支中的属性Temperature为测试属性，则测试属性Temperatu