浏览本文须要的背景知识点：一丢丢编程常识

一、引言

  在生活中，每次到饭点时都会在心里默念——“等下吃啥？”，可能明天工作的一天了不想走远了，这时咱们会决定餐厅的间隔不能超过两百米，再看看本人钱包里的二十块钱，决定吃的货色不能超过二十，最初点了份兰州拉面。从下面的例子中能够看到，咱们明天吃兰州拉面都是由后面一系列的决策所决定的。

<center> 图 1 -1</center>

  如图 1 - 1 所示，将下面的决策过程用一颗二叉树来示意，这个树就被称为决策树（Decision Tree）。在机器学习中，同样能够通过数据集训练出如图 1 - 1 所示的决策树模型，这种算法被称为决策树学习算法（Decision Tree Learning）¹。

二、模型介绍

模型

  决策树学习算法（Decision Tree Learning），首先必定是一个树状构造，由外部结点与叶子结点组成，外部结点示意一个维度（特色），叶子结点示意一个分类。结点与结点之间通过肯定的条件相连接，所以决策树又能够看成一堆 if…else… 规定的汇合。

<center> 图 2 -1</center>

  如图 2 - 1 所示，其展现了一颗根本的决策树数据结构与其蕴含的决策办法。

特征选择

  既然要做决策，须要决定的就是从哪个维度（特色）来做决策，例如后面例子中的店铺间隔、钱包零钱数等。在机器学习中咱们须要一个量化的指标来确定应用的特色更加适合，即应用该特色划分后，失去的子集合的“纯度”更高。这时引入三种指标——信息增益（Information Gain）、基尼指数（Gini Index）、均方差（MSE）来解决后面说的问题。

信息增益（Information Gain）

  式 2 - 1 是一种示意样本集纯度的指标，被称为信息熵（Information Entropy），其中 D 示意样本集，K 示意样本集分类数，p_k 示意第 k 类样本在样本集所占比例。Ent(D) 的值越小，样本集的纯度越高。

$$
\operatorname{Ent}(D)=-\sum_{k=1}^{K} p_{k} \log _{2} p_{k}
$$

<center> 式 2 -1</center>

  式 2 - 2 示意用一个离散属性划分后对样本集的影响，被称为信息增益（Information Gain），其中 D 示意样本集，a 示意离散属性，V 示意离散属性 a 所有可能取值的数量，D^v 示意样本集中第 v 种取值的子样本集。

$$
\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)
$$

<center> 式 2 -2</center>

  当属性是间断属性时，其可取值不像离散属性那样是无限的，这时能够将间断属性在样本集中的值排序后俩俩取平均值作为划分点，改写一下式 2 -2，失去如式 2 - 3 的后果，其中 T_a 示意平均值汇合，D_t^v 示意子集合，当 v = – 时示意样本中小于均值 t 的样本子集，当 v = + 时示意样本中大于均值 t 的样本子集，取划分点中最大的信息增益作为该属性的信息增益值。

$$
\begin{aligned}
T_{a} &=\left\{\frac{a^{i}+a^{i+1}}{2} \mid 1 \leq i \leq n-1\right\} \\
\operatorname{Gain}(D, a) &=\max _{t \in T_{a}} \operatorname{Gain}(D, a, t) \\
&=\max _{t \in T_{a}} \operatorname{Ent}(D)-\sum_{v \in\{-,+\}} \frac{\left|D_{t}^{v}\right|}{|D|} \operatorname{Ent}\left(D_{t}^{v}\right)
\end{aligned}
$$

<center> 式 2 -3</center>

  Gain(D, a) 的值越大，样本集按该属性划分后纯度的晋升越高。由此可找到最合适的划分属性，如式 2 - 4 所示：

$$
a_{\text {best}}=\underset{a}{\operatorname{argmax}} \operatorname{Gain}(D, a)
$$

<center> 式 2 -4</center>

基尼指数（Gini Index）

  式 2 - 5 是另一种示意样本集纯度的指标，被称为基尼值（Gini），其中 D 示意样本集，K 示意样本集分类数，p_k 示意第 k 类样本在样本集所占比例。Gini(D) 的值越小，样本集的纯度越高。

$$
\operatorname{Gini}(D)=1-\sum_{k=1}^{K} p_{k}^{2}
$$

<center> 式 2 -5</center>

  式 2 - 6 示意用一个离散属性划分后对样本集的影响，被称为基尼指数（Gini Index），其中 D 示意样本集，a 示意离散属性，V 示意离散属性 a 所有可能取值的数量，D^v 示意样本集中第 v 种取值的子样本集。

$$
\operatorname{Gini_{-}index}(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)
$$

<center> 式 2 -6</center>

  同式 2 - 3 一样，将间断属性排序后俩俩取平均值作为划分点，改写式 2 -6，失去如式 2 - 7 的后果，其中 T_a 示意平均值汇合，D_t^v 示意子集合，当 v = – 时示意样本中小于均值 t 的样本子集，当 v = + 时示意样本中大于均值 t 的样本子集，取划分点中最小的基尼指数作为该属性的基尼指数值。

$$
\operatorname{Gini_{-}index}(D, a)=\min _{t \in T_{a}} \sum_{v \in\{-,+\}} \frac{\left|D_{t}^{v}\right|}{|D|} \operatorname{Gini}\left(D_{t}^{v}\right)
$$

<center> 式 2 -7</center>

  Gini_index(D, a) 的值越小，样本集按该离散属性划分后纯度的晋升越高。由此可找到最合适的划分属性，如式 2 - 8 所示：

$$
a_{\text {best}}=\underset{a}{\operatorname{argmin}} \operatorname{Gini\_index}(D, a)
$$

<center> 式 2 -8</center>

均方差（MSE）

  后面两种指标使得决策树能够用来做分类问题，那么决策树如果用来做回归问题时，就须要不同的指标来决定划分的特色，这个指标就是如式 2 - 9 所示的均方差（MSE），其中 T_a 示意平均值汇合，y_t^v 示意子集合标签，当 v = – 时示意样本中小于均值 t 的样本子集标签，当 v = + 时示意样本中大于均值 t 的样本子集标签，后一项为对应子集合标签的均值。

$$
\operatorname{MSE}(D, a)=\min _{t \in T_{a}} \sum_{v \in\{-,+\}}\left(y_{t}^{v}-\hat{y_{t}^{v}}\right)^{2}
$$

<center> 式 2 -9</center>

  MSE(D, a) 的值越小，决策树对样本集的拟合水平越高。由此可找到最合适的划分属性，如式 2 -10 所示：

$$
a_{\text {best}}=\underset{a}{\operatorname{argmin}} \operatorname{MSE}(D, a)
$$

<center> 式 2 -10</center>

  晓得了决策树模型的数据结构，又晓得如何划分最佳的数据集，那么接下来就来学习如何生成一颗决策树。

三、算法步骤

  既然决策树的数据结构是一颗树，其子结点也必然是一颗树，能够通过递归的形式来生成决策树，步骤如下：

生成新结点 node；

当样本中只存在一种分类 C 时：

  将结点 node 标记为分类 C 的叶子结点，返回结点 node；

遍历所有特色：

  计算以后特色的信息增益或基尼指数或均方差；

结点 node 中记录最佳的划分特色；

依照最佳特色划分后右边局部递归调用以后办法，当作结点 node 的左子结点；

依照最佳特色划分后左边局部递归调用以后办法，当作结点 node 的右子结点；

返回结点 node；

四、正则化

  当递归的生成决策树时，模型对训练数据的分类会十分精确，然而对未知的预测数据的体现并不现实，这就是所谓的过拟合的景象，这时能够同后面线性回归学习到的应答过拟合的解决办法一样，对模型进行正则化。

决策树的深度

  能够通过限度决策树的最大深度来达到对其正则化的成果，避免决策树过拟合。这时只需在算法步骤中加上一个用于记录以后递归下树深度的参数，当达到预设的最大深度时，不再生成新的子结点，将以后结点标记为样本中分类占比最大的分类并退出以后递归。

决策树的叶子结点大小

  另一个对决策树进行正则化的办法是限度叶子结点起码蕴含的样本数量，同样能够避免过拟合的景象。当结节蕴含的样本数，将以后结点标记为样本中分类占比最大的分类并退出以后递归

决策树的剪枝

  还能够通过对决策树进行剪枝来避免其过拟合，将多余的子树剪断。剪枝的办法又分成两种，别离为预剪枝（prepruning）、后剪枝（post-pruning）。

预剪枝

  顾名思义，预剪枝就是在生成决策树的时候就决定是否生成子结点，判断的办法为应用验证数据集比拟生成子结点与不生成子结点的精度，当生成子结点的精度有晋升，则生成子结点，反之则不生成子结点。

<center> 图 4 -1 图片来源于周志华《机器学习》</center>

后剪枝

  后剪枝则是学生成一个残缺的决策树，而后再从叶子结点开始，同预剪枝一样的判断办法，当生成子结点的精度有晋升，则保留子结点，反之则将子结点剪断。

<center> 图 4 -2 图片来源于周志华《机器学习》</center>

五、代码实现

应用 Python 实现基于信息增益的决策树分类：

import numpy as np

class GainNode:
    """
    分类决策树中的结点
    基于信息增益 -Information Gain
    """
    
    def __init__(self, feature=None, threshold=None, gain=None, left=None, right=None):
        # 结点划分的特色下标
        self.feature = feature
        # 结点划分的临界值，当结点为叶子结点时为分类值
        self.threshold = threshold
        # 结点的信息增益值
        self.gain = gain
        # 左结点
        self.left = left
        # 右结点
        self.right = right

class GainTree:
    """
    分类决策树
    基于信息增益 -Information Gain
    """
    
    def __init__(self, max_depth = None, min_samples_leaf = None):
        # 决策树最大深度
        self.max_depth = max_depth
        # 决策树叶结点最小样本数
        self.min_samples_leaf = min_samples_leaf
        
    def fit(self, X, y):
        """
        分类决策树拟合
        基于信息增益 -Information Gain
        """
        y = np.array(y)
        self.root = self.buildNode(X, y, 0)
        return self
    
    def buildNode(self, X, y, depth):
        """
        构建分类决策树结点
        基于信息增益 -Information Gain
        """
        node = GainNode()
        # 当没有样本时间接返回
        if len(y) == 0:
            return node
        y_classes = np.unique(y)
        # 当样本中只存在一种分类时间接返回该分类
        if len(y_classes) == 1:
            node.threshold = y_classes[0]
            return node
        # 当决策树深度达到最大深度限度时返回样本中分类占比最大的分类
        if self.max_depth is not None and depth >= self.max_depth:
            node.threshold = max(y_classes, key=y.tolist().count)
            return node
        # 当决策树叶结点样本数达到最小样本数限度时返回样本中分类占比最大的分类
        if self.min_samples_leaf is not None and len(y) <= self.min_samples_leaf:
            node.threshold = max(y_classes, key=y.tolist().count)
            return node
        max_gain = -np.inf
        max_middle = None
        max_feature = None
        # 遍历所有特色，获取信息增益最大的特色
        for i in range(X.shape[1]):
            # 计算特色的信息增益
            gain, middle = self.calcGain(X[:,i], y, y_classes)
            if max_gain < gain:
                max_gain = gain
                max_middle = middle
                max_feature = i
        # 信息增益最大的特色
        node.feature = max_feature
        # 临界值
        node.threshold = max_middle
        # 信息增益
        node.gain = max_gain
        X_lt = X[:,max_feature] < max_middle
        X_gt = X[:,max_feature] > max_middle
        # 递归解决左汇合
        node.left = self.buildNode(X[X_lt,:], y[X_lt], depth + 1)
        # 递归解决右汇合
        node.right = self.buildNode(X[X_gt,:], y[X_gt], depth + 1)
        return node
    
    def calcMiddle(self, x):
        """计算连续型特色的俩俩平均值"""
        middle = []
        if len(x) == 0:
            return np.array(middle)
        start = x[0]
        for i in range(len(x) - 1):
            if x[i] == x[i + 1]:
                continue
            middle.append((start + x[i + 1]) / 2)
            start = x[i + 1]
        return np.array(middle)

    def calcEnt(self, y, y_classes):
        """计算信息熵"""
        ent = 0
        for j in range(len(y_classes)):
            p = len(y[y == y_classes[j]])/ len(y)
            if p != 0:
                ent = ent + p * np.log2(p)
        return -ent

    def calcGain(self, x, y, y_classes):
        """计算信息增益"""
        x_sort = np.sort(x)
        middle = self.calcMiddle(x_sort)
        max_middle = -np.inf
        max_gain = -np.inf
        ent = self.calcEnt(y, y_classes)
        # 遍历每个平均值
        for i in range(len(middle)):
            y_gt = y[x > middle[i]]
            y_lt = y[x < middle[i]]
            ent_gt = self.calcEnt(y_gt, y_classes)
            ent_lt = self.calcEnt(y_lt, y_classes)
            # 计算信息增益
            gain = ent - (ent_gt * len(y_gt) / len(x) + ent_lt * len(y_lt) / len(x))
            if max_gain < gain:
                max_gain = gain
                max_middle = middle[i]
        return max_gain, max_middle
    
    def predict(self, X):
        """分类决策树预测"""
        y = np.zeros(X.shape[0])
        self.checkNode(X, y, self.root)
        return y
    
    def checkNode(self, X, y, node, cond = None):
        """通过分类决策树结点判断分类"""
        # 当没有子结点时，间接返回以后临界值
        if node.left is None and node.right is None:
            return node.threshold
        X_lt = X[:,node.feature] < node.threshold
        if cond is not None:
            X_lt = X_lt & cond
        # 递归判断左结点
        lt = self.checkNode(X, y, node.left, X_lt)
        if lt is not None:
            y[X_lt] = lt
        X_gt = X[:,node.feature] > node.threshold
        if cond is not None:
            X_gt = X_gt & cond
        # 递归判断右结点
        gt = self.checkNode(X, y, node.right, X_gt)
        if gt is not None:
            y[X_gt] = gt

应用 Python 实现基于基尼指数的决策树分类：

import numpy as np

class GiniNode:
    """
    分类决策树中的结点
    基于基尼指数 -Gini Index
    """
    
    def __init__(self, feature=None, threshold=None, gini_index=None, left=None, right=None):
        # 结点划分的特色下标
        self.feature = feature
        # 结点划分的临界值，当结点为叶子结点时为分类值
        self.threshold = threshold
        # 结点的基尼指数值
        self.gini_index = gini_index
        # 左结点
        self.left = left
        # 右结点
        self.right = right

class GiniTree:
    """
    分类决策树
    基于基尼指数 -Gini Index
    """
    
    def __init__(self, max_depth = None, min_samples_leaf = None):
        # 决策树最大深度
        self.max_depth = max_depth
        # 决策树叶结点最小样本数
        self.min_samples_leaf = min_samples_leaf
        
    def fit(self, X, y):
        """
        分类决策树拟合
        基于基尼指数 -Gini Index
        """
        y = np.array(y)
        self.root = self.buildNode(X, y, 0)
        return self

    def buildNode(self, X, y, depth):
        """
        构建分类决策树结点
        基于基尼指数 -Gini Index
        """
        node = GiniNode()
        # 当没有样本时间接返回
        if len(y) == 0:
            return node
        y_classes = np.unique(y)
        # 当样本中只存在一种分类时间接返回该分类
        if len(y_classes) == 1:
            node.threshold = y_classes[0]
            return node
        # 当决策树深度达到最大深度限度时返回样本中分类占比最大的分类
        if self.max_depth is not None and depth >= self.max_depth:
            node.threshold = max(y_classes, key=y.tolist().count)
            return node
        # 当决策树叶结点样本数达到最小样本数限度时返回样本中分类占比最大的分类
        if self.min_samples_leaf is not None and len(y) <= self.min_samples_leaf:
            node.threshold = max(y_classes, key=y.tolist().count)
            return node
        min_gini_index = np.inf
        min_middle = None
        min_feature = None
        # 遍历所有特色，获取基尼指数最小的特色
        for i in range(X.shape[1]):
            # 计算特色的基尼指数
            gini_index, middle = self.calcGiniIndex(X[:,i], y, y_classes)
            if min_gini_index > gini_index:
                min_gini_index = gini_index
                min_middle = middle
                min_feature = i
        # 基尼指数最小的特色
        node.feature = min_feature
        # 临界值
        node.threshold = min_middle
        # 基尼指数
        node.gini_index = min_gini_index
        X_lt = X[:,min_feature] < min_middle
        X_gt = X[:,min_feature] > min_middle
        # 递归解决左汇合
        node.left = self.buildNode(X[X_lt,:], y[X_lt], depth + 1)
        # 递归解决右汇合
        node.right = self.buildNode(X[X_gt,:], y[X_gt], depth + 1)
        return node
    
    def calcMiddle(self, x):
        """计算连续型特色的俩俩平均值"""
        middle = []
        if len(x) == 0:
            return np.array(middle)
        start = x[0]
        for i in range(len(x) - 1):
            if x[i] == x[i + 1]:
                continue
            middle.append((start + x[i + 1]) / 2)
            start = x[i + 1]
        return np.array(middle)

    def calcGiniIndex(self, x, y, y_classes):
        """计算基尼指数"""
        x_sort = np.sort(x)
        middle = self.calcMiddle(x_sort)
        min_middle = np.inf
        min_gini_index = np.inf
        for i in range(len(middle)):
            y_gt = y[x > middle[i]]
            y_lt = y[x < middle[i]]
            gini_gt = self.calcGini(y_gt, y_classes)
            gini_lt = self.calcGini(y_lt, y_classes)
            gini_index = gini_gt * len(y_gt) / len(x) + gini_lt * len(y_lt) / len(x)
            if min_gini_index > gini_index:
                min_gini_index = gini_index
                min_middle = middle[i]
        return min_gini_index, min_middle

    def calcGini(self, y, y_classes):
        """计算基尼值"""
        gini = 1
        for j in range(len(y_classes)):
            p = len(y[y == y_classes[j]])/ len(y)
            gini = gini - p * p
        return gini
    
    def predict(self, X):
        """分类决策树预测"""
        y = np.zeros(X.shape[0])
        self.checkNode(X, y, self.root)
        return y
    
    def checkNode(self, X, y, node, cond = None):
        """通过分类决策树结点判断分类"""
        if node.left is None and node.right is None:
            return node.threshold
        X_lt = X[:,node.feature] < node.threshold
        if cond is not None:
            X_lt = X_lt & cond
        lt = self.checkNode(X, y, node.left, X_lt)
        if lt is not None:
            y[X_lt] = lt
        X_gt = X[:,node.feature] > node.threshold
        if cond is not None:
            X_gt = X_gt & cond
        gt = self.checkNode(X, y, node.right, X_gt)
        if gt is not None:
            y[X_gt] = gt

应用 Python 实现基于均方差的决策树回归：

import numpy as np

class RegressorNode:
    """回归决策树中的结点"""
    
    def __init__(self, feature=None, threshold=None, mse=None, left=None, right=None):
        # 结点划分的特色下标
        self.feature = feature
        # 结点划分的临界值，当结点为叶子结点时为分类值
        self.threshold = threshold
        # 结点的均方差值
        self.mse = mse
        # 左结点
        self.left = left
        # 右结点
        self.right = right

class RegressorTree:
    """回归决策树"""
    
    def __init__(self, max_depth = None, min_samples_leaf = None):
        # 决策树最大深度
        self.max_depth = max_depth
        # 决策树叶结点最小样本数
        self.min_samples_leaf = min_samples_leaf
        
    def fit(self, X, y):
        """回归决策树拟合"""
        self.root = self.buildNode(X, y, 0)
        return self

    def buildNode(self, X, y, depth):
        """构建回归决策树结点"""
        node = RegressorNode()
        # 当没有样本时间接返回
        if len(y) == 0:
            return node
        y_classes = np.unique(y)
        # 当样本中只存在一种分类时间接返回该分类
        if len(y_classes) == 1:
            node.threshold = y_classes[0]
            return node
        # 当决策树深度达到最大深度限度时返回样本中分类占比最大的分类
        if self.max_depth is not None and depth >= self.max_depth:
            node.threshold = np.average(y)
            return node
        # 当决策树叶结点样本数达到最小样本数限度时返回样本中分类占比最大的分类
        if self.min_samples_leaf is not None and len(y) <= self.min_samples_leaf:
            node.threshold = np.average(y)
            return node
        min_mse = np.inf
        min_middle = None
        min_feature = None
        # 遍历所有特色，获取均方差最小的特色
        for i in range(X.shape[1]):
            # 计算特色的均方差
            mse, middle = self.calcMse(X[:,i], y)
            if min_mse > mse:
                min_mse = mse
                min_middle = middle
                min_feature = i
        # 均方差最小的特色
        node.feature = min_feature
        # 临界值
        node.threshold = min_middle
        # 均方差
        node.mse = min_mse
        X_lt = X[:,min_feature] < min_middle
        X_gt = X[:,min_feature] > min_middle
        # 递归解决左汇合
        node.left = self.buildNode(X[X_lt,:], y[X_lt], depth + 1)
        # 递归解决右汇合
        node.right = self.buildNode(X[X_gt,:], y[X_gt], depth + 1)
        return node
    
    def calcMiddle(self, x):
        """计算连续型特色的俩俩平均值"""
        middle = []
        if len(x) == 0:
            return np.array(middle)
        start = x[0]
        for i in range(len(x) - 1):
            if x[i] == x[i + 1]:
                continue
            middle.append((start + x[i + 1]) / 2)
            start = x[i + 1]
        return np.array(middle)

    def calcMse(self, x, y):
        """计算均方差"""
        x_sort = np.sort(x)
        middle = self.calcMiddle(x_sort)
        min_middle = np.inf
        min_mse = np.inf
        for i in range(len(middle)):
            y_gt = y[x > middle[i]]
            y_lt = y[x < middle[i]]
            avg_gt = np.average(y_gt)
            avg_lt = np.average(y_lt)
            mse = np.sum((y_lt - avg_lt) ** 2) + np.sum((y_gt - avg_gt) ** 2)
            if min_mse > mse:
                min_mse = mse
                min_middle = middle[i]
        return min_mse, min_middle
    
    def predict(self, X):
        """回归决策树预测"""
        y = np.zeros(X.shape[0])
        self.checkNode(X, y, self.root)
        return y
    
    def checkNode(self, X, y, node, cond = None):
        """通过回归决策树结点判断分类"""
        if node.left is None and node.right is None:
            return node.threshold
        X_lt = X[:,node.feature] < node.threshold
        if cond is not None:
            X_lt = X_lt & cond
        lt = self.checkNode(X, y, node.left, X_lt)
        if lt is not None:
            y[X_lt] = lt
        X_gt = X[:,node.feature] > node.threshold
        if cond is not None:
            X_gt = X_gt & cond
        gt = self.checkNode(X, y, node.right, X_gt)
        if gt is not None:
            y[X_gt] = gt

六、第三方库实现

scikit-learn² 决策树分类实现

from sklearn import tree

# 决策树分类
clf = tree.DecisionTreeClassifier()
# 拟合数据
clf = clf.fit(X, y)

scikit-learn³ 决策树回归实现

from sklearn import tree

# 决策树回归
clf = tree.DecisionTreeRegressor()
# 拟合数据
clf = clf.fit(X, y)

七、动画演示

  图 7 - 1 展现了一颗未进行正则化的决策树的分类后果，图 7 - 2 展现了一颗正则化后的决策树（max_depth = 3, min_samples_leaf = 5）的分类后果

<center> 图 7 -1</center>

<center> 图 7 -2</center>

  图 7 - 3 展现了一颗未进行正则化的决策树的回归后果，图 7 - 4 展现了一颗正则化后的决策树（max_depth = 3, min_samples_leaf = 5）的回归后果

<center> 图 7 -3</center>

<center> 图 7 -4</center>

  能够看到未进行正则化的决策树对训练数据集显著过拟合，进行正则化后的决策树的状况绝对好一些。

八、思维导图

<center> 图 8 -1</center>

九、参考文献

1. https://en.wikipedia.org/wiki…
2. https://scikit-learn.org/stab…
3. https://scikit-learn.org/stab…

残缺演示请点击这里

注：本文力求精确并通俗易懂，但因为笔者也是初学者，程度无限，如文中存在谬误或脱漏之处，恳请读者通过留言的形式批评指正

本文首发于——AI 导图 ，欢送关注