决策树分类回归，ID3，c4.5，CART，及其Python代码

决策树模型

内部节点表示一个特征或者属性，叶子结点表示一个类。决策树工作时，从根节点开始，对实例的每个特征进行测试，根据测试结果，将实例分配到其子节点中，这时的每一个子节点对应着特征的一个取值，如此递归的对实例进行测试并分配，直到达到叶节点，最后将实例分配到叶节点所对应的类中。
决策树具有一个重要的性质：互斥并且完备。每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖，这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

决策树与条件概率分布

决策树将特种空间划分为互不相交的单元或区域，在每个单元上定义了一个类的概率分布，则构成了条件概率分布。分类时，将该节点的实例强行分到条件概率大的那一类中。
决策树学习就是由训练数据集估计条件概率模型的过程。一个数据集可能对应不想矛盾的多个决策树，通常选择使损失函数最小的决策树。通常现实中决策树学习算法采用启发式方法，近似求解这一优化问题，这样得到的决策树是次优的。
学习算法通常是递归的选择最优特征。首先开始构建根节点，然后将所有训练数据放到根节点中，选择一个最优特征，按照这一特征对数据集分割成子集，使得各个子集有一个在当前条件下最好的分类，如果这个子集已经能够被基本正确分类，则构建叶节点，如果还有子集不能正确分类，则对这些子集选择新的最优特征，继续对其分割构建新的节点。
但是这样的方法可能能够对训练数据具有好的分类能力，但是不具有好的泛化能力，容易出现过拟合，因此我们需要对树进行减枝，让树变得简单，复杂度降低，使其具有很好的泛化能力，方法为去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，将父节点或更高节点改为新的叶节点。如果特征数量很多，也可以在开始时对特征进行选择，只留下对训练数据具有足够分类能力的特征。
决策树的生成对应于模型的局部选择，决策树的减枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的减枝则考虑全局最优。

信息增益

信息增益是用来选择最优划分特征的指标。首先给出熵的概念。
在信息论与概率统计中，熵是表示随机变量不确定性的度量。X为取值有限的离散随机变量。概率分布为

P (X = x_{i}) = p_{i} i = 1, 2, . . ., n

则X的熵为

H (X) = - \sum_{i = 1}^{n} p_{i} \log p_{i}

若

p_{i} = 0

则

0 \log 0 = 0

。对数以2为底定义单位为比特(bit)，以e为底定义单位为纳特(nat)，熵只依赖于X的分布，不依赖于X的取值。熵越大，信息的不确定性越大。
条件熵

H (Y | X) = \sum_{i = 1}^{n} p_{i} H (Y | X = x_{i})

如果概率由数据估计得到，所对应的熵称为经验熵。
信息增益：得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A)，定义为

g (D, A) = H (D) - H (D | A)

一般熵H(Y)与条件熵H(Y|X)之差称为互信息。信息增益大的特征具有更强的分类能力。
特征选择的方法为：队训练数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。

信息增益比

信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，用信息增益比可以很好的解决。
信息增益比：特征A对训练数据集D的信息增益比 $g_{R} (D, A)$ 定义为其信息增益与训练数据集D关于特征A的值的熵 $H_{A} (D)$ 之比

g_{R} (D, A) = \frac{g (D, A)}{H_{A} (D)}

其中，

H_{A} (D) = - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} \log_{2} \frac{| D_{i} |}{| D |}

，n为特征A取值的个数。

ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归的构建决策树。
输入：数据集D，特征集A，阈值 $σ$
输出：决策树T
(1).若D中的所有实例均属于同一类 $C_{k}$ ，则T为单节点树，并将类 $C_{k}$ 作为该节点的类标记，返回T。
(2).若 $A = \emptyset$ ，则T为单节点树，选择对多的特征作为该节点的类标记，返回T。
(3).计算A中各个特征对D的信息增益，选择信息增益最大的特征 $A_{g}$ 。
(4).若 $A_{g}$ 的信息增益小于阈值 $σ$ ，则T为单节点树，选择对多的特征作为该节点的类标记，返回T。
(5).否则，对 $A_{g}$ 按其每一个可能取值将数据集D划分为非空子集 $D_{i}$ ，将 $D_{i}$ 中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T。
(6).对第i个子节点，以 $D_{i}$ 为训练集，以 $A - A_{g}$ 为特征集，递归的调用(1)~(5)，得到树 $T_{i}$ ，返回 $T_{i}$ 。

# 实验数据
ID,年龄,有工作,有自己的房子,信贷情况,类别
1,青年,否,否,一般,否
2,青年,否,否,好,否
3,青年,是,否,好,是
4,青年,是,是,一般,是
5,青年,否,否,一般,否
6,中年,否,否,一般,否
7,中年,否,否,好,否
8,中年,是,是,好,是
9,中年,否,是,非常好,是
10,中年,否,是,非常好,是
11,老年,否,是,非常好,是
12,老年,否,是,好,是
13,老年,是,否,好,是
14,老年,是,否,非常好,是
15,老年,否,否,一般,否

ID3, C4.5代码实现

# classification with Decision Tree by ID3 and C4.5 algorithm

import  numpy as np
import pandas as pd
from sklearn.model_selection import  train_test_split

class DecisionTree():
    def __init__(self, feature_names, eps=0.03, depth=10, min_leaf_size=1, method="gain"):
        '''
        eps:精度
        depth:深度
        min_leaf_size:最小叶子大小
        method:方法gain或者ratio
        '''
        self.feature_names = feature_names
        self.eps = eps
        self.depth = depth
        self.min_leaf_size=min_leaf_size
        self.method = method


    def gain_entropy(self, x):
        """
        计算信息增益
        x: 数据集的某个特征
        :return ent: H(D)=-sum_{k=1}^Kfrac{|C_k|}{|D|}log_2frac{|C_k|}{|D|}
        """
        entropy = 0
        for x_value in set(x):
            p = x[x == x_value].shape[0] / x.shape[0]
            entropy -= p * np.log2(p)
        return entropy

    def gain_condition_entropy(self, x, y):
        entropy = 0
        for x_value in set(x):
            sub_y = y[x == x_value]
            tmp_ent = self.gain_entropy(sub_y)
            p = sub_y.shape[0] / y.shape[0]
            entropy += p * tmp_ent
        return entropy


    def Gain(self, x, y):
        if self.method == "gain":
            return self.gain_entropy(x) - self.gain_condition_entropy(x, y)
        else:
            return 1 - self.gain_condition_entropy(x, y) / self.gain_entropy(x)

    def fit(self, X, y):
       self.tree = self._built_tree(X, y)

    def _built_tree(self, X, y, depth=1):
        if len(set(y)) == 1:
            return y[0]



        label_1, label_2 = set(y)
        max_label = label_1 if np.sum(y == label_1) > np.sum(y == label_2) else label_2
        # print("max_label", max_label)

        if len(X[0]) == 0:
            return max_label
        if depth > self.depth:
            return max_label

        if len(y) < self.min_leaf_size:
            return max_label


        best_feature_index = 0
        max_gain = 0
        for feature_index in range(len(X[0])):
            gain = self.Gain(X[:, feature_index], y)
            if max_gain < gain:
                max_gain = gain
                best_feature_index = feature_index

        # print(max_gain)

        if max_gain < self.eps:
            return max_label

        T = {}
        sub_T = {}
        for best_feature in set(X[:, best_feature_index]):
            '''
            best_feature：某个特征下的特征类别
            '''
            sub_y = y[X[:, best_feature_index] == best_feature]
            sub_X = X[X[:, best_feature_index] == best_feature]
            sub_X = np.delete(sub_X, best_feature_index, 1) # 删除最佳特征列

            sub_T[best_feature+"__"+str(len(sub_X))] = self._built_tree(sub_X, sub_y, depth+1) # 关键代码

        T[self.feature_names[best_feature_index]+"__"+str(len(X))] = sub_T # 关键代码

        return T

    def predict(self, x, tree=None):
        if x.ndim == 2:
            res = []
            for x_ in x:

                res.append(self.predict(x_))
            return res

        if not tree:
            tree = self.tree

        tree_key = list(tree.keys())[0]

        x_feature = tree_key.split("__")[0]

        x_index = self.feature_names.index(x_feature) # 从列表中定位索引
        x_tree = tree[tree_key]
        for key in x_tree.keys():
            if key.split("__")[0] == x[x_index]:
                tree_key = key
                x_tree = x_tree[tree_key]

        if type(x_tree) == dict:
            return self.predict(x, x_tree)
        else:
            return x_tree


if __name__ == "__main__":
    df = pd.read_csv("/mnt/hgfs/Ubuntu/统计学习方法笔记/CH05/Input/mdata_5-1.txt", index_col=0)

    cols = df.columns.tolist()  # 特征名称列表
    X = df[cols[:-1]].values
    y = df[cols[-1]].values
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)
    clf = DecisionTree(feature_names=cols, eps=0.03, depth=5, min_leaf_size=1, method='gain')
    clf.fit(X_train, y_train)

    print(clf.tree)



    print(cols)
    # print(X_test)
    print("Result:")
    print("predict:")
    print(clf.predict(X_test))
    print("test:")
    print(y_test)

```

C4.5

C4.5就是讲ID3中的信息增益换为信息增益比。

决策树的减枝

由于决策树生成后有过拟合现象，缺乏泛化能力，因此需要进行减枝达到全局最优。
减枝通过极小化决策树整体的损失函数或代价函数来实现。 $| T |$ 表示树 $T$ 的叶节点个数。t为一个叶节点，该叶节点上有 $N_{t}$ 个样本，其中k类样本点有 $N_{t k}$ 个。 $H_{t} (T)$ 为叶节点t上的经验熵。则损失函数可以定义为

C_{α} = \sum_{t = 1}^{| T |} N_{t} H_{t} (T) + α | T | = C (T) + α | T |

D_{t} (T) = - \sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}}

C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，

α

用来控制占比。

减枝算法

输入：树T， $α$
输出：修建好的树 $T_{α}$
(1)计算每个节点的经验熵
(2)递归的从树的叶节点向上回缩
设一组叶节点回缩前后对应的损失函数为 $C_{α} (T_{B})$ 与 $C_{α} (T_{A})$ 。如果 $C_{α} (T_{A}) \leq C_{α} (T_{B})$ 则进行减枝，将父节点变为新的叶节点。
(3)返回(2)。直至不能继续为止。

CART算法

CART假定决策树是二叉树，内部节点特征的取值为“是”或“否”。也包含决策树的生成与减枝两个过程。回归树用平方误差最小化准则，分类树用基尼指数最小化准则。

CART回归树的生成

回归树将输入空间(特征空间)划分为多个单元，每个单元有一个固定的输出值 $c_{m}$ ，当输入空间的划分确定时，可以用平方误差 $\sum_{x_{i} \in R_{m}}$ 来表示回归树的预测误差。单元输出最优值 ${\hat{c}}_{m}$ 是单元上所有实例输出值的平均值。则问题可以变为使用启发式的方法确定切分变量以及切分点，使误差最小。可以固定一个输入变量，然后启发式的寻找最优切分点，通过这样的方法遍历所有输入变量，确定最优的切分变量与切分点。

最小二乘回归树生成算法

输入：训练数据集D
输出：回归树
在训练数据集上递归的将每个区域划分为两个子区域并决定每个子区域的输出值，构建二叉决策树：
（1）选择最优切变量与切分点。遍历变量，对固定的切分变量扫描切分点，选择最优结果。
（2）通过选择的最优结果划分数据区域并确定相应的输出值。
（3）连续对两个子区域调用（1）（2），直至满足停止条件。
（4）得到决策树

CART分类树的生成

首先介绍基尼指数：分类问题中，假设有K个类，样本属于第k类的概率为 $p_{k}$ ，则概率分布的基尼指数为

G i n i (p) = \sum_{k = 1}^{K} p_{k} (1 - p_{k}) = 1 - \sum_{k = 1}^{K} p_{k}^{2}

对于给定样本集其基尼指数为

G i n i (D) = 1 - \sum_{k = 1}^{K} (\frac{| C_{k} |}{| D |})^{2}

在特征A的条件下，集合D的基尼指数为

G i n i (D, A) = \frac{| D_{1} |}{| D |} G i n i (D_{1}) + \frac{| D_{2} |}{| D |} G i n i (D_{2})

基尼指数可以表示数据的不确定性，指数越大表示集合的不确定性越大。

基尼指数分类树生成算法

输入：训练数据集，停止条件
输出：分类树
从根节点开始，递归的对每个节点进行一下操作，构建二叉决策树。
（1）计算所有特征的所有可能取值的基尼指数
（2）选择最优特征与最优取值，将数据集切分为两个子数据集
（3）递归调用（1）（2）直到满足停止条件
（4）生成CART分类树
停止条件为：节点中的样本个数小于预定阈值，或样本集的基尼指数小于阈值，或没有更多的特征。

CART减枝

CART减枝步骤：首先从生成算法产生的决策树 $T_{0}$ 底端开始不断减枝，直到 $T_{0}$ 的根节点，形成子树序列 $T_{0}, T_{1}, . . ., T_{n}$ ；然后通过交叉验证算法在独立的验证数据集上对子树进行测试，从中选择最优子树。
减枝过程中损失函数为 $C_{α} (T) = C (T) + α | T |$ ， $C (T)$ 可以是基尼指数或是误差平方和。当 $α$ 固定时，最优子树唯一。可以通过将 $α$ 从小增大，确定一系列 $T_{0}, T_{1}, . . ., T_{n}$ ，然后从中通过交叉验证选择最优子树。具体可以参看Breiman算法。
在对 $T_{0}$ 中每一内部节点t，计算

g (t) = \frac{C (t) - C (T_{t})}{| T_{t} | - 1}

C (t)

为以t为单节点树的损失函数，

C (T_{t})

为以t为根节点的子树

T_{t}

的损失函数。

g (t)

表示减枝后损失函数减少的程度。在

T_{0}

中减去

g (t)

最小的

T_{t}

，将得到的子树作为

T_{1}

，同时将最小的

g (t)

设为

α_{1}

。

T_{1}

为区间

[α_{1}, α_{2})

的最优子树。不断增加

α

，产生新的区间。
然后利用独立的验证数据，交叉验证子树序列

T_{0}, T_{1}, . . ., T_{n}

，平方误差或基尼指数最小的决策树被认为是最优的。

CART减枝算法

输入：原完整的生成树
输出：减枝后的生成树
（1）设 $k = 0, T = T_{0}$
（2）设 $α \to inf$
（3）自上而下的对各内部节点t计算

g (t) = \frac{C (t) - C (T_{t})}{| T_{t} | - 1}

α = min (α, g (t))

（4）对

g (t) = α

的内部节点t进行减枝，并对节点t以多数表决法确定类,得T。
（5）k=k+1，

α_{k} = α

，

T_{k} = T

（6）如果

T_{k}

不是右根节点及其两个叶子组成的树，则回到（3），否则令

T_{k} = T_{n}

（7）交叉验证子树序列，得到最优子树

CRAT

'''
Implement the decision_tree to adjust more than 1 dimension
'''

import  numpy as np
import  matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

class DecisionTreeRegression():
    def __init__(self, depth = 5, min_leaf_size = 5):
        self.depth = depth
        self.min_leaf_size = min_leaf_size
        self.left = None
        self.right = None
        self.prediction = None

        self.j = None
        self.s = None


    def mean_squared_error(self, labels, prediction):

        if labels.ndim != 1:
            print("Error: Input labels must be one dimensional")

        return np.mean((labels - prediction) ** 2)

    def train(self, X, y):
        if X.ndim == 1:
            X = X.reshape(-1, 1)

        if y.ndim != 1:
            print("Error: Data set labels must be one dimensional")
            return

        #控制最小叶子
        if len(X) < 2 * self.min_leaf_size:
            self.prediction = np.mean(y)
            return

        #深度为一
        if self.depth == 1:
            self.prediction = np.mean(y)
            return

        j, s, best_split, _ = self.split(X, y)

        if s != None:
            left_X = X[:best_split]
            left_y = y[:best_split]
            right_X = X[best_split:]
            right_y = y[best_split:]

            self.s = s
            self.j = j
            self.left = DecisionTreeRegression(depth = self.depth - 1, min_leaf_size = self.min_leaf_size)
            self.right = DecisionTreeRegression(depth = self.depth - 1, min_leaf_size = self.min_leaf_size)

            #左右递归
            self.left.train(left_X, left_y)
            self.right.train(right_X, right_y)

        else:
            self.prediction = np.mean(y)

        # 出口
        return

    def squaErr(self, X, y, j, s):
        mask_left = X[:, j] < s
        mask_right = X[:, j] >= s
        X_left = X[mask_left, j]
        X_right = X[mask_right, j]

        c_left = np.mean(y[mask_left])
        c_right = np.mean((y[mask_right]))

        error_left = np.sum((X_left - c_left) ** 2)
        error_right = np.sum((X_right - c_right) ** 2)
        return error_left + error_right


    def split(self, X, y):
        min_j = 0
        min_error = np.inf

        for j in range(len(X[0])):
            X_sorted = np.sort(X[:, min_j])  # 不改变X
            slice_value = (X_sorted[1:] + X_sorted[:-1]) / 2
            min_s = X[0, min_j] + X[-1, min_j]
            min_s_index = slice_value[0]
            for s_index in range(len(slice_value)):
                error = self.squaErr(X, y, j, slice_value[s_index])
                if error < min_error:
                    min_error = error
                    min_j = j
                    min_s = slice_value[s_index]
                    min_s_index = s_index

            return  min_j, min_s, s_index, min_error

    def predict(self, x):
        # to avoid a number
        if x.ndim == 0:
            x = np.array([x])

        if self.prediction is not None:

            return self.prediction

        elif self.left or self.right is not None:

            if x[self.j] >= self.s:
                return self.right.predict(x)
            else:
                return self.left.predict(x)
        else:
            print("Error: Decision tree not yet trained")
            return None

def main():

    X = np.array([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 10]])
    y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])



    tree = DecisionTreeRegression(depth = 5, min_leaf_size = 2)
    tree.train(X,y)


    test_cases = np.array([np.arange(0.0, 10.0, 0.01), np.arange(0.0, 10.0, 0.01)]).T
    predictions = np.array([tree.predict(x) for x in test_cases])

    #绘图
    fig = plt.figure(figsize=(10, 8))
    ax = fig.add_subplot(111, projection="3d")
    ax.scatter(X[:, 0], X[:, 1], y, s=20, edgecolor="black",
               c="darkorange", label="data")
    ax.plot(test_cases[:, 0], test_cases[:, 1], predictions, c='r')

    # plt.scatter(X[:, 0], y, s=20, edgecolor="black", c="darkorange", label="data")
    # plt.plot(test_cases[:, 1], predictions, c="r")

    plt.show()



if __name__ == '__main__':
    main()

对比

ID3与C4.5区别：
ID3采用信息增益进行特征选择，C4.5采用信息增益比进行特征选择。信息增益存在偏向于选择取值较多的特征。
ID3，C4.5为多叉树，CART为二叉树。
CART在一条通路上可以对一个特征进行多次划分，ID3或C4.5在一个通路上只能对一个特征进行一次划分。
ID3，C4.5无法直接处理离散问题，CART可以直接处理离散问题。
信息增益、基尼指数、方差都能表示数据的不确定性。
信息增益通常用在有限离散特征有限离散类型的情况，即特征离散的分类情况，信息增益需要各个特征概率的极大似然估计以及类型概率的极大似然估计。
基尼指数用于有限离散类型的情况，即特征连续或离散的分类情况。基尼指数只需要知道类型概率的极大似然估计。
方差不根据分布概率确定不确定性，方差根据特征的取值情况度量信息的离散程度。需要知道具体的值。可以用于连续型数据。用于KDTree选择切分特征，在主成分分析(PCA)对数据进行降维降噪。
减枝区别
CART减枝的方法为交叉验证，需要测试数据集，不需要事先确定好 $α$ 值的大小， $T_{0}, T_{1}, . . ., T_{n}$ 由训练数据集生成。
ID3，C4.5需要事先确定 $α$ 值的大小，但是不需要测试数据。
两种减枝方法可以互用。