本文共 18657 字，大约阅读时间需要 62 分钟。

决策树的学习过程：利用训练数据，根据损失函数最小化的原则建立决策树模型。学习通常包括特征选择、决策树的生成、决策树的修剪三个步骤。

决策树的预测过程：对新的数据，利用决策树模型进行分类。

决策树的类别划分：

• 用于解决分类和回归问题的监督学习模型
• 概率模型：模型取条件概率分布形式 $P(y|x)$
• 非参数化模型：假设模型参数的维度不固定
• 判别模型：由数据直接学习决策函数 $f(X)$

决策树的主要优点：模型具有可读性，分类速度快。

决策树的主要缺点：

【扩展阅读】

5.1 决策树模型与学习

【名词解释】划分 （以下定义来自浙江大学《概率论与数理统计》第四版 P. 17）

设 S 为试验 E 的样本空间，$B_1,B_2,\cdots ,B_n$ 为 E 的一组事件。若

1. $B_i{B}_j=\varnothing$，$i\ne j$，$i,j=1,2,\cdots ,n$；
2. $B_1\cup B_2\cup \cdots \cup B_n=S$，

则称 $B_1,B_2,\cdots ,B_n$ 为样本空间 S 的一个划分。

【补充说明】图 5.2 (b) 中左下角区域的条件概率分布似乎应为 0。

NP 完全问题

【推荐阅读】

【什么是 P 问题、NP 问题和 NPC 问题 - Matrix67】摘要

多项式时间 我们可以将时间复杂度分为两类；第一类我们称为多项式级的复杂度，其规模 n 出现在底数的位置，例如 $O(1)$、$O(logN)$、$O(N^a)$ 等；第二类我们称为非多项式级的复杂度，例如 $O(a^n)$、$O(N!)$ 等。我们将第一类时间复杂度称为多项式时间。

P 问题 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题。

NP 问题 NP 问题有两种定义。第一种定义：如果一个问题可以在多项式的时间内验证一个解的问题，那么这个问题就属于 NP 问题。第二种定义：如果一个问题可以在多项式的时间内踩出一个解，那么这个问题就属于 NP 问题。

约化 一个问题 A 可以约化为问题 B 的含义是，可以用问题 B 的解法解决问题 A。一般来说，B 的时间复杂度高于或等于 A 的时间复杂度。另外，约化具有传递性，如果问题 A 可约化为问题 B，问题 B 可约化为问题 C，则问题 A 一定可约化为问题 C。

NPC 问题(NP 完全问题) NPC 问题定义为同时满足如下两个条件的问题。首先，它必须是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。在现阶段，我们可以直观地理解，NPC 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

NP-Hard 问题 NP-Hard 问题不一定是一个 NP 问题，但是所有的 NP 问题都可以约化到它。

5.2 特征选择

【补充说明】训练数据集 D 关于特征 A 的值的熵 $H_A(D)$ 即特征 A 的熵。

例 5.1 数据集

【】code.example.load_li_5_1

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/example/_li.pyimport numpy as npdef load_li_5_1():    """《统计学习方法》李航 例5.1 P.71"""    return [np.array([["青年", "否", "否", "一般"],                      ["青年", "否", "否", "好"],                      ["青年", "是", "否", "好"],                      ["青年", "是", "是", "一般"],                      ["青年", "否", "否", "一般"],                      ["中年", "否", "否", "一般"],                      ["中年", "否", "否", "好"],                      ["中年", "是", "是", "好"],                      ["中年", "否", "是", "非常好"],                      ["中年", "否", "是", "非常好"],                      ["老年", "否", "是", "非常好"],                      ["老年", "否", "是", "好"],                      ["老年", "是", "否", "好"],                      ["老年", "是", "否", "非常好"],                      ["老年", "否", "否", "一般", "否"]]),            np.array(["否", "否", "是", "是", "否",                      "否", "否", "是", "是", "是",                      "是", "是", "是", "是", "否"])]

熵（Python 实现）

【】code.dicision_tree.entropy

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_entropy.pyimport collectionsfrom math import logdef entropy(y, base=2):    """计算随机变量Y的熵"""    count = collections.Counter(y)    ans = 0    for freq in count.values():        prob = freq / len(y)        ans -= prob * log(prob, base)    return ans

【】测试

>>> from code.dicision_tree import entropy>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> entropy(Y)  # H(D)0.9709505944546686

条件熵（Python 实现）

【】code.dicision_tree.conditional_entropy

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_conditional_extropy.pyimport collectionsfrom math import logdef conditional_entropy(x, y, base=2):    """计算随机变量X给定的条件下随机变量Y的条件熵H(Y|X)"""    freq_y_total = collections.defaultdict(collections.Counter)  # 统计随机变量X取得每一个取值时随机变量Y的频数    freq_x = collections.Counter()  # 统计随机变量X每一个取值的频数    for i in range(len(x)):        freq_y_total[x[i]][y[i]] += 1        freq_x[x[i]] += 1    ans = 0    for xi, freq_y_xi in freq_y_total.items():        res = 0        for freq in freq_y_xi.values():            prob = freq / freq_x[xi]            res -= prob * log(prob, base)        ans += res * (freq_x[xi] / len(x))    return ans

【】测试

>>> from code.dicision_tree import conditional_entropy>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> conditional_entropy([X[i][0] for i in range(len(X))], Y)  # H(D|X=x_1)0.8879430945988998

信息增益（Python 实现）

【】code.dicision_tree.information_gain

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_information_gain.pyfrom ._conditional_extropy import conditional_entropy  # code.dicision_tree.conditional_entropyfrom ._entropy import entropy  # code.dicision_tree.entropydef information_gain(x, y, idx, base=2):    """计算特征A(第idx个特征)对训练数据集D(输入数据x,输出数据y)的信息增益"""    return entropy(y, base=base) - conditional_entropy([x[i][idx] for i in range(len(x))], y, base=base)

【】测试

>>> from code.dicision_tree import information_gain>>> from code.example import load_li_5_1>>> X, Y = load_example()>>> information_gain(X, Y, idx=0)  # g(D,A1)0.08300749985576883

信息增益比（Python 实现）

【】code.dicision_tree.information_gain_ratio

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_information_gain_ratio.pyfrom ._entropy import entropy  # code.dicision_tree.entropyfrom ._information_gain import information_gain  # code.dicision_tree.information_gaindef information_gain_ratio(x, y, idx, base=2):    """计算特征A(第idx个特征)对训练数据集D(输入数据x,输出数据y)的信息增益比"""    return information_gain(x, y, idx, base=base) / entropy([x[i][idx] for i in range(len(x))], base=base)

【】测试

>>> from code.dicision_tree import information_gain_ratio>>> from code.example import load_li_5_1>>> X, Y = load_example()>>> information_gain_ratio(X, Y, idx=0)  # gR(D,A1)0.05237190142858302>>> information_gain_ratio(X, Y, idx=1)  # gR(D,A2)0.3524465495205019>>> information_gain_ratio(X, Y, idx=2)  # gR(D,A3)0.4325380677663126>>> information_gain_ratio(X, Y, idx=3)  # gR(D,A4)0.23185388128724224

5.3.1 决策树的生成-ID3 算法

ID3 算法生成决策树-不包含剪枝（Python 实现）

【】code.dicision_tree.DecisionTreeID3WithoutPruning

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_decision_tree_id3_without_pruning.pyimport collectionsfrom ._conditional_extropy import conditional_entropy  # code.dicision_tree.conditional_entropyfrom ._entropy import entropy  # code.dicision_tree.entropyclass DecisionTreeID3WithoutPruning:    """ID3生成算法构造的决策树（仅支持离散型特征）-不包括剪枝"""    class Node:        def __init__(self, mark, use_feature=None, children=None):            if children is None:                children = {
   }            self.mark = mark            self.use_feature = use_feature  # 用于分类的特征            self.children = children  # 子结点        @property        def is_leaf(self):            return len(self.children) == 0    def __init__(self, x, y, labels=None, base=2, epsilon=0):        if labels is None:            labels = ["特征{}".format(i + 1) for i in range(len(x[0]))]        self.labels = labels  # 特征的标签        self.base = base  # 熵的单位（底数）        self.epsilon = epsilon  # 决策树生成的阈值        # ---------- 构造决策树 ----------        self.n = len(x[0])        self.root = self._build(x, y, set(range(self.n)))  # 决策树生成    def _build(self, x, y, spare_features_idx):        """根据当前数据构造结点        :param x: 输入变量        :param y: 输出变量        :param spare_features_idx: 当前还可以使用的特征的下标        """        freq_y = collections.Counter(y)        # 若D中所有实例属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记        if len(freq_y) == 1:            return self.Node(y[0])        # 若A为空集，则T为单结点树，并将D中实例数最大的类Ck作为该结点的标记        if not spare_features_idx:            return self.Node(freq_y.most_common(1)[0][0])        # 计算A中各特征对D的信息增益，选择信息增益最大的特征Ag        best_feature_idx, best_gain = -1, 0        for feature_idx in spare_features_idx:            gain = self.information_gain(x, y, feature_idx)            if gain > best_gain:                best_feature_idx, best_gain = feature_idx, gain        # 如果Ag的信息增益小于阈值epsilon，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记        if best_gain <= self.epsilon:            return self.Node(freq_y.most_common(1)[0][0])        # 依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点        node = self.Node(freq_y.most_common(1)[0][0], use_feature=best_feature_idx)        features = set()        sub_x = collections.defaultdict(list)        sub_y = collections.defaultdict(list)        for i in range(len(x)):            feature = x[i][best_feature_idx]            features.add(feature)            sub_x[feature].append(x[i])            sub_y[feature].append(y[i])        for feature in features:            node.children[feature] = self._build(sub_x[feature], sub_y[feature],                                                 spare_features_idx - {
   best_feature_idx})        return node    def __repr__(self):        """深度优先搜索绘制可视化的决策树"""        def dfs(node, depth=0, value=""):            if node.is_leaf:  # 处理叶结点的情况                res.append(value + " -> " + node.mark)            else:                if depth > 0:  # 处理中间结点的情况                    res.append(value + " :")                for val, child in node.children.items():                    dfs(child, depth + 1, "  " * depth + self.labels[node.use_feature] + " = " + val)        res = []        dfs(self.root)        return "\n".join(res)    def information_gain(self, x, y, idx):        """计算信息增益"""        return entropy(y, base=self.base) - conditional_entropy([x[i][idx] for i in range(len(x))], y, base=self.base)

【】测试

>>> from code.dicision_tree import DecisionTreeID3WithoutPruning>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> decision_tree = DecisionTreeID3WithoutPruning(X, Y, labels=["年龄", "有工作", "有自己的房子", "信贷情况"])>>> decision_tree有自己的房子 = 是 -> 是有自己的房子 = 否 :  有工作 = 是 -> 是  有工作 = 否 -> 否

5.3.2 决策树的生成-C4.5 的生成算法

【补充说明】C4.5 算法在生成的过程中，除了用信息增益比来选择特征外，还增加了通过动态定义将连续属性值分隔成一组离散间隔的离散属性，从而支持了连续属性的情况。以下实现的内容为书中描述的 C4.5 生成算法！

C4.5 的生成算法生成决策树-不包含剪枝（Python 实现）

【】code.dicision_tree.DecisionTreeC45WithoutPruning

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_decision_tree_c45_without_pruning.pyfrom ._decision_tree_id3_without_pruning import DecisionTreeID3WithoutPruning  # code.dicision_tree.DecisionTreeID3WithoutPruningfrom ._entropy import entropy  # code.dicision_tree.entropyclass DecisionTreeC45WithoutPruning(DecisionTreeID3WithoutPruning):    """C4.5生成算法构造的决策树（仅支持离散型特征）-不包含剪枝"""    def information_gain(self, x, y, idx):        """重写计算信息增益的方法，改为计算信息增益比"""        return super().information_gain(x, y, idx) / entropy([x[i][idx] for i in range(len(x))], base=self.base)

【】测试

>>> from code.dicision_tree import DecisionTreeC45WithoutPruning>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> decision_tree = DecisionTreeC45WithoutPruning(X, Y, labels=["年龄", "有工作", "有自己的房子", "信贷情况"])>>> decision_tree有自己的房子 = 是 -> 是有自己的房子 = 否 :  有工作 = 是 -> 是  有工作 = 否 -> 否

5.4 决策树的剪枝

【问题】决策树的剪枝为什么可以使用动态规划？

这是树形 DP 的标准案例，即每一个结点在计算时，先计算出所有子结点的最优解，然后其根据子结点的最优解计算当前结点的最优解。

参考资料：

ID3 算法生成决策树-包含剪枝（Python 实现）

【】code.decision_tree.DecisionTreeID3

# https://github.com/ChangxingJiang/Data-Mining-HandBook/blob/master/code/dicision_tree/_decision_tree_id3.pyimport collectionsfrom ._conditional_extropy import conditional_entropy  # code.dicision_tree.conditional_entropyfrom ._entropy import entropy  # code.dicision_tree.entropyclass DecisionTreeID3:    """ID3生成算法构造的决策树（仅支持离散型特征）"""    class Node:        def __init__(self, mark, ee, use_feature=None, children=None):            if children is None:                children = {
   }            self.mark = mark            self.use_feature = use_feature  # 用于分类的特征            self.children = children  # 子结点            self.ee = ee  # 以当前结点为叶结点的经验熵        @property        def is_leaf(self):            return len(self.children) == 0    def __init__(self, x, y, labels=None, base=2, epsilon=0, alpha=0.05):        if labels is None:            labels = ["特征{}".format(i + 1) for i in range(len(x[0]))]        self.labels = labels  # 特征的标签        self.base = base  # 熵的单位（底数）        self.epsilon = epsilon  # 决策树生成的阈值        self.alpha = alpha  # 决策树剪枝的参数        # ---------- 构造决策树 ----------        self.n = len(x[0])        self.root = self._build(x, y, set(range(self.n)))  # 决策树生成        self._pruning(self.root)  # 决策树剪枝    def _build(self, x, y, spare_features_idx):        """根据当前数据构造结点        :param x: 输入变量        :param y: 输出变量        :param spare_features_idx: 当前还可以使用的特征的下标        """        freq_y = collections.Counter(y)        ee = entropy(y, base=self.base)  # 计算以当前结点为叶结点的经验熵        # 若D中所有实例属于同一类Ck，则T为单结点树，并将Ck作为该结点的类标记        if len(freq_y) == 1:            return self.Node(y[0], ee)        # 若A为空集，则T为单结点树，并将D中实例数最大的类Ck作为该结点的标记        if not spare_features_idx:            return self.Node(freq_y.most_common(1)[0][0], ee)        # 计算A中各特征对D的信息增益，选择信息增益最大的特征Ag        best_feature_idx, best_gain = -1, 0        for feature_idx in spare_features_idx:            gain = self.information_gain(x, y, feature_idx)            if gain > best_gain:                best_feature_idx, best_gain = feature_idx, gain        # 如果Ag的信息增益小于阈值epsilon，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记        if best_gain <= self.epsilon:            return self.Node(freq_y.most_common(1)[0][0], ee)        # 依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点        node = self.Node(freq_y.most_common(1)[0][0], ee, use_feature=best_feature_idx)        features = set()        sub_x = collections.defaultdict(list)        sub_y = collections.defaultdict(list)        for i in range(len(x)):            feature = x[i][best_feature_idx]            features.add(feature)            sub_x[feature].append(x[i])            sub_y[feature].append(y[i])        for feature in features:            node.children[feature] = self._build(sub_x[feature], sub_y[feature],                                                 spare_features_idx - {
   best_feature_idx})        return node    def _pruning(self, node):        # 处理当前结点为叶结点的情况：不剪枝，直接返回        if node.is_leaf:            return 1, node.ee        # 计算剪枝（以当前结点为叶结点）的损失函数        loss1 = node.ee + 1 * self.alpha        # 计算不剪枝的损失函数        num, ee = 1, 0        for child in node.children.values():            child_num, child_ee = self._pruning(child)            num += child_num            ee += child_ee        loss2 = ee + num * self.alpha        # 处理需要剪枝的情况        if loss1 < loss2:            node.children = {
   }            return 1, node.ee        # 处理不需要剪枝的情况        else:            return num, ee    def __repr__(self):        """深度优先搜索绘制可视化的决策树"""        def dfs(node, depth=0, value=""):            if node.is_leaf:  # 处理叶结点的情况                res.append(value + " -> " + node.mark)            else:                if depth > 0:  # 处理中间结点的情况                    res.append(value + " :")                for val, child in node.children.items():                    dfs(child, depth + 1, "  " * depth + self.labels[node.use_feature] + " = " + val)        res = []        dfs(self.root)        return "\n".join(res)    def information_gain(self, x, y, idx):        """计算信息增益"""        return entropy(y, base=self.base) - conditional_entropy([x[i][idx] for i in range(len(x))], y, base=self.base)

【】测试

>>> from code.dicision_tree import DecisionTreeID3>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> DecisionTreeID3(X, Y, labels=["年龄", "有工作", "有自己的房子", "信贷情况"], alpha=0.2)有自己的房子 = 是 -> 是有自己的房子 = 否 :  有工作 = 是 -> 是  有工作 = 否 -> 否>>> DecisionTreeID3(X, Y, labels=["年龄", "有工作", "有自己的房子", "信贷情况"], alpha=0.3) -> 是

5.5 CART 算法

分类误差率

分类误差率，即分类错误的实例数占总实例数的比例。因为在叶结点中，我们选择实例数最大的类作为标记，所以不是该类的实例均会被标记错误。因此，分类误差率可定义为：

$$error(p)=1-\underset{k}{\max }{p}_k,k=1,2,\cdots ,K$$

【问题】为什么不用分类误差率衡量信息增益？

当某个结点中实例数最多的类，与其每个子结点中实例数最多的类均相同时；若用分类误差率衡量信息增益，因为不会考虑子结点中各类比例的变化，所以信息增益为 0；但若用熵或基尼系数衡量信息增益，因为会考虑子结点中各类比例的变化，所以信息增益不为 0。我们通过一个例子来看（以下“类标记”均表示以该结点为叶结点时的类标记，熵的单位均为比特）：

现有结点 T0，其中包含 A 类实例 80 个，B 类实例 20 个；当结点 T0 时，其类标记为 A，分类误差率为 0.2，熵为 0.722。

现有一种分割方法，可以将结点 T0 分隔为结点 T1 和结点 T2；其中结点 T1 包含 A 类实例 60 个，B 类实例 5 个；结点 T2 包含 A 类实例 20 个，B 类实例 15 个。此时结点 T1 的类标记为 A，分类误差率为 0.077，熵为 0.391；结点 T2 的类标记为 A，分类误差率为 0.429，熵为 0.985。对于结点 T0，其分类误差率为 $0.077\times 0.65+0.429\times 0.35=0.2$，其熵为 $0.391\times 0.65+0.985\times 0.35=0.599$。

此时，使用分类误差率衡量的信息增益为 0，使用熵衡量的信息增益为 0.123。

CART 分类树（Python+sklearn 实现）

【】测试实例 1（例 5.1 的测试集）

>>> from sklearn.tree import DecisionTreeClassifier>>> from sklearn.tree import export_text>>> from code.example import load_li_5_1>>> X, Y = load_li_5_1()>>> N = len(X)>>> n = len(X[0])# 坐标压缩（将可能存在的非数值的特征及类别转换为数值）>>> y_list = list(set(Y))>>> y_mapping = {
   c: i for i, c in enumerate(y_list)}>>> x_list = [list(set(X[i][j] for i in range(N))) for j in range(n)]>>> x_mapping = [{
   c: i for i, c in enumerate(x_list[j])} for j in range(n)]>>> for i in range(N):...     for j in range(n):...         X[i][j] = x_mapping[j][X[i][j]]>>> for i in range(N):...     Y[i] = y_mapping[Y[i]]>>> clf = DecisionTreeClassifier()>>> clf.fit(X, Y)>>> export_text(clf, feature_names=["年龄", "有工作", "有自己的房子", "信贷情况"],show_weights=True)|--- 有自己的房子 <= 0.50|   |--- 有工作 <= 0.50|   |   |--- weights: [6.00, 0.00] class: 0|   |--- 有工作 >  0.50|   |   |--- weights: [0.00, 3.00] class: 1|--- 有自己的房子 >  0.50|   |--- weights: [0.00, 6.00] class: 1

【】测试示例 2（鸢尾花数据集）

>>> from sklearn.datasets import load_iris>>> from sklearn.model_selection import train_test_split>>> from sklearn.tree import DecisionTreeClassifier>>> from sklearn.tree import export_text>>> iris = load_iris()>>> X = iris.data>>> Y = iris.target>>> x1, x2, y1, y2 = train_test_split(X, Y, test_size=1 / 3, random_state=0)>>> clf = DecisionTreeClassifier(ccp_alpha=0.02, random_state=0)>>> clf.fit(x1, y1)>>> export_text(clf, feature_names=iris.feature_names, show_weights=True)|--- petal width (cm) <= 0.75|   |--- weights: [34.00, 0.00, 0.00] class: 0|--- petal width (cm) >  0.75|   |--- petal length (cm) <= 4.95|   |   |--- petal width (cm) <= 1.65|   |   |   |--- weights: [0.00, 29.00, 0.00] class: 1|   |   |--- petal width (cm) >  1.65|   |   |   |--- weights: [0.00, 1.00, 3.00] class: 2|   |--- petal length (cm) >  4.95|   |   |--- weights: [0.00, 1.00, 32.00] class: 2>>> clf.score(x2, y2)0.98

CART 回归树（Python+sklearn 实现）

【】测试示例（波士顿房价数据集）

>>> from sklearn.datasets import load_boston>>> from sklearn.model_selection import train_test_split>>> from sklearn.tree import DecisionTreeRegressor>>> from sklearn.tree import export_text>>> boston = load_boston()>>> X = boston.data>>> Y = boston.target>>> x1, x2, y1, y2 = train_test_split(X, Y, test_size=1 / 3, random_state=0)>>> clf = DecisionTreeRegressor(ccp_alpha=0.16, random_state=0)>>> clf.fit(x1, y1)>>> export_text(clf, feature_names=list(boston.feature_names))|--- LSTAT <= 7.88|   |--- RM <= 7.43......|   |   |   |   |--- NOX >  0.68|   |   |   |   |   |--- value: [9.21]>>> clf.score(x2, y2)  # 平方误差0.7217463605968275

转载地址：https://dataartist.blog.csdn.net/article/details/118033550 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！