精华内容
下载资源
问答
  • 主要介绍了决策树剪枝算法的python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下
  • 决策树剪枝算法

    2018-03-16 21:16:08
    决策树剪枝 决策树为了防止过拟合,会采用剪枝的方式,符合奥卡姆剃刀原理。决策树剪枝分为预剪枝(pre-pruning)和后剪枝(post-pruning)。 预剪枝 预剪枝是在决策树生成时限制树的生长,防止树过度生长而导致...

    决策树剪枝

    决策树为了防止过拟合,会采用剪枝的方式,符合奥卡姆剃刀原理。决策树剪枝分为预剪枝(pre-pruning)和后剪枝(post-pruning)。

    预剪枝

    预剪枝是在决策树生成时限制树的生长,防止树过度生长而导致过拟合。常用方法有:限制树的高度、限制树的叶子结点数、设置分裂时增益的阈值(低于阈值就不继续分裂)。

    后剪枝

    相比预剪枝,后剪枝使用更广泛。主要有:

    • REP (Reduce-Error Pruning): 降低错误率剪枝
    • PEP (Pessimistic-Error Pruning): 悲观剪枝
    • CCP (Cost-Complexity Pruning): 代价复杂度剪枝
    • EBP (Error-Based Pruning): 基于错误的剪枝
    展开全文
  • 本文实例讲述了决策树剪枝算法的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学习者聚集地

    展开全文
  • 决策树剪枝算法原理

    万次阅读 2017-05-31 22:22:52
    算法目的:决策树剪枝是为了简化决策树模型,避免过拟合。 同样层数的决策树,叶结点的个数越多就越复杂;同样的叶结点个数的决策树,层数越多越复杂。 剪枝前相比于剪枝后,叶结点个数和层数只能更多或者其中一...

    算法目的:

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

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

    算法基本思路:

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

    模型损失函数

    1. 变量预定义:∣Tleaf∣|T_{leaf}|Tleaf表示树T的叶结点个数,记号t表示树T的某个叶结点,同时,NtN_tNt表示该叶结点含有的样本点个数,其中属于k类的样本点有NtkN_{tk}Ntk个,K表示类别的个数,Ht(T)H_t(T)Ht(T)为叶结点t上的经验熵,α≥0\alpha≥0α0为参数。
      注:显然有Nt=∑k=1KNtkN_t=\displaystyle \sum^{K}_{k=1} {N_{tk}}Nt=k=1KNtk
    2. 损失函数(经验熵损失):Ht(T)=−∑k=1KNtkNtlog⁡NtkNtH_t(T) = -\displaystyle \sum_{k=1}^K \frac {N_{tk}} {N_t} \log \frac {N_{tk}}{N_t}Ht(T)=k=1KNtNtklogNtNtk
      注:以经验熵为评价函数(即损失函数Loss(Y,T(x))Loss(Y,T(x))Loss(Y,T(x)))。称为经验熵,是因为它是基于样本对真实随机变量的熵的估计。
    3. 经验风险:C(T)=∑t=1∣Tleaf∣NtHt(T)C(T)=\displaystyle \sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)}C(T)=t=1TleafNtHt(T)
      注:损失函数的期望称为期望风险,需要知道整个特征空间的联合概率分布求积分,通常用经验风险估计它,即用样本的损失函数的期望对它估计,与经验熵的叫法类似。
    4. 结构风险(目标函数):Ca(T)=∑t=1∣Tleaf∣NtHt(T)+α∣Tleaf∣C_a(T)=\displaystyle \sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)+\alpha|T_{leaf}|}Ca(T)=t=1TleafNtHt(T)+αTleaf
      注:结构风险=经验风险+正则项,正则项即是惩罚项,与模型复杂度正相关,可减轻过拟合。
      目标函数简化形式:Ca(T)=C(T)+α∣Tleaf∣C_a(T)=C(T)+\alpha|T_{leaf}|Ca(T)=C(T)+αTleaf
    • 经验熵反映了一个叶结点中的分类结果的混乱程度。经验熵越大,说明该叶结点所对应的分类结果越混乱,也就是说分类结果中包含了较多的类别,表明该分支的分类效果较差。
    • 评价函数越小越好。经验熵越小越好。而以经验熵作为评价函数,其值越大,说明模型的分类效果越差,因而又称损失函数。
    • 经验风险其实是求叶结点的经验熵期望。用NtN_tNt给经验熵加权的依据是叶子节点含有的样本个数越多,其分类效果或混乱程度越占主导,相当于求样本期望,可以更好的描述分支前后的关系。例如设一个结点r有n个样本,其组成是第i类有nin_ini个样本,在分了几个孩子结点后各个叶结点的成分仍保持原比例,记新的子树为R,可以计算得出评价函数C(r)=C(R)C(r)=C(R)C(r)=C(R),即在随机分组后不会有任何分类效果的改进。
    • 修正项α∣Tleaf∣\alpha|T_{leaf}|αTleaf被称为正则项或惩罚项,表示模型复杂度。加入正则项的原因有2个:a.模型过于复杂会出现过拟合现象(在训练集上表现较好而在测试集上表现较差);b.在保障效果的同时尽可能选取简单的模型(即奥卡姆剃刀原理)。如上面提到的随机分组的例子,r与R其实在评价函数评估后的得分是一样的,但是我们仍然觉得r更好,原因在于R的复杂度更高。此外,加了此正则项后,α\alphaα的值具有与现实对应的意义:当α=0\alpha=0α=0,表示未剪枝的完全树损失更小(熵更小的占主导地位);当α−>∞\alpha->∞α>,表示剪枝到只剩根结点更好(叶结点个数占主导地位)。
      正则项α∣Tleaf∣\alpha|T_{leaf}|αTleaf可以避免过拟合的解释。正则项α∣Tleaf∣\alpha|T_{leaf}|αTleaf考虑到了复杂度,α\alphaα值设置得好可以避免出现完全树和根结点这类的极端情况,因此可以避免过拟合。加入了正则项,目标函数将从“经验风险”变为“结构风险”,即结构风险=经验风险+正则项。
      纯结点的经验熵Hp=0H_p=0Hp=0最小,即设Ntj=NtN_{tj}=N_tNtj=Nt则有Hp=−(1log⁡1+∑k=1...K且k≠j0)=0H_p=-(1\log 1+\displaystyle \sum_{k=1...K且k≠j} {0})=0Hp=(1log1+k=1...Kk=j0)=0
      均结点的经验熵Hu=log⁡KH_u=\log KHu=logK最大,即Hp=−∑k=1K1Klog⁡1K=log⁡KH_p=-\displaystyle \sum^{K}_{k=1} {\frac{1}{K}\log\frac{1}{K}}=\log KHp=k=1KK1logK1=logK

    剪枝类型:

    预剪枝、后剪枝

    • 预剪枝是在决策树生成过程中,对树进行剪枝,提前结束树的分支生长。
    • 后剪枝是在决策树生长完成之后,对树进行剪枝,得到简化版的决策树。

    预剪枝依据:

    • 作为叶结点或作为根结点需要含的最少样本个数
    • 决策树的层数
    • 结点的经验熵小于某个阈值才停止

    后剪枝思路:

    1. 如何由TiT_iTi剪枝得到Ti−1T_{i-1}Ti1
      如图
      R为r结点分支后的子树
    • Cα(r)=C(r)+αC_\alpha(r)=C(r)+\alphaCα(r)=C(r)+α
    • Cα(R)=C(R)+NR∗αC_\alpha(R)=C(R)+N_R*\alphaCα(R)=C(R)+NRα,其中NRN_RNR为子树R的叶子结点数
    • 一般地有C(r)>=C(R)C(r)>=C(R)C(r)>=C(R), 我们可以令Cα(r)=Cα(R)C_\alpha(r)=C_\alpha(R)Cα(r)=Cα(R)求出α=C(r)−C(R)NR−1\alpha=\frac{C(r)-C(R)}{N_R-1}α=NR1C(r)C(R)
    • 当我们把所有的非叶结点的α\alphaα求出来后比较它们的α\alphaα值,在最小的α\alphaα所在结点处剪枝。
      为什么要在最小的α\alphaα所在结点处剪枝:设给定一α\alphaα来求两个结点r1r_1r1r2r_2r2处的损失函数Cα(r1)C_\alpha(r_1)Cα(r1)Cα(r2)C_\alpha(r_2)Cα(r2)以判定是否适合继续分支,且使得给定的α\alphaα介于它们自己的阈值参数α1\alpha_1α1α2\alpha_2α2之间,假设α1\alpha_1α1<α\alphaα<α2\alpha_2α2。则
      对于r1r_1r1来说,α1\alpha_1α1<α\alphaαα\alphaα给大了,参数占主导,剪枝能使得叶结点数(即参数的系数)变小,剪枝能使得Cα(r1)C_\alpha(r_1)Cα(r1)较小,剪枝更好;
      对于r2r_2r2来说,α\alphaα<α2\alpha_2α2α\alphaα给小了,C(r2)−C(R2)C(r_2)-C(R_2)C(r2)C(R2)的值占主导,即
      Cα(r)−Cα(R)C_\alpha(r)- C_\alpha(R)Cα(r)Cα(R)
      =C(r)+α−C(R)−NR∗α=C(r)+\alpha-C(R)-N_R*\alpha=C(r)+αC(R)NRα
      =[C(r2)−C(R2)]+[1−NR]∗α= [C(r_2)-C(R_2)]+[1-N_R]*\alpha=[C(r2)C(R2)]+[1NR]α
      不剪枝能使得叶结点数(即参数的系数)更大,Cα(r)−Cα(R)C_\alpha(r)- C_\alpha(R)Cα(r)Cα(R)更接近0,剪枝更好。
      我们看出参数阈值较小的r1r_1r1处剪枝更好,因此要在最小的α\alphaα所在结点处剪枝。
    1. TiT_iTi剪枝得到Ti−1T_{i-1}Ti1后,可以得出T0−>T1−>T2−>...−>TnT_0->T_1->T_2->...->T_nT0>T1>T2>...>Tn,但不一定每次剪枝都能使得损失函数降低,可以对每一个TiT_iTi算出其损失函数进行比较,取损失函数值最小的那棵决策树。

    注:10 决策树和随机森林实践
    参考:http://blog.csdn.net/ritchiewang/article/details/50254009

    展开全文
  • 决策树剪枝算法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

    展开全文
  • 文章目录CART算法1. CART生成算法①. CART回归树的生成②. CART分类树的生成2. CART剪枝算法 CART算法 CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”。...(2)决策树剪枝:用验证数据集对已生成的树...
  • 前言  在机器学习经典算法中,决策树算法的重要性想必大家都是知道的。不管是ID3算法还是比如C4.5算法等等,都面临一个问题,就是通过直接生成...解决这个问题的方法就是对决策树进行剪枝,剪去影响预测精度的分支...
  • 算法目的:决策树剪枝是为了简化决策树模型,避免过拟合。同样层数的决策树,叶结点的个数越多就越复杂;同样的叶结点个数的决策树,层数越多越复杂。剪枝前相比于剪枝后,叶结点个数和层数只能更多或者其中一特征...
  • 决策树剪枝算法(二)

    千次阅读 2017-06-01 16:15:05
    上一章主要描述了ID3算法的的原理,它是以信息熵为度量,用于决策树节点的属性选择,每次优选信息量最多 的属性,以构造一颗熵值下降最快的决策树,到叶子节点处的熵值为0,此时每个叶子节点对应的实例集中的实例...
  • 决策树剪枝算法的研究,决策树剪枝算法的研究,决策树剪枝算法的研究
  • 决策树——剪枝算法

    2020-11-20 14:33:42
    剪枝算法主要分为两种,预剪枝和后剪枝 2.1 预剪枝 预剪枝是在构建决策树的过程中,提前停止使模型性能变差的分支 预剪枝方法: 当树的深度达到一定的规模,停止生长。 当前节点的样本数量小于某个阈值,停止...
  • 决策树学习及其剪枝算法研究论文。
  • 5-5 决策树剪枝算法

    2020-04-08 19:10:24
    树的剪枝算法 输入: ID3或C4.5的决策树 参数a 输出: 剪枝后的决策树TaT_aTa​ 递归版本 从树的根结点开始 如果该结点的孩子中存在子树(不全是叶子结点),则先对子树做prune 所有子树都prune之后,再判断该结点...
  • 决策树剪枝

    2019-07-26 16:18:52
    知识交点:决策树剪枝 为什么要剪枝 一颗完全生长的决策树难免会遇到过拟合的情况。因此,我们需要对决策树进行剪枝,提升模型的泛化能力。 决策树的剪枝操作通常有两种方法,预剪枝与后剪枝。 预剪枝 预剪枝的核心...
  • 参考了两篇文章: 基本概念和经典算法 ID3 C4.5 CART的理解参考: ... 剪枝算法常用的有悲观错误剪枝法和代价复杂度剪枝法参考: https://www.cnblogs.com/starfire86/p/5749334.html...
  • 利用Mtalab编写实现决策树生成ID3算法,利用Sogou_webpage数据集进行训练、验证与测试。之后实现剪枝
  • 决策树剪枝通常有两种方法,预剪枝( Pre-Pruning )和后剪枝( Post-Pruning )。 预剪枝( Pre-Pruning ) 预剪枝 , 即在生成决策树的过程中提前停止树的增长。核心思想是在树中结点进行扩展之前,先计算当前的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,270
精华内容 6,108
关键字:

决策树剪枝算法