精华内容
下载资源
问答
  • 主要介绍了决策树剪枝算法的python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下
  • 本文实例讲述了决策树剪枝算法的python实现方法。分享给大家供大家参考,具体如下: 决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射...

    本文实例讲述了决策树剪枝算法的python实现方法。分享给大家供大家参考,具体如下:
    决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能的属性值,而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出,如果有多个输出,可以分别建立独立的决策树以处理不同的输出。

    ID3算法:ID3算法是决策树的一种,是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。在信息论中,期望信息越小,那么信息增益就越大,从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
    信息熵,将其定义为离散随机事件出现的概率,一个系统越是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

    基尼指数:在CART里面划分决策树的条件是采用Gini Index,定义如下:gini(T)=1−sumnj=1p2j。其中,( p_j )是类j在T中的相对频率,当类在T中是倾斜的时,gini(T)会最小。将T划分为T1(实例数为N1)和T2(实例数为N2)两个子集后,划分数据的Gini定义如下:ginisplit(T)=fracN1Ngini(T1)+fracN2Ngini(T2),然后选择其中最小的(gini_{split}(T) )作为结点划分决策树
    具体实现
    首先用函数calcShanno计算数据集的香农熵,给所有可能的分类创建字典

    def calcShannonEnt(dataSet): 
      numEntries = len(dataSet) 
      labelCounts = {} 
      # 给所有可能分类创建字典 
      for featVec in dataSet: 
        currentLabel = featVec[-1] 
        if currentLabel not in labelCounts.keys(): 
          labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
      shannonEnt = 0.0
      # 以2为底数计算香农熵
      for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
      return shannonEnt
    
    # 对离散变量划分数据集,取出该特征取值为value的所有样本
    def splitDataSet(dataSet, axis, value):
      retDataSet = []
      for featVec in dataSet:
        if featVec[axis] == value:
          reducedFeatVec = featVec[:axis]
          reducedFeatVec.extend(featVec[axis + 1:])
          retDataSet.append(reducedFeatVec)
      return retDataSet
    

    对连续变量划分数据集,direction规定划分的方向, 决定是划分出小于value的数据样本还是大于value的数据样本集

    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    bestSplitDict = {}
    for i in range(numFeatures):
      featList = [example[i] for example in dataSet]
      # 对连续型特征进行处理
      if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
        # 产生n-1个候选划分点
        sortfeatList = sorted(featList)
        splitList = []
        for j in range(len(sortfeatList) - 1):
          splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)
     
        bestSplitEntropy = 10000
        slen = len(splitList)
        # 求用第j个候选划分点划分时,得到的信息熵,并记录最佳划分点
        for j in range(slen):
          value = splitList[j]
          newEntropy = 0.0
          subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)
          subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)
          prob0 = len(subDataSet0) / float(len(dataSet))
          newEntropy += prob0 * calcShannonEnt(subDataSet0)
          prob1 = len(subDataSet1) / float(len(dataSet))
          newEntropy += prob1 * calcShannonEnt(subDataSet1)
          if newEntropy < bestSplitEntropy:
            bestSplitEntropy = newEntropy
            bestSplit = j
        # 用字典记录当前特征的最佳划分点
        bestSplitDict[labels[i]] = splitList[bestSplit]
        infoGain = baseEntropy - bestSplitEntropy
      # 对离散型特征进行处理
      else:
        uniqueVals = set(featList)
        newEntropy = 0.0
        # 计算该特征下每种划分的信息熵
        for value in uniqueVals:
          subDataSet = splitDataSet(dataSet, i, value)
          prob = len(subDataSet) / float(len(dataSet))
          newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
      if infoGain > bestInfoGain:
        bestInfoGain = infoGain
        bestFeature = i
    # 若当前节点的最佳划分特征为连续特征,则将其以之前记录的划分点为界进行二值化处理
    # 即是否小于等于bestSplitValue
    if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
      bestSplitValue = bestSplitDict[labels[bestFeature]]
      labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
      for i in range(shape(dataSet)[0]):
        if dataSet[i][bestFeature] <= bestSplitValue:
          dataSet[i][bestFeature] = 1
        else:
          dataSet[i][bestFeature] = 0
    return bestFeature
    
    def chooseBestFeatureToSplit(dataSet, labels):
      numFeatures = len(dataSet[0]) - 1
      baseEntropy = calcShannonEnt(dataSet)
      bestInfoGain = 0.0
      bestFeature = -1
      bestSplitDict = {}
      for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        # 对连续型特征进行处理
        if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
          # 产生n-1个候选划分点
          sortfeatList = sorted(featList)
          splitList = []
          for j in range(len(sortfeatList) - 1):
            splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)
     
          bestSplitEntropy = 10000
          slen = len(splitList)
          # 求用第j个候选划分点划分时,得到的信息熵,并记录最佳划分点
          for j in range(slen):
            value = splitList[j]
            newEntropy = 0.0
            subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)
            subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)
            prob0 = len(subDataSet0) / float(len(dataSet))
            newEntropy += prob0 * calcShannonEnt(subDataSet0)
            prob1 = len(subDataSet1) / float(len(dataSet))
            newEntropy += prob1 * calcShannonEnt(subDataSet1)
            if newEntropy < bestSplitEntropy:
              bestSplitEntropy = newEntropy
              bestSplit = j
          # 用字典记录当前特征的最佳划分点
          bestSplitDict[labels[i]] = splitList[bestSplit]
          infoGain = baseEntropy - bestSplitEntropy
        # 对离散型特征进行处理
        else:
          uniqueVals = set(featList)
          newEntropy = 0.0
          # 计算该特征下每种划分的信息熵
          for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
          infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
          bestInfoGain = infoGain
          bestFeature = i
      # 若当前节点的最佳划分特征为连续特征,则将其以之前记录的划分点为界进行二值化处理
      # 即是否小于等于bestSplitValue
      if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
        bestSplitValue = bestSplitDict[labels[bestFeature]]
        labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
        for i in range(shape(dataSet)[0]):
          if dataSet[i][bestFeature] <= bestSplitValue:
            dataSet[i][bestFeature] = 1
          else:
            dataSet[i][bestFeature] = 0
      return bestFeature
    ``def classify(inputTree, featLabels, testVec):
      firstStr = inputTree.keys()[0]
      if u'<=' in firstStr:
        featvalue = float(firstStr.split(u"<=")[1])
        featkey = firstStr.split(u"<=")[0]
        secondDict = inputTree[firstStr]
        featIndex = featLabels.index(featkey)
        if testVec[featIndex] <= featvalue:
          judge = 1
        else:
          judge = 0
        for key in secondDict.keys():
          if judge == int(key):
            if type(secondDict[key]).__name__ == 'dict':
              classLabel = classify(secondDict[key], featLabels, testVec)
            else:
              classLabel = secondDict[key]
      else:
        secondDict = inputTree[firstStr]
        featIndex = featLabels.index(firstStr)
        for key in secondDict.keys():
          if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
              classLabel = classify(secondDict[key], featLabels, testVec)
            else:
              classLabel = secondDict[key]
      return classLabel
    
    def majorityCnt(classList):
      classCount={}
      for vote in classList:
        if vote not in classCount.keys():
          classCount[vote]=0
        classCount[vote]+=1
      return max(classCount)
    def testing_feat(feat, train_data, test_data, labels):
      class_list = [example[-1] for example in train_data]
      bestFeatIndex = labels.index(feat)
      train_data = [example[bestFeatIndex] for example in train_data]
      test_data = [(example[bestFeatIndex], example[-1]) for example in test_data]
      all_feat = set(train_data)
      error = 0.0
      for value in all_feat:
        class_feat = [class_list[i] for i in range(len(class_list)) if train_data[i] == value]
        major = majorityCnt(class_feat)
        for data in test_data:
          if data[0] == value and data[1] != major:
            error += 1.0
      # print 'myTree %d' % error
      return error
    

    测试

    error = 0.0
      for i in range(len(data_test)):
        if classify(myTree, labels, data_test[i]) != data_test[i][-1]:
          error += 1
      # print 'myTree %d' % error
      return float(error)
    def testingMajor(major, data_test):
      error = 0.0
      for i in range(len(data_test)):
        if major != data_test[i][-1]:
          error += 1
      # print 'major %d' % error
      return float(error)
     
    **递归产生决策树**
     
    ```def createTree(dataSet,labels,data_full,labels_full,test_data,mode):
      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)
      labels_copy = copy.deepcopy(labels)
      bestFeat=chooseBestFeatureToSplit(dataSet,labels)
      bestFeatLabel=labels[bestFeat]
     
      if mode == "unpro" or mode == "post":
        myTree = {bestFeatLabel: {}}
      elif mode == "prev":
        if testing_feat(bestFeatLabel, dataSet, test_data, labels_copy) < testingMajor(majorityCnt(classList),
                                                test_data):
          myTree = {bestFeatLabel: {}}
        else:
          return majorityCnt(classList)
      featValues=[example[bestFeat] for example in dataSet]
      uniqueVals=set(featValues)
     
      if type(dataSet[0][bestFeat]).__name__ == 'unicode':
        currentlabel = labels_full.index(labels[bestFeat])
        featValuesFull = [example[currentlabel] for example in data_full]
        uniqueValsFull = set(featValuesFull)
     
      del (labels[bestFeat])
     
      for value in uniqueVals:
        subLabels = labels[:]
        if type(dataSet[0][bestFeat]).__name__ == 'unicode':
          uniqueValsFull.remove(value)
     
        myTree[bestFeatLabel][value] = createTree(splitDataSet \
                               (dataSet, bestFeat, value), subLabels, data_full, labels_full,
                             splitDataSet \
                               (test_data, bestFeat, value), mode=mode)
      if type(dataSet[0][bestFeat]).__name__ == 'unicode':
        for value in uniqueValsFull:
          myTree[bestFeatLabel][value] = majorityCnt(classList)
     
      if mode == "post":
        if testing(myTree, test_data, labels_copy) > testingMajor(majorityCnt(classList), test_data):
          return majorityCnt(classList)
      return myTree
     
     
     
     
     
     
     
     
    <div class="se-preview-section-delimiter"></div>
     
    ```**读入数据**
     
    ```def load_data(file_name):
      with open(r"dd.csv", 'rb') as f:
       df = pd.read_csv(f,sep=",")
       print(df)
       train_data = df.values[:11, 1:].tolist()
      print(train_data)
      test_data = df.values[11:, 1:].tolist()
      labels = df.columns.values[1:-1].tolist()
      return train_data, test_data, labels
     
     
     
     
     
    <div class="se-preview-section-delimiter"></div>
     
    ```测试并绘制树图
    import matplotlib.pyplot as plt
    decisionNode = dict(boxstyle="round4", color='red') # 定义判断结点形态
    leafNode = dict(boxstyle="circle", color='grey') # 定义叶结点形态
    arrow_args = dict(arrowstyle="<-", color='blue') # 定义箭头
     
     
    # 计算树的叶子节点数量
    def getNumLeafs(myTree):
      numLeafs = 0
      firstSides = list(myTree.keys())
      firstStr = firstSides[0]
      secondDict = myTree[firstStr]
      for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
          numLeafs += getNumLeafs(secondDict[key])
        else:
          numLeafs += 1
      return numLeafs
     
     
    # 计算树的最大深度
    def getTreeDepth(myTree):
      maxDepth = 0
      firstSides = list(myTree.keys())
      firstStr = firstSides[0]
      secondDict = myTree[firstStr]
      for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
          thisDepth = 1 + getTreeDepth(secondDict[key])
        else:
          thisDepth = 1
        if thisDepth > maxDepth:
          maxDepth = thisDepth
      return maxDepth
     
     
    # 画节点
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
      createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', \
                  xytext=centerPt, textcoords='axes fraction', va="center", ha="center", \
                  bbox=nodeType, arrowprops=arrow_args)
     
     
    # 画箭头上的文字
    def plotMidText(cntrPt, parentPt, txtString):
      lens = len(txtString)
      xMid = (parentPt[0] + cntrPt[0]) / 2.0 - lens * 0.002
      yMid = (parentPt[1] + cntrPt[1]) / 2.0
      createPlot.ax1.text(xMid, yMid, txtString)
     
     
    def plotTree(myTree, parentPt, nodeTxt):
      numLeafs = getNumLeafs(myTree)
      depth = getTreeDepth(myTree)
      firstSides = list(myTree.keys())
      firstStr = firstSides[0]
      cntrPt = (plotTree.x0ff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.y0ff)
      plotMidText(cntrPt, parentPt, nodeTxt)
      plotNode(firstStr, cntrPt, parentPt, decisionNode)
      secondDict = myTree[firstStr]
      plotTree.y0ff = plotTree.y0ff - 1.0 / plotTree.totalD
      for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
          plotTree(secondDict[key], cntrPt, str(key))
        else:
          plotTree.x0ff = plotTree.x0ff + 1.0 / plotTree.totalW
          plotNode(secondDict[key], (plotTree.x0ff, plotTree.y0ff), cntrPt, leafNode)
          plotMidText((plotTree.x0ff, plotTree.y0ff), cntrPt, str(key))
      plotTree.y0ff = plotTree.y0ff + 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.x0ff = -0.5 / plotTree.totalW
      plotTree.y0ff = 1.0
      plotTree(inTree, (0.5, 1.0), '')
    

    选择mode就可以分别得到三种树图

    if __name__ == "__main__":
      train_data, test_data, labels = load_data("dd.csv")
      data_full = train_data[:]
      labels_full = labels[:]
     
      mode="post"
      mode = "prev"
      mode="post"
      myTree = createTree(train_data, labels, data_full, labels_full, test_data, mode=mode)
      createPlot(myTree)
      print(json.dumps(myTree, ensure_ascii=False, indent=4))
    

    选择mode就可以分别得到三种树图在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    最后给大家推荐我们的Python学习扣qun:774711191 ,看看前辈们是如何学习的!从基础的python脚本到web开发、爬虫、django、数据挖掘等【PDF,实战源码】,零基础到项目实战的资料都有整理。送给每一位python的小伙伴!每天都有大牛定时讲解Python技术,分享一些学习的方法和需要注意的小细节,点击加入我们的 python学习者聚集地

    展开全文
  • ![图片说明](https://img-ask.csdn.net/upload/201905/13/1557681499_941647.png) 在进行决策树剪枝的时候出现AttributeError: 'function' object has no attribute 'deepcopy'错误,一直解决不了。
  • 决策树剪枝算法1、算法目的2、算法基本思路:3、决策树损失函数4、剪枝类型:4.1 预剪枝4.2 后剪枝4.3 两种剪枝策略对比 1、算法目的 决策树的剪枝是为了简化决策树模型,避免过拟合。 同样层数的决策树,叶结点的...

    引言

    \quad \quad决策树、ID3、C4.5算法一文中,简单地介绍了决策树模型,以及决策树生成算法:决策树生成算法递归地产生决策树,直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即容易出现过拟合现象。解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化,下面来探讨以下决策树剪枝算法。

    1、算法目的

    \quad \quad决策树的剪枝是为了简化决策树模型,避免过拟合。

    • 同样层数的决策树,叶结点的个数越多就越复杂;同样的叶结点个数的决策树,层数越多越复杂。
    • 剪枝前相比于剪枝后,叶结点个数和层数只能更多或者其中一特征一样多,剪枝前必然更复杂。
    • 层数越多,叶结点越多,分的越细致,对训练数据分的也越深,越容易过拟合,导致对测试数据预测时反而效果差,泛化能力差。

    2、算法基本思路:

    \quad \quad剪去决策树模型中的一些子树或者叶结点,并将其上层的根结点作为新的叶结点,从而减少了叶结点甚至减少了层数,降低了决策树复杂度。

    \quad \quad决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

    3、决策树损失函数

    \quad \quad设树T的叶节点个数为T|T|,t是树T的叶节点,该叶节点有NtN_t个样本点,其中k类的样本点有NtkN_{tk}个,k=1,2,...,Kk=1,2,...,K,Ht(T)H_t(T)为叶节点t上的经验熵,α0\alpha\geq0为参数,则决策树学习的损失寒素可以定义为
    Cα(T)=t=1TNtHt(T)+αTC_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|

    其中,经验熵为Ht(T)=kNtkNtlogNtkNtH_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}

    • C(T)=t=1TNtHt(T)=t=1Tk=1KNtklogNtkNtC(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}
      Cα(T)=C(T)+αTC_\alpha(T)=C(T)+\alpha|T|
    • C(T)C(T)表示模型对训练数据的预测误差,即模型与训练数据的拟合程度,|T|表示模型复杂度。
    • αT\alpha|T|是为了避免过拟合,给优化目标函数增加一个正则项,正则项包含模型的复杂度信息|T|。对于决策树来说,其叶结点的数量 ∣T∣ 越多就越复杂。参数 α\alpha 控制了两者之间的影响程度。较大的 α\alpha促使选择较简单的模型(树),较小的 α\alpha 促使选择较复杂的模型(树)。
    • 上式定义的损失函数Cα(T)C_\alpha(T)的极小化等价于正则化的极大似然估计。

    \quad \quad剪枝,就是当α\alpha确定时,选择损失函数最小的模型,即损失函数最小的子树。当α\alpha确定时,子树越大,往往与训练数据的拟合越好,但是模型的复杂度就越高;相反,子树越小,模型的复杂度就越低,但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

    4、剪枝类型:

    \quad \quad决策树的剪枝基本策略有 预剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning) [Quinlan, 1933]。根据周志华老师《机器学习》一书中所描述是先对数据集划分成训练集和验证集,训练集用来决定树生成过程中每个结点划分所选择的属性;验证集在预剪枝中用于决定该结点是否有必要依据该属性进行展开,在后剪枝中用于判断该结点是否需要进行剪枝。

    4.1 预剪枝

    \quad \quad预剪枝是在决策树生成过程中,对树进行剪枝,提前结束树的分支生长。

    加入预剪枝后的决策树生成流程图如下:
    在这里插入图片描述
    \quad \quad其中的核心思想就是,在每一次实际对结点进行进一步划分之前,先采用验证集的数据来验证划分是否能提高划分的准确性。如果不能,就把结点标记为叶结点并退出进一步划分;如果可以就继续递归生成节点。

    4.2 后剪枝

    \quad \quad后剪枝是在决策树生长完成之后,对树进行剪枝,得到简化版的决策树。

    \quad \quad对于后剪枝,周志华老师《机器学习》中述说如下:

    后剪枝则是先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来泛化性能提升,则将该子树替换为叶结点。

    李航《统计学习方法》中述说如下:

    输入:生成算法产生的整个树T,参数α\alpha
    输出:修剪后的子树Tα

    1. 计算每个结点的经验熵
    2. 递归地从树的叶结点向上回缩
      \quad设一组叶结点回缩到父结点之前与之后的整体树分别为TBT_BTAT_A,其对应的损失函数值分别是Cα(TB)Cα(T_B)Cα(TA)Cα(T_A),如果Cα(TA)Cα(TB)Cα(T_A)≤Cα(T_B)则进行剪枝,即将父结点变为新的叶结点。
    3. 返回(2),直至不能继续为止,得到损失函数最小的子树Tα

    代码稍后更新

    4.3 两种剪枝策略对比

    • 后剪枝决策树通常比预剪枝决策树保留了更多的分支;
    • 后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树;
    • 后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

    参考资料:
    https://blog.csdn.net/yujianmin1990/article/details/49864813
    https://blog.csdn.net/ylhlly/article/details/93213633

    展开全文
  • 决策树剪枝简单python实现

    千次阅读 2017-12-18 16:52:31
    决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能的属性值,而每一个...

    决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能的属性值,而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出,如果有多个输出,可以分别建立独立的决策树以处理不同的输出。

    ID3算法:ID3算法是决策树的一种,是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。在信息论中,期望信息越小,那么信息增益就越大,从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
    信息熵,将其定义为离散随机事件出现的概率,一个系统越是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

    基尼指数:在CART里面划分决策树的条件是采用Gini Index,定义如下:gini(T)=1−sumnj=1p2j。其中,( p_j )是类j在T中的相对频率,当类在T中是倾斜的时,gini(T)会最小。将T划分为T1(实例数为N1)和T2(实例数为N2)两个子集后,划分数据的Gini定义如下:ginisplit(T)=fracN1Ngini(T1)+fracN2Ngini(T2),然后选择其中最小的(gini_{split}(T) )作为结点划分决策树
    具体实现
    首先用函数calcShanno计算数据集的香农熵,给所有可能的分类创建字典 def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    # 给所有可能分类创建字典
    for featVec in dataSet:
    currentLabel = featVec[-1]
    if currentLabel not in labelCounts.keys():
    labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    # 以2为底数计算香农熵
    for key in labelCounts:
    prob = float(labelCounts[key]) / numEntries
    shannonEnt -= prob * log(prob, 2)
    return shannonEnt

    # 对离散变量划分数据集,取出该特征取值为value的所有样本
    def splitDataSet(dataSet, axis, value):
        retDataSet = []
        for featVec in dataSet:
            if featVec[axis] == value:
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis + 1:])
                retDataSet.append(reducedFeatVec)
        return retDataSet
    

    对连续变量划分数据集,direction规定划分的方向, 决定是划分出小于value的数据样本还是大于value的数据样本集

        numFeatures = len(dataSet[0]) - 1
        baseEntropy = calcShannonEnt(dataSet)
        bestInfoGain = 0.0
        bestFeature = -1
        bestSplitDict = {}
        for i in range(numFeatures):
            featList = [example[i] for example in dataSet]
            # 对连续型特征进行处理
            if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
                # 产生n-1个候选划分点
                sortfeatList = sorted(featList)
                splitList = []
                for j in range(len(sortfeatList) - 1):
                    splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)
    
                bestSplitEntropy = 10000
                slen = len(splitList)
                # 求用第j个候选划分点划分时,得到的信息熵,并记录最佳划分点
                for j in range(slen):
                    value = splitList[j]
                    newEntropy = 0.0
                    subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)
                    subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)
                    prob0 = len(subDataSet0) / float(len(dataSet))
                    newEntropy += prob0 * calcShannonEnt(subDataSet0)
                    prob1 = len(subDataSet1) / float(len(dataSet))
                    newEntropy += prob1 * calcShannonEnt(subDataSet1)
                    if newEntropy < bestSplitEntropy:
                        bestSplitEntropy = newEntropy
                        bestSplit = j
                # 用字典记录当前特征的最佳划分点
                bestSplitDict[labels[i]] = splitList[bestSplit]
                infoGain = baseEntropy - bestSplitEntropy
            # 对离散型特征进行处理
            else:
                uniqueVals = set(featList)
                newEntropy = 0.0
                # 计算该特征下每种划分的信息熵
                for value in uniqueVals:
                    subDataSet = splitDataSet(dataSet, i, value)
                    prob = len(subDataSet) / float(len(dataSet))
                    newEntropy += prob * calcShannonEnt(subDataSet)
                infoGain = baseEntropy - newEntropy
            if infoGain > bestInfoGain:
                bestInfoGain = infoGain
                bestFeature = i
        # 若当前节点的最佳划分特征为连续特征,则将其以之前记录的划分点为界进行二值化处理
        # 即是否小于等于bestSplitValue
        if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
            bestSplitValue = bestSplitDict[labels[bestFeature]]
            labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
            for i in range(shape(dataSet)[0]):
                if dataSet[i][bestFeature] <= bestSplitValue:
                    dataSet[i][bestFeature] = 1
                else:
                    dataSet[i][bestFeature] = 0
        return bestFeature
    
    def chooseBestFeatureToSplit(dataSet, labels):
        numFeatures = len(dataSet[0]) - 1
        baseEntropy = calcShannonEnt(dataSet)
        bestInfoGain = 0.0
        bestFeature = -1
        bestSplitDict = {}
        for i in range(numFeatures):
            featList = [example[i] for example in dataSet]
            # 对连续型特征进行处理
            if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
                # 产生n-1个候选划分点
                sortfeatList = sorted(featList)
                splitList = []
                for j in range(len(sortfeatList) - 1):
                    splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)
    
                bestSplitEntropy = 10000
                slen = len(splitList)
                # 求用第j个候选划分点划分时,得到的信息熵,并记录最佳划分点
                for j in range(slen):
                    value = splitList[j]
                    newEntropy = 0.0
                    subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)
                    subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)
                    prob0 = len(subDataSet0) / float(len(dataSet))
                    newEntropy += prob0 * calcShannonEnt(subDataSet0)
                    prob1 = len(subDataSet1) / float(len(dataSet))
                    newEntropy += prob1 * calcShannonEnt(subDataSet1)
                    if newEntropy < bestSplitEntropy:
                        bestSplitEntropy = newEntropy
                        bestSplit = j
                # 用字典记录当前特征的最佳划分点
                bestSplitDict[labels[i]] = splitList[bestSplit]
                infoGain = baseEntropy - bestSplitEntropy
            # 对离散型特征进行处理
            else:
                uniqueVals = set(featList)
                newEntropy = 0.0
                # 计算该特征下每种划分的信息熵
                for value in uniqueVals:
                    subDataSet = splitDataSet(dataSet, i, value)
                    prob = len(subDataSet) / float(len(dataSet))
                    newEntropy += prob * calcShannonEnt(subDataSet)
                infoGain = baseEntropy - newEntropy
            if infoGain > bestInfoGain:
                bestInfoGain = infoGain
                bestFeature = i
        # 若当前节点的最佳划分特征为连续特征,则将其以之前记录的划分点为界进行二值化处理
        # 即是否小于等于bestSplitValue
        if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
            bestSplitValue = bestSplitDict[labels[bestFeature]]
            labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
            for i in range(shape(dataSet)[0]):
                if dataSet[i][bestFeature] <= bestSplitValue:
                    dataSet[i][bestFeature] = 1
                else:
                    dataSet[i][bestFeature] = 0
        return bestFeature
    ``def classify(inputTree, featLabels, testVec):
        firstStr = inputTree.keys()[0]
        if u'<=' in firstStr:
            featvalue = float(firstStr.split(u"<=")[1])
            featkey = firstStr.split(u"<=")[0]
            secondDict = inputTree[firstStr]
            featIndex = featLabels.index(featkey)
            if testVec[featIndex] <= featvalue:
                judge = 1
            else:
                judge = 0
            for key in secondDict.keys():
                if judge == int(key):
                    if type(secondDict[key]).__name__ == 'dict':
                        classLabel = classify(secondDict[key], featLabels, testVec)
                    else:
                        classLabel = secondDict[key]
        else:
            secondDict = inputTree[firstStr]
            featIndex = featLabels.index(firstStr)
            for key in secondDict.keys():
                if testVec[featIndex] == key:
                    if type(secondDict[key]).__name__ == 'dict':
                        classLabel = classify(secondDict[key], featLabels, testVec)
                    else:
                        classLabel = secondDict[key]
        return classLabel
    def majorityCnt(classList):
        classCount={}
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote]=0
            classCount[vote]+=1
        return max(classCount)
    def testing_feat(feat, train_data, test_data, labels):
        class_list = [example[-1] for example in train_data]
        bestFeatIndex = labels.index(feat)
        train_data = [example[bestFeatIndex] for example in train_data]
        test_data = [(example[bestFeatIndex], example[-1]) for example in test_data]
        all_feat = set(train_data)
        error = 0.0
        for value in all_feat:
            class_feat = [class_list[i] for i in range(len(class_list)) if train_data[i] == value]
            major = majorityCnt(class_feat)
            for data in test_data:
                if data[0] == value and data[1] != major:
                    error += 1.0
        # print 'myTree %d' % error
        return error
    

    测试

        error = 0.0
        for i in range(len(data_test)):
            if classify(myTree, labels, data_test[i]) != data_test[i][-1]:
                error += 1
        # print 'myTree %d' % error
        return float(error)
    def testingMajor(major, data_test):
        error = 0.0
        for i in range(len(data_test)):
            if major != data_test[i][-1]:
                error += 1
        # print 'major %d' % error
        return float(error)
    
    **递归产生决策树**
    
    ```def createTree(dataSet,labels,data_full,labels_full,test_data,mode):
        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)
        labels_copy = copy.deepcopy(labels)
        bestFeat=chooseBestFeatureToSplit(dataSet,labels)
        bestFeatLabel=labels[bestFeat]
    
        if mode == "unpro" or mode == "post":
            myTree = {bestFeatLabel: {}}
        elif mode == "prev":
            if testing_feat(bestFeatLabel, dataSet, test_data, labels_copy) < testingMajor(majorityCnt(classList),
                                                                                           test_data):
                myTree = {bestFeatLabel: {}}
            else:
                return majorityCnt(classList)
        featValues=[example[bestFeat] for example in dataSet]
        uniqueVals=set(featValues)
    
        if type(dataSet[0][bestFeat]).__name__ == 'unicode':
            currentlabel = labels_full.index(labels[bestFeat])
            featValuesFull = [example[currentlabel] for example in data_full]
            uniqueValsFull = set(featValuesFull)
    
        del (labels[bestFeat])
    
        for value in uniqueVals:
            subLabels = labels[:]
            if type(dataSet[0][bestFeat]).__name__ == 'unicode':
                uniqueValsFull.remove(value)
    
            myTree[bestFeatLabel][value] = createTree(splitDataSet \
                                                          (dataSet, bestFeat, value), subLabels, data_full, labels_full,
                                                      splitDataSet \
                                                          (test_data, bestFeat, value), mode=mode)
        if type(dataSet[0][bestFeat]).__name__ == 'unicode':
            for value in uniqueValsFull:
                myTree[bestFeatLabel][value] = majorityCnt(classList)
    
        if mode == "post":
            if testing(myTree, test_data, labels_copy) > testingMajor(majorityCnt(classList), test_data):
                return majorityCnt(classList)
        return myTree
    
    
    
    
    
    
    
    
    <div class="se-preview-section-delimiter"></div>
    
    ```**读入数据**
    
    ```def load_data(file_name):
        with open(r"dd.csv", 'rb') as f:
          df = pd.read_csv(f,sep=",")
          print(df)
          train_data = df.values[:11, 1:].tolist()
        print(train_data)
        test_data = df.values[11:, 1:].tolist()
        labels = df.columns.values[1:-1].tolist()
        return train_data, test_data, labels
    
    
    
    
    
    <div class="se-preview-section-delimiter"></div>
    
    ```测试并绘制树图
    import matplotlib.pyplot as plt
    decisionNode = dict(boxstyle="round4", color='red')  # 定义判断结点形态
    leafNode = dict(boxstyle="circle", color='grey')  # 定义叶结点形态
    arrow_args = dict(arrowstyle="<-", color='blue')  # 定义箭头
    
    
    # 计算树的叶子节点数量
    def getNumLeafs(myTree):
        numLeafs = 0
        firstSides = list(myTree.keys())
        firstStr = firstSides[0]
        secondDict = myTree[firstStr]
        for key in secondDict.keys():
            if type(secondDict[key]).__name__ == 'dict':
                numLeafs += getNumLeafs(secondDict[key])
            else:
                numLeafs += 1
        return numLeafs
    
    
    # 计算树的最大深度
    def getTreeDepth(myTree):
        maxDepth = 0
        firstSides = list(myTree.keys())
        firstStr = firstSides[0]
        secondDict = myTree[firstStr]
        for key in secondDict.keys():
            if type(secondDict[key]).__name__ == 'dict':
                thisDepth = 1 + getTreeDepth(secondDict[key])
            else:
                thisDepth = 1
            if thisDepth > maxDepth:
                maxDepth = thisDepth
        return maxDepth
    
    
    # 画节点
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', \
                                xytext=centerPt, textcoords='axes fraction', va="center", ha="center", \
                                bbox=nodeType, arrowprops=arrow_args)
    
    
    # 画箭头上的文字
    def plotMidText(cntrPt, parentPt, txtString):
        lens = len(txtString)
        xMid = (parentPt[0] + cntrPt[0]) / 2.0 - lens * 0.002
        yMid = (parentPt[1] + cntrPt[1]) / 2.0
        createPlot.ax1.text(xMid, yMid, txtString)
    
    
    def plotTree(myTree, parentPt, nodeTxt):
        numLeafs = getNumLeafs(myTree)
        depth = getTreeDepth(myTree)
        firstSides = list(myTree.keys())
        firstStr = firstSides[0]
        cntrPt = (plotTree.x0ff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.y0ff)
        plotMidText(cntrPt, parentPt, nodeTxt)
        plotNode(firstStr, cntrPt, parentPt, decisionNode)
        secondDict = myTree[firstStr]
        plotTree.y0ff = plotTree.y0ff - 1.0 / plotTree.totalD
        for key in secondDict.keys():
            if type(secondDict[key]).__name__ == 'dict':
                plotTree(secondDict[key], cntrPt, str(key))
            else:
                plotTree.x0ff = plotTree.x0ff + 1.0 / plotTree.totalW
                plotNode(secondDict[key], (plotTree.x0ff, plotTree.y0ff), cntrPt, leafNode)
                plotMidText((plotTree.x0ff, plotTree.y0ff), cntrPt, str(key))
        plotTree.y0ff = plotTree.y0ff + 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.x0ff = -0.5 / plotTree.totalW
        plotTree.y0ff = 1.0
        plotTree(inTree, (0.5, 1.0), '')
        plt.show()
    if __name__ == "__main__":
        train_data, test_data, labels = load_data("dd.csv")
        data_full = train_data[:]
        labels_full = labels[:]
    
        mode="post"
        mode = "prev"
        mode="post"
        myTree = createTree(train_data, labels, data_full, labels_full, test_data, mode=mode)
        createPlot(myTree)
        print(json.dumps(myTree, ensure_ascii=False, indent=4))
    
    

    选择mode就可以分别得到三种树图

    if __name__ == "__main__":
        train_data, test_data, labels = load_data("dd.csv")
        data_full = train_data[:]
        labels_full = labels[:]
    
        mode="post"
        mode = "prev"
        mode="post"
        myTree = createTree(train_data, labels, data_full, labels_full, test_data, mode=mode)
        createPlot(myTree)
        print(json.dumps(myTree, ensure_ascii=False, indent=4))
    
    

    选择mode就可以分别得到三种树图
    这里写图片描述

    这里写图片描述

    这里写图片描述

    展开全文
  • 周志华《机器学习》西瓜书 小白Python学习笔记(三) ———— 第四章 决策树 python代码 预剪枝 基于西瓜数据集2.0(提取码:esa8) ,选择信息增益作为属性选择指标,建立决策树。 步骤如下: 输入离散变量的取值...
  • 本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下1. C4.5算法简介C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进:(1)通过信息增益率...

    本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下

    1. C4.5算法简介

    C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进:

    (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;

    (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理;

    (3)构造决策树之后进行剪枝操作;

    (4)能够处理具有缺失属性值的训练数据。

    2. 分裂属性的选择——信息增益率

    分裂属性选择的评判标准是决策树算法之间的根本区别。区别于ID3算法通过信息增益选择分裂属性,C4.5算法通过信息增益率选择分裂属性。

    属性A的“分裂信息”(split information):

    2017122014125733.png

    其中,训练数据集S通过属性A的属性值划分为m个子数据集,|Sj|表示第j个子数据集中样本数量,|S|表示划分之前数据集中样本总数量。

    通过属性A分裂之后样本集的信息增益:

    2017122014125734.png

    信息增益的详细计算方法,可以参考博客“决策树之ID3算法及其Python实现”中信息增益的计算。

    通过属性A分裂之后样本集的信息增益率:

    2017122014125735.png

    通过C4.5算法构造决策树时,信息增益率最大的属性即为当前节点的分裂属性,随着递归计算,被计算的属性的信息增益率会变得越来越小,到后期则选择相对比较大的信息增益率的属性作为分裂属性。

    3. 连续型属性的离散化处理

    当属性类型为离散型,无须对数据进行离散化处理;当属性类型为连续型,则需要对数据进行离散化处理。C4.5算法针对连续属性的离散化处理,核心思想:将属性A的N个属性值按照升序排列;通过二分法将属性A的所有属性值分成两部分(共有N-1种划分方法,二分的阈值为相邻两个属性值的中间值);计算每种划分方法对应的信息增益,选取信息增益最大的划分方法的阈值作为属性A二分的阈值。详细流程如下:

    (1)将节点Node上的所有数据样本按照连续型属性A的具体取值,由小到大进行排列,得到属性A的属性值取值序列(xA1,...,xAN)。

    (2)在序列(xA1,...,xAN)中共有N-1种二分方法,即共产生N-1个分隔阈值。对于第i种二分方法,其二分阈值θi=xAi+xAi+12。它将该节点上的数据集划分为2个子数据集(xA1,...,xAi)(xAi+1,...,xAN)。计算此种二分结果下的信息增益。

    (3)分别计算N-1种二分结果下的信息增益,选取信息增益最大的二分结果作为对属性A的划分结果,并记录此时的二分阈值。

    4. 剪枝——PEP(Pessimistic Error Pruning)剪枝法

    由于决策树的建立完全是依赖于训练样本,因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树对于测试样本来说过于庞大而复杂,可能产生较高的分类错误率。这种现象就称为过拟合。因此需要将复杂的决策树进行简化,即去掉一些节点解决过拟合问题,这个过程称为剪枝。

    剪枝方法分为预剪枝和后剪枝两大类。预剪枝是在构建决策树的过程中,提前终止决策树的生长,从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强,因为很难精确的判断何时终止树的生长。后剪枝是在决策树构建完成之后,对那些置信度不达标的节点子树用叶子结点代替,该叶子结点的类标号用该节点子树中频率最高的类标记。后剪枝方法又分为两种,一类是把训练数据集分成树的生长集和剪枝集;另一类算法则是使用同一数据集进行决策树生长和剪枝。常见的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。

    C4.5算法采用PEP(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出,是一种自上而下的剪枝法,根据剪枝前后的错误率来判定是否进行子树的修剪,因此不需要单独的剪枝数据集。接下来详细介绍PEP(Pessimistic Error Pruning)剪枝法。

    对于一个叶子节点,它覆盖了n个样本,其中有e个错误,那么该叶子节点的错误率为(e+0.5)/n,其中0.5为惩罚因子(惩罚因子一般取值为0.5)。

    对于一棵子树,它有L个叶子节点,那么该子树的误判率为:

    2017122014125736.png

    其中,ei表示子树第i个叶子节点错误分类的样本数量,ni表示表示子树第i个叶子节点中样本的总数量。

    假设一棵子树错误分类一个样本取值为1,正确分类一个样本取值为0,那么子树的误判次数可以认为是一个伯努利分布,因此可以得到该子树误判次数的均值和标准差:

    2017122014125737.png

    把子树替换成叶子节点后,该叶子节点的误判率为:

    2017122014125738.png

    其中,e′=∑Li=1ei,n′=∑Li=1ni。

    同时,该叶子结点的误判次数也是一个伯努利分布,因此该叶子节点误判次数的均值为:

    2017122014125739.png

    剪枝的条件为:

    2017122014125740.png

    满足剪枝条件时,则将所得叶子节点替换该子树,即为剪枝操作。

    5. 缺失属性值的处理

    训练样本集中有可能会出现一些样本缺失了一些属性值,待分类样本中也会出现这样的情况。当遇到这样的样本集时该如何处理呢?含有缺失属性的样本集会一般会导致三个问题:

    (1)在构建决策树时,每一个分裂属性的选取是由训练样本集中所有属性的信息増益率来决定的。而在此阶段,如果训练样本集中有些样本缺少一部分属性,此时该如何计算该属性的信息増益率;

    (2)当已经选择某属性作为分裂属性时,样本集应该根据该属性的值来进行分支,但对于那些该属性的值为未知的样本,应该将它分支到哪一棵子树上;

    (3)在决策树已经构建完成后,如果待分类样本中有些属性值缺失,则该样本的分类过程如何进行。

    针对上述因缺失属性值引起的三个问题,C4.5算法有多种解决方案。

    面对问题一,在计算各属性的信息増益率时,若某些样本的属性值未知,那么可以这样处理:计算某属性的信息増益率时忽略掉缺失了此属性的样本;或者通过此属性的样本中出现频率最高的属性值,賦值给缺失了此属性的样本。

    面对问题二,假设属性A已被选择作为决策树中的一个分支节点,在对样本集进行分支的时候,对于那些属性A的值未知的样本,可以送样处理:不处理那些属性A未知的样本,即简单的忽略它们;或者根据属性A的其他样本的取值,来对未知样本进行赋值;或者为缺失属性A的样本单独创建一个分支,不过这种方式得到的决策树模型结点数显然要増加,使模型更加复杂了。

    面对问题三,根据己经生成的决策树模型,对一个待分类的样本进行分类时,若此样本的属性A的值未知,可以这样处理:待分类样本在到达属性A的分支结点时即可结束分类过程,此样本所属类别为属性A的子树中概率最大的类别;或者把待分类样本的属性A赋予一个最常见的值,然后继续分类过程。

    6. C4.5算法流程

    2017122014125741.png

    7. C4.5算法优缺点分析

    优点:

    (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;

    (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理;

    (3)构造决策树之后进行剪枝操作;

    (4)能够处理具有缺失属性值的训练数据。

    缺点:

    (1)算法的计算效率较低,特别是针对含有连续属性值的训练样本时表现的尤为突出。

    (2)算法在选择分裂属性时没有考虑到条件属性间的相关性,只计算数据集中每一个条件属性与决策属性之间的期望信息,有可能影响到属性选择的正确性。

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

    本文标题: python决策树之C4.5算法详解

    本文地址: http://www.cppcns.com/jiaoben/python/215277.html

    展开全文
  • 决策树之CART(分类回归树)详解,具体内容如下1、CART分类回归树简介CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量。如果待预测分类是离散型数据,则CART生成分类决策树;如果待预测分类...
  • 周志华《机器学习》西瓜书 小白Python学习笔记(三) ———— 第四章 决策树 python代码 预剪枝 基于西瓜数据集2.0(提取码:esa8) ,选择信息增益作为属性选择指标,建立决策树。 步骤如下: 输入离散变量的取值...
  • 机器学习算法的Python实现 (3):决策树剪枝处理

    万次阅读 多人点赞 2016-04-04 17:00:22
    本文数据参照 机器学习-周志华 一书中的决策树一章。可作为此章课后习题4的答案 ...本文内容包括未剪枝CART决策树、预剪枝CART决策树以及后剪枝决策树 本文使用的Python库包括 numpypandasmath
  • 最近看完了《机器学习实战》和天池直播课堂中的决策树算法,觉得意犹未尽,特别是信息熵部分理解并不透彻,于是又把西瓜书中的决策树看了,略有感悟,希望与大家分享一下,下面我按照自己的理解,尽量用通俗的语言...
  • 还没关注?快动动手指!往期回顾从零开始学Python【34】--CART决策树(理论部分)从零开始学Python【35】--CART决策树(实战部分)前言决策树剪枝通常...
  • Python编程实现预剪枝的CART决策树

    千次阅读 2019-09-06 21:21:23
    前面在Python编程实现基于基尼指数...决策树剪枝的基本策略有预剪枝和后剪枝。本文主要是对预剪枝的实现。预剪枝是指在决策树的生成过程中,对每个结点在划分前后先进行评估,如果当前结点的划分不能带来决策树泛化...
  • python输出决策树图形的例子windows10:1,先要pip安装pydotplus和graphviz:pip install pydotpluspip install graphviz3,系统环境变量path中增加两项:C:\Program Files (x86)\Graphviz2.38\binC:\Program Files ...
  • 剪枝问题决策树的应用_解决人工棋子问题
  • 决策树优点:- 计算复杂度不高,易于理解和解释,甚至比线性回归更直观;- 与人类做决策思考的思维习惯契合;- 模型可以通过树的形式进行可视化展示;- 可以直接处理非数值型数据,不需要进行哑变量的转化,甚至可以...
  • python决策树代码

    2018-10-12 13:41:50
    决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画...
  • Python编程实现后剪枝的CART决策树

    千次阅读 2019-09-07 23:21:30
    前面实现了不进行剪枝的CART决策树和预剪枝决策树,本文是对后剪枝的CART决策树的实现,这样关于CART决策树的东西就凑全了。 后剪枝的策略是一种“事后诸葛亮”的策略,因而效果往往要比预剪枝和不剪枝要好。主要...
  • 选自Machine Learning Mastery作者:Jason Brownlee机器之心编译参与:沈泽江、吴攀决策树算法是一个强大的预测方法,它非常流行。因为它们的模型能够让新手轻而易举地理解得和专家一样好,所以它们比较流行。同时,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,621
精华内容 1,848
关键字:

python决策树剪枝

python 订阅