第5章 决策树

第5章 决策树

习题5.1

  根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。

解答：

表5.1 贷款申请样本数据表

解答思路：

1. 列出C4.5的生成算法；
2. 使用sklearn的DecisionTreeClassifier类构建决策树，并使用graphviz包展示，默认是Gini，这里可以作为自编程的验证
3. 通过自编程实现C4.5算法生成决策树，并进行特征选择

解题步骤：

第1步：列出C4.5的生成算法

根据书中第5.3.2节C4.5的生成算法：

算法5.3 C4.5的生成算法
输入：训练数据集D，特征集A阈值\epsilon；
输出：决策树T。
（1）如果D中所有实例属于同一类C_k，则置T为单结点树，并将C_k作为该结点的类，返回T；
（2）如果A = \emptyset，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T；
（3）否则，按式\displaystyle g_R(D,A)=\frac{g(D,A)}{H_A(D)}计算A中各特征对D的信息增益比，选择信息增益比最大的特征A_g；
（4）如果A_g的信息增益比小于阈值\epsilon，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T；
（5）否则，对A_g的每一可能值a_i，依A_g=a_i将D分割为子集若干非空D_i，将D_i中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
（6）对结点i，以D_i为训练集，以A-\{A_g\}为特征集，递归地调用步(1)~步(5)，得到子树T_i，返回T_i

第2步：调用sklearn的DecisionTreeClassifier类构建决策树

from sklearn.tree import DecisionTreeClassifier
from sklearn import preprocessing
import numpy as np
import pandas as pd

from sklearn import tree
import graphviz

features = ["年龄", "有工作", "有自己的房子", "信贷情况"]
X_train = pd.DataFrame([
    ["青年", "否", "否", "一般"],
    ["青年", "否", "否", "好"],
    ["青年", "是", "否", "好"],
    ["青年", "是", "是", "一般"],
    ["青年", "否", "否", "一般"],
    ["中年", "否", "否", "一般"],
    ["中年", "否", "否", "好"],
    ["中年", "是", "是", "好"],
    ["中年", "否", "是", "非常好"],
    ["中年", "否", "是", "非常好"],
    ["老年", "否", "是", "非常好"],
    ["老年", "否", "是", "好"],
    ["老年", "是", "否", "好"],
    ["老年", "是", "否", "非常好"],
    ["老年", "否", "否", "一般"]
])
y_train = pd.DataFrame(["否", "否", "是", "是", "否",
                        "否", "否", "是", "是", "是",
                        "是", "是", "是", "是", "否"])
class_names = [str(k) for k in np.unique(y_train)]
# 数据预处理
le_x = preprocessing.LabelEncoder()
le_x.fit(np.unique(X_train))
X_train = X_train.apply(le_x.transform)
# 调用sklearn的DecisionTreeClassifier建立决策树模型
model_tree = DecisionTreeClassifier()
# 训练模型
model_tree.fit(X_train, y_train)

# 导出决策树的可视化文件，文件格式是dot
dot_data = tree.export_graphviz(model_tree, out_file=None,
                                feature_names=features,
                                class_names=class_names,
                                filled=True, rounded=True,
                                special_characters=True)
# 使用graphviz包，对决策树进行展示
graph = graphviz.Source(dot_data)
# 可使用view方法展示决策树
# 中文乱码：需要对源码_export.py文件（文件路径：sklearn/tree/_export.py）修改，
# 在文件第451行中将helvetica改成SimSun
graph
​

# 打印决策树
tree_text = tree.export_text(model_tree, feature_names=features)
print(tree_text)
​

|--- 有自己的房子 <= 3.00
|   |--- 有工作 <= 3.00
|   |   |--- class: 否
|   |--- 有工作 >  3.00
|   |   |--- class: 是
|--- 有自己的房子 >  3.00
|   |--- class: 是
​

第3步：自编程实现C4.5算法生成决策树

import json
from collections import Counter

import numpy as np


# 节点类
class Node:
    def __init__(self, node_type, class_name, feature_name=None,
                 info_gain_ratio_value=0.0):
        # 结点类型（internal或leaf）
        self.node_type = node_type
        # 特征名
        self.feature_name = feature_name
        # 类别名
        self.class_name = class_name
        # 子结点树
        self.child_nodes = []
        # Gini指数值
        self.info_gain_ratio_value = info_gain_ratio_value

    def __repr__(self):
        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)

    def add_sub_tree(self, key, sub_tree):
        self.child_nodes.append({"condition": key, "sub_tree": sub_tree})
​

class MyDecisionTree:
    def __init__(self, epsilon):
        self.epsilon = epsilon
        self.tree = None

    def fit(self, train_set, y, feature_names):
        features_indices = list(range(len(feature_names)))
        self.tree = self._fit(train_set, y, features_indices, feature_names)
        return self

    # C4.5算法
    def _fit(self, train_data, y, features_indices, feature_labels):
        LEAF = 'leaf'
        INTERNAL = 'internal'
        class_num = len(np.unique(y))

        # （1）如果训练数据集所有实例都属于同一类Ck
        label_set = set(y)
        if len(label_set) == 1:
            # 将Ck作为该结点的类
            return Node(node_type=LEAF, class_name=label_set.pop())

        # （2）如果特征集为空
        # 计算每一个类出现的个数
        class_len = Counter(y).most_common()
        (max_class, max_len) = class_len[0]

        if len(features_indices) == 0:
            # 将实例数最大的类Ck作为该结点的类
            return Node(LEAF, class_name=max_class)

        # （3）按式(5.10)计算信息增益，并选择信息增益最大的特征
        max_feature = 0
        max_gda = 0
        D = y.copy()
        # 计算特征集A中各特征
        for feature in features_indices:
            # 选择训练集中的第feature列（即第feature个特征）
            A = np.array(train_data[:, feature].flat)
            # 计算信息增益
            gda = self._calc_ent_grap(A, D)
            if self._calc_ent(D) != 0:
                # 计算信息增益比
                gda /= self._calc_ent(D)
            # 选择信息增益最大的特征Ag
            if gda > max_gda:
                max_gda, max_feature = gda, feature

        # （4）如果Ag信息增益小于阈值
        if max_gda < self.epsilon:
            # 将训练集中实例数最大的类Ck作为该结点的类
            return Node(LEAF, class_name=max_class)

        max_feature_label = feature_labels[max_feature]

        # （6）移除已选特征Ag
        sub_feature_indecs = np.setdiff1d(features_indices, max_feature)
        sub_feature_labels = np.setdiff1d(feature_labels, max_feature_label)

        # （5）构建非空子集
        # 构建结点
        feature_name = feature_labels[max_feature]
        tree = Node(INTERNAL, class_name=None, feature_name=feature_name,
                    info_gain_ratio_value=max_gda)

        max_feature_col = np.array(train_data[:, max_feature].flat)
        # 将类按照对应的实例数递减顺序排列
        feature_value_list = [x[0] for x in Counter(max_feature_col).most_common()]
        # 遍历Ag的每一个可能值ai
        for feature_value in feature_value_list:
            index = []
            for i in range(len(y)):
                if train_data[i][max_feature] == feature_value:
                    index.append(i)

            # 递归调用步（1）~步（5），得到子树
            sub_train_set = train_data[index]
            sub_train_label = y[index]
            sub_tree = self._fit(sub_train_set, sub_train_label, sub_feature_indecs, sub_feature_labels)
            # 在结点中，添加其子结点构成的树
            tree.add_sub_tree(feature_value, sub_tree)

        return tree

    # 计算数据集x的经验熵H(x)
    def _calc_ent(self, x):
        x_value_list = set([x[i] for i in range(x.shape[0])])
        ent = 0.0
        for x_value in x_value_list:
            p = float(x[x == x_value].shape[0]) / x.shape[0]
            logp = np.log2(p)
            ent -= p * logp

        return ent

    # 计算条件熵H(y/x)
    def _calc_condition_ent(self, x, y):
        x_value_list = set([x[i] for i in range(x.shape[0])])
        ent = 0.0
        for x_value in x_value_list:
            sub_y = y[x == x_value]
            temp_ent = self._calc_ent(sub_y)
            ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent

        return ent

    # 计算信息增益
    def _calc_ent_grap(self, x, y):
        base_ent = self._calc_ent(y)
        condition_ent = self._calc_condition_ent(x, y)
        ent_grap = base_ent - condition_ent

        return ent_grap

    def __repr__(self):
        return str(self.tree)
​

# 表5.1的训练数据集
feature_names = np.array(["年龄", "有工作", "有自己的房子", "信贷情况"])
X_train = np.array([
    ["青年", "否", "否", "一般"],
    ["青年", "否", "否", "好"],
    ["青年", "是", "否", "好"],
    ["青年", "是", "是", "一般"],
    ["青年", "否", "否", "一般"],
    ["中年", "否", "否", "一般"],
    ["中年", "否", "否", "好"],
    ["中年", "是", "是", "好"],
    ["中年", "否", "是", "非常好"],
    ["中年", "否", "是", "非常好"],
    ["老年", "否", "是", "非常好"],
    ["老年", "否", "是", "好"],
    ["老年", "是", "否", "好"],
    ["老年", "是", "否", "非常好"],
    ["老年", "否", "否", "一般"]
])
y = np.array(["否", "否", "是", "是", "否",
              "否", "否", "是", "是", "是",
              "是", "是", "是", "是", "否"])

dt_tree = MyDecisionTree(epsilon=0.1)
dt_tree.fit(X_train, y, feature_names)
dt_tree
​

{
   "node_type": "internal",
   "feature_name": "有自己的房子",
   "class_name": null,
   "child_nodes": [
      {
         "condition": "否",
         "sub_tree": {
            "node_type": "internal",
            "feature_name": "年龄",
            "class_name": null,
            "child_nodes": [
               {
                  "condition": "否",
                  "sub_tree": {
                     "node_type": "leaf",
                     "feature_name": null,
                     "class_name": "否",
                     "child_nodes": [],
                     "info_gain_ratio_value": 0.0
                  }
               },
               {
                  "condition": "是",
                  "sub_tree": {
                     "node_type": "leaf",
                     "feature_name": null,
                     "class_name": "是",
                     "child_nodes": [],
                     "info_gain_ratio_value": 0.0
                  }
               }
            ],
            "info_gain_ratio_value": 1.0
         }
      },
      {
         "condition": "是",
         "sub_tree": {
            "node_type": "leaf",
            "feature_name": null,
            "class_name": "是",
            "child_nodes": [],
            "info_gain_ratio_value": 0.0
         }
      }
   ],
   "info_gain_ratio_value": 0.4325380677663126
}
​

习题5.2

  已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。
表5.2 训练数据表

解答：

解答思路：

1. 根据书中第5.5.1节平方误差最小的准则，列出最小二乘回归树生成算法（算法5.5）；
2. 编写代码，实现算法，并用表5.2训练数据进行验证。

解题步骤：

第1步：算法5.5的最小二乘回归树生成算法

根据书中第5.5.1节的算法5.5：

  决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

算法5.5（最小二乘回归树生成算法）
输入：训练数据集D
输出：回归树f(x)
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树；
（1）选择最优切分变量j与切分点s，求解

\min_{j,s} \left[ \min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2\right]

R_1(j,s)={x|x^{(j)}\leqslant s}, R_2(j,s)={x|x^{(j)} > s} \
\hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i, x \in R_m, m=1,2

f(x)=\sum_{m=1}^M \hat{c}_m I(x \in R_m)

习题5.3

  证明 CART 剪枝算法中，当\alpha确定时，存在唯一的最小子树T_{\alpha}使损失函数C_{\alpha}(T)最小。

解答：

解答思路：

1. 列出CART剪枝算法；
2. 列出树的剪枝算法；
3. 采用反证法，假设存在两棵子树使得损失函数最小。

解答步骤：

第1步：算法5.7的CART剪枝算法

根据书中的算法5.7：

算法5.7（CART剪枝算法）
输入：CART算法生成的决策树T_0；
输出：最优决策树T_\alpha。
（1）设k=0,T=T_0。
（2）设\alpha=+\infty。
（3）自下而上地对各内部结点t计算C(T_t),|T_t|，以及

g(t)=\cfrac{C(t)-C(T_t)}{|T_t|-1} \
\alpha = \min(\alpha,g(t))

C_\alpha(T_A) \leqslant C_\alpha(T_B)

C_{\alpha}(T_2)=C_{\alpha}(T_3)

C_{\alpha}(t_2)<C_{\alpha}(T_2)

C_{\alpha}(t_3)<C_{\alpha}(T_3)

C_{\alpha}(t_2)<C_{\alpha}(T_3) \
C_{\alpha}(t_3)<C_{\alpha}(T_2)

T(\alpha) = \left{ \begin{array}{l}
{t_1 }, \quad R_{\alpha}(t_1) \leqslant R_{\alpha}(T_L(\alpha))+R_{\alpha}(T_R(\alpha)) \
{t_1} \cup T_L(\alpha) \cup T_R(\alpha), \quad \text{otherwise}
\end{array}\right.