python决策树的实现

概述python对决策树的实现一、实验目的此表中有14条实例数据，就是我们的训练数据。其中Outlook,Temperature,Humidity,Wind称作条件属性，PlayTennis称作是决策属性(标签)。每一个属性都有各自的值记做：Value(Outlook)={Sunny,OverCast,Rain}Value(Temperature)={Hot,Mild python对决策树的实现一、实验目的

此表中有14条实例数据，就是我们的训练数据。

其中 Outlook, Temperature, HumIDity, Wind 称作条件属性，PlayTennis 称作是决策属性(标签)。

每一个属性都有各自的值记做：

Value(Outlook)={Sunny, OverCast, Rain}Value(Temperature)={Hot, Mild, Cool}Value(HumIDity)={High, normal}Value(Wind)={Strong, Weak}Value(PlayTennis)={NO, Yes}

有以上数据，目的是建立决策树，导入数据，选择特征值并挑选最佳特征位，训练数据计算熵值。

二、代码实现过程1、引用

from math import log    #进行对数运算from matplotlib.Font_manager import FontPropertIEs  #中文字体import matplotlib.pyplot as plt  #画图

2、算给定数据集的经验熵（香农熵）

香农熵公式：

def calcShannonEnt(dataSet):    numEntrIEs=len(dataSet)    						 #数据集行数    labelCounts={}  								 #声明保存每个标签（label）出现次数的字典    for featVec in dataSet:    						 #对每组特征向量进行统计        currentLabel=featVec[-1]                     #提取标签信息        if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去            labelCounts[currentLabel]=0        labelCounts[currentLabel]+=1                 #label计数#以上是将每个标签出现的次数放入labelCounts字典中，目的就是求出香农公式里的P(x)    shannonEnt=0.0                                   #经验熵    for key in labelCounts:    						 #计算经验熵        prob=float(labelCounts[key])/numEntrIEs      #选择该标签的概率        shannonEnt-=prob*log(prob,2)                 #利用公式计算    return shannonEnt                                #返回经验熵

3、创建数据集

以上面给的数据为例，因为数据较少，没有进行文件数据的读取 *** 作，直接定义数据

def createDataSet():    data = [        ['Sunny', 'Hot', 'High', 'Weak', 'No'],        ['Sunny', 'Hot', 'High', 'Strong', 'No'],        ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],        ['Rain', 'Mild', 'High', 'Weak', 'Yes'],        ['Rain', 'Cool', 'normal', 'Weak', 'Yes'],        ['Rain', 'Cool', 'normal', 'Strong', 'No'],        ['Overcast', 'Cool', 'normal', 'Strong', 'Yes'],        ['Sunny', 'Mild', 'High', 'Weak', 'No'],        ['Sunny', 'Cool', 'normal', 'Weak', 'Yes'],        ['Rain', 'Mild', 'normal', 'Weak', 'Yes'],        ['Sunny', 'Mild', 'normal', 'Strong', 'Yes'],        ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],        ['Overcast', 'Hot', 'normal', 'Weak', 'Yes'],        ['Rain', 'Mild', 'High', 'Strong', 'No'],    ]    labels = ['Outlook', 'Temperature', 'HumIDity', 'Wind']    return data,labels 								 #最后返回的是数据集和分类属性

4、对数据集进行划分

例如、观察矩阵的第一列是否满足需要，如果满足需要，就把后面的添加进来，然后追加到新的矩阵中。

为什么这么做呢？除此之外，axis是轴的意思，这段代码给出了三个参数，第一个是要被划分的数据集（dataSet），第二个是轴线（axis），也就是说的第一列，第二列等，第三个是value，看这一列的数值是否等于value

目的就是为下面的步骤做准备，选出最好的数据分化方式。

def SplitData(dataSet,axis,value):    retDataSet=[]    								  #创建返回的数据集列表    for featVec in dataSet:    						  #遍历数据集        if featVec[axis]==value:					  #如果            reduceFeatVec=featVec[:axis]              #去掉axis特征            reduceFeatVec.extend(featVec[axis+1:])	  #将符合条件的添加到返回的数据集            retDataSet.append(reduceFeatVec)    #返回划分后的数据集    return retDataSet

5、选择最好的数据分化方式

信息增益的公式（信息增益于集合熵的关系式）：

其中，|S|为原集合的数量，|Sa|为分类后子集中元素的个数。Entropy(S)为原集合的熵
所以，G(S,A)是在给定属性A的值知道后，导致期望熵的减少,也就是说，若知道A的值，可以获得最大的信息增益，则属性A对数据集分类数量的降低有很大的积极作用。知道A之后，得到的信息是相对其他属性最多的。

def chooseBestFeaturetoSplit(dataSet):    numFeatures = len(dataSet[0]) - 1                 #特征数量    baseEntropy = calcShannonEnt(dataSet)			  #计数数据集的香农熵    bestInfoGain = 0.0   		 					  #信息增益    bestFeature = -1    							  #最优特征的索引值    for i in range(numFeatures):    				  #循环的作用就是遍历所有特征        featList = [example[i] for example in dataSet]# 获取dataSet的第i个所有特征        uniqueVals = set(featList)        			  #创建set集合{}，元素不可重复        newEntropy = 0.0        					  #经验条件熵        for value in uniqueVals:        			  #计算信息增益            subDataSet = splitDataSet(dataSet, i, value)#subDataSet划分后的子集            prob = len(subDataSet) / float(len(dataSet))#计算子集的概率            newEntropy += prob * calcShannonEnt((subDataSet))#根据公式计算经验条件熵        infoGain = baseEntropy - newEntropy        	  #信息增益        print("第%d个特征的增益为%.3f" % (i, infoGain))  #打印每个特征的信息增益        if (infoGain > bestInfoGain):        		  #计算信息增益            bestInfoGain = infoGain            		  #更新信息增益，找到最大的信息增益            bestFeature = i							  #记录信息增益最大的特征的索引值    return bestFeature    							  #最终返回的是信息增益最大特征的索引值

以上运行完以后可以先实验程序

mydata,labels=createDataSet()						  chooseBestFeaturetoSplit(mydata)

6、找到出现次数最多的分类名称

def moretype_con(classList):    classCount={}									  #主要是存储每个类标签出现的频率    for i in classList:        if i not  in classList.keys(): classCount[i]=0 # 如果一次也没有，次数就赋值为0        classCount+=1        sorted_classCount=sorted(classCount.iteriterms(),key=operator.itemgetter(1),reverse=True)    return  sorted_classCount

7、递归创建决策树

def createTree(dataSet, labels,featLabels):    classList = [example[-1] for example in dataSet]  # 取分类标签（是否出去玩：yes or no）    if classList.count(classList[0]) == len(classList):# 如果类别完全相同则停止继续划分        return classList[0]    if len(dataSet[0]) == 1:    					  # 遍历完所有特征时返回出现次数最多的类标签        return majorityCnt(classList)        bestFeat = ChoosebestSplitData(dataSet)			  # 选择最优特征    bestFeatLabel = labels[bestFeat]    			  # 最优特征的标签    featLabels.append(bestFeatLabel)    myTree = {bestFeatLabel: {}}    				  # 根据最优特征的标签生成树    												  # 删除已经使用的特征标签    												  # 得到训练集中所有最优解特征的属性值    featValues = [example[bestFeat] for example in dataSet]    uniqueVals = set(featValues)    				  # 去掉重复的属性值    for value in uniqueVals:    					  # 遍历特征，创建决策树        del_bestFeat = bestFeat        del_labels = labels[bestFeat]        del (labels[bestFeat])        myTree[bestFeatLabel][value] = createTree(SplitData(dataSet, bestFeat, value), labels, featLabels)        labels.insert(del_bestFeat, del_labels)    return myTree

8、获取叶节点的数目和树的层次（1）、获取叶节点的数目@H_301_99@

def getleaf_num(myTree):    leaf_num=0    Start = next(iter(myTree))    #print("\nStart",Start)    Then = myTree[Start]    #print("\nThen",Then)    for key in Then.keys():        if type(Then[key]).__name__ == 'dict':            leaf_num += getleaf_num(Then[key])        else:            leaf_num += 1    return leaf_num

（2）、获取树的层次@H_301_99@

def getTree_Depth(myTree):    Depth = 0    Start=next(iter(myTree))    Then = myTree[Start]    for key in Then.keys():        if type(Then[key]).__name__ == 'dict':            thisDepth =1 + getTree_Depth(Then[key])        else:            thisDepth = 1    if thisDepth>Depth:Depth=thisDepth    return Depth

（3）、查看树的叶节点的数目和树的层次@H_301_99@

mydata,labels=createDataSet()myTree=createTree(mydata,labels)print("叶子节点",getleaf_num(myTree))print("树的层数节",getTree_Depth(myTree))

9、绘制树（1）、定义箭头样式@H_301_99@

def plotNode(nodeTxt, centerPt, parentPt, nodeType):                                              Font = FontPropertIEs(fname=r"c:\windows\Fonts\simsun.ttc", size=14)        #设置中文字体    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点        xytext=centerPt, textcoords='axes fraction',        va="center", ha="center", bBox=nodeType, arrowprops=dict(arrow), FontPropertIEs=Font)

（2）、标注有向边属性值@H_301_99@

def plotMIDText(cntrPt, parentPt, txtString):    xMID = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                               #计算标注位置    yMID = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]    createPlot.ax1.text(xMID, yMID, txtString)

（3）、绘制决策树@H_301_99@

def plottree(myTree, parentPt, nodeTxt):    decisionNode = dict(Box, fc="0.8")  # 设置结点格式    leafNode = dict(Box, fc="0.8")    #设置叶结点格式    numLeafs = getleaf_num(myTree)                                                 #获取决策树叶结点数目，决定了树的宽度    depth = getTree_Depth(myTree)                                                  #获取决策树层数    firstStr = next(iter(myTree))                                                  #下个字典    cntrPt = (plottree.xOff + (1.0 + float(numLeafs))/2.0/plottree.totalW, plottree.yOff)    #中心位置    plotMIDText(cntrPt, parentPt, nodeTxt)                                         #标注有向边属性值    plotNode(firstStr, cntrPt, parentPt, decisionNode)                             #绘制结点    secondDict = myTree[firstStr]                                                  #下一个字典，也就是继续绘制子结点    plottree.yOff = plottree.yOff - 1.0/plottree.totalD                            #y偏移    for key in secondDict.keys():        if type(secondDict[key]).__name__=='dict':                                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点            plottree(secondDict[key],cntrPt,str(key))                              #不是叶结点，递归调用继续绘制        else:                                                                      #如果是叶结点，绘制叶结点，并标注有向边属性值            plottree.xOff = plottree.xOff + 1.0/plottree.totalW            plotNode(secondDict[key], (plottree.xOff, plottree.yOff), cntrPt, leafNode)            plotMIDText((plottree.xOff, plottree.yOff), cntrPt, str(key))    plottree.yOff = plottree.yOff + 1.0/plottree.totalD

10、测试

myDat,labels=creatDataSet()    myTree=createTree(myDat,labels)    print(myTree)    print(createPlot(myTree))

三、整个程序

from math import logimport operatorfrom matplotlib.Font_manager import FontPropertIEsimport matplotlib.pyplot as plt#计算数据集的香农公式的值#新建数据集合def creatDataSet():    # 数据集    data = [        ['Sunny', 'Hot', 'High', 'Weak', 'No'],        ['Sunny', 'Hot', 'High', 'Strong', 'No'],        ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],        ['Rain', 'Mild', 'High', 'Weak', 'Yes'],        ['Rain', 'Cool', 'normal', 'Weak', 'Yes'],        ['Rain', 'Cool', 'normal', 'Strong', 'No'],        ['Overcast', 'Cool', 'normal', 'Strong', 'Yes'],        ['Sunny', 'Mild', 'High', 'Weak', 'No'],        ['Sunny', 'Cool', 'normal', 'Weak', 'Yes'],        ['Rain', 'Mild', 'normal', 'Weak', 'Yes'],        ['Sunny', 'Mild', 'normal', 'Strong', 'Yes'],        ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],        ['Overcast', 'Hot', 'normal', 'Weak', 'Yes'],        ['Rain', 'Mild', 'High', 'Strong', 'No'],    ]    labels = ['Outlook', 'Temperature', 'HumIDity', 'Wind']  # 5个特征    return data,labelsdef xiangnong(dataSet):    #返回数据集行数    numEntrIEs=len(dataSet)    #保存每个标签（label）出现次数的字典    labelCounts={}    #对每组特征向量进行统计    for featVec in dataSet:        currentLabel=featVec[-1]                     #提取标签信息        if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去            labelCounts[currentLabel]=0        labelCounts[currentLabel]+=1                 #label计数    shannonEnt=0.0                                   #经验熵    #计算经验熵    for key in labelCounts:        prob=float(labelCounts[key])/numEntrIEs      #选择该标签的概率        shannonEnt-=prob*log(prob,2)                 #利用公式计算    return shannonEnt#对数据集进行划分def SplitData(dataSet,axis,value):    #创建返回的数据集列表    retDataSet=[]    #遍历数据集    for featVec in dataSet:        if featVec[axis]==value:            #去掉axis特征            reduceFeatVec=featVec[:axis]            #将符合条件的添加到返回的数据集            reduceFeatVec.extend(featVec[axis+1:])            retDataSet.append(reduceFeatVec)    #返回划分后的数据集    return retDataSet#选择最好的数据集划分方式def ChoosebestSplitData(data):    numFeatures = len(data[0]) - 1  # 获取样本集中特征个数，-1是因为最后一列是label    baseEntropy = xiangnong(data)  # 计算根节点的信息熵    bestInfoGain = 0.0  # 初始化信息增益    bestFeature = -1  # 初始化最优特征的索引值    for i in range(numFeatures):  # 遍历所有特征，i表示第几个特征        featList = [example[i] for example in  data]  # 将dataSet中的数据按行依次放入example中，然后取得example中的example[i]元素，即获得特征i的所有取值        uniqueVals = set(featList)  # 由上一步得到了特征i的取值，比如[1,1,1,0,0]，使用集合这个数据类型删除多余重复的取值，则剩下[1,0]        newEntropy = 0.0        for value in uniqueVals:            subDataSet = SplitData(data, i, value)  # 逐个划分数据集，得到基于特征i和对应的取值划分后的子集            prob = len(subDataSet) / float(len(data))  # 根据特征i可能取值划分出来的子集的概率            newEntropy += prob * xiangnong(subDataSet)  # 求解分支节点的信息熵        infoGain = baseEntropy - newEntropy  # 计算信息增益        if (infoGain > bestInfoGain):  # 对循环求得的信息增益进行大小比较            bestInfoGain = infoGain            bestFeature = i  # 如果计算所得信息增益最大，则求得最佳划分方法    return bestFeature  # 返回划分属性（特征）#该函数使用分类名称的列表，然后创建键值为ClassList中唯一的数据字典，字典对象存储了ClassList中每个类标签出现的评率，最后利用operator *** 作键值排序#字典，并返回出现次数最多的分类名称。def moretype_con(classList):    classCount={}#主要是存储每个类标签出现的评率    for i in classList:        if i not  in classList.keys(): classCount[i]=0 # 如果一次也没有，次数就赋值为0        classCount+=1        sorted_classCount=sorted(classCount.iteriterms(),key=operator.itemgetter(1),reverse=True)    return  sorted_classCount#创建树def createTree(dataSet, labels,featLabels):    # 取分类标签（是否出去玩：yes or no）    classList = [example[-1] for example in dataSet]    # 如果类别完全相同则停止继续划分    if classList.count(classList[0]) == len(classList):        return classList[0]    # 遍历完所有特征时返回出现次数最多的类标签    if len(dataSet[0]) == 1:        return majorityCnt(classList)    # 选择最优特征    bestFeat = ChoosebestSplitData(dataSet)    # 最优特征的标签    bestFeatLabel = labels[bestFeat]    featLabels.append(bestFeatLabel)    # 根据最优特征的标签生成树    myTree = {bestFeatLabel: {}}    # 删除已经使用的特征标签    # 得到训练集中所有最优解特征的属性值    featValues = [example[bestFeat] for example in dataSet]    # 去掉重复的属性值    uniqueVals = set(featValues)    # 遍历特征，创建决策树    for value in uniqueVals:        del_bestFeat = bestFeat        del_labels = labels[bestFeat]        del (labels[bestFeat])        myTree[bestFeatLabel][value] = createTree(SplitData(dataSet, bestFeat, value), labels, featLabels)        labels.insert(del_bestFeat, del_labels)    return myTreedef getleaf_num(myTree):    leaf_num=0    Start = next(iter(myTree))    Then = myTree[Start]    for key in Then.keys():        if type(Then[key]).__name__ == 'dict':            leaf_num += getleaf_num(Then[key])        else:            leaf_num += 1    return leaf_numdef getTree_Depth(myTree):    Depth = 0    Start=next(iter(myTree))    Then = myTree[Start]    for key in Then.keys():        if type(Then[key]).__name__ == 'dict':            thisDepth =1 + getTree_Depth(Then[key])        else:            thisDepth = 1    if thisDepth>Depth:Depth=thisDepth    return Depthdef plotNode(nodeTxt, centerPt, parentPt, nodeType):                                           #定义箭头格式    Font = FontPropertIEs(fname=r"c:\windows\Fonts\simsun.ttc", size=14)        #设置中文字体    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点        xytext=centerPt, textcoords='axes fraction',        va="center", ha="center", bBox=nodeType, arrowprops=dict(arrow), FontPropertIEs=Font)"""函数说明:标注有向边属性值"""def plotMIDText(cntrPt, parentPt, txtString):    xMID = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                                            #计算标注位置    yMID = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]    createPlot.ax1.text(xMID, yMID, txtString)"""函数说明:绘制决策树Parameters:    myTree - 决策树(字典)    parentPt - 标注的内容    nodeTxt - 结点名"""def plottree(myTree, parentPt, nodeTxt):    decisionNode = dict(Box, fc="0.8")  # 设置结点格式    leafNode = dict(Box, fc="0.8")    #设置叶结点格式    numLeafs = getleaf_num(myTree)                                                          #获取决策树叶结点数目，决定了树的宽度    depth = getTree_Depth(myTree)                                                            #获取决策树层数    firstStr = next(iter(myTree))                                                            #下个字典    cntrPt = (plottree.xOff + (1.0 + float(numLeafs))/2.0/plottree.totalW, plottree.yOff)    #中心位置    plotMIDText(cntrPt, parentPt, nodeTxt)                                                    #标注有向边属性值    plotNode(firstStr, cntrPt, parentPt, decisionNode)                                        #绘制结点    secondDict = myTree[firstStr]                                                            #下一个字典，也就是继续绘制子结点    plottree.yOff = plottree.yOff - 1.0/plottree.totalD                                        #y偏移    for key in secondDict.keys():        if type(secondDict[key]).__name__=='dict':                                            #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点            plottree(secondDict[key],cntrPt,str(key))                                        #不是叶结点，递归调用继续绘制        else:                                                                                #如果是叶结点，绘制叶结点，并标注有向边属性值            plottree.xOff = plottree.xOff + 1.0/plottree.totalW            plotNode(secondDict[key], (plottree.xOff, plottree.yOff), cntrPt, leafNode)            plotMIDText((plottree.xOff, plottree.yOff), cntrPt, str(key))    plottree.yOff = plottree.yOff + 1.0/plottree.totalD"""函数说明:创建绘制面板Parameters:    inTree - 决策树(字典)"""def createPlot(inTree):    fig = plt.figure(1, facecolor='white')#创建fig    fig.clf()#清空fig    axprops = dict(xticks=[], yticks=[])    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)#去掉x、y轴    plottree.totalW = float(getleaf_num(inTree))#获取决策树叶结点数目    plottree.totalD = float(getTree_Depth(inTree))#获取决策树层数    plottree.xOff = -0.5/plottree.totalW; plottree.yOff = 1.0#x偏移    plottree(inTree, (0.5,1.0), '')#绘制决策树    plt.show()#显示绘制结果if __name__=='__main__':    myDat,labels=creatDataSet()    featLabels = []    myTree=createTree(myDat,labels,featLabels)    createPlot(myTree)

总结

以上是内存溢出为你收集整理的python决策树的实现全部内容，希望文章能够帮你解决python决策树的实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。