决策树

决策树决策树简介决策树算法A1,A2两方案投资分别为450万和240万，经营年限为5年，销路好的概率为0.7，销路差的概率为0.3，A1方案销路好年、差年的损益值分别为300万和负60万，A2方案分别为120万和30万。决策树简介决策树简介决策状态状态结结果点A1A20.70.30.70.3300—6012030决策树简介决策状态状态结结果点最后选择的最佳方案代表备选方案的经济效果将每个方案在各种自然状态下取得的损益值标注于结果节点的右端决策树的一般流程：（1）收集数据（2）准备数据（3）分析数据（4）训练算法（5）测试算法（6）使用算法决策树简介划分数据集的大原则就是将无序的数据变得更加有序。划分数据集前后信息发生的变化成为信息增益。决策树简介集合信息的度量方式称为香农熵（熵）条件熵决策树简介i2iHUPulogPu()=-()()iij2jjjiuuH(UV)P(v)P()logP()vv计算给定数据集的香农熵frommathimportlogdefcalcShannonEnt(dataSet):numEntries=len(dataSet)labelCounts={}forfeatVecindataSet:currentLabel=featVec[-1]ifcurrentLabelnotinlabelCounts.keys():labelCounts[currentLabel]=0labelCounts[currentLabel]+=1shannonEnt=0.0forkeyinlabelCounts:prob=float(labelCount[key])/numEntriesshannonEnt-=prob*log(prob,2)returnshannonEnt决策树简介(1)(2)计算给定数据集的香农熵首先，计算数据集中实例的总数。为了提高代码效率，我们显式的声明一个变量保存实例总数。然后，创建一个数据字典，它的键值是最后一列的数值（1）。如果当前键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。最后，使用所有类标签的发生频率计算类别出现的频率（2）。我们将用这个概率计算香农熵。决策树简介选择最好的数据集划分方式要求：1数据必须是一种列表元素组成的列表，而且所有的列表元素都要具有相同的数据长度。2数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。决策树简介递归构建决策树defcreateTree(dataSet,labels):classList=[example[-1]forexampleindataSet]ifclassList.count(classList[0])==len(classList):returnclassList[0]#stopsplittingwhenalloftheclassesareequaliflen(dataSet[0])==1:#stopsplittingwhentherearenomorefeaturesindataSetreturnmajorityCnt(classList)bestFeat=chooseBestFeatureToSplit(dataSet)bestFeatLabel=labels[bestFeat]myTree={bestFeatLabel:{}}del(labels[bestFeat])featValues=[example[bestFeat]forexampleindataSet]uniqueVals=set(featValues)forvalueinuniqueVals:subLabels=labels[:]#copyalloflabels,sotreesdon'tmessupexistinglabelsmyTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)returnmyTree决策树简介(1)(2)(3)递归构建决策树首先创建了名为classList列变量，其中包含了数据集的所有类标签。递归函数的第一个停止条件是所有的类标签完全相同，则直接返回该类标签(1)。递归函数的第二个停止条件是使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组(2)。决策树简介递归构建决策树第二步，开始创建树，这里使用python语言的字典类型存储树的信息(3)。决策树简介递归构建决策树第三步，代码遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree(),得到的返回值将被插入到字典变量MyTree中。决策树简介3种算法比较ID3较小数据算法清晰C4增加信息增益率可以处理连续数值型属性规则后修剪C5Unix决策树算法一ID3基本思想二ID3算法三实例四ID3缺点决策树算法在决策树各个结点上应用信息增益准则选择特征递归地构建决策树。天气，取值为：晴，多云，雨。气温，取值为：冷，适中，热。湿度，取值为：高，正常。风，取值为：有风，无风。决策树算法ID3基本思想某天早晨气候描述为：天气－多云；气温－冷；湿度－正常；风－无风。它属于哪类气候呢？要解决这个问题，需要用某个原则来判定，这个原则来自于大量的实际例子，从例子中总结出原则，有了原则就可以判定任何一天的气候了。每个实体在世界中属于不同的类别，为简单起见，假定仅有两个类别，分别为P、N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知正例和反例放在一起便得到训练集。决策树算法ID3基本思想决策树算法天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风NNO.类别属性ID3基本思想决策树算法晴多云雨P正常PNNP有风无风湿度风天气高ID3基本思想决策树算法PN多云(12)雨(14)风有风(2,6,7,11,12,14)温度高(2,12,14)正常(6,7,11)气温气温N热(2)适中(12,14)天气P适中(11)冷(6,7)NP多云(6)雨(7)天气高(1,3,4,8)无风(1,3,4,5,8,9,10,13)正常(5,9,10,13)适中(4,8)P热(1,3)PNPN晴(1)多云(3)晴(8)雨(4)温度气温天气天气ID3算法从根结点（rootnode）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归的调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。最后，得到一个决策树。决策树算法ID3算法决策树算法三实例对于气候分类问题进行以下具体计算。1、信息熵计算：类别ui出现概率：|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例u1和5个反例u2有：i2iHUPulogPu()=-()()iiuP(u)=S19P(u)1425P(u)1422951414H(U)()log()()log()0.94bit1491452．条件熵计算条件熵：属性A1取值vj时，类别ui的条件概率：A1＝天气的取值：v1＝晴，v2＝多云，v3＝雨在A1处取值“晴”的例子5个，取值“多云”的例子4个，取值“雨”的例子5个，故：决策树算法三实例iij2jjjiuuH(UV)P(v)P()logP()vviijjuuP()vv35P(v)1424P(v)1415P(v)14取值为晴的5个例子中有两个正例、3个反例，故：同理有决策树算法三实例11u2P()v521u3P()v512u4P()v413u2P()v522uP()0v23u3P()v52222255352444H(UV)()()log()+()log()()()log()+0145253144455352()()log()+()log()0.69bit1452533．互信息计算对A1＝天气，有：类似可得：（气温）＝0.029bit（湿度）＝0.151bit（风）＝0.048bit决策树算法三实例决策树算法三实例天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风NNO.类别属性4．建决策树的树根和分支ID3算法将选择互信息最大的属性“天气”作为树根，在14个例子中对“天气”的3个取值进行分支，3个分支对应3个子集，分别是：F1晴＝｛1，2，8，9，11｝，F2多云＝｛3，7，12，13｝，F3雨＝｛4，5，6，10，14｝其中，F2中的例子全属于P类，因此对应分支标记为P，其余两个子集既含有正例P又含有反例，将递归调用建树算法决策树算法三实例5．递归建树分别对F1和F3子集利用ID3算法，在每个子集中对各属性（仍为4个属性）求互信息。（1）F1中的天气全取“晴”值，则H（U）＝H（U｜V），有I（U｜V）＝0，在余下3个属性中求出“湿度”互信息最大，以它为该分支的根结点。再向下分支，“湿度”取“高”的例子全为N类，该分支标记N；取值“正常”的例子全为P类，该分支标记P。决策树算法三实例（2）在F3中，对4个属性求互信息，得到“风”属性互信息最大，则以它为该分支的根结点。再向下分支，“风”取“有风”时全为N类，该分支标记N；取“无风”时全为P类，该分支标记P。这样就得到如图所示的决策树。决策树算法三实例晴多云雨P高正常PNNP有风无风湿度风天气图1ID3算法的缺点：1．只适合属性值为离散的；2．决策树层次较多时，决策质量低；3．倾向于选择取值较多的属性；决策树算法四ID3缺点取得熵划分数据集构造决策树决策树Matplotlib注解绘制树形图测试存储优点：决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。决策树缺点：1)对连续性的字段比较难预测。2)对有时间顺序的数据，需要很多预处理的工作。决策树A1的净收益值=[300*0.7+（-60）*0.3]*5-450=510万A2的净收益值=[120*0.7+30*0.3]*5-240=225万谢谢THEEND