精华内容
下载资源
问答
  • python决策树例题经典案例-决策树python实现小样例
    千次阅读
    2020-11-11 14:54:45

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

    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 实现

    2018-05-20 12:06:17
    决策树入门了解,数据挖掘经典算法之一,内容包括决策树的实例,是入门的必备材料!
  • 最终实现了基于基尼系数和基于信息熵的两种决策树模型,能够处理离散型数据和连续型数据,并将生成的决策树可视化。在模型评估时还实现了基于numpy和pandas的准确率计算、混淆矩阵计算与可视化函数。
  • 决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画...
  • 决策树python实现

    热门讨论 2014-03-10 21:36:25
    基于python逐步实现Decision Tree(决策树),分为以下几块: 加载数据集 熵的计算 根据最佳分割feature进行数据分割 根据最大信息增益选择最佳分割feature 递归构建决策树 样本分类
  • 本压缩包包含: 1.本决策树(DecisionTree)项目python源代码文件; 2.项目用的数据(csv格式); 3.一个普通文件,记录本项目的调试过程,用作实战参考
  • 《机器学习实战》决策树python实现,《统计学习方法》第五章决策树,使用python实现决策树的一个例子,详细的注释,可读性更高。 参照我的博客链接https://blog.csdn.net/u012324136/article/details/80894993
  • c4.5基于信息增益比的多分类决策树python实现,包含数据集,运行结果以字典的形式进行存储
  • 目录python实现分步源代码(全部)测试集1(鸢尾花集)测试集2(红酒品类数据集)总结 python实现 分步 划分数据子集(注意区分离散特征值和连续特征值) #获取数据子集,分类与回归的做法相同 #将数据集根据划分...


    python实现

    分步

    • 划分数据子集(注意区分离散特征值和连续特征值)
    #获取数据子集,分类与回归的做法相同
    #将数据集根据划分特征切分为两类
    def split_dataset(data_x,data_y,fea_axis,fea_value):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
              fea_axis(int):进行划分的特征编号(列数)
              fea_value(int):进行划分的特征对应特征值
        output:data_x[equal_Idx],data_y[equal_Idx](ndarry):特征值等于(大于等于)目标特征值的样本与标签
               data_x[nequal_Idx],data_y[nequal_Idx](ndarry):特征值不等于(小于)目标特征的样本与标签
        '''
        if  isinstance(fea_value,float): 
            #如果特征值为浮点数(连续特征值),那么进行连续值离散化
            equal_Idx = np.where(data_x[:,fea_axis]>=fea_value) #找出特征值大于等于fea_alue的样本序号
            nequal_Idx = np.where(data_x[:,fea_axis]<fea_value) #找出特征值小于fea_alue的样本序号
        else:
            equal_Idx = np.where(data_x[:,fea_axis]==fea_value) #找出特征值等于fea_alue的样本序号
            nequal_Idx = np.where(data_x[:,fea_axis]!=fea_value) #找出特征值不等于fea_alue的样本序号
        return data_x[equal_Idx],data_y[equal_Idx],data_x[nequal_Idx],data_y[nequal_Idx]
    
    • 求解基尼系数(在该数据集相下,随机抽取两个样本,标签不同的概率)
    #使用决策树进行分类需要用到
    #求解基尼系数,即两个样本不属于同一标签的概率(二分类问题)
    def cal_gini(data_y):
        '''
        input:data_y(ndarry):标签值
        output:gini(float):基尼指数
        '''
        m = len(data_y)  #全部样本的标签数量
        labels = np.unique(data_y) #获得不同种类的标签(去重)
        gini = 1.0  #最后返回的基尼指数
        for label in labels:
            ans = data_y[np.where(data_y[:]==label)].size/m  #该标签的出现概率
            gini -= ans*ans  #累减计算基尼指数(两两不同的总概率)
        return gini
    
    • 最优特征选取以及特征值划分(遍历计算每个特征下每个特征值的基尼系数,取最小值(纯度最高)进行划分标准)
    #分类方法实现最优特征的选取以及特征值划分
    def classify_get_best_fea(data_x,data_y):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
        output:best_fea(int):最优特征
               best_fea_val(int):最优特征值
        '''
        m,n = np.shape(data_x)  #m,n分别为样本数以及特征属性数
        #初始化
        best_fea = -1
        best_fea_val = -1
        min_fea_gini = np.inf
        
        for i in range(n):  #遍历所有特征(列)
            feas = np.unique(data_x[:,i])  #获得该特征下所有特征值
            #分别以每个特征值为中心进行划分求基尼系数,找到使基尼系数最小的划分
            for j in feas:
                equal_data_x,equal_data_y,nequal_data_x,nequal_data_y = split_dataset(data_x,data_y,i,j)
                fea_gini = 0.0
                #计算该划分下的基尼系数
                fea_gini = len(equal_data_y)/m*cal_gini(equal_data_y)+len(nequal_data_y)/m*cal_gini(nequal_data_y)
                #如果该划分方式的基尼系数更小(纯度更高),那么直接进行更新
                if fea_gini<min_fea_gini:
                    min_fea_gini = fea_gini
                    best_fea = i
                    best_fea_val = j
            
        return best_fea,best_fea_val
    
    • 创建分类决策树(使用递归的方法构建决策树字典,注意处理特殊情况:只有一类标签的情况,无特征的情况,当基尼系数过低时也可以中断划分)
    #创建分类方法的决策树
    def classify_create_tree(data_x,data_y,fea_label):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
              fea_label(list):特征属性列表
        output:my_tree(dict):生成的CART分类树
        '''
        labels = np.unique(data_y)
        #只有一个标签的情况
        if len(labels)==1:
            return data_y[0]
        #特征集为0的情况,采用多数投票的方法
        if data_x.shape[1]==0:
            best_fea,best_fea_num = 0,0
            for label in labels:
                num = data_y[np.where(data_y==label)].size
                if num>best_fea_num:
                    best_fea = label
                    best_fea_num = num
            return best_fea
        
        best_fea,best_fea_val = classify_get_best_fea(data_x,data_y)
        best_fea_label = fea_label[best_fea]
        print(u"此时最优索引为:"+str(best_fea_label))
        my_tree = {best_fea_label:{}}
        
        #获得划分结果
        equal_data_x,equal_data_y,nequal_data_x,nequal_data_y = split_dataset(data_x,data_y,best_fea,best_fea_val)
        #删除最优特征
        equal_data_x = np.delete(equal_data_x,best_fea,1)
        nequal_data_x = np.delete(nequal_data_x,best_fea,1)
        
        fea_label = np.delete(fea_label,best_fea,0)
        
        #递归生成CART分类树
        my_tree[best_fea_label]["{}_{}".format(1,best_fea_val)] = classify_create_tree(equal_data_x,equal_data_y,fea_label)
        my_tree[best_fea_label]["{}_{}".format(0,best_fea_val)] = classify_create_tree(nequal_data_x,nequal_data_y,fea_label)
    
        return my_tree
    

    ​ 决策树字典格式为{“划分属性”:{“含于该划分值中”,划分结果/继续分类},{“不含于该划分值中”,划分结果/继续分类}},注意在判断是否含于该划分值中,构建如“1_划分值”, “0 _划分值”这样的字符串,1表示包含,0表示不包含。如下如所示:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pgWzKlis-1637412940662)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120181205717.png)]

    • 测试函数

      #测试操作
      import re
      #预测一条测试数据结果
      def classify(inputTree,xlabel,testdata):
          '''
          input:inputTree(dict):CART分类决策树
                xlabel(list):特征属性列表
                testdata(darry):一条测试数据特征值
          output:classLabel(int):测试数据预测结果
          '''
          firstStr = list(inputTree.keys())[0]
          secondDict = inputTree[firstStr]
          featIndex = xlabel.index(firstStr)#根据key值得到索引
          classLabel = '0'#定义变量classLabel,默认值为0
          
          ans = re.findall(r'\d+\.\d+',list(secondDict.keys())[0])
          if isinstance(testdata[featIndex],float):
              if float(testdata[featIndex]) >= float(ans[0]):
                  if type(secondDict['1_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                          classLabel = classify(secondDict['1_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                  else:
                      classLabel = secondDict['1_'+ans[0]]
              else:
                  if type(secondDict['0_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                          classLabel = classify(secondDict['0_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                  else:
                      classLabel = secondDict['0_'+ans[0]]
              return int(classLabel)
          else:
              if float(testdata[featIndex]) == float(ans[0]):
                  if type(secondDict['1_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                          classLabel = classify(secondDict['1_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                  else:
                      classLabel = secondDict['1_'+ans[0]]
              else:
                  if type(secondDict['0_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                          classLabel = classify(secondDict['0_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                  else:
                      classLabel = secondDict['0_'+ans[0]]
              return int(classLabel)
      
      #预测所有测试数据结果
      def classifytest(inputTree, xlabel, testDataSet):
          '''
          input:inputTree(dict):训练好的决策树
                xlabel(list):特征值标签列表
                testDataSet(ndarray):测试数据集
          output:classLabelAll(list):测试集预测结果列表
          '''    
          classLabelAll = []#创建空列表
          for testVec in testDataSet:#遍历每条数据
              classLabelAll.append(classify(inputTree, xlabel, testVec))#将每条数据得到的特征标签添加到列表
          return  np.array(classLabelAll)
      

    源代码(全部)

    import numpy as np
    import re
    #获取数据子集,分类与回归的做法相同
    #将数据集根据划分特征切分为两类
    def split_dataset(data_x,data_y,fea_axis,fea_value):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
              fea_axis(int):进行划分的特征编号(列数)
              fea_value(int):进行划分的特征对应特征值
        output:data_x[equal_Idx],data_y[equal_Idx](ndarry):特征值等于(大于等于)目标特征值的样本与标签
               data_x[nequal_Idx],data_y[nequal_Idx](ndarry):特征值不等于(小于)目标特征的样本与标签
        '''
        if  isinstance(fea_value,float): 
            #如果特征值为浮点数(连续特征值),那么进行连续值离散化
            equal_Idx = np.where(data_x[:,fea_axis]>=fea_value) #找出特征值大于等于fea_alue的样本序号
            nequal_Idx = np.where(data_x[:,fea_axis]<fea_value) #找出特征值小于fea_alue的样本序号
        else:
            equal_Idx = np.where(data_x[:,fea_axis]==fea_value) #找出特征值等于fea_alue的样本序号
            nequal_Idx = np.where(data_x[:,fea_axis]!=fea_value) #找出特征值不等于fea_alue的样本序号
        return data_x[equal_Idx],data_y[equal_Idx],data_x[nequal_Idx],data_y[nequal_Idx]
    
    #使用决策树进行分类需要用到
    #求解基尼指数,即两个样本不属于同一标签的概率(二分类问题)
    def cal_gini(data_y):
        '''
        input:data_y(ndarry):标签值
        output:gini(float):基尼指数
        '''
        m = len(data_y)  #全部样本的标签数量
        labels = np.unique(data_y) #获得不同种类的标签(去重)
        gini = 1.0  #最后返回的基尼指数
        for label in labels:
            ans = data_y[np.where(data_y[:]==label)].size/m  #该标签的出现概率
            gini -= ans*ans  #累减计算基尼指数(两两不同的总概率)
        return gini
    
    #分类方法实现最优特征的选取以及特征值划分
    def classify_get_best_fea(data_x,data_y):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
        output:best_fea(int):最优特征
               best_fea_val(int):最优特征值
        '''
        m,n = np.shape(data_x)  #m,n分别为样本数以及特征属性数
        #初始化
        best_fea = -1
        best_fea_val = -1
        min_fea_gini = np.inf
        
        for i in range(n):  #遍历所有特征(列)
            feas = np.unique(data_x[:,i])  #获得该特征下所有特征值
            #分别以每个特征值为中心进行划分求基尼系数,找到使基尼系数最小的划分
            for j in feas:
                equal_data_x,equal_data_y,nequal_data_x,nequal_data_y = split_dataset(data_x,data_y,i,j)
                fea_gini = 0.0
                
                fea_gini = len(equal_data_y)/m*cal_gini(equal_data_y)+len(nequal_data_y)/m*cal_gini(nequal_data_y)
                #如果该划分方式的基尼系数更小(纯度更高),那么直接进行更新
                if fea_gini<min_fea_gini:
                    min_fea_gini = fea_gini
                    best_fea = i
                    best_fea_val = j
            
        return best_fea,best_fea_val
    
    #创建分类方法的决策树
    def classify_create_tree(data_x,data_y,fea_label):
        '''
        input:data_x(ndarry):特征值
              data_y(ndarry):标签值
              fea_label(list):特征属性列表
        output:my_tree(dict):生成的CART分类树
        '''
        labels = np.unique(data_y)
        #只有一个标签的情况
        if len(labels)==1:
            return data_y[0]
        #特征集为0的情况,采用多数投票的方法
        if data_x.shape[1]==0:
            best_fea,best_fea_num = 0,0
            for label in labels:
                num = data_y[np.where(data_y==label)].size
                if num>best_fea_num:
                    best_fea = label
                    best_fea_num = num
            return best_fea
        
        best_fea,best_fea_val = classify_get_best_fea(data_x,data_y)
        best_fea_label = fea_label[best_fea]
        print(u"此时最优索引为:"+str(best_fea_label))
        my_tree = {best_fea_label:{}}
        
        #获得划分结果
        equal_data_x,equal_data_y,nequal_data_x,nequal_data_y = split_dataset(data_x,data_y,best_fea,best_fea_val)
        #删除最优特征
        equal_data_x = np.delete(equal_data_x,best_fea,1)
        nequal_data_x = np.delete(nequal_data_x,best_fea,1)
        
        fea_label = np.delete(fea_label,best_fea,0)
        
        #递归生成CART分类树
        my_tree[best_fea_label]["{}_{}".format(1,best_fea_val)] = classify_create_tree(equal_data_x,equal_data_y,fea_label)
        my_tree[best_fea_label]["{}_{}".format(0,best_fea_val)] = classify_create_tree(nequal_data_x,nequal_data_y,fea_label)
    
        return my_tree
    
    #预测一条测试数据结果
    def classify(inputTree,xlabel,testdata):
        '''
        input:inputTree(dict):CART分类决策树
              xlabel(list):特征属性列表
              testdata(darry):一条测试数据特征值
        output:classLabel(int):测试数据预测结果
        '''
        firstStr = list(inputTree.keys())[0]
        secondDict = inputTree[firstStr]
        featIndex = xlabel.index(firstStr)#根据key值得到索引
        classLabel = '0'#定义变量classLabel,默认值为0
        
        ans = re.findall(r'\d+\.\d+',list(secondDict.keys())[0])
        if isinstance(testdata[featIndex],float):
            if float(testdata[featIndex]) >= float(ans[0]):
                if type(secondDict['1_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                        classLabel = classify(secondDict['1_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                else:
                    classLabel = secondDict['1_'+ans[0]]
            else:
                if type(secondDict['0_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                        classLabel = classify(secondDict['0_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                else:
                    classLabel = secondDict['0_'+ans[0]]
            return int(classLabel)
        else:
            if float(testdata[featIndex]) == float(ans[0]):
                if type(secondDict['1_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                        classLabel = classify(secondDict['1_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                else:
                    classLabel = secondDict['1_'+ans[0]]
            else:
                if type(secondDict['0_'+ans[0]]).__name__ == 'dict':#判断secondDict[key]是否是字典格式
                        classLabel = classify(secondDict['0_'+ans[0]], xlabel, testdata)#如果是字典格式,进行递归
                else:
                    classLabel = secondDict['0_'+ans[0]]
            return int(classLabel)
    
    #预测所有测试数据结果
    def classifytest(inputTree, xlabel, testDataSet):
        '''
        input:inputTree(dict):训练好的决策树
              xlabel(list):特征值标签列表
              testDataSet(ndarray):测试数据集
        output:classLabelAll(list):测试集预测结果列表
        '''    
        classLabelAll = []#创建空列表
        for testVec in testDataSet:#遍历每条数据
            classLabelAll.append(classify(inputTree, xlabel, testVec))#将每条数据得到的特征标签添加到列表
        return  np.array(classLabelAll)
    

    测试集1(鸢尾花集)

    全部属性以及部分标签如下:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vUOmkfyz-1637412940665)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120182558070.png)]

    导入以及训练CART分类树过程如下:

    #测试数据集一(鸢尾花集)
    import pandas
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import OneHotEncoder
    
    #导入数据集iris
    url = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"
    names = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'class']
    dataset = pandas.read_csv(url, names=names) #读取csv数据
    dataset.head()
    X = dataset.iloc[:,:-1].values
    y = dataset.iloc[:,-1].values
    #将标签分别改为0,1,2
    for i in range(len(y)):
        if y[i]=='Iris-setosa':
            y[i]=0
        elif y[i]=='Iris-versicolor':
            y[i]=1
        elif y[i]=='Iris-virginica':
            y[i]=2
    
    #获得特征属性名称列表
    fea_label = names[:-1]
    #划分训练集与测试集,参数test_size设为0.3,random_state设为666
    x_train,x_test,y_train,y_test = train_test_split(X,y,test_size = 0.3,random_state = 666)
    #生成CART分类树
    cartTree = classify_create_tree(x_train,y_train,fea_label)
    print(cartTree)
    

    生成结果如下:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4yr9rFn1-1637412940667)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120182033087.png)]

    选取测试数据进行测试,并计算相应的分类正确率:

    classlist=classifytest(cartTree,names,x_test)
    print("预测结果",classlist)
    print("真实结果",y_test)
    print("准确率为:%.4f"%np.mean(classlist==y_test))
    

    结果如下:

    在这里插入图片描述


    测试集2(红酒品类数据集)

    13个属性如下图所示:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AERzqg3m-1637412940671)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120182924343.png)]

    导入以及训练CART分类树过程如下:

    #测试数据集二
    from sklearn.datasets import load_wine
    wine = load_wine()
    data = wine.data
    target = wine.target
    fea_names = list(wine.feature_names)
    
    
    # #划分训练集与测试集,参数test_size设为0.3,random_state设为666
    x_train,x_test,y_train,y_test = train_test_split(data,target,test_size = 0.35,random_state = 666)
    # #生成CART分类树
    cartTree = classify_create_tree(x_train,y_train,fea_names)
    print(cartTree)
    

    生成结果如下:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kv3GvQ3E-1637412940673)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120204946213.png)]

    选取测试数据进行测试,并计算相应的分类正确率:

    classlist=classifytest(cartTree,fea_names,x_test)
    print("预测结果",classlist)
    print("真实结果",y_test)
    print("准确率为:%.4f"%np.mean(classlist==y_test))
    

    结果如下:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-p8w4Y8MC-1637412940674)(C:\Users\CQU  CJ\AppData\Roaming\Typora\typora-user-images\image-20211120205100255.png)]


    总结

    (1)主要面对特征值离散或者连续的问题,离散值只需要判断是否相等就可以进行二分类,而连续值需要不断的选择不同的特征值进行划分,然后计算求得基尼系数,选取基尼系数最小的情况作为划分结果。

    (2)因为可能存在连续的属性,也可能存在离散的属性,所以在划分子集的时候,对这些情况就需要考虑全面。不同的值对应不同的划分方法。同样对于测试集的预测,我们也需要更具不同的属性选择不同的预测方式。

    展开全文
  • 主要介绍了决策树剪枝算法的python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下
  • 决策树python代码

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

    千次阅读 2021-07-15 11:35:03
    本文摘要:决策树的概述,决策树相关概念以及公式,构建决策树的三种算法:ID3、C4.5、CART,用Python实现ID3算法,用sklearn实现决策树

    概述

    决策树

      决策树是一种树形结构,包括决策结点(内部结点)、分支和叶节点三部分。其中,决策结点代表某个测试,通常对应于待分类对象的某个属性,在该属性上的不同测试结果对应一个分支。每个叶节点存放某个类标号值,表示一种可能的分类结果。
      决策树是一种常用的分类方法。它是一种监督学习,所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

    决策树的剪枝

      剪枝是决策树停止分支的方法之一,剪枝有分预先剪枝和后剪枝两种。
      预先剪枝是在树的生长过程中设定一个指标,当达到该指标时就停止生长,这样做容易产生“视界局限”,就是一旦停止分支,使得节点N成为叶节点,就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法,导致产生的树不纯度降差最大的地方过分靠近根节点。
      后剪枝中树首先要充分生长,直到叶节点都有最小的不纯度值为止,因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们,如果消去能引起令人满意的不纯度增长,那么执行消去,并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反,经过剪枝后叶节点常常会分布在很宽的层次上,树也变得非平衡。

    优缺点

    优点:决策树易于理解和实现;易于通过静态测试来对模型进行评测,可以测定模型可信度;如果给定一个观察的模型,那么根据所产生的决策树很容易推出相应的逻辑表达式。
    缺点:对连续性的字段比较难预测;对有时间顺序的数据,需要很多预处理的工作;当类别太多时,错误可能就会增加的比较快;一般的算法分类的时候,只是根据一个字段来分类。

    决策树的构建

    特征选择/计算公式

      特征选择即决定用哪个特征来划分特征空间,其目的在于选取对训练数据具有分类能力的特征,提高决策树的学习效率。决策树需要找出最佳节点和最佳的分枝方法,而衡量这个“最佳”的指标叫做不纯度。由此还衍生出其他两个常用指标,一个是ID3中信息增益的计算方法可用熵推导,即最为人熟知的信息熵,又叫香农熵,另一个是基尼系数,主要用于CART决策树的纯度判定中。
      决策树最终的优化目标是使得叶节点的总不纯度最低,即对应衡量不纯度的指标最低。

    不纯度

      决策树的每个叶子节点都会包含一组数据,在这组数据中,如果有某一类标签占有较大的比例,就说叶子节点“纯”,分枝分得好。某一类标签占的比例越大,叶子就越纯,不纯度就越低,分枝就越好。
      如果没有哪一类标签的比例很大,各类标签都相对平均,则说叶子节点“不纯”,分枝不好,不纯度高。
      定义 t t t代表决策树的某个节点, D t D_t Dt t t t节点所对应的数据集,设第 i i i类样本为 x i x_i xi p ( x i ) p(x_i) p(xi)是选择该分类的概率,这个比例越高,则代表叶子越纯。对于节点不纯度的计算和表示方法因决策树模型而异,但不管不纯度的度量方法如何,都是有误差率衍生而来,误差率越低,则纯度越高。误差率的计算公式如下:
    C l a s s i f i c a t i o n    e r r o r ( t ) = 1 − max ⁡ i = 1 p ( x i ) Classification\ \ error(t) = 1 - \max_{i=1}p(x_i) Classification  error(t)=1i=1maxp(xi)

    香农熵(Entropy)

    假定当前样本集合 D D D中一共有 n n n类样本,第 i i i类样本为 x i x_i xi p ( x i ) p(x_i) p(xi)是选择该分类的概率,则 x i x_i xi信息定义为:
    l ( x i ) = − l o g 2 p ( x i ) l(x_i) = -log_2p(x_i) l(xi)=log2p(xi)

    通过上式,可以得到所有类别的信息,为了计算熵,需要计算所有类别所有可能值包含的信息期望(数学期望),香农熵的计算公式如下:
    E n t r o p y ( D ) = − ∑ i = 1 n p ( x i ) l o g 2 p ( x i ) Entropy(D) = -\sum_{i=1}^n p(x_i)log_2p(x_i) Entropy(D)=i=1np(xi)log2p(xi)

    信息增益(Information Gain)

    信息增益的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。但此时子节点的总信息熵不能简单求和,而要求在求和汇总之前进行修正。
    假设离散属性 a a a V V V个可能的取值 { a 1 , a 2 , . . . . . . , a V } \{a^1, a^2, ...... ,a^V\} {a1,a2,......,aV},若使用 a a a对样本数据集 D D D进行划分,则会产生 V V V个分支节点,其中第 v v v个分支节点包含了 D D D中所有在属性 a a a上取值为 a v a^v av的样本,记为 D v D^v Dv。根据信息熵的计算公式计算出 D v D^v Dv的信息熵,再考虑到不同分支节点说包含的样本数不同,给分支节点赋予权重 ∣ D v ∣ / ∣ D ∣ |D^v|/|D| Dv/D,进行修正。所以,信息增益的计算公式如下:
    G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|} {|D|}Ent(D^v) Gain(D,a)=Ent(D)v=1VDDvEnt(Dv)

    基尼(Gini)指数

    基尼指数主要用于CART决策树的纯度判定中。假定当前样本集合 D D D中一共有 n n n类样本,第 i i i类样本为 x i x_i xi p ( x i ) p(x_i) p(xi)是选择该分类的概率,基尼系数的计算公式如下:
    G i n i = 1 − ∑ i = 1 n [ p ( x i ) ] 2 Gini = 1 - \sum_{i=1}^{n}[p(x_i)]^2 Gini=1i=1n[p(xi)]2

    分支度(Information Value)

      在C4.5中,引入分支度的概念对信息增益的计算方法进行修正,简而言之,就是在信息增益计算方法的子节点总信息熵的计算方法中添加了随着分类变量水平的惩罚项。而分支度的计算公式仍然是基于熵的算法,只是将信息熵计算公式中的 p ( x i ) p(x_i) p(xi)(即某类别样本占总样例数)改成了 p ( v i ) p(v_i) p(vi),即某子节点的总样本数占父节点总样本数的比例。这个分支度指标让我们在切分的时候,自动避免那些分类水平太多,信息熵减小过快的特征影响模型,减少过拟合情况。IV计算公式如下
    I n f o r m a t i o n    V a l u e = − ∑ i = 1 k p ( v i ) l o g 2 p ( v i ) Information\ \ Value=-\sum_{i=1}^k p(v_i)log_2p(v_i) Information  Value=i=1kp(vi)log2p(vi)

      其中, i i i表示父节点的第 i i i个子节点, v i v_i vi表示第 i i i个子节点样例数, p ( v i ) p(v_i) p(vi)表示第 i i i个子节点拥有样例数占父节点总样例数的比例。
      IV值可作为惩罚项带入子节点的信息熵计算中,IV值会随着叶子结点上的样本量的变小而逐渐变大,也就是说一个特征中如果标签分类太多,每个叶子上的IV值就会非常大。

    信息增益率(Gain Ratio)

      在C4.5中,使用信息增益除以分支度作为选取切分字段的参考指标,该指标被称作Gain Ratio(获利比例,或信息增益率),其计算公式如下:
    G a i n    R a t i o = I n f o r m a t i o n    G a i n I n f o r m a t i o n    V a l u e Gain\ \ Ratio = \frac{Information\ \ Gain}{Information\ \ Value} Gain  Ratio=Information  ValueInformation  Gain

      信息增益率是决定对哪一列进行分枝的标准,分枝的是数值最大的那一列,本质是信息增益最大,分支度又比较小的列(也就是纯度提升很快,但又不是靠着把类别分特别细来提升的那些特征)。分支度越大,即某一列的分类水平越多,信息增益率实现的惩罚比例越大。我们希望信息增益率越大越好,即在分枝时选择最大的信息增益率切分字段。

    决策树的生成

    ID3算法

      ID3算法的核心是在决策树的各个节点上对应信息增益准则选择特征,递归地构建决策树。具体方法是:从根节点开始,对节点计算所有可能的特征的信息增益,选择信息增益最大的特征作为节点的特征,由该特征的不同取值建立子节点;再对子节点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止,最后得到一个决策树。
      递归结束的条件是:程序遍历完所有的特征列,或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同分类,则得到一个叶节点。任何打到叶节点的数据必然属于叶节点的分类,即叶节点里面必须是标签。

    ID3算法的局限性

    1. 分支度越高(分类水平越多)的离散变量往往子节点的总信息熵会更小,ID3是按照某一列进行切分,有一些列的分类可能不会对我们需要的结果有足够好的指示。
    2. 不能直接处理连续型变量,若要使用ID3处理连续型变量,则首先需要对连续型变量进行离散化处理。
    3. 对缺失值较为敏感,使用ID3之前需要提前对缺失值进行处理。
    4. 没有剪枝的设置,容易导致过拟合,即在训练集上表现很好,测试集上表现很差。

    C4.5算法

    C4.5算法继承了ID3算法的优点,并在以下几个方面对ID3算法进行了改进:

    1. 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
    2. 在构树的过程中进行剪枝;
    3. 能够完成对连续属性的离散化;
    4. 能够对不完整数据进行处理。

    C4.5中对连续变量的处理

    在C4.5中,同样还增加了针对连续变量的处理手段。如果输入特征字段是连续型变量,则有以下步骤:

    1. 算法首先会对这一列数进行从小到大的排序;
    2. 选取相邻的两个数的中间数作为切分数据集的备选点,若一个连续变量有N个值,则在C4.5的处理过程中将会产生N-1个备选切分点,并且每个切分点都代表着一种二叉树的切分方案。

    CART

    CART(Classification And Regression Tree)是一种十分有效的非参数分类和回归方法。CART与C4.5的区别不大,它通过构建二叉树达到预测目的。

    决策树的剪枝

      剪枝作为决策树后期处理的重要步骤,是必不可少的。没有剪枝,就是一个完全生长的决策树,是过拟合的,需要去掉一些不必要的节点以使得决策树模型更具有泛化能力。

    决策树的剪枝方法

    1. 预剪枝(Pre-Pruning)
      剪枝是在构造决策树的同时进行剪枝。所有决策树的构建方法,都是在无法进一步降低熵的情况下才会停止创建分支的过程,为了避免过拟合,可以设定一个阈值,熵减小的数量小于这个阈值,即使还可以继续降低熵,也停止继续创建分支。但是这种方法实际中的效果并不好,因为在实际中,面对不同问题,很难说有一个明确的阈值可以保证树模型足够好。
    2. 后剪枝(Post-Pruning)
      后剪枝的剪枝过程是删除一些子树,然后用其叶子节点代替。这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识。
      决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查,判断如果将其合并,熵的增加量是否小于某一阈值。如果确实小,则这一组节点可以合并一个节点,其中包含了所有可能的结果。后剪枝是目前最普遍的做法。

    sklearn中的决策树

    决策树的随机性控制

    • sklearn使用集成算法构建决策树:建许多不同的树,然后从中选择最好的。在每次分枝时,不使用全部特征,而是随机选取一部分特征,从中选取不纯度相关指标最优的作为分枝用的节点。

    随机性控制参数

    1. random_state
      random_state用来设置分枝中的随机模式的参数,默认为None,在高纬度时随机性会表现更明显,低纬度的数据,随机性几乎不会显现。输入任意整数,会一直长出同一棵树,让模型稳定下来。
    2. splitter
      splitter也是用来控制决策树中的随机选项的,有两种输入值,输入"best",决策树在分枝时虽然随机,但还是会优先选择更重要的特征进行分枝(重要性可以通过属性feature_importances_查看)。输入"random",决策树在分枝时会更加随机,树会因为含有更多的不必要信息而更深更大,并因这些不必要信息而降低对训练集的拟合,防止过拟合。

    决策树中的剪枝

    • 确认最优的剪枝参数
      使用超参数的曲线进行判断。超参数的学习曲线,是一条以超参数的取值作为横坐标,模型的度量指标为纵坐标的曲线,它是用来衡量不同超参数取值下模型的表现的线。在建好的决策树中,模型的度量指标就是score

    剪枝参数

    1. max_depth
      限制树的最大深度,超过设定深度的树枝全部剪掉。
      这是用得最广泛的剪枝参数,在高维度低样本量时非常有效。决策树多生长一层,对样本量的需求会增加一倍,所以限制树深度能够有效地限制过拟合。实际使用时,建议从=3开始尝试,看看拟合的效果再决定是否增加设定深度。
    2. min_samples_leaf & min_samples_split
      min_samples_leaf限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本,否则分枝就不会发生,或者,分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生。一般搭配max_depth使用,在回归树中可以让模型变得更加平滑。min_samples_leaf参数的数量设置得太小就会引起过拟合,设置得太大就会阻止模型学习数据。一般来说,建议从=5开始使用。
      min_samples_split限定一个节点必须包含至少min_samples_split个训练样本(分枝前),这个节点才允许被分枝,否则分枝就不会发生。
    3. max_features & min_impurtiy_decrease
      max_features限制分枝时考虑的特征个数,超过限制个数的特征都会被舍弃。max_features是用来限制高纬度数据的过拟合的剪枝参数,但其方法比较暴力,是直接限制可以使用的特征数量而强行使决策树停下的参数,在不知道决策树中的各个特征的重要性的情况下,强行设定这个参数可能会导致模型学习不足。如果通过降维的方式防止过拟合,建议使用PCI、ICA或者特征选择模块中的降维算法。
      min_impurity_decrease限制信息增益的大小,信息增益小于设定数值的分枝不会发生。

    重要属性和接口

    • 属性
      feature_importances_:查看各个特征对模型的重要性
    • 接口
      apply:输入测试集后返回每个测试样本所在叶子节点的索引
      predict:输入测试集后返回每个测试样本的标签

    Python实现

    导入的库

    # 导入常用库
    import numpy as np
    import pandas as pd
    from matplotlib import pylot as plt
    # 导入sklearn中的库
    from sklearn import tree	# 导入树
    from sklearn.tree import DecisionTreeClassifier		# 分类树
    from sklearn.model_selection import train_test_split		# 切分数据集
    import graphviz		# 绘制树
    
    • graphviz库的安装不能直接用pip安装,具体安装方法自行百度,此处不多赘述

    香农熵

    def calcEnt(dataSet):
        """
        计算香农熵
        :param dataSet: 原始数据集(dataFrame)
        :return: 香农熵
        """
        tag_col = -1      # 标签所在列,根据实际dataFrame确定
        n = dataSet.shape[0]        # 数据集总行数
        iset = dataSet.iloc[:, tag_col].value_counts()       # 标签的所有类别
        p = iset / n        # 每一类标签所占比
        ent = (-p * np.log2(p)).sum()       # 计算信息熵
        return ent
    

    数据集最佳切分函数

    划分数据集的最大准则是选择最大信息增益,也就是信息下降最快的方向。

    def bestSplit(dataSet):
        """
        数据集最佳切分函数:根据信息增益选出最佳数据集切分的列
        :param dataSet: 原始数据集
        :return: 数据集最佳切分列的索引
        """
        baseEnt = calcEnt(dataSet)  # 计算原始熵
        bestGain = 0  # 初始化信息增益
        axis = -1  # 初始化最佳切分列,标签列,根据实际dataFrame确定
        for i in range(dataSet.shape[1] - 1):  # 对特征的每一列(除去标签列)进行循环
            levels = dataSet.iloc[:, i].value_counts().index  # 提取出当前列的所有值
            ents = 0  # 初始化子节点的信息熵
            for j in levels:  # 对当前列的每一个取值进行循环
                childSet = dataSet[dataSet.iloc[:, i] == j]  # 某一个子节点的dataframe
                ent = calcEnt(childSet)  # 计算某个子节点的信息熵
                ents += (childSet.shape[0] / dataSet.shape[0]) * ent  # 计算当前列的信息熵
            # print(f'第{i}列的信息熵为{ents}')
            infoGain = baseEnt - ents  # 计算当前列的信息增益
            # print(f'第{i}列的信息增益为{infoGain}')
            if infoGain > bestGain:  # 选择最大信息增益
                bestGain = infoGain
                axis = i
        return axis  # 返回最大信息增益所在列的索引
    

    按照给定列切分数据集

    def dataSetSpilt(dataSet, axis, value):
        """
        按照给定的列划分数据集
        :param dataSet: 原始数据集
        :param axis: 指定的列索引
        :param value: 指定的属性值
        :return: 按照指定列索引和属性值切分后的数据集
        """
        col = dataSet.columns[axis]     # 指定列的索引
        SpiltDataSet = dataSet.loc[dataSet[col] == value, :].drop(col, axis=1)
        return SpiltDataSet
    

    ID3算法

    def createTree_ID3(dataSet):
        """
        ID3算法构建决策树
        :param dataSet:原始数据集,注意标签列不能是数值
        :return: 字典形式的树
        """
        tag_col = -1  # 标签所在列,根据实际dataFrame确定
        featlist = list(dataSet.columns)        # 提取出数据集所有的列
        classlist = dataSet.iloc[:, tag_col].value_counts()      # 获取类标签
        if classlist[0] == dataSet.shape[0] or dataSet.shape[1] == 1:       # 判断最多标签数目是否等于数据集行数或者数据集是否只有一列
            return classlist.index[0]       # 若是则返回类标签
        axis = bestSplit(dataSet)       # 确定当前最佳切分列的索引
        bestfeat = featlist[axis]       # 获取该索引对应的特征
        myTree = {bestfeat: {}}     # 采用字典嵌套的方式存储树信息
        del featlist[axis]      # 删除当前特征
        valuelist = set(dataSet.iloc[:, axis])      # 提取最佳切分列的所有属性值
        for value in valuelist:     # 对每一个属性值递归建树
            myTree[bestfeat][value] = createTree_ID3(dataSetSpilt(dataSet, axis, value))
        return myTree
    

    决策树的存储

    构造决策树是很耗时的任务,因此为了节省时间,建树后应立即将其保存,后续使用直接调用即可。使用numpy中的save()函数,可以直接将字典形式的数据保存为*.npy文件,调用时直接使用load()函数即可。

    1. 树的存储
    def save_tree(Tree, filename="mytree.npy"):
        """
        保存决策树
        :param filename: 保存为*.npy文件
        :param Tree: 所构建的决策树
        """
        try:
            np.save(filename, Tree)
            print("Tree Saved in " + filename)
        except Exception as e:
            print(e)
            print("Failed to Save the Tree.")
    
    1. 树的读取
    def load_tree(filename="mytree.npy"):
        """
        加载决策树
        :param filename: 读取的*.npy文件
        :return: 决策树
        """
        try:
            Tree = np.load(filename, allow_pickle=True).item()
            return Tree
        except Exception as e:
            print(e)
            print("Failed to Load the Tree.")
    

    使用决策树执行分类

    1. 对一个测试实例进行分类
    def classify(inputTree, labels, testVec):
        """
        对一个测试实例进行分类
        :param inputTree: 已经生成的决策树
        :param labels: 存储选择的最优特征标签
        :param testVec: 测试数据列表,顺序对应原数据集
        :return: 分类结果
        """
        firstStr = next(iter(inputTree))        # 获取决策树第一个节点
        secondDict = inputTree[firstStr]        # 下一个字典
        featIndex = labels.index(firstStr)      # 第一个节点所在列的索引
        classLabel = secondDict[list(secondDict.keys())[0]]     # 标签初始化
        for key in secondDict.keys():
            if testVec[featIndex] == key:
                if type(secondDict[key]) == dict:
                    classLabel = classify(secondDict[key], labels, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel
    
    1. 对测试集进行预测,并返回预测后的结果
    def acc_classify(train, test, Tree):
        """
        对测试集进行预测,并返回预测后的结果
        :param train: 训练集
        :param test: 测试集
        :param Tree: 决策树
        :return: 预测好分类的测试集和准确率(tuple)
        """
        labels = list(train.columns)        # 数据集所有的名称
        row_index = test.index.to_list()
        result = pd.DataFrame(None, index=row_index, columns=["predict"])       # 初始化result,dataframe类型
        for i in range(test.shape[0]):      # 对测试集中每一行数据(每一个实例)进行循环
            testVec = test.iloc[i, :-1]     # 取出每行的数据部分;标签列是最后一列,根据实际dataframe确定
            classLabel = classify(Tree, labels, testVec)       # 预测该实例的分类
            result.iloc[i, 0] = classLabel      # 将分类结果追加到result列表中
        test = pd.concat([test, result], axis=1)        # 拼接两个dataframe
        acc = (test.iloc[:, -1] == test.iloc[:, -2]).mean()     # 计算准确率;最后一列为预测结果,倒数第二列为标签列
        return test, acc     # 返回测试集和准确率
    

    使用iris数据集测试ID3算法

    def ID3():
        data = datasets.load_iris()     # 加载数据集
        dataset = Bunch2dataframe(data)
        target_col = -1
        # 标签列不可为数值,故对标签列进行处理
        for i in range(len(dataset)):
            if dataset.iloc[i, target_col] == 0:
                dataset.iloc[i, target_col] = 'a'
            elif dataset.iloc[i, target_col] == 1:
                dataset.iloc[i, target_col] = 'b'
            elif dataset.iloc[i, target_col] == 2:
                dataset.iloc[i, target_col] = 'c'
        print(dataset)
        train, test = train_test_split(dataset, test_size=0.3)      # 切分训练集和测试集
        mytree = createTree_ID3(train)      # 构建决策树
        save_tree(mytree)
        tree_model = load_tree()
        print(tree_model)
        test_result, score = acc_classify(train, test, tree_model)      # 对测试集进行预测并给出准确率
        print(test_result)
        print(score)
    

    在sklearn中实现决策树

    • sklearn中使用的是CART
    1. 训练模型
    def best_depth_tree(train, test):
        """
        调参得到最佳的max_depth值并返回对应训练后的模型
        :param train: 训练集
        :param test: 测试集
        :return: 训练后的模型列表和测试集预测准确率最大值的索引
        """
        train_score_list = []
        test_score_list = []
        clf_list = []
        max_test_depth = 10     # 最大树深(超参数上限)
        train_data = train.iloc[:, :-1]
        train_target = train.iloc[:, -1]
        test_data = test.iloc[:, :-1]
        test_target = test.iloc[:, -1]
        for i in range(max_test_depth):
            clf = DecisionTreeClassifier(criterion="entropy",
                                         max_depth=i+1,
                                         random_state=30,
                                         splitter="random"
                                         )
            clf = clf.fit(train_data, train_target)     # 训练模型
            score_train = clf.score(train_data, train_target)       # 训练集预测准确率
            score = clf.score(test_data, test_target)       # 测试集预测准确率
            train_score_list.append(score_train)
            test_score_list.append(score)
            clf_list.append(clf)
        plt.plot(range(1, max_test_depth+1), train_score_list, color="blue", label="train")        # 绘制分数曲线
        plt.plot(range(1, max_test_depth+1), test_score_list, color="red", label="test")
        plt.legend()
        plt.show()
        return clf_list, test_score_list.index(max(test_score_list))
    
    1. 保存决策树为*.pdf文件
    def Draw_tree(clf, filename, feature_names=None, class_names=None):
        """
        绘制决策树并保存为*.pdf文件
        :param clf: 训练后的模型
        :param filename: 保存的文件名
        :param feature_names: 特征名
        :param class_names: 标签名
        :return: None
        """
        dot_data = tree.export_graphviz(clf,
                                        out_file=None,
                                        feature_names=feature_names,
                                        class_names=class_names,
                                        filled=True,
                                        rounded=True)
        graph = graphviz.Source(dot_data)
        graph.render(filename)
        print("Done.")
    
    1. 使用wine数据集进行测试
    def sklearn():
        data = datasets.load_wine()     # 加载数据集
        dataset = Bunch2dataframe(data)     # 转换成dataframe类型进行处理,最后一列为标签列
        train, test = train_test_split(dataset)     # 切分训练集和测试集
        feature_names = dataset.columns[:-1]        # 获取特征名
        clf_list, i = best_depth_tree(train, test)      # 训练模型
        print("max_depth: " + str(i+1))
        clf = clf_list[i]     # 选取测试集预测准确率最大值的模型
        Draw_tree(clf, "wine", feature_names=feature_names)     # 绘制决策树
    

    源码

    完整代码放在GitHub

    参考资料

    [1] 决策树-百度百科
    [2] 菊安酱的机器学习-哔哩哔哩
    [3] Python算法之决策树-哔哩哔哩
    [4] 决策树剪枝(cart剪枝)的原理介绍-CSDN

    展开全文
  • 决策树python实现及常见问题总结

    千次阅读 2020-06-15 19:12:11
    决策树基本知识,以及三种决策树算法ID3,C4.5,CART之间的比较。利用python实现一个简单的决策树分类模型。

    一、概述

    决策树是一种基于树结构,使用层层推理来解决分类(回归)问题的算法
    决策树由下面几种元素构成:
    在这里插入图片描述
    决策树模型的三个步骤

    1. 特征选择
    2. 决策树生成
    3. 决策树剪枝

    二、特征选择

    根据特征选择不同方法有三种经典的决策树算法:ID3、C4.5、CART
    特征选择的目标:决策树分类的目标就是让同类样本最终在同一叶节点中,不同类最终在不同叶节点中,所以在划分过程中,我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。

    1.ID3

    采用信息增益作为特征选择的方法。“信息熵”是度量样本纯度的常用的一种指标信息熵越小,纯度越高。

    在这里插入图片描述
    在这里插入图片描述
    G a i n ( D , a ) Gain(D,a) Gain(D,a)可知,信息增益越大,使用属性a来进行划分得到纯度提升越大,所以我们选择信息增益最大的属性来进行划分。
    使用信息增益来进行特征选择一个缺点是:该方法对数目较多的属性有所偏好

    2、C4.5

    C4.5算法采用信息增益率作为特征选择的方法,此方法正是为了解决信息增益准则对可取值较多的属性有所偏好的不利影响。
    在这里插入图片描述
    但遗憾的是,采用欣喜增益率准也有缺点:对可取值较少的属性有所偏好

    3、CART

    CART采用基尼指数作为特征选择的方法。
    在这里插入图片描述
    基尼指数表示在数据集中随机抽取两个样本,他们类别不一致的概率,很明显,基尼指数越小,即随机抽取的两个样本类别不一致的概率越小,类别一致的概率就越高,那么纯度就越高。采用基尼指数也减少了大量的对数运算
    在这里插入图片描述
    另外,CART可以用于回归任务。

    三、剪枝处理

    剪枝处理是决策树算法解决过拟合的主要手段,基本策略有:

    1. 预剪枝:在决策树生成过程中,对每个进行划分前先进行估计,如果不能带来决策树泛化能力的提升,则停止划分并将当前结点标记为叶节点。预剪枝也带了“欠拟合的风险
    2. 后剪枝:先生成一颗完整的决策树,然后自底而上的对非叶结点进行考察,若将该结点替换成叶结点能带泛化能力的提升,则将该子树替换成叶结点。时间开销大于预剪枝

    ID3算法没有剪枝策略,
    根据衡量泛化能力的方法有很多不同策略的剪枝,ID3算法采用悲观剪枝策略,CART采用代价复杂度剪枝策略。

    **代价复杂度剪枝(后剪枝)**主要包含以下两个步骤:

    1. 从完整决策树 T 0 T_0 T0开始,生成一个子树序列${T_0,T_1,…,T_n},其中 T ( i + 1 ) T_(i+1) T(i+1) T i T_i Ti 生成, T n T_n Tn为根结点。
      如何从从 T i T_i Ti 生成 T ( i + 1 ) T_(i+1) T(i+1)呢?
      裁剪 T i T_i Ti中误差增加率最小的分支节点得到,意思就是计算 T i T_i Ti所有结点进行剪枝前后决策树的误差增加率最小的,误差增加率最小,说明在这个结点进行剪枝处理对决策树的泛化能力影响最小。
      误差增加率定义:
      alpha =
      其中R(t)表示进行剪枝之后的该结点误差, R ( T t ) R(T_t) R(Tt))表示未进行剪枝时子树 T t T_t Tt的误差。考虑到树的复杂性因素,我们用 L ( T t ) L(T_t) L(Tt)|表示子树 T t T_t Tt的叶子结点个数.

    四、缺失值处理

    1. 如何在特征值缺失的情况下进行划分特征的选择?
    2. 选定该划分特征,模型对于缺失该特征值的样本该进行怎样处理?

    CART采取的机制是代理分裂,即如果某个存在缺失值的特征是当前最佳的分裂特征,那么我们需要遍历剩余所有特征,选择能与最佳增益的缺失特征分裂之后增益最接近的特征进行分裂,剩余特征中如果也存在缺失值,那这些特征也忽略。选定划分特征之后,当前缺失该特征的样本划分到左右子树取决于代理特征。这种处理缺失值的方法,需要遍历其他所有特征代价太大。Sklearn中决策树模型没有缺失值的处理。

    C4.5处理缺失值的方法,是通过计特征上未缺失值的样本的信息增益,然后加上个未缺失样本的权重,选择划分特征之后,对于缺失特征值的样本,让该样本以不同概率划分到不同的节点中去。

    五、优缺点及使用场景

    1、回答决策树的优缺点?

    决策树的优点:
    1、计算复杂度不高,输出结果易于理解,
    2、对中间值的缺失不敏感(CART、C4.5),比较适合处理有缺失属性的样本
    3、可以处理不相关特征数据。
    4、可以同时处理标称型和数值型数据
    缺点:
    1、容易过拟合
    2、容易忽略数据集中属性的相互关联
    3、使用信息增益和CART的决策树对可取数目较多的属性有所偏好,使用信息增益率对可取值较少的属性有所偏好。

    2、三种算法之间的差异

    除了特征选择,剪枝处理的差异之外,还可以从以下角度来考虑三者之间的差异。

    1. 从应用角度,ID3和C4.5只能用于分类任务,而CART(Classification and Regression Tree,分类回归树)从名字就可以看出其不仅可以用于分类,也可以应用于回归任务(回归树使用最小平方误差准则)
    2. 从样本类型的角度,ID3只能处理离散型变量,而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时,通过对数据排序之后找到类别不同的分割线作为切分点,根据切分点把连续属性转换为布尔型,从而将连续型变量转换多个取值区间的离散型变量。而对于CART,由于其构建时每次都会对特征进行 二值划分,因此可以很好地适用于连续性变量。
    3. 从实现细节、优化过程等角度,这三种决策树还有一些不同。比如,ID3对样本特征缺失值比较敏感,而C4.5和CART可以对缺失值进行不同方式的处理;ID3和C4.5可以在每个结点上产生出多叉分支,且每个特征在层级之间不会复用,而CART每个结点只会产生两个分支,因此最后会形成一颗二叉树,且每个特征可以被重复使用;ID3和C4.5通过剪枝来权衡树的准确性与泛化能力,而CART直接利用全部数据发现所有可能的树结构进行对比。

    六、CART决策树构建回归树的区别

    CART回归树和CART分类树的建立算法大部分都是类似的,所以我们这里只讨论CART回归树和CART分类树之间的建立算法的不同。

    回归树和分类树的最主要区别在于样本输出,如果样本输出是离散值,那么这是一颗分类树,如果样本输出是连续值,那么这是一颗回归树。

    除了概念上的不同之外,CART回归树和CART分类树的建立和预测的其区别主要有下面两点:

    • 连续值的处理不同:确定特征以及特征值的划分点不同。
    • 决策树建立之后做预测的方式不同

    对于连续值的处理,CART分类时是基于基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类树,对于回归模型,我们知道最常用的度量方式是均方误差,这里回归树采用的是和方差的度量方式,对于任意划分特征A,对应的任意划分点s两边划分成的数据集D1和D2,求出使D1和D2各自集合的均方差最小,同时D1和D2的均方差之和最小对应的特征和特征值划分点。表达式为:

    在这里插入图片描述
    对于决策树建立后做预测的方式,上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别,它采用的是用最终叶子的均值或者中位数来预测输出结果。

    除了上面提到了以外,CART回归树和CART分类树的建立算法和预测没有什么区别。

    七、决策树算法小结

    优点:

    1. 简单直观,相比较于神经网络之类的黑盒模型,决策树逻辑上可以得到很好的解释。
    2. 基本不需要数据预处理,不需要提前归一化,处理缺失值。
    3. 使用决策树预测代价是O(log2m)。m为样本数
    4. 既可以处理离散值也可以处理连续。
    5. 可以处理多维度输出的分类问题。叶子结点做多分类。
    6. 对异常点的容错能力好,健壮性高

    缺点:

    1. 决策树非常容易过拟合,导致泛化能力不强,可以通过剪枝,设置节点最小样本数量和限制树的深度来改进,
    2. 决策树回因为样本一点点变动,就会导致树结构的剧烈改变,这个可以通过集成学习的方法来改进。
    3. 模型的表达能力有限。
    4. 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

    八、python简单实现

    """
    伪代码:
    creteBranch函数
    检测数据集中的每个子项是否属于同一分类:
        if so return 类标签;
        else
            寻找划分数据集的最好特征
            划分数据集
            创建分支节点
                for 每个划分子集
                    调用函数createBranch并增加返回结果到分支节点中
            return 分支节点
    """
    from math import *
    import operator
    class Tree:
    
        def clacShannonEnt(self, dataset):
            """
            计算香浓熵的函数
            :param dataset:数据集
            :return: 香浓熵的值
            """
            numEntries = len(dataset)
            labelCounts = {}
            for featVec in dataset:
                currentLabel = featVec[-1]
                labelCounts[currentLabel] = labelCounts.get(currentLabel, 0)+1
    
            shannonEnt = 0.0
            for key in labelCounts:
                prob = float(labelCounts[key])/numEntries
                shannonEnt -= prob*log(prob, 2)
            return shannonEnt
    
        def splitDataSet(self,dataset, axis, value):
            """
            按照给定特征划分数据集
            :param dataset: 待划分数据集
            :param axis: 待划分数据集特征索引
            :param value: 需要返回的特征的值
            :return:
            """
            retDataSet = []
            for featVec in dataset:
                if featVec[axis] == value:
                    reduceFeatVec = featVec[:axis]
                    reduceFeatVec.extend(featVec[axis+1:])
                    retDataSet.append(reduceFeatVec)
            return retDataSet
    
        def chooseBestFeatureToSplit(self,dataset):
            """
            选择最好的数据集划分方式
            :param dataset: 数据集
            :return: 最好的划分特征
            """
            numFeatures = len(dataset[0]) - 1
            bestEntropy = self.clacShannonEnt(dataset)
            bestInfoGain = 0.0
            bestFeature = -1
            for i in range(numFeatures):
                featList = [example[i] for example in dataset]
                uniqueVals = set(featList)
                newEntropy = 0.0
                for value in uniqueVals:
                    subDataSet = self.splitDataSet(dataset, i, value)
                    prob = len(subDataSet)/float(len(dataset))
                    newEntropy += prob*self.clacShannonEnt(subDataSet)
                infoGain = bestEntropy-newEntropy
                if (infoGain>bestInfoGain):
                    bestInfoGain = infoGain
                    bestFeature = i
            return bestFeature
    
        def majorityCnt(self, classList):
            """
            多数投票法
            :param classList:分类名称的列表
            :return: 返回出现次数最多的类
            """
            classCount = {}
            for vote in classList:
                classCount[vote] = classCount.get(vote, 0) + 1
            sortedClassCount = sorted(classCount.iteritems(),
                                      key=operator.itemgetter(1), reverse=True)
            return sortedClassCount[0][0]
    
        def createTree(self, dataset, labels):
            """
            创建树的函数代码
            :param dataset: 数据集
            :param labels: 标签列表
            :return: 决策树
            """
            classList = [example[-1] for example in dataset]
            #print(classList)
            #递归终止条件
            if classList.count(classList[0]) == len(classList):
                return classList[0]
            if len(dataset[0])==1:
                return self.majorityCnt(classList)
            bestFeat = self.chooseBestFeatureToSplit(dataset)
            bestFeatLabel = labels[bestFeat]
            myTree = {bestFeatLabel:{}}
            del(labels[bestFeat])
            featValue = [example[bestFeat] for example in dataset]
            uniqueVals = set(featValue)
            for value in uniqueVals:
                subLabels = labels[:]
                myTree[bestFeatLabel][value] = self.createTree(self.splitDataSet(dataset, bestFeat, value)
                                                               , subLabels)
            return myTree
    
        def classify(self, inputTree, featLabels, testVec):
            global classLabel
            firstStr = list(inputTree.keys())[0]
            # print(featLabels)
            # print(firstStr)
            secondDict = inputTree[firstStr]
            featIndex = featLabels.index(firstStr)
            #print(featIndex)
            for key in secondDict.keys():
                print(key)
                if testVec[featIndex] == key:
                    if type(secondDict[key]).__name__=='dict':
                        classLabel = self.classify(secondDict[key],featLabels,testVec)
                    else:
                        classLabel = secondDict[key]
            return classLabel
    if __name__ == "__main__":
        dataset = [[1,1,'yes'],
                   [1,1,"yes"],
                   [1,0,'no'],
                   [0,1,'no'],
                   [0,1,'no']]
        labels = ["no surfacing", "fileters"]
        #print(labels.index("no surfacing"))
        tree = Tree()
        myTree = tree.createTree(dataset, labels)
        print(myTree)
        a = tree.classify(myTree,["no surfacing", "fileters"], [1,0])
        print("leibie",a)
    
    展开全文
  • 主要为大家详细介绍了python实现C4.5决策树算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 基于Python决策树的代码实现,包含了信息增益的计算,数据集的划分以及使用递归算法进行决策树的构建,还有将决策树的绘制代码
  • 一、CART决策树算法简介 CART(Classification And Regression Trees 分类回归树)算法是一种树构建算法,既可以用于分类任务,又可以用于回归。相比于 ID3 和 C4.5 只能用于离散型数据且只能用于分类任务,CART ...
  • 使用Python实现决策树

    2017-06-24 19:30:13
    2017年3月16号关于决策树的资源上传错了,这一份才是决策树Python代码实现,包含详细的中文注释,欢迎下载学习。Python版本为2.7.
  • ''' 数据集:Mnist 训练集数量:60000 测试集数量:10000 ------------------------------ 运行结果:ID3(未剪枝) 正确率:85.9% 运行时长:356s ''' import time import numpy as np def loadData(fileName): ...
  • python实现机器学习之决策树分类算法,简单易学,而且可直接运行。
  • 决策树Python 实现——决策树回归

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

    千次阅读 2021-10-25 20:37:23
    最近布置了个课堂作业,用python实现决策树算法。整了几天勉勉强强画出了棵歪脖子树,记录一下。 大体思路: 1.创建决策树My_Decision_Tree类,类函数__init__()初始化参数、fit()进行决策树模型训练、predict()...
  • 只用到了numpy库,自己编写的函数,计算交叉熵、信息增益、递归创建决策树、解码分类 # 第1步: 针对每个特征,计算信息增益 # 第2步: 选取最大增益的特征,分裂决策树,递归调用 # 第3步: 解码决策树,进行分类
  • 本篇文章主要介绍了Python实现决策树C4.5算法的示例,详解的介绍了决策树C4.5算法的原理和实现代码,非常具有实用价值,需要的朋友可以参考下
  • 本文实例讲述了决策树python实现方法。分享给大家供大家参考。具体实现方法如下: 决策树算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺点:可能会产生...
  • C4.5主要是在ID3的基础上改进,ID3选择(属性)节点是选择信息增益值最大的属性作为节点。而C4.5引入了新概念“信息增益率”,C4.5是选择信息增益率最大的属性作为节点。 二、信息增益 以上公式是求信息增益率...
  • 本文实例为大家分享了基于信息增益的决策树归纳的Python实现代码,供大家参考,具体内容如下 # -*- coding: utf-8 -*- import numpy as np import matplotlib.mlab as mlab import matplotlib.pyplot as plt from ...
  • 机器学习实战第三章决策树代码,说实话感觉这一章不太实用
  • ID3决策树算法及其Python实现

    千次阅读 2021-10-29 09:39:25
    目录一、决策树算法基础理论决策树的学习过程ID3算法二、实现针对西瓜数据集的ID3算法实现代码参考文章 一、决策树算法 决策树是一种基于树结构来进行决策的分类算法,我们希望从给定的训练数据集学得一个模型(即...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,057
精华内容 12,822
关键字:

决策树python实现