决策树案例学习（Python实现）

深碍√TFBOYSˉ_ 2023-07-24 02:03 10阅读 0赞

## 一、介绍 ##

决策树（Decision Tree）是有监督学习中的一种算法，并且是一种基本的分类与回归的方法。有分类树和回归树两种。

决策树的算法本质是树形结构，我们可以把决策树看成是一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：

*  由决策树的根节点到叶节点的每一条路径构建一条规则
 *  路径上中间节点的特征对应着规则的条件，叶节点的类标签对应着规则的结论

决策树的路径或者其对应的if-then规则集合有一个重要的性质：互斥且完备。即每一个实例都被有且仅有一条路径或者规则所覆盖。这里的覆盖指实例的特征与路径上的特征一致，或实例满足规则的条件。

## 二、香农熵和信息增益 ##

#### 香农熵及计算函数： ####

l ( x i ) l(x\_i) l(xi) =  − l o g 2 p ( x i ) -log\_2p(x\_i) −log2p(xi)

E n t ( D ) Ent(D) Ent(D) =  − ∑ i = 1 n p ( x i ) l o g 2 p ( x i ) -\\sum\_\{i=1\}^np(x\_i)log\_2p(x\_i) −∑i=1np(xi)log2p(xi)

E n t ( D ) Ent(D) Ent(D)的值越小，则D的不纯度就越低。

#### 信息增益 ####

G a i n ( D , a ) Gain(D,a) Gain(D,a) =  E n t ( D ) Ent(D) Ent(D) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) -\\sum\_\{v=1\}^V \\frac\{|D^v|\}\{|D|\}Ent(D^v) −∑v=1V∣D∣∣Dv∣Ent(Dv)

Python实现：

#创建数据集，书中海洋生物为例
    import numpy as np
    import pandas as pd
    
    def createDataSet():
        row_data = {'no surfacing':[1,1,1,0,0],
                    'flippers':[1,1,0,1,1],
                    'fish':['yes','yes','no','no','no']}
        dataSet = pd.DataFrame(row_data)
        return dataSet
    
    # 计算香农熵
    def calEnt(dataSet):
        n = dataSet.shape[0] 
        iset = dataSet.iloc[:,-1].value_counts() 
        p = iset/n 
        ent = (-p*np.log2(p)).sum()
        return ent
    
    # 根据信息增益选择出最佳数据集切分的列
    def bestSplit(dataSet):
        baseEnt = calEnt(dataSet) #计算原始熵
        bestGain = 0 #初始化信息增益
        axis = -1 #初始化最佳切分列，标签列
        for i in range(dataSet.shape[1]-1): #对特征的每一列进行循环，-1是不需要对标签列循环
            levels= dataSet.iloc[:,i].value_counts().index #提取出当前列的所有取值
            ents = 0 #初始化子节点的信息熵
            for j in levels: #对当前列的每一个取值进行循环
                childSet = dataSet[dataSet.iloc[:,i]==j] #某一个子节点的dataframe
                ent = calEnt(childSet) #计算某一个子节点的信息熵
                ents += (childSet.shape[0]/dataSet.shape[0])*ent #计算当前列的信息熵
                #print(f'第{i}列的信息熵为{ents}')
            infoGain = baseEnt-ents #计算当前列的信息增益
            #print(f'第{i}列的信息增益为{infoGain}')
            if (infoGain > bestGain):
                bestGain = infoGain #选择最大信息增益
                axis = i #最大信息增益所在列的索引
        return axis
    
    # 按照给定的列划分数据集
    def mySplit(dataSet,axis,value):
        col = dataSet.columns[axis]
        redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)
        return redataSet

三、递归构建决策树

构建决策树的算法有很多，例如ID3、C4.5、CART。在此处选择ID3。

ID3算法的核心是在决策树各个节点上对应信息增益准则选择特征，递归地构建决策树。  
具体做法：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征信息增益均很小或没有特征可以选择为止。最后得到一个决策树。

递归结束的条件：程序遍历完所有的特征列，或者每个分支下的所有实例都具有相同的分类。如果所有实例均具有相同分类，则得到一个叶节点。任何到达叶节点的数据必然属于叶节点的分类，即叶节点里面必须是标签。

def createTree(dataSet):
        featlist = list(dataSet.columns) 
        classlist = dataSet.iloc[:,-1].value_counts() 
        #判断最多标签数目是否等于数据集行数，或者数据集是否只有一列
        if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
            return classlist.index[0] 
        axis = bestSplit(dataSet) 
        bestfeat = featlist[axis] 
        myTree = {bestfeat:{}} 
        del featlist[axis] 
        valuelist = set(dataSet.iloc[:,axis]) 
        for value in valuelist: 
            myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
        return myTree
    
    myTree = createTree(dataSet)
    myTree
    
    #树的存储
    np.save('myTree.npy',myTree)
    
    #树的读取
    read_myTree = np.load('myTree.npy').item()
    read_myTree
    
    # 对一个测试实例进行分类
    def classify(inputTree,labels, testVec):
        firstStr = next(iter(inputTree)) 
        secondDict = inputTree[firstStr] 
        featIndex = labels.index(firstStr)
        for key in secondDict.keys():
            if testVec[featIndex] == key:
                if type(secondDict[key]) == dict :
                    classLabel = classify(secondDict[key], labels, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel
    
    
    # 对测试集进行预测，并返回预测后的结果
    def acc_classify(train,test):
        inputTree = createTree(train)
        labels = list(train.columns)
        result = []
        for i in range(test.shape[0]): 
            testVec = test.iloc[i,:-1] 
            classLabel = classify(inputTree,labels,testVec) 
            result.append(classLabel)
        test['predict']=result 
        acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean() 
        print(f'模型预测准确率为{acc}')
        return test

## 四、使用SKlearn中graphviz绘制决策树 ##

#导入相应的包
    from sklearn import tree
    from sklearn.tree import DecisionTreeClassifier
    import graphviz
    
    #特征
    Xtrain = dataSet.iloc[:,:-1]
    #标签
    Ytrain = dataSet.iloc[:,-1]
    labels = Ytrain.unique().tolist()
    Ytrain = Ytrain.apply(lambda x: labels.index(x))
    
    #绘制树模型
    clf = DecisionTreeClassifier()
    clf = clf.fit(Xtrain, Ytrain)
    tree.export_graphviz(clf)
    dot_data = tree.export_graphviz(clf, out_file=None)
    graphviz.Source(dot_data)
    
    #给图形增加标签和颜色
    dot_data = tree.export_graphviz(clf, out_file=None,
                                    feature_names=['no surfacing', 'flippers'],
                                    class_names=['fish', 'not fish'],
                                    filled=True, rounded=True,
                                    special_characters=True)
    graphviz.Source(dot_data)
    
    #利用render方法生成图形
    graph = graphviz.Source(dot_data)
    graph.render("fish")

五、决策树可视化

# 递归计算叶子节点的数目
    def getNumLeafs(myTree):
        numLeafs = 0 
        firstStr = next(iter(myTree))
        secondDict = myTree[firstStr] 
        for key in secondDict.keys():
            if type(secondDict[key]) == dict: 
                numLeafs += getNumLeafs(secondDict[key]) 
            else:
                numLeafs +=1 #不是字典，代表此结点为叶子结点
        return numLeafs
    
    
    # 递归计算树的深度
    def getTreeDepth(myTree):
        maxDepth = 0
        firstStr = next(iter(myTree))
        secondDict = myTree[firstStr]
        for key in secondDict.keys():
            if type(secondDict[key]) == dict:
                thisDepth = 1+getTreeDepth(secondDict[key])
            else:
                thisDepth = 1
            if thisDepth>maxDepth:
                maxDepth = thisDepth
        return maxDepth
    
    
    # 绘制节点
    def plotNode(nodeTxt, cntrPt, parentPt, nodeType):
        arrow_args = dict(arrowstyle="<-") 
        createPlot.ax1.annotate(nodeTxt,
                                xy=parentPt,xycoords='axes fraction',  
                                # axes fraction
                                xytext=cntrPt, textcoords='axes fraction',
                                va="center", ha="center",
                                bbox=nodeType,
                                arrowprops=arrow_args)
    
    
    # 标注有向边属性值
    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, va="center", ha="center", rotation=0)
    
    
    # 绘制决策树
    def plotTree(myTree, parentPt, nodeTxt):
        decisionNode = dict(boxstyle="sawtooth", fc="0.8") 
        leafNode = dict(boxstyle="round4", fc="0.8")
        numLeafs = getNumLeafs(myTree) 
        depth = getTreeDepth(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 
        for key in secondDict.keys():
            if type(secondDict[key])== 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
    
    
    # 创建绘制面板
    def createPlot(inTree):
        fig = plt.figure(1, facecolor='white')
        fig.clf() 
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) 
        plotTree.totalW = float(getNumLeafs(inTree)) 
        plotTree.totalD = float(getTreeDepth(inTree))
        plotTree.xOff = -0.5/plotTree.totalW
        plotTree.yOff = 1.0 
        plotTree(inTree, (0.5,1.0), '') 
        plt.show()

## 六、使用决策树预测隐形眼镜 ##

# 导入数据集
    lenses = pd.read_table('lenses.txt',header = None)
    lenses.columns =['age','prescript','astigmatic','tearRate','class']
    
    
    # 划分训练集和测试集
    import random
    def randSplit(dataSet, rate):
        l = list(dataSet.index) #提取出索引
        random.shuffle(l) #随机打乱索引
        dataSet.index = l #将打乱后的索引重新赋值给原数据集
        n = dataSet.shape[0] #总行数
        m = int(n * rate) #训练集的数量
        train = dataSet.loc[range(m), :] #提取前m个记录作为训练集
        test = dataSet.loc[range(m, n), :] #剩下的作为测试集
        dataSet.index = range(dataSet.shape[0]) #更新原数据集的索引
        test.index = range(test.shape[0]) #更新测试集的索引
        return train, test
    
    
    #利用训练集生成决策树
    lensesTree = createTree(train1)
    lensesTree
    
    #构造注解树
    createPlot(lensesTree)
    
    #用决策树进行分类并计算有预测准确率
    acc_classify(train1,test1)
    
    # 使用SKlearn中graphviz绘制决策树
    #特征列
    Xtrain1 = train1.iloc[:,:-1]
    for i in Xtrain1.columns:
        labels = Xtrain1[i].unique().tolist()
        Xtrain1[i]= Xtrain1[i].apply(lambda x: labels.index(x))
    
    #标签列
    Ytrain1 = train1.iloc[:,-1]
    labels = Ytrain1.unique().tolist()
    Ytrain1= Ytrain1.apply(lambda x: labels.index(x))
    
    #绘制树形图
    clf = DecisionTreeClassifier()
    clf = clf.fit(Xtrain1, Ytrain1)
    tree.export_graphviz(clf)
    dot_data = tree.export_graphviz(clf, out_file=None)
    graphviz.Source(dot_data)
    
    #添加标签和颜色
    dot_data = tree.export_graphviz(clf, out_file=None,
                                    feature_names=['age', 'prescript', 'astigmatic','tearRate'],
                                    class_names=['soft','hard','no lenses'],
                                    filled=True, rounded=True,special_characters=True)
    graphviz.Source(dot_data)
    
    #使用render存储树形图
    graph = graphviz.Source(dot_data)
    graph.render("lense")

## 七、算法优缺点 ##

#### 优点： ####

（1）决策树可以可视化，易于理解和解释;

（2）数据准备工作很少。其他很多算法通常都需要数据规范化，需要创建虚拟变量并删除空值等;

（3）能够同时处理数值和分类数据，既可以做回归又可以做分类。其他技术通常专门用于分析仅具有一种变类型的数据集;

（4）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度;

（5）能够处理多输出问题，即含有多个标签的问题，注意与一个标签中含有 多种标签分类的问题区别开;

（6）是一个白盒模型，结果很容易能够被解释。如果在模型中可以观察到给定的情况，则可以通过布尔逻辑轻松解释条件。相反,在黑盒模型中(例如，在人工神经网络中)，结果可能更难以解释。

#### 缺点： ####

（1）递归生成树的方法很容易出现过拟合。

（2）决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树

（3）如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在拟合决策树之前平衡数据集。