机器学习-3：决策树的构建及应用

1、_3：决策树的构建及应章录实验背景在之前的实验：我们了解到了K-近邻算法是种需训练就可以拿来进分类的算法，但缺点也很多，最的缺点就是法给出数据的内在含义，今天我就来介绍种容易理解数据形式的分类算法决策树算法。1.决策树算法原理什么是决策树严格定义上来说，分类决策树模型是种描述对实例进分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表个特征或属性，叶节点表个类。通俗来说决策树只有个功能判断，通过不断的判断最终得出个结果，以相亲为例我们将相亲简单的化为三个属性的思考（对象不，富不富，美不美），实际上的相亲远这复杂，很显然，富美的对象乎没有会拒绝。个新的对象放进决

2、策树判断，这个对象是，富，不美，经过3次判断之后，得出的结论是去。这就是决策树，当然，这种海王决策树不是我们特别需要的。决策树的使更多倾向于专家系统中，以病情诊断为例，将以前们记录的各种疾病以及这些疾病发时的症状记录下来，于构建决策树，经过这些疾病的训练后，当病根据提输体温等各种信息后，这个病情决策树就能判断出患者得了哪种病。那么问题就来了，哪种属性作为判断的依据呢，或者说，哪种属性作为判断依据可以有最好的效果呢？如何构建好的决策树想要构造好的决策树，就得找到合适的属性作为判断依据，如何选择合适的属性呢，这引四个概念，浓熵，信息增益，信息增益率，基尼指数。1.2.1.熵，本质是指个系统的“内在

3、混乱程度”，浓熵也样，这个词来形容个事物的确定程度，浓熵越，事物的就越不确定，浓熵越，事物越确定。公式为：Ent（D）表熵，pk表k事件出现的概率，k=1y表共有y种事件以硬币为例，枚硬币抛出，正或反朝上的概率均为50%，此时熵为：-（1/2（log2（1/2）+1/2（log2（1/2）=1。很显然，此时就是这个硬币最不确定的时候，如果我们对硬币作脚，让其概率发变化，浓熵也会随之变化。这就是硬币概率变化导致熵的变化，当然，这硬币只有两种结果，当这两种概率相等的时候熵最。当事件越多，熵值就会越。1.2.2.在划分数据集之前之后信息发的变化称为信息增益，计算公式为：Gain(D,a)表集合D中属

4、性a的信息增益，Dv表属性a有V种分，第v个节点包含了D在a属性上取值为av的所有样本。Gain（D,a)越，代表根据属性a划分获得的“纯度提升”越。1.2.3.虽然信息增益可以帮助我们选择合适的划分属性，但他也有个很明显的问题，那就是明显偏好可取数较多的属性，以硬币为例，如果抛10次硬币，5次朝上，5次朝下，如果以次数为属性，可以发现，每次都只有个值即属性是确定的，这样信息增益就会变成1-0=1。所以我们引信息增益率IV(a)称为属性a的固有值，属性a的可能取值越多，IV(a)的值通常就越，显然，这种法也有个缺点，那就是偏好可取数较少的属性，所以我们先挑选信息增益于平均平的属性，再对其求信息

5、增益率，这样就能得到合适的属性。1.2.4.基尼指数是不同于信息增益和信息增益率的另套属性，他来描述数据集的纯度，反应了随机抽取两个样本，其类别标记不致的概率，也就是基尼指数越，这个数据集的标记越统公式为：给定数据集D，属性a的基尼指数定义为：在候选属性集合A中，选择那个使得划分后基尼指数最的属性作为最有划分属性。如何优化构建完的决策树尽管有多种法可以选择合适的属性来划分数据集，构造决策树，但根据训练数据集训练出来的决策树也有很明显的问题，那就是过度拟合训练数据，导致泛性下降。实际上，训练数据集不可能包含了世界上的所有情况，这就导致个新的样例丢决策树进判断，得出的结果有很可能不是我们想要的，因

6、为这种样例决策树没有接触过。这就需要我们对决策树进“剪枝”。1.3.1.顾名思义，预剪枝通过提前停树的构建对树剪枝，主要法有4种：1.当决策树达到预设的度时就停决策树的长。2.达到某个节点的实例具有相同的特征向量，即使这些实例不属于同类，也可以停决策树的长。（如同样是头疼，发热，部分是感冒，部分是中暑，我们就认为头疼，发热都是感冒）3.定义个阈值，当达到某个节点的实例个数于阈值时就可以停决策树的长。（这是为了防过度拟合训练数据，如头疼的样例有10个，头疼发热的样例只有1个，那就需再发热进划分）4.通过计算每次扩张对系统性能的增益，决定是否停决策树的（提升系统性能就扩张，降低就砍掉这个属性）法3

7、中有个很明显的问题，这个阈值是我们事先规定的，但是如何确定这个阈值是值得讨论的，如何控制好拟合-过拟合的平衡是这个地的难点。尽管预剪枝能降低过拟合风险并且显著减少训练时间和测试时间开销。但因为他的“贪”导致可能会陷局部最优，也就是法解决-低-更的情况，会困死在包上。同时因为限制分枝的展开，使得拟合风险提（毕竟头疼发热的样例哪怕只有例，如果是病毒的情况，这种也是需要注意的，预剪枝就可能会导致忽视这种问题）如图所，预剪枝情况下是没有上那棵完整的决策树的，直接画出下那棵剪枝后的决策树。1.3.2.后剪枝先从训练集成棵完整的决策树，然后底向上地对叶结点进分析计算，若将该结点对应的树替换为叶结点能带来决

8、策树泛化性能提升，则将该树替换为叶结点。如果没有提升，保持不便的话，我们就保留。优缺点都很明显，保留更多的分使得拟合的风险减，有够分的情况下般也分过少的预剪枝泛化性更好；更优秀的表现往往需要更多的付出，因为这种法是成完整的决策树后，底向上进剪枝，导致训练时间很长，开销。后剪枝先成上那棵完整的决策树，再对那棵决策树进剪枝。2.三种决策树构造原理解释完后，我们来分别构建基于信息增益，信息增益率，基尼指数的决策树，先，我们需要计算浓熵，代码如下：def calcShannonEnt(dataSet):#字典，存储类别及个数#dataSet进后为list形式，使变量featVec进列表遍历#取出列表最

9、后个标签if currentLabel not in labelCounts.keys(): #若标签不在字典中for key in labelCounts:#使关键字循环遍历shannonEnt -= prob *log(prob,2)return shannonEnt#测试数据#公式求熵labels =no surfacing,flippers#change to discrete valuesreturn dataSet, labels基于信息增益构造的决策树（ID ）#按照给定的特征划分数据集def splitDataSet(dataSet, axis, value):retDataS

10、et =#存储分割数据#list遍历#如果数据集的value符合我们给定的axis#将该数据加reducedFeatVec#选择最好的数据集划分式(信息增益)def chooseBestFeatureToSplit1(dataSet):numFeatures =len(dataSet0) - 1#去除标签的特征数量baseEntropy =calcShannonEnt(dataSet) #得到浓熵#初始化参数#迭代所有特征featList =example for example in dataSet #创建列表存放特征样例#删除重复数据，获取唯数据#0/1分类，遍历for value in

11、uniqueVals:#0,1实例分别计算条件熵newEntropy +=prob *calcShannonEnt(subDataSet) #条件熵infoGain =baseEntropy - newEntropy #信息增益#选择最的信息增益return bestFeature#返回特征下标#找出出现次数最多的标签，于投票def majorityCnt(classList):classCountdef createTree(dataSet,labels):classList =example-1 for example in dataSet#-1表列表最后个if classList.cou

12、nt(classList0) =len(classList): #所有结果样就需再次分类return classList0#返回结果if len(dataSet0) =1:#只剩下种结果时也需分类#返回出现次数最多的类return majorityCnt(classList)#使信息增益选择最佳划分式myTree =bestFeatLabel:myTreebestFeatLabelvalue =createTree(splitDataSet(dataSet, bestFeat, value),subLabels)return myTree这样的决策树明显不够直观，我们加点绘制图像。#获取叶节点

13、if type(secondDictkey)._name_=dict:#测试节点是否为字典,如果不是，则是叶结点#获取树的深度if type(secondDictkey)._name_=dict:#test to see if the nodes are dictonaires, if not they are leaf nodesif thisDepth maxDepth: maxDepth =thisDepthreturn maxDepthdef plotNode(nodeTxt, centerPt, parentPt, nodeType):va=center, ha=center, bb

14、oxnodeType, arrowpropsarrow_args )def plotMidText(cntrPt, parentPt, txtString):xMid =(parentPt0-cntrPt0)/2.0 +cntrPt0yMid =(parentPt1-cntrPt1)/2.0 +cntrPt1createPlot.ax1.text(xMid, yMid, txtString, va=center, ha=center, rotation30)firstStr =myTree.keys()0 #the text label for this node should be this

15、cntrPt =(plotTree.xOff +(1.0 +float(numLeafs)/2.0/plotTree.totalW, plotTree.yOff)plotMidText(cntrPt, parentPt, nodeTxt)plotNode(firstStr, cntrPt, parentPt, decisionNode)secondDict =myTreefirstStrplotTree.yOff =plotTree.yOff - 1.0/plotTree.totalDfor key in secondDict.keys():if type(secondDictkey)._na

16、me_=dict:#test to see if the nodes are dictonaires, if not they are leaf nodesplotTree(secondDictkey,cntrPt,str(key)#recursionplotNode(secondDictkey, (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)plotMidText(plotTree.xOff, plotTree.yOff), cntrPt, str(key)def createPlot(inTree):fig =plt.figure(1,

17、facecolor=white)fig.clf()fig = plt.figure(1, facecolor=white)fig.clf()#createPlot(thisTree)基于信息增益率构造的决策树（C ）#去除标签的特征数量baseEntropy =calcShannonEnt(dataSet) #得到浓熵#初始化参数#获取平均信息增益#统计数量featList =example for example in dataSet #创建列表存放特征样例#删除重复数据，获取唯数据#0/1分类，遍历for value in uniqueVals:#0,1实例分别计算条件熵subDataSe

18、t =splitDataSet(dataSet, j, value)prob =len(subDataSet)/float(len(dataSet)newEntropy +=prob *calcShannonEnt(subDataSet) #条件熵IV-=prob *log(prob,2)infoGain =baseEntropy - newEntropy #信息增益sum+=infoGainfor i in range(numFeatures):#迭代所有特征featList =example for example in dataSet #创建列表存放特征样例#删除重复数据，获取唯数据IV

19、0.0#0/1分类，遍历for value in uniqueVals:#0,1实例分别计算条件熵subDataSet =splitDataSet(dataSet, i, value)prob =len(subDataSet)/float(len(dataSet)newEntropy +=prob *calcShannonEnt(subDataSet) #条件熵IV-=prob *log(prob,2)infoGain =baseEntropy - newEntropy #信息增益if 0.0:infoGainration0.0else:#选择最的信息增益率return bestFeature

20、#返回特征下标C 4.5的代码和ID 3很像，核区别只在于如何选择信息收益于平均收益的情况下的信息增益率。微量数据下法看出明显区别基于基尼指数构造的决策树（CART）#计算基尼指数def calcGini(dataset):for feat in uniqueFeat:bestFeature =-1for i in range(numFeatures):newEntropy =0.0for value in uniqueVals:# 通过不同的特征值划分数据集subDataSet =splitDataSet(dataSet, i, value)prob =len(subDataSet)/flo

21、at(len(dataSet)newEntropy +=prob calcGini(subDataSet)infoGini =newEntropyif(infoGini bestInfoGini): # 选择最的基尼系数作为划分依据bestInfoGini =infoGinireturn bestFeature #返回决策属性的最佳索引微量数据下没有区别。3.决策树测试对于量的数据集，为了便存储与复，我们需要保存在硬盘内#存储件#读取件def loadTree(filename):fr =open(filename)return pickle.load(fr)if _name_ =_main_:fr=open(D:/vscode/python/.vscode/car.data ,r)dataSetinst.strip().spli