精华内容
下载资源
问答
  • 决策树python实现

    热门讨论 2014-03-10 21:36:25
    基于python逐步实现Decision Tree(决策树),分为以下几块: 加载数据集 熵的计算 根据最佳分割feature进行数据分割 根据最大信息增益选择最佳分割feature 递归构建决策树 样本分类
  • 决策树Python 实现——决策树回归

    千次阅读 2019-10-07 18:34:32
    原文以及代码来自于,本人对每段代码进行了详细注释,...决策树回归 Decision Tree Regression 带有决策树的 1D 回归。 决策树用于拟合正数曲线和加噪声观测。因此,它学习接近主数曲线的局部线性回归。 我们可以...

    原文以及代码来自于,本人对每段代码进行了详细注释,希望对初学者有用。
    https://scikit-learn.org/stable/auto_examples/tree/plot_tree_regression.html
    决策树回归 Decision Tree Regression
    带有决策树的 1D 回归。
    决策树用于拟合正数曲线和加噪声观测。因此,它学习接近主数曲线的局部线性回归。
    我们可以看到,如果树的最大深度(由最大深度参数控制)设置得过高,则决策树会学习训练数据的细节,并从噪声中学习,即它们过度拟合。
    在这里插入图片描述

    print(__doc__)
    
    # Import the necessary modules and libraries
    import numpy as np
    from sklearn.tree import DecisionTreeRegressor
    import matplotlib.pyplot as plt
    
    # Create a random dataset
    rng = np.random.RandomState(1)
    X = np.sort(5 * rng.rand(80, 1), axis=0)
    y = np.sin(X).ravel()
    y[::5] += 3 * (0.5 - rng.rand(16))
    '''
    numpy.random.RandomState()是一个伪随机数生成器。那么伪随机数是什么呢? ()括号内是seed,确保不同电脑上产生相同的伪随机数
    伪随机数是用确定性的算法计算出来的似来自[0,1]均匀分布的随机数序列。并不真正的随机,但具有类似于随机数的统计特征,如均匀性、独立性等。
    运行一下下面两个
    rng = np.random.RandomState(1)
    x = rng.rand(4)
    y = rng.rand(4)
    rng = np.random.RandomState(1)
    x = rng.rand(4)
    rng = np.random.RandomState(1)
    y = rng.rand(4)
    
    .sort axis =0 每列从小到大排列
    import numpy as np
    x=np.array([[0,12,48],[4,18,14],[7,1,99]])
    np.sort(x)
    Out[61]: 
    array([[ 0, 12, 48],
           [ 4, 14, 18],
           [ 1,  7, 99]])
    np.sort(x, axis=0)
    Out[62]: 
    array([[ 0,  1, 14],
           [ 4, 12, 48],
           [ 7, 18, 99]])
    np.sort(x, axis=1)
    Out[63]: 
    array([[ 0, 12, 48],
           [ 4, 14, 18],
           [ 1,  7, 99]]) 
           
    .ravel() 将多维数组降位一维
    
    y[::5] 从开始到结束,每隔5个数,第0个开始取出算起,更加详细的取数组元素方式可以参看下面链接
    https://blog.csdn.net/sinat_34474705/article/details/74458605
    '''
    
    # Fit regression model
    regr_1 = DecisionTreeRegressor(max_depth=2)
    regr_2 = DecisionTreeRegressor(max_depth=5)
    regr_1.fit(X, y)
    regr_2.fit(X, y)
    
    # Predict
    X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
    y_1 = regr_1.predict(X_test)
    y_2 = regr_2.predict(X_test)
    '''
    [:, np.newaxis], 将一行数据转换为一列数据,每行是一个一维输入,每列是一个feature,这个例子只有一个feature
    '''
    
    
    # Plot the results
    plt.figure()
    plt.scatter(X, y, s=20, edgecolor="black",
                c="darkorange", label="data")
    plt.plot(X_test, y_1, color="cornflowerblue",
             label="max_depth=2", linewidth=2)
    plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
    plt.xlabel("data")
    plt.ylabel("target")
    plt.title("Decision Tree Regression")
    plt.legend()
    plt.show()
    
    展开全文
  • 决策树python源码实现(含预剪枝和后剪枝)

    千次阅读 多人点赞 2019-06-21 19:30:41
    决策树python源码实现(含预剪枝和后剪枝) 一、说明         所用的环境为Ubuntu + python 3.6,在jupyter中运行。本文实现周志华《机器学习》西瓜书中的4.1 ~ 4.3中的...

    决策树python源码实现(含预剪枝和后剪枝)

    一、说明

            所用的环境为Ubuntu + python 3.6,在jupyter中运行。本文实现周志华《机器学习》西瓜书中的4.1 ~ 4.3中的决策树算法(不含连续值、缺失值处理),对应李航《统计学习方法》的5.1 ~ 5.4节。画图工具参考《机器学习实战》中的部分代码,本文树的生成代码大部分由自己完成,部分思路可能与该书有差异。另外本文程序的效率应该比《机器学习实战》的高,因为该书上有很多逐个样本的遍历,在本文中则使用numpy直接操作向量实现。
             由于个人理解问题,并且未经过大量数据的测试,算法实现可能会存在问题或值得改进的地方,请遇到的朋友帮忙指出,共同学习!
             代码中有足够的注释!

    二、代码实现

    1. 开始
    import math
    import numpy as np 
    
    1. 创建数据
    # 创建数据集 备注 李航《统计学习方法》中表5.1 贷款申请数据数据
    def createDataLH():
        data = np.array([['青年', '否', '否', '一般']])
        data = np.append(data, [['青年', '否', '否', '好']], axis = 0)
        data = np.append(data, [['青年', '是', '否', '好'] 
                                , ['青年', '是', '是', '一般']
                                , ['青年', '否', '否', '一般']
                                , ['中年', '否', '否', '一般']
                                , ['中年', '否', '否', '好']
                                , ['中年', '是', '是', '好']
                                , ['中年', '否', '是', '非常好']
                                , ['中年', '否', '是', '非常好']
                                , ['老年', '否', '是', '非常好']
                                , ['老年', '否', '是', '好']
                                , ['老年', '是', '否', '好']
                                , ['老年', '是', '否', '非常好']
                                , ['老年', '否', '否', '一般']
                               ], axis = 0)
        label = np.array(['否', '否', '是', '是', '否', '否', '否', '是', '是', '是', '是', '是', '是', '是', '否'])
        name = np.array(['年龄', '有工作', '有房子', '信贷情况'])
        return data, label, name
    
    # 创建西瓜书数据集2.0
    def createDataXG20():
        data = np.array([['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
                        , ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑']
                        , ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
                        , ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑']
                        , ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
                        , ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘']
                        , ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘']
                        , ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑']
                        , ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑']
                        , ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘']
                        , ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑']
                        , ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘']
                        , ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑']
                        , ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑']
                        , ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘']
                        , ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑']
                        , ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']])
        label = np.array(['是', '是', '是', '是', '是', '是', '是', '是', '否', '否', '否', '否', '否', '否', '否', '否', '否'])
        name = np.array(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感'])
        return data, label, name
    
    def splitXgData20(xgData, xgLabel):
        xgDataTrain = xgData[[0, 1, 2, 5, 6, 9, 13, 14, 15, 16],:]
        xgDataTest = xgData[[3, 4, 7, 8, 10, 11, 12],:]
        xgLabelTrain = xgLabel[[0, 1, 2, 5, 6, 9, 13, 14, 15, 16]]
        xgLabelTest = xgLabel[[3, 4, 7, 8, 10, 11, 12]]
        return xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest
    
    
    1. 创建基础函数
      如计算熵、计算条件熵、信息增益、信息增益率等
    # 定义一个常用函数 用来求numpy array中数值等于某值的元素数量
    equalNums = lambda x,y: 0 if x is None else x[x==y].size
    
    
    # 定义计算信息熵的函数
    def singleEntropy(x):
        """计算一个输入序列的信息熵"""
        # 转换为 numpy 矩阵
        x = np.asarray(x)
        # 取所有不同值
        xValues = set(x)
        # 计算熵值
        entropy = 0
        for xValue in xValues:
            p = equalNums(x, xValue) / x.size 
            entropy -= p * math.log(p, 2)
        return entropy
        
        
    # 定义计算条件信息熵的函数
    def conditionnalEntropy(feature, y):
        """计算 某特征feature 条件下y的信息熵"""
        # 转换为numpy 
        feature = np.asarray(feature)
        y = np.asarray(y)
        # 取特征的不同值
        featureValues = set(feature)
        # 计算熵值 
        entropy = 0
        for feat in featureValues:
            # 解释:feature == feat 是得到取feature中所有元素值等于feat的元素的索引(类似这样理解)
            #       y[feature == feat] 是取y中 feature元素值等于feat的元素索引的 y的元素的子集
            p = equalNums(feature, feat) / feature.size 
            entropy += p * singleEntropy(y[feature == feat])
        return entropy
        
        
    # 定义信息增益
    def infoGain(feature, y):
        return singleEntropy(y) - conditionnalEntropy(feature, y)
    
    
    # 定义信息增益率
    def infoGainRatio(feature, y):
        return 0 if singleEntropy(feature) == 0 else infoGain(feature, y) / singleEntropy(feature)
    

    函数功能测试
    使用李航数据测试函数 p62

    # 使用李航数据测试函数 p62
    lhData, lhLabel, lhName = createDataLH()
    print("书中H(D)为0.971,函数结果:" + str(round(singleEntropy(lhLabel), 3)))  
    print("书中g(D, A1)为0.083,函数结果:" + str(round(infoGain(lhData[:,0] ,lhLabel), 3)))  
    print("书中g(D, A2)为0.324,函数结果:" + str(round(infoGain(lhData[:,1] ,lhLabel), 3)))  
    print("书中g(D, A3)为0.420,函数结果:" + str(round(infoGain(lhData[:,2] ,lhLabel), 3)))  
    print("书中g(D, A4)为0.363,函数结果:" + str(round(infoGain(lhData[:,3] ,lhLabel), 3)))  
    # 测试正常,与书中结果一致
    

    运行结果

    书中H(D)为0.971,函数结果:0.971
    书中g(D, A1)为0.083,函数结果:0.083
    书中g(D, A2)为0.324,函数结果:0.324
    书中g(D, A3)为0.420,函数结果:0.42
    书中g(D, A4)为0.363,函数结果:0.363
    

    使用西瓜数据测试函数 p75-p77

    # 使用西瓜数据测试函数  p75-p77
    xgData, xgLabel, xgName = createDataXG20()
    print("书中Ent(D)为0.998,函数结果:" + str(round(singleEntropy(xgLabel), 4)))  
    print("书中Gain(D, 色泽)为0.109,函数结果:" + str(round(infoGain(xgData[:,0] ,xgLabel), 4)))  
    print("书中Gain(D, 根蒂)为0.143,函数结果:" + str(round(infoGain(xgData[:,1] ,xgLabel), 4)))  
    print("书中Gain(D, 敲声)为0.141,函数结果:" + str(round(infoGain(xgData[:,2] ,xgLabel), 4)))  
    print("书中Gain(D, 纹理)为0.381,函数结果:" + str(round(infoGain(xgData[:,3] ,xgLabel), 4)))  
    print("书中Gain(D, 脐部)为0.289,函数结果:" + str(round(infoGain(xgData[:,4] ,xgLabel), 4)))  
    print("书中Gain(D, 触感)为0.006,函数结果:" + str(round(infoGain(xgData[:,5] ,xgLabel), 4)))  
    

    运行结果

    书中Ent(D)为0.998,函数结果:0.9975
    书中Gain(D, 色泽)为0.109,函数结果:0.1081
    书中Gain(D, 根蒂)为0.143,函数结果:0.1427
    书中Gain(D, 敲声)为0.141,函数结果:0.1408
    书中Gain(D, 纹理)为0.381,函数结果:0.3806
    书中Gain(D, 脐部)为0.289,函数结果:0.2892
    书中Gain(D, 触感)为0.006,函数结果:0.006
    

    测试结果与书中数据基本一致

    1. 创建树生成相关函数
      如 特征选取、数据分割、多数投票、树生成、使用树分类、树信息统计
    # 特征选取
    def bestFeature(data, labels, method = 'id3'):
        assert method in ['id3', 'c45'], "method 须为id3或c45"
        data = np.asarray(data)
        labels = np.asarray(labels)
        # 根据输入的method选取 评估特征的方法:id3 -> 信息增益; c45 -> 信息增益率
        def calcEnt(feature, labels):
            if method == 'id3':
                return infoGain(feature, labels)
            elif method == 'c45' :
                return infoGainRatio(feature, labels)
        # 特征数量  即 data 的列数量
        featureNum = data.shape[1]
        # 计算最佳特征
        bestEnt = 0 
        bestFeat = -1
        for feature in range(featureNum):
            ent = calcEnt(data[:, feature], labels)
            if ent >= bestEnt:
                bestEnt = ent 
                bestFeat = feature
            # print("feature " + str(feature + 1) + " ent: " + str(ent)+ "\t bestEnt: " + str(bestEnt))
        return bestFeat, bestEnt 
    
    
    # 根据特征及特征值分割原数据集  删除data中的feature列,并根据feature列中的值分割 data和label
    def splitFeatureData(data, labels, feature):
        """feature 为特征列的索引"""
        # 取特征列
        features = np.asarray(data)[:,feature]
        # 数据集中删除特征列
        data = np.delete(np.asarray(data), feature, axis = 1)
        # 标签
        labels = np.asarray(labels)
        
        uniqFeatures = set(features)
        dataSet = {}
        labelSet = {}
        for feat in uniqFeatures:
            dataSet[feat] = data[features == feat]
            labelSet[feat] = labels[features == feat]
        return dataSet, labelSet
        
        
    # 多数投票 
    def voteLabel(labels):
        uniqLabels = list(set(labels))
        labels = np.asarray(labels)
    
        finalLabel = 0
        labelNum = []
        for label in uniqLabels:
            # 统计每个标签值得数量
            labelNum.append(equalNums(labels, label))
        # 返回数量最大的标签
        return uniqLabels[labelNum.index(max(labelNum))]
    
    
    # 创建决策树
    def createTree(data, labels, names, method = 'id3'):
        data = np.asarray(data)
        labels = np.asarray(labels)
        names = np.asarray(names)
        # 如果结果为单一结果
        if len(set(labels)) == 1: 
            return labels[0] 
        # 如果没有待分类特征
        elif data.size == 0: 
            return voteLabel(labels)
        # 其他情况则选取特征 
        bestFeat, bestEnt = bestFeature(data, labels, method = method)
        # 取特征名称
        bestFeatName = names[bestFeat]
        # 从特征名称列表删除已取得特征名称
        names = np.delete(names, [bestFeat])
        # 根据选取的特征名称创建树节点
        decisionTree = {bestFeatName: {}}
        # 根据最优特征进行分割
        dataSet, labelSet = splitFeatureData(data, labels, bestFeat)
        # 对最优特征的每个特征值所分的数据子集进行计算
        for featValue in dataSet.keys():
            decisionTree[bestFeatName][featValue] = createTree(dataSet.get(featValue), labelSet.get(featValue), names, method)
        return decisionTree 
    
    
    # 树信息统计 叶子节点数量 和 树深度
    def getTreeSize(decisionTree):
        nodeName = list(decisionTree.keys())[0]
        nodeValue = decisionTree[nodeName]
        leafNum = 0
        treeDepth = 0 
        leafDepth = 0
        for val in nodeValue.keys():
            if type(nodeValue[val]) == dict:
                leafNum += getTreeSize(nodeValue[val])[0]
                leafDepth = 1 + getTreeSize(nodeValue[val])[1] 
            else :
                leafNum += 1 
                leafDepth = 1 
            treeDepth = max(treeDepth, leafDepth)
        return leafNum, treeDepth 
    
    
    # 使用模型对其他数据分类
    def dtClassify(decisionTree, rowData, names):
        names = list(names)
        # 获取特征
        feature = list(decisionTree.keys())[0]
        # 决策树对于该特征的值的判断字段
        featDict = decisionTree[feature]
        # 获取特征的列
        feat = names.index(feature)
        # 获取数据该特征的值
        featVal = rowData[feat]
        # 根据特征值查找结果,如果结果是字典说明是子树,调用本函数递归
        if featVal in featDict.keys():
            if type(featDict[featVal]) == dict:
                classLabel = dtClassify(featDict[featVal], rowData, names)
            else:
                classLabel = featDict[featVal] 
        return classLabel
    
    1. 树可视化
      画图的方法主要参考《机器学习实战》,细节有较多改动。画图时须提前配置好支持中文的画图。
    # 可视化 主要源自《机器学习实战》
    import matplotlib.pyplot as plt 
    
    decisionNodeStyle = dict(boxstyle = "sawtooth", fc = "0.8")
    leafNodeStyle = {"boxstyle": "round4", "fc": "0.8"}
    arrowArgs = {"arrowstyle": "<-"}
    
    
    # 画节点
    def plotNode(nodeText, centerPt, parentPt, nodeStyle):
        createPlot.ax1.annotate(nodeText, xy = parentPt, xycoords = "axes fraction", xytext = centerPt
                                , textcoords = "axes fraction", va = "center", ha="center", bbox = nodeStyle, arrowprops = arrowArgs)
    
    
    # 添加箭头上的标注文字
    def plotMidText(centerPt, parentPt, lineText):
        xMid = (centerPt[0] + parentPt[0]) / 2.0
        yMid = (centerPt[1] + parentPt[1]) / 2.0 
        createPlot.ax1.text(xMid, yMid, lineText)
        
        
    # 画树
    def plotTree(decisionTree, parentPt, parentValue):
        # 计算宽与高
        leafNum, treeDepth = getTreeSize(decisionTree) 
        # 在 1 * 1 的范围内画图,因此分母为 1
        # 每个叶节点之间的偏移量
        plotTree.xOff = plotTree.figSize / (plotTree.totalLeaf - 1)
        # 每一层的高度偏移量
        plotTree.yOff = plotTree.figSize / plotTree.totalDepth
        # 节点名称
        nodeName = list(decisionTree.keys())[0]
        # 根节点的起止点相同,可避免画线;如果是中间节点,则从当前叶节点的位置开始,
        #      然后加上本次子树的宽度的一半,则为决策节点的横向位置
        centerPt = (plotTree.x + (leafNum - 1) * plotTree.xOff / 2.0, plotTree.y)
        # 画出该决策节点
        plotNode(nodeName, centerPt, parentPt, decisionNodeStyle)
        # 标记本节点对应父节点的属性值
        plotMidText(centerPt, parentPt, parentValue)
        # 取本节点的属性值
        treeValue = decisionTree[nodeName]
        # 下一层各节点的高度
        plotTree.y = plotTree.y - plotTree.yOff
        # 绘制下一层
        for val in treeValue.keys():
            # 如果属性值对应的是字典,说明是子树,进行递归调用; 否则则为叶子节点
            if type(treeValue[val]) == dict:
                plotTree(treeValue[val], centerPt, str(val))
            else:
                plotNode(treeValue[val], (plotTree.x, plotTree.y), centerPt, leafNodeStyle)
                plotMidText((plotTree.x, plotTree.y), centerPt, str(val))
                # 移到下一个叶子节点
                plotTree.x = plotTree.x + plotTree.xOff
        # 递归完成后返回上一层
        plotTree.y = plotTree.y + plotTree.yOff
        
        
    # 画出决策树
    def createPlot(decisionTree):
        fig = plt.figure(1, facecolor = "white")
        fig.clf()
        axprops = {"xticks": [], "yticks": []}
        createPlot.ax1 = plt.subplot(111, frameon = False, **axprops)
        # 定义画图的图形尺寸
        plotTree.figSize = 1.5 
        # 初始化树的总大小
        plotTree.totalLeaf, plotTree.totalDepth = getTreeSize(decisionTree)
        # 叶子节点的初始位置x 和 根节点的初始层高度y
        plotTree.x = 0 
        plotTree.y = plotTree.figSize
        plotTree(decisionTree, (plotTree.figSize / 2.0, plotTree.y), "")
        plt.show()
    
    1. 使用示例数据进行测试
      使用李航的数据
    # 使用李航数据测试函数 p62
    lhData, lhLabel, lhName = createDataLH()
    lhTree = createTree(lhData, lhLabel, lhName, method = 'id3')
    print(lhTree)
    createPlot(lhTree)
    

    输出如下
    李航数据的结果

    # 使用西瓜数据测试函数  p75-p77
    xgData, xgLabel, xgName = createDataXG20()
    xgTree = createTree(xgData, xgLabel, xgName, method = 'id3')
    print(xgTree)
    createPlot(xgTree)
    

    输出如下
    西瓜数据2.0的结果备注:西瓜数据的结果与书上可能有差异,原因是西瓜数据在特征选择时,有多个特征信息增益(率)是相同的,本文算法的选择就容易和书上的选择有出入。

    1. 预剪枝
      仅供参考
    # 创建预剪枝决策树
    def createTreePrePruning(dataTrain, labelTrain, dataTest, labelTest, names, method = 'id3'):
        """
        预剪枝 需要使用测试数据对每次的划分进行评估
             策略说明:原本如果某节点划分前后的测试结果没有提升,根据奥卡姆剃刀原则将不进行划分(即执行剪枝),但考虑到这种策略容易造成欠拟合,
                       且不能排除后续划分有进一步提升的可能,因此,没有提升仍保留划分,即不剪枝
             另外:周志华的书上评估的是某一个节点划分前后对该层所有数据综合评估,如评估对脐部 凹陷下色泽是否划分,
                   书上取的色泽划分前的精度是71.4%(5/7),划分后的精度是57.1%(4/7),都是脐部下三个特征(凹陷,稍凹,平坦)所有的数据的精度,计算也不易
                   而我觉得实际计算时,只对当前节点下的数据划分前后进行评估即可,如脐部凹陷时有三个测试样本,
                   三个样本色泽划分前的精度是2/3=66.7%,色泽划分后的精度是1/3=33.3%,因此判断不划分
        """
        trainData = np.asarray(dataTrain)
        labelTrain = np.asarray(labelTrain)
        testData = np.asarray(dataTest)
        labelTest = np.asarray(labelTest)
        names = np.asarray(names)
        # 如果结果为单一结果
        if len(set(labelTrain)) == 1: 
            return labelTrain[0] 
        # 如果没有待分类特征
        elif trainData.size == 0: 
            return voteLabel(labelTrain)
        # 其他情况则选取特征 
        bestFeat, bestEnt = bestFeature(dataTrain, labelTrain, method = method)
        # 取特征名称
        bestFeatName = names[bestFeat]
        # 从特征名称列表删除已取得特征名称
        names = np.delete(names, [bestFeat])
        # 根据最优特征进行分割
        dataTrainSet, labelTrainSet = splitFeatureData(dataTrain, labelTrain, bestFeat)
    
        # 预剪枝评估
        # 划分前的分类标签
        labelTrainLabelPre = voteLabel(labelTrain)
        labelTrainRatioPre = equalNums(labelTrain, labelTrainLabelPre) / labelTrain.size
        # 划分后的精度计算 
        if dataTest is not None: 
            dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, bestFeat)
            # 划分前的测试标签正确比例
            labelTestRatioPre = equalNums(labelTest, labelTrainLabelPre) / labelTest.size
            # 划分后 每个特征值的分类标签正确的数量
            labelTrainEqNumPost = 0
            for val in labelTrainSet.keys():
                labelTrainEqNumPost += equalNums(labelTestSet.get(val), voteLabel(labelTrainSet.get(val))) + 0.0
            # 划分后 正确的比例
            labelTestRatioPost = labelTrainEqNumPost / labelTest.size 
        
        # 如果没有评估数据 但划分前的精度等于最小值0.5 则继续划分
        if dataTest is None and labelTrainRatioPre == 0.5:
            decisionTree = {bestFeatName: {}}
            for featValue in dataTrainSet.keys():
                decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
                                          , None, None, names, method)
        elif dataTest is None:
            return labelTrainLabelPre 
        # 如果划分后的精度相比划分前的精度下降, 则直接作为叶子节点返回
        elif labelTestRatioPost < labelTestRatioPre:
            return labelTrainLabelPre
        else :
            # 根据选取的特征名称创建树节点
            decisionTree = {bestFeatName: {}}
            # 对最优特征的每个特征值所分的数据子集进行计算
            for featValue in dataTrainSet.keys():
                decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
                                          , dataTestSet.get(featValue), labelTestSet.get(featValue)
                                          , names, method)
        return decisionTree 
    

    预剪枝测试

    # 将西瓜数据2.0分割为测试集和训练集
    xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest = splitXgData20(xgData, xgLabel)
    # 生成不剪枝的树
    xgTreeTrain = createTree(xgDataTrain, xgLabelTrain, xgName, method = 'id3')
    # 生成预剪枝的树
    xgTreePrePruning = createTreePrePruning(xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest, xgName, method = 'id3')
    # 画剪枝前的树
    print("剪枝前的树")
    createPlot(xgTreeTrain)
    # 画剪枝后的树
    print("剪枝后的树")
    createPlot(xgTreePrePruning)
    

    输出结果
    预剪枝结果对比备注,由于特征选择的问题,结果与书上有差异。

    1. 后剪枝

    后剪枝评估时需要划分前的标签,这里思考两种方法:
            一是,不改变原来的训练函数,评估时使用训练数据对划分前的节点标签重新打标
            二是,改进训练函数,在训练的同时为每个节点增加划分前的标签,这样可以保证评估时只使用测试数据,避免再次使用大量的训练数据
            这里采用第二种方法 写新的函数 createTreeWithLabel,当然也可以修改createTree来添加参数实现

    另外,后剪枝的程序代码中有很多过程中的提示信息,已注释掉。

    # 创建决策树 带预划分标签
    def createTreeWithLabel(data, labels, names, method = 'id3'):
        data = np.asarray(data)
        labels = np.asarray(labels)
        names = np.asarray(names)
        # 如果不划分的标签为
        votedLabel = voteLabel(labels)
        # 如果结果为单一结果
        if len(set(labels)) == 1: 
            return votedLabel 
        # 如果没有待分类特征
        elif data.size == 0: 
            return votedLabel
        # 其他情况则选取特征 
        bestFeat, bestEnt = bestFeature(data, labels, method = method)
        # 取特征名称
        bestFeatName = names[bestFeat]
        # 从特征名称列表删除已取得特征名称
        names = np.delete(names, [bestFeat])
        # 根据选取的特征名称创建树节点 划分前的标签votedPreDivisionLabel=_vpdl
        decisionTree = {bestFeatName: {"_vpdl": votedLabel}}
        # 根据最优特征进行分割
        dataSet, labelSet = splitFeatureData(data, labels, bestFeat)
        # 对最优特征的每个特征值所分的数据子集进行计算
        for featValue in dataSet.keys():
            decisionTree[bestFeatName][featValue] = createTreeWithLabel(dataSet.get(featValue), labelSet.get(featValue), names, method)
        return decisionTree 
    
    
    # 将带预划分标签的tree转化为常规的tree
    # 函数中进行的copy操作,原因见有道笔记 【YL20190621】关于Python中字典存储修改的思考
    def convertTree(labeledTree):
        labeledTreeNew = labeledTree.copy()
        nodeName = list(labeledTree.keys())[0]
        labeledTreeNew[nodeName] = labeledTree[nodeName].copy()
        for val in list(labeledTree[nodeName].keys()):
            if val == "_vpdl": 
                labeledTreeNew[nodeName].pop(val)
            elif type(labeledTree[nodeName][val]) == dict:
                labeledTreeNew[nodeName][val] = convertTree(labeledTree[nodeName][val])
        return labeledTreeNew
    
    
    # 后剪枝 训练完成后决策节点进行替换评估  这里可以直接对xgTreeTrain进行操作
    def treePostPruning(labeledTree, dataTest, labelTest, names):
        newTree = labeledTree.copy()
        dataTest = np.asarray(dataTest)
        labelTest = np.asarray(labelTest)
        names = np.asarray(names)
        # 取决策节点的名称 即特征的名称
        featName = list(labeledTree.keys())[0]
        # print("\n当前节点:" + featName)
        # 取特征的列
        featCol = np.argwhere(names==featName)[0][0]
        names = np.delete(names, [featCol])
        # print("当前节点划分的数据维度:" + str(names))
        # print("当前节点划分的数据:" )
        # print(dataTest)
        # print(labelTest)
        # 该特征下所有值的字典
        newTree[featName] = labeledTree[featName].copy()
        featValueDict = newTree[featName]
        featPreLabel = featValueDict.pop("_vpdl")
        # print("当前节点预划分标签:" + featPreLabel)
        # 是否为子树的标记
        subTreeFlag = 0
        # 分割测试数据 如果有数据 则进行测试或递归调用  np的array我不知道怎么判断是否None, 用is None是错的
        dataFlag = 1 if sum(dataTest.shape) > 0 else 0
        if dataFlag == 1:
            # print("当前节点有划分数据!")
            dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, featCol)
        for featValue in featValueDict.keys():
            # print("当前节点属性 {0} 的子节点:{1}".format(featValue ,str(featValueDict[featValue])))
            if dataFlag == 1 and type(featValueDict[featValue]) == dict:
                subTreeFlag = 1 
                # 如果是子树则递归
                newTree[featName][featValue] = treePostPruning(featValueDict[featValue], dataTestSet.get(featValue), labelTestSet.get(featValue), names)
                # 如果递归后为叶子 则后续进行评估
                if type(featValueDict[featValue]) != dict:
                    subTreeFlag = 0 
                
            # 如果没有数据  则转换子树
            if dataFlag == 0 and type(featValueDict[featValue]) == dict: 
                subTreeFlag = 1 
                # print("当前节点无划分数据!直接转换树:"+str(featValueDict[featValue]))
                newTree[featName][featValue] = convertTree(featValueDict[featValue])
                # print("转换结果:" + str(convertTree(featValueDict[featValue])))
        # 如果全为叶子节点, 评估需要划分前的标签,这里思考两种方法,
        #     一是,不改变原来的训练函数,评估时使用训练数据对划分前的节点标签重新打标
        #     二是,改进训练函数,在训练的同时为每个节点增加划分前的标签,这样可以保证评估时只使用测试数据,避免再次使用大量的训练数据
        #     这里考虑第二种方法 写新的函数 createTreeWithLabel,当然也可以修改createTree来添加参数实现
        if subTreeFlag == 0:
            ratioPreDivision = equalNums(labelTest, featPreLabel) / labelTest.size
            equalNum = 0
            for val in labelTestSet.keys():
                equalNum += equalNums(labelTestSet[val], featValueDict[val])
            ratioAfterDivision = equalNum / labelTest.size 
            # print("当前节点预划分标签的准确率:" + str(ratioPreDivision))
            # print("当前节点划分后的准确率:" + str(ratioAfterDivision))
            # 如果划分后的测试数据准确率低于划分前的,则划分无效,进行剪枝,即使节点等于预划分标签
            # 注意这里取的是小于,如果有需要 也可以取 小于等于
            if ratioAfterDivision < ratioPreDivision:
                newTree = featPreLabel 
        return newTree
    

    代码测试,我对自己训练的模型和书上生成的模型都进行了测试,这里篇幅限制,且尽量保持与书中一致,仅提供书上模型的后剪枝

    # 书中的树结构 p81 p83
    xgTreeBeforePostPruning = {"脐部": {"_vpdl": "是"
                                       , '凹陷': {'色泽':{"_vpdl": "是", '青绿': '是', '乌黑': '是', '浅白': '否'}}
                                       , '稍凹': {'根蒂':{"_vpdl": "是"
                                                      , '稍蜷': {'色泽': {"_vpdl": "是"
                                                                      , '青绿': '是'
                                                                      , '乌黑': {'纹理': {"_vpdl": "是"
                                                                                   , '稍糊': '是', '清晰': '否', '模糊': '是'}}
                                                                      , '浅白': '是'}}
                                                      , '蜷缩': '否'
                                                      , '硬挺': '是'}}
                                       , '平坦': '否'}}
    xgTreePostPruning = treePostPruning(xgTreeBeforePostPruning, xgDataTest, xgLabelTest, xgName)
    createPlot(convertTree(xgTreeBeforePostPruning))
    createPlot(xgTreePostPruning)
    

    输出结果
    书中模型的后剪枝结论:对比书中p81和p83的图4.5和图4.7,与以上程序输出一致!
    图p81
    p81的图
    图p83
    图p83

    展开全文
  • 决策树python sklearn 示例

    千次阅读 2017-10-11 20:47:58
    本文主要是使用python sklearn,完成决策树的demo,以及可视化,最终生成的决策树结果。from sklearn.datasets import load_iris from sklearn import tree from sklearn.tree import export_graphviz import ...

    本文主要是使用python sklearn,完成决策树的demo,以及可视化,最终生成的决策树结果。

    from sklearn.datasets import load_iris
    from sklearn import tree
    from sklearn.tree import export_graphviz
    import subprocess
    
    
    def visualize_tree(tree, feature_name, dot_file):
        """Create tree png using graphviz.
        tree -- scikit-learn DecsisionTree.
        feature_names -- list of feature names.
        dot_file -- dot file name and path
        """
        with open("tree.dot", 'w') as f:
            export_graphviz(tree, out_file=f,
                            feature_names=feature_name)
    
        dt_png = "dt.png"
        command = ["dot", "-Tpng", dot_file, "-o", dt_png]
        try:
            subprocess.check_call(command)
        except Exception as e:
            print e
            exit("Could not run dot, ie graphviz, to "
                 "produce visualization")
    
    
    def iris_demo():
        clf = tree.DecisionTreeClassifier()
        iris = load_iris()
        # iris.data属性150*4,iris.target 类别归一化为了0,1,2(150*1)
        clf = clf.fit(iris.data, iris.target)
        dot_file = 'tree.dot'
        tree.export_graphviz(clf, out_file=dot_file)
        visualize_tree(clf, iris.feature_names, dot_file)
    
        # (graph,) = pydot.graph_from_dot_file('tree.dot')
        # graph.write_png('somefile.png')
    
    
    if __name__ == '__main__':
        iris_demo()
        pass

    数据集


    1. 花的分类的四种属性,150个示例

    这里写图片描述

    2. 花的分类,一共三类对应于0,1,2

    这里写图片描述

    3. 花的四个属性的描述

    这里写图片描述

    最终生成的结果:

    这里写图片描述

    pydot的安装见另一篇bolg

    http://blog.csdn.net/haluoluo211/article/details/78200078

    转载注明出处,并在下面留言!!!

    参考

    http://chrisstrelioff.ws/sandbox/2015/06/08/decision_trees_in_python_with_scikit_learn_and_pandas.html

    http://www.kdnuggets.com/2017/05/simplifying-decision-tree-interpretation-decision-rules-python.html

    展开全文
  • 我们经常使用决策树处理分类问题,近年来的调查表明决策树也是经常使用的数据挖掘算法K-NN可以完成多分类任务,但是它最大的缺点是无法给出数据的内在含义,决策树的主要优势在于数据形式非常容易理解决策树的优缺点...

    我们经常使用决策树处理分类问题,近年来的调查表明决策树也是经常使用的数据挖掘算法

    K-NN可以完成多分类任务,但是它最大的缺点是无法给出数据的内在含义,决策树的主要优势在于数据形式非常容易理解

    决策树的优缺点:

    优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据

    缺点:可能会产生过度匹配问题

    适用数据类型:数值型和标称型

    在构造决策树时,我们需要解决的第一个问题是,当前数据集上哪个特征在划分数据分类时起决定性作用。

    为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成测试之后,原始数据集就被划

    分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一

    类型,则当前无需阅读的垃圾邮件已经正确地划分数据分类,无需进一步对数据集进行分割。如果数据子

    集内的数据不属于同一类型,则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集

    的方法相同,直到所有具有相同类型的数据均在一个数据子集内

    决策树的一般流程

    (1)收集数据:可以使用任何方法

    (2)准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化

    (3)分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期

    (4)训练算法:构造树的数据结构

    (5)测试算法:使用经验树计算错误率

    (6)使用算法:此步骤可以适用于任何监督学习算法,而适用决策树可以更好地理解数据的内在含义

    从数据集构造决策树算法所需要的子功能模块,其工作原理如下:得到原始数据集,然后基于

    最好的属性值划分数据集,由于特征值可能多余两个,因此可能存在大于两个分支的数据集划

    分,第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再

    次划分数据。

    1 计算给定数据集的香农熵2 from math importlog3 importoperator4 importtreePlotter5

    6

    7 defcalcShannonEnt(dataSet):8 #计算数据集的实例总数

    9 numEntries =len(dataSet)10 labelCounts ={}11 #创建一个字典,他的键值是最后一列的数值,如果当前键值不存在,则扩展字典并将当前键值加入字典。

    12 #每个键值都记录了当前类别出现的次数。最后,使用所有类标签的发生频率计算类别出现的概率。我们

    13 #将用这个概率计算香农熵,统计所有类标签发生的次数。

    14 for featVec in dataSet: #the the number of unique elements and their occurance

    15 #为所有可能分类创建字典

    16 currentLabel = featVec[-1]17 if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] =018 labelCounts[currentLabel] += 1

    19 shannonEnt = 0.0

    20 for key inlabelCounts:21 prob = float(labelCounts[key]) /numEntries22 #以2为底求对数,香农定理

    23 shannonEnt -= prob * log(prob, 2) #log base 2

    24 returnshannonEnt25 defcreateDataSet():26 dataSet = [[1, 1, "yes"],27 [1, 1, "yes"],28 [1, 0, "no"],29 [0, 1, "no"],30 [0, 1, "no"]]31 labels = ["no surfacing","flippers"]32 #change to discrete values

    33 returndataSet, labels34

    35 #按照给定特征划分数据集

    36 #三个输入参数:待划分的数据集、划分数据集的特征、特征的返回值。

    37 #注:python不考虑内存分配的问题

    38 defsplitDataSet(dataSet, axis, value):39 #创建新的list对象

    40 retDataSet =[]41 for featVec indataSet:42 if featVec[axis] ==value:43 #抽取

    44 reducedFeatVec = featVec[:axis] #chop out axis used for splitting

    45 reducedFeatVec.extend(featVec[axis+1:])46 retDataSet.append(reducedFeatVec)47 returnretDataSet48

    49 #选择最好的数据集划分方式

    50 defchooseBestFeatureToSplit(dataSet):51 numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels

    52 #计算了整个数据集的香农熵

    53 baseEntropy =calcShannonEnt(dataSet)54 bestInfoGain = 0.0; bestFeature = -1

    55 for i in range(numFeatures): #iterate over all the features

    56 #创建唯一的分类标签列表

    57 featList = [example[i] for example in dataSet]#create a list of all the examples of this feature

    58 uniqueVals = set(featList) #get a set of unique values

    59 newEntropy = 0.0

    60 for value inuniqueVals:61 #计算每种划分方式的信息熵

    62 subDataSet =splitDataSet(dataSet, i, value)63 prob = len(subDataSet)/float(len(dataSet))64 newEntropy += prob *calcShannonEnt(subDataSet)65 infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy

    66 if (infoGain >bestInfoGain):67 #计算最好的增益compare this to the best gain so far

    68 bestInfoGain = infoGain #if better than current best, set to best

    69 bestFeature =i70 returnbestFeature71

    72 #这与投票代码非常类似,该函数使用分类名称的列表,然后创建键值为classList中唯一值的数据字典,字典对象

    73 #存储了classList中每个类标签出现的频率,最后利用operator操作键值排序字典,并返回出现次数最多的分类名称。

    74 defmajorityCnt(classList):75 classCount={}76 for vote inclassList:77 if vote not in classCount.keys(): classCount[vote] =078 classCount[vote] += 1

    79 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)80 returnsortedClassCount[0][0]81

    82 #创建树的函数代码

    83 """

    84 两个输入参数:数据集和标签列表85 """

    86 defcreateTree(dataSet,labels):87 classList = [example[-1] for example indataSet]88 #类别完全相同则停止继续划分

    89 if classList.count(classList[0]) ==len(classList):90 return classList[0]#stop splitting when all of the classes are equal

    91 #遍历完所有特征时,返回出现次数最多的

    92 if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet

    93 returnmajorityCnt(classList)94 bestFeat =chooseBestFeatureToSplit(dataSet)95 bestFeatLabel =labels[bestFeat]96 myTree ={bestFeatLabel:{}}97 del(labels[bestFeat])98 #得到列表包含的所有属性值

    99 featValues = [example[bestFeat] for example indataSet]100 uniqueVals =set(featValues)101 for value inuniqueVals:102 subLabels = labels[:] #copy all of labels, so trees don"t mess up existing labels

    103 myTree[bestFeatLabel][value] =createTree(splitDataSet(dataSet, bestFeat, value),subLabels)104 returnmyTree105

    106 #使用决策树分类函数

    107 defclassify(inputTree,featLabels,testVec):108 firstStr =list(inputTree.keys())[0]109 secondDict =inputTree[firstStr]110 featIndex =featLabels.index(firstStr)111 key =testVec[featIndex]112 valueOfFeat =secondDict[key]113 ifisinstance(valueOfFeat, dict):114 classLabel =classify(valueOfFeat, featLabels, testVec)115 else: classLabel =valueOfFeat116 returnclassLabel117

    118

    119 myDat,label=createDataSet()120

    121 print("数据集"+str(myDat))122 print("labels"+str(label))123 #A=calcShannonEnt(myDat)

    124 #print("香农熵"+str(A))

    125 #B=splitDataSet(myDat,0,1)

    126 #print("按给定特征划分数据集"+str(B))

    127 #C=chooseBestFeatureToSplit(myDat)

    128 #print("最好的增益"+str(C))

    129 """

    130 # 结果告诉我们,第0个特征是最好的用于划分数据集的特征。131 # 如果我们按照第一个特征属性划分数据,也就是说第一个特征是1的放在一组,132 # 第一个特征是0的放在另一组133 #"""

    134 mytree=treePlotter.retrieveTree(0)135 D=classify(mytree,label,[1,0])136 print(D)

    展开全文
  • 机器学习 --- 决策树 python

    千次阅读 多人点赞 2020-10-22 20:58:16
    本实训项目的主要内容是基于 python 语言搭建出决策树模型对数据分类,并使用 sklearn 的决策时模型对鸢尾花数据进行分类。 信息熵与信息增益 import numpy as np def calcInfoGain(feature, label, index): ''' ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,549
精华内容 19,419
关键字:

决策树python

python 订阅