决策树(详细易懂,很多例子)

决策树DecisionTree决策树算法是一种归纳分类算法,它通过对训练集的学习,挖掘出有用的规则,用于对新集进行预测。有监督的学习。非参数学习算法。对每个输入使用由该区域的训练数据计算得到的对应的局部模型。决策树归纳的基本算法是贪心算法，自顶向下递归方式构造决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。简介决策树的结构决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。根节点非叶子节点（决策点）叶子节点分支决策树的结构4根部节点(rootnode)非叶子节点(non-leafnode)(代表测试的条件，对数据属性的测试)分支(branches)(代表测试的结果)叶节点(leafnode)(代表分类后所获得的分类标记)2019/8/29单变量树每个内部节点中的测试只使用一个输入维。如果使用的输入维是离散的，取n个可能的值之一，则该节点检测的值，并取相应的分支，实现一个n路划分。决策点具有离散分支，而数值输入应当离散化。如果是数值的（有序的），则测试函数是比较：其中是适当选择阈值。该决策节点将输入空间一份为二：和，称为一个二元划分。决策树根据所选取的属性是数值型还是离散型，每次将数据划分成两个或n个子集。然后使用对应的子集递归地进行划分，直到不需要划分，此时，创建一个树叶节点标记它。jxjxjx0:)(mjmwxxf0mw0|mjmwxxL0|mjmwxxR决策树分类1.训练阶段从给定的训练数据集DB，构造出一棵决策树class=DecisionTree(DB)2.分类阶段从根开始，按照决策树的分类属性逐层往下划分，直到叶节点，获得概念（决策、分类）结果。y=DecisionTree(x)ExampleofaDecisionTreeAnotherExampleofDecisionTreeApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataStartfromtherootoftree.ApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10TestDataAssignCheatto“No”决策树原理基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是离散值字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树方法：（1）创建结点N；（2）ifsamples都在同一个类Cthen（3）返回N作为叶结点，用类C标记；（4）ifattribute_list为空then（5）返回N作为叶结点，标记samples中最普通的类；//多数表决（6）选择attribute_list中的最优分类属性test_attribute；//用信息增益作为属性选择度量（7）标记结点N为test_attribute；（8）foreachtest_attribute中的已知值ai//划分samples（9）由结点N生长出一个条件为test_attribute＝ai的分枝；（10）设si为samples中test_attribute＝ai的样本集合；//一个划分（11）ifsi为空then（12）加上一个叶结点，标记为标记samples中最普通的类；//多数表决（13）else加上一个由Generate_decision_tree（si,attribute_list-test_attribute）返回的结点；例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo1.samples={1,2,3,4,5,6,7,8,9,10}attribute_list={Refund,MarSt,TaxInc}假设选择Refund为最优分割属性：2.samples={1,4,7}attribute_list={MarSt,TaxInc}3.samples={2,3,5,6,8,9,10}attribute_list={MarSt,TaxInc}例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNosamples中所有样本属于同一个类Cheat=No2.samples={1,4,7}attribute_list={MarSt,TaxInc}NO例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo假设选择MarSt为最优分割属性：3.samples={2,3,5,6,8,9,10}attribute_list={MarSt,TaxInc}NOMarStSingleMarriedDivorced4.samples={3,8,10},attribute_list={TaxInc}5.samples={5,7},attribute_list={TaxInc}6.samples={2,9},attribute_list={TaxInc}例子：算法过程TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundYesNo选择TaxInc为最优分割属性：4.samples={3,8,10}attribute_list={TaxInc}NOMarStSingleMarriedDivorcedTaxInc80K=80KYESNO问题1：分类从哪个属性开始？——选择分裂变量的标准问题2：为什么工资以80为界限？——找到被选择的变量的分裂点的标准（连续变量情况）分类划分的优劣用不纯性度量来分析。如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类，则这个划分是纯的。对于节点m，令为到达节点m的训练实例数，个实例中个属于类，而。如果一个实例到节点m，则它属于类的概率估计为：节点m是纯的，如果对于所有i，为0或1。当到达节点m的所有实例都不属于类时，为0，当到达节点m的所有实例都属于类时，为1。一种度量不纯性的可能函数是熵函数（entropy)。mNimNiCmiimNNmimimiNNpmxCp),|(ˆmNiCimpiCiCimpimpFatherofinformationtheory证明熵与信息内容的不确定程度有等价关系系统科学领域三大论之一C.Shannon的信息论信息熵熵(entropy)121212222entropy(,,,)logloglognnnppppppppp描述物质系统状态:该状态可能出现的程度。平均信息量若一个系统中存在多个事件E1,E2,…En每个事件出现的概率是p1,p2,…pn则这个系统的平均信息量是指的是系统的混乱的程度!(bits)系统越无序、越混乱，熵就越大。构造决策树，熵定义为无序性度量。选择一个属性划分数据，使得子女节点上数据的类值（例中“yes”或“no”）大部分都相同（低无序性）。如果一个节点上的数据类值在可能的类值上均匀分布，则称节点的熵（无序性）最大。如果一个节点上的数据的类值对于所有数据都相同，则熵最小。通过分裂，得到尽可能纯的节点。这相当于降低系统的熵。例子气象数据集，都是标称属性什么因素影响是否去打网球？OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNo1.基于天气的划分2.基于温度的划分3.基于湿度的划分4.基