概述

决策树

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

决策树的剪枝

  剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。
  预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点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