---

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表示不包含。如下如所示：

• 测试函数

  #测试操作
  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（鸢尾花集）

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

导入以及训练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)

生成结果如下：

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

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

结果如下：

---

测试集2（红酒品类数据集）

13个属性如下图所示：

导入以及训练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)

生成结果如下：

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

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

结果如下：

---

总结

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

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

概述

决策树

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

决策树的剪枝

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

优缺点

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

决策树的构建

特征选择/计算公式

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

不纯度

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

香农熵(Entropy)

假定当前样本集合$D$中一共有$n$类样本，第$i$类样本为$x_i$，$p(x_i)$是选择该分类的概率，则$x_i$的信息定义为：
$$l(x_i)=-lo{g}_{2}p(x_i)$$

通过上式，可以得到所有类别的信息，为了计算熵，需要计算所有类别所有可能值包含的信息期望(数学期望)，香农熵的计算公式如下：
$$Entropy(D)=-\sum _{i=1}^{n}p(x_i)lo{g}_{2}p(x_i)$$

信息增益(Information Gain)

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

基尼(Gini)指数

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

分支度(Information Value)

  在C4.5中，引入分支度的概念对信息增益的计算方法进行修正，简而言之，就是在信息增益计算方法的子节点总信息熵的计算方法中添加了随着分类变量水平的惩罚项。而分支度的计算公式仍然是基于熵的算法，只是将信息熵计算公式中的$p(x_i)$(即某类别样本占总样例数)改成了$p(v_i)$，即某子节点的总样本数占父节点总样本数的比例。这个分支度指标让我们在切分的时候，自动避免那些分类水平太多，信息熵减小过快的特征影响模型，减少过拟合情况。IV计算公式如下：
$$InformationValue=-\sum _{i=1}^{k}p(v_i)lo{g}_{2}p(v_i)$$

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

信息增益率(Gain Ratio)

  在C4.5中，使用信息增益除以分支度作为选取切分字段的参考指标，该指标被称作Gain Ratio(获利比例，或信息增益率)，其计算公式如下：
$$GainRatio=\frac{InformationGain}{InformationValue}$$

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

决策树的生成

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.")

2. 树的读取

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

2. 对测试集进行预测，并返回预测后的结果

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))

2. 保存决策树为*.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.")

3. 使用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

一、概述

决策树是一种基于树结构，使用层层推理来解决分类（回归）问题的算法
决策树由下面几种元素构成：

决策树模型的三个步骤

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

二、特征选择

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

1.ID3

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

有$Gain(D,a)$可知，信息增益越大，使用属性a来进行划分得到纯度提升越大，所以我们选择信息增益最大的属性来进行划分。
使用信息增益来进行特征选择一个缺点是：该方法对数目较多的属性有所偏好。

2、C4.5

C4.5算法采用信息增益率作为特征选择的方法，此方法正是为了解决信息增益准则对可取值较多的属性有所偏好的不利影响。

但遗憾的是，采用欣喜增益率准也有缺点：对可取值较少的属性有所偏好。

3、CART

CART采用基尼指数作为特征选择的方法。

基尼指数表示在数据集中随机抽取两个样本，他们类别不一致的概率，很明显，基尼指数越小，即随机抽取的两个样本类别不一致的概率越小，类别一致的概率就越高，那么纯度就越高。采用基尼指数也减少了大量的对数运算。

另外，CART可以用于回归任务。

三、剪枝处理

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

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

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

**代价复杂度剪枝（后剪枝）**主要包含以下两个步骤：

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

四、缺失值处理

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. 对异常点的容错能力好，健壮性高

缺点：

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

八、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)