[05] 决策树

机器学习笔记

前言

导读

决策树是一种基本的分类与回归方法. 在书中CART算法之前的章节说的都是分类树，ID3和C4.5都只能处理分类问题，从CART(Classification and Regression Tree)开始有回归树，统称为决策树；
决策树学习的损失函数是对数似然损失，关于决策树的剪枝，最重要的在于这个损失函数的理解；
CART虽然在本书中排在ID3和C4.5后面，但是发表的时间顺序为CART->ID3->C4.5；
熵，基尼指数衡量的都是集合的不确定性，应用在推荐的场景，不确定性越大，覆盖率可能就越大；
书中有提到，分类问题中，决策树表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间上与类空间的条件概率分布。书中第一小节对这个问题做了解释；
剪枝是模型压缩领域中的经典技术。剪枝可以降低模型复杂度，防止过拟合，提升模型泛化性能；

概念

熵

$$
H(p)=H(X)=-\sum_{i=1}^{n}p_i\log p_i
$$

熵只与X的分布有关，与X取值无关。根据定义，$0 \times \log(0) = 0$，熵是非负的；其实按照个人理解也就是对于一些信息推断其他信息的把握性；（当然我的解释不一定准确）

条件熵

随机变量(X,Y)的联合概率分布为：

$P(X = x_i, Y = y_j) = p_{ij}, \quad i = 1, 2, \ldots, n; \quad j = 1, 2, \ldots, m$

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量，Y的不确定性；

$$
H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)
$$

其中 $ p_i = P(X = x_i), \quad i = 1, 2, \ldots, n $；

经验熵，经验条件熵

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵

就是从已知的数据计算得到的结果。

信息增益

特征A对训练数据集D的信息增益g(D|A)，定义为集合D的经验熵H(D)与特征A给定的条件下D的经验条件熵H(D|A)之差；熵与条件熵的差称为互信息；

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

决策树中的信息增益等价于训练数据集中的类与特征的互信息。

考虑ID这种特征，本身是唯一的。按照ID做划分，得到的经验条件熵为0, 会得到最大的信息增益。所以，按照信息增益的准则来选择特征，可能会倾向于取值比较多的特征。

信息增益比

$$
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}
$$

算法构建

算法5.1 信息增益

输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益$g(D,A)$；
数据集 $ D $ 的经验熵 $ H(D) $ 定义为：\[ H(D) = -\sum_{k=1}^K \frac{|C_k|}{|D|} \log_2 \left(\frac{|C_k|}{|D|}\right) \]
特征 $ A $ 对数据集 $ D $ 的经验条件熵 $ H(D|A) $ 定义为：\[ H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|} \log_2 \left(\frac{|D_{ik}|}{|D_i|}\right) \]
信息增益 $ g(D,A) $ 计算为：\[ g(D,A) = H(D) - H(D|A) \]

算法5.2 ID3算法

输入：训练数据集 $ D $，特征集 $ A $，阈值 $ \epsilon $ 输出：决策树 $ T $ ：
如果 $ D $ 属于同一类 $ C_k $，$ T $ 为单节点树，类 $ C_k $ 作为该节点的类标记，返回 $ T $ ；
如果 $ A $ 是空集，置 $ T $ 为单节点树，实例数最多的类作为该节点类标记，返回 $ T $ ；
计算 $ g $，选择信息增益最大的特征 $ A_g $；
如果 $ A_g $ 的信息增益小于 $ \epsilon $，$ T $ 为单节点树，$ D $ 中实例数最大的类 $ C_k $ 作为类标记，返回 $ T $
用 $ A_g $ 划分若干非空子集 $ D_i $；
对每个 $ D_i $ 训练集，用 $ A - A_g $ 为特征集，递归调用前面步骤，得到 $ T_i $，返回 $ T_i $ 。

算法5.3 C4.5生成

输入：训练数据集 $ D $，特征集 $ A $，阈值 $ \epsilon $ 输出：决策树 $ T $：
如果 $ D $ 属于同一类 $ C_k $，$ T $ 为单节点树，类 $ C_k $ 作为该节点的类标记，返回 $ T $；
如果 $ A $ 是空集，置 $ T $ 为单节点树，实例数最多的类作为该节点类标记，返回 $ T $；
计算 $ g $，选择信息增益比最大的特征 $ A_g $；
如果 $ A_g $ 的信息增益比小于 $ \epsilon $，$ T $ 为单节点树，$ D $ 中实例数最大的类 $ C_k $ 作为类标记，返回 $ T $；
用 $ A_g $ 划分若干非空子集 $ D_i $，对每个 $ D_i $ 训练集，用 $ A - A_g $ 为特征集，递归调用前面步骤，得到 $ T_i $，返回 $ T_i $；
ID3 和 C4.5 在生成上，差异只在准则的差异。

算法5.4 树的剪枝

决策树损失函数摘录如下：

树 $ T $ 的叶结点个数为 $ |T| $，$ t $ 是树 $ T $ 的叶结点，该结点有 $ N_t $ 个样本点，其中 $ k $ 类的样本点有 $ N_{tk} $ 个，$ H_t(T) $ 为叶结点 $ t $ 上的经验熵，$ \alpha \geqslant 0 $ 为参数，决策树学习的损失函数可以定义为：
$$
C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|
$$
其中：
$$
H_t(T)=-\sum_k\color{red}\frac{N_{tk}}{N_t}\color{black}\log \frac{N_{tk}}{N_t}
$$
$$
C(T)=\sum_{t=1}^{|T|}\color{red}N_tH_t(T)\color{black}=-\sum_{t=1}^{|T|}\sum_{k=1}^K\color{red}N_{tk}\color{black}\log\frac{N_{tk}}{N_t}
$$
这时有：
$$
C_\alpha(T)=C(T)+\alpha|T|
$$
其中 $ C(T) $ 表示模型对训练数据的误差，$ |T| $ 表示模型复杂度，参数 $ \alpha \geqslant 0 $ 控制两者之间的影响。

上面这组公式中，注意红色部分，下面插入一个图：

在决策树的损失函数中，并没有直接对 $ H_t(T) $ 求和，但是系数 $ N_t $ 确保了每个叶结点 $ t $ 的经验熵 $ H_t(T) $ 乘以该结点的样本数量，从而使得模型对训练数据的误差 $ C(T) $ 和模型复杂度 $ |T| $ 的大小可以相互比较。参数 $ \alpha \geqslant 0 $ 控制着误差和复杂度之间的权衡。

输入：生成算法生成的整个树 $ T $，参数 $ \alpha $;
输出：修剪后的子树 $ T_\alpha $;
计算每个结点的经验熵；
递归地从树的叶结点向上回缩，假设一组叶结点回缩到其父结点之前与之后的整体树分别是 $ T_B $ 和 $ T_A $，其对应的损失函数分别是 $ C_\alpha(T_A) $ 和 $ C_\alpha(T_B) $。如果 $ C_\alpha(T_A) \leqslant C_\alpha(T_B) $ 则进行剪枝，即将父结点变为新的叶结点
返回步骤 2，直至不能继续为止，得到损失函数最小的子树 $ T_\alpha $。

CART

算法5.5 最小二乘回归树生成

输入：训练数据集 $ D $
输出：回归树 $ f(x) $
遍历变量 $ j $，对固定的切分变量 $ j $ 扫描切分点 $ s $，得到满足上面关系的 $ (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]
\]
用选定的 $ (j, s) $ 划分区域并决定相应的输出值：
\[
\begin{align*}
R_1(j,s) &= \{x | x^{(j)} \leq s\}, \\
R_2(j,s) &= \{x | x^{(j)} > s\}, \\
\hat{c}_m &= \frac{1}{N}\sum_{x_i\in R_m(j,s)} y_j, & x\in R_m, m=1,2.
\end{align*}
\]
对两个子区域调用步骤 (1) 和 (2)，直至满足停止条件。
将输入空间划分为 $ M $ 个区域 $ R_1, R_2, \dots, R_M $，生成决策树：
\[
f(x) = \sum_{m=1}^M \hat{c}_m I(x\in R_m)
\]

算法5.6 CART分类树生成

这个算法用到的策略是基尼系数，所以是分类树的生成算法。

概率分布的基尼指数定义

$$
Gini(p) = \sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2
$$

基尼系数是一个来源于经济学的指标. 范围(0, 1), 有很多中表示形式, 比如衡量收入分布的基尼系数.

$$
G=\frac{1}{n-1}\sum_{j=1}^n(2j-n-1)p(i_j)
$$

基尼系数为 $ \text{Gini Coefficient} = \frac{A}{A+B} $，其中 $ A $ 表示图中面积表示不平等的部分，$ B $ 表示图中面积表示完全平等的部分。

算法5.7 CART剪枝

python代码实现

根据书中表5.1数据构建决策树模型：（建议在类似jupyter环境中运行，由于网页代码构建代码高亮标注配置麻烦，可以复制到本地IDE查看）

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter
import math
from math import log
import pprint

# 书上题目5.1，构建数据集
def create_data():
    datasets = [['青年', '否', '否', '一般', '否'],
               ['青年', '否', '否', '好', '否'],
               ['青年', '是', '否', '好', '是'],
               ['青年', '是', '是', '一般', '是'],
               ['青年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '好', '否'],
               ['中年', '是', '是', '好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '好', '是'],
               ['老年', '是', '否', '好', '是'],
               ['老年', '是', '否', '非常好', '是'],
               ['老年', '否', '否', '一般', '否'],
               ]
    labels = ['年龄','有工作','有自己的房子','信贷情况','类别']
    return datasets, labels
  
datasets, labels = create_data()
train_data = pd.DataFrame(datasets, columns=labels)
train_data  # jupyter中检查返回表格数据问题

# 算法部分
# 熵
def calc_ent(datasets):
    data_length = len(datasets)
    label_count = {}
    for i in range(data_length):
        label = datasets[i][-1]
        if label not in label_count:
            label_count[label] = 0
        label_count[label] += 1
    ent = -sum([(p / data_length) * log(p / data_length, 2)
                for p in label_count.values()])
    return ent
# 算法优化：使用 NumPy 的 bincount 和 log2 函数来简化计算过程    
# def entropy(y):
#     """
#     Entropy of a label sequence
#     """
#     hist = np.bincount(y)
#     ps = hist / np.sum(hist)
#     return -np.sum([p * np.log2(p) for p in ps if p > 0])


# 经验条件熵
def cond_ent(datasets, axis=0):
    data_length = len(datasets)
    feature_sets = {}
    for i in range(data_length):
        feature = datasets[i][axis]
        if feature not in feature_sets:
            feature_sets[feature] = []
        feature_sets[feature].append(datasets[i])
    cond_ent = sum(
        [(len(p) / data_length) * calc_ent(p) for p in feature_sets.values()])
    return cond_ent


# 信息增益
def info_gain(ent, cond_ent):
    return ent - cond_ent


def info_gain_train(datasets):
    count = len(datasets[0]) - 1
    ent = calc_ent(datasets)
    #ent = entropy(datasets)
    best_feature = []
    for c in range(count):
        c_info_gain = info_gain(ent, cond_ent(datasets, axis=c))
        best_feature.append((c, c_info_gain))
        print('特征({}) - info_gain - {:.3f}'.format(labels[c], c_info_gain))
    # 比较大小
    best_ = max(best_feature, key=lambda x: x[-1])
    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])
    
info_gain_train(np.array(datasets))

特征(年龄) - info_gain - 0.083
特征(有工作) - info_gain - 0.324
特征(有自己的房子) - info_gain - 0.420
特征(信贷情况) - info_gain - 0.363
'特征(有自己的房子)的信息增益最大，选择为根节点特征'

利用ID3算法生成决策树，例5.3

# 定义节点类 二叉树
class Node:
    def __init__(self, root=True, label=None, feature_name=None, feature=None):
        self.root = root
        self.label = label
        self.feature_name = feature_name
        self.feature = feature
        self.tree = {}
        self.result = {
            'label:': self.label,
            'feature': self.feature,
            'tree': self.tree
        }

    def __repr__(self):
        return '{}'.format(self.result)

    def add_node(self, val, node):
        self.tree[val] = node

    def predict(self, features):
        if self.root is True:
            return self.label
        return self.tree[features[self.feature]].predict(features)


class DTree:
    def __init__(self, epsilon=0.1):
        self.epsilon = epsilon
        self._tree = {}

    # 熵
    @staticmethod
    def calc_ent(datasets):
        data_length = len(datasets)
        label_count = {}
        for i in range(data_length):
            label = datasets[i][-1]
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        ent = -sum([(p / data_length) * log(p / data_length, 2)
                    for p in label_count.values()])
        return ent

    # 经验条件熵
    def cond_ent(self, datasets, axis=0):
        data_length = len(datasets)
        feature_sets = {}
        for i in range(data_length):
            feature = datasets[i][axis]
            if feature not in feature_sets:
                feature_sets[feature] = []
            feature_sets[feature].append(datasets[i])
        cond_ent = sum([(len(p) / data_length) * self.calc_ent(p)
                        for p in feature_sets.values()])
        return cond_ent

    # 信息增益
    @staticmethod
    def info_gain(ent, cond_ent):
        return ent - cond_ent

    def info_gain_train(self, datasets):
        count = len(datasets[0]) - 1
        ent = self.calc_ent(datasets)
        best_feature = []
        for c in range(count):
            c_info_gain = self.info_gain(ent, self.cond_ent(datasets, axis=c))
            best_feature.append((c, c_info_gain))
        # 比较大小
        best_ = max(best_feature, key=lambda x: x[-1])
        return best_

    def train(self, train_data):
        """
        input:数据集D(DataFrame格式)，特征集A，阈值eta
        output:决策树T
        """
        _, y_train, features = train_data.iloc[:, :
                                               -1], train_data.iloc[:,
                                                                    -1], train_data.columns[:
                                                                                            -1]
        # 1,若D中实例属于同一类Ck，则T为单节点树，并将类Ck作为结点的类标记，返回T
        if len(y_train.value_counts()) == 1:
            return Node(root=True, label=y_train.iloc[0])

        # 2, 若A为空，则T为单节点树，将D中实例树最大的类Ck作为该节点的类标记，返回T
        if len(features) == 0:
            return Node(
                root=True,
                label=y_train.value_counts().sort_values(
                    ascending=False).index[0])

        # 3,计算最大信息增益 同5.1,Ag为信息增益最大的特征
        max_feature, max_info_gain = self.info_gain_train(np.array(train_data))
        max_feature_name = features[max_feature]

        # 4,Ag的信息增益小于阈值eta,则置T为单节点树，并将D中是实例数最大的类Ck作为该节点的类标记，返回T
        if max_info_gain < self.epsilon:
            return Node(
                root=True,
                label=y_train.value_counts().sort_values(
                    ascending=False).index[0])

        # 5,构建Ag子集
        node_tree = Node(
            root=False, feature_name=max_feature_name, feature=max_feature)

        feature_list = train_data[max_feature_name].value_counts().index
        for f in feature_list:
            sub_train_df = train_data.loc[train_data[max_feature_name] ==
                                          f].drop([max_feature_name], axis=1)

            # 6, 递归生成树
            sub_tree = self.train(sub_train_df)
            node_tree.add_node(f, sub_tree)

        # pprint.pprint(node_tree.tree)
        return node_tree

    def fit(self, train_data):
        self._tree = self.train(train_data)
        return self._tree

    def predict(self, X_test):
        return self._tree.predict(X_test)
        
datasets, labels = create_data()
data_df = pd.DataFrame(datasets, columns=labels)
dt = DTree()
tree = dt.fit(data_df)

{'label:': None, 'feature': 2, 'tree': {'否': {'label:': None, 'feature': 1, 'tree': {'否': {'label:': '否', 'feature': None, 'tree': {}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}, '是': {'label:': '是', 'feature': None, 'tree': {}}}}

dt.predict(['老年', '否', '否', '一般'])
# '否'

使用scikit-learn实现对鸢尾花数据的决策树模型

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import pandas as pd
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
import graphviz

def create_data():
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = [
'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
]
data = df.iloc[:1000, [0, 1, -1]]
return data[['sepal length', 'sepal width']], data['label'], iris.target_names

X, y, target_names = create_data()
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=2423)

clf = DecisionTreeClassifier(random_state=2423)
clf.fit(X_train, y_train)

accuracy = clf.score(X_test, y_test)
print(f"Model accuracy: {accuracy:.2f}")

dot_data = tree.export_graphviz(
clf,
out_file=None,
feature_names=['sepal length', 'sepal width'],
class_names=target_names,
filled=True, rounded=True, special_characters=True
)

graph = graphviz.Source(dot_data)
graph.render("iris_decision_tree")
graph.view()

# Model accuracy: 0.63

习题5.3

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

第1步：内部节点是否剪枝只与以该节点为根节点的子树有关；

剪枝过程：计算子树的损失函数：$$C_{\alpha}(T)=C(T)+\alpha$$其中，$\displaystyle C(T) = \sum_{t=1}^{|T|}N_t (1 - \sum_{k=1}^K (\frac{N_{tk}}{N_t})^2)$，$|T|$是叶结点个数，$K$是类别个数；

有剪枝前子树$T_0$，剪枝后子树$T_1$，满足$C_{\alpha}(T_1) \leqslant C_{\alpha}(T_0)$则进行剪枝

第2步（反证法）：

假设当$\alpha$确定时，存在两颗子树$T_1,T_2$都使得损失函数$C_{\alpha}$最小。

第1种情况：假设被剪枝的子树在同一边，易知其中一个子树会由另一个子树剪枝而得到，故不可能存在两个最优子树，原结论得证。

第2种情况：假设被剪枝的子树不在同一边，易知被剪枝掉的子树都可以使损失函数$C_{\alpha}$最小，故两颗子树都可以继续剪枝，故不可能存在两个最优子树，原结论得证。

2024-08-26

查看评论

Comments | 8条评论

sxihosuyem

回复

2025年01月06日

哈哈哈，写的太好了https://www.lawjida.com/
rfwinsduye

回复

2024年12月16日

《公道天职》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/110660.html
iwxkpumybh

回复

2024年12月09日

《暴力云与送子鹳》动画片高清在线免费观看：https://www.jgz518.com/xingkong/11461.html
dsoxkztikn

回复

2024年11月20日

博主太厉害了！
hzpqzcwcci

回复

2024年10月06日

不错不错，我喜欢看 www.jiwenlaw.com
btsgahodxr

回复

2024年10月04日

不错不错，我喜欢看 https://www.ea55.com/
mmuhipdqje

回复

2024年09月23日

想想你的文章写的特别好
qovebqhboa

回复

2024年09月22日

博主真是太厉害了！！！

[05] 决策树

[05] 决策树

前言

导读

概念

熵

条件熵

经验熵，经验条件熵

信息增益

信息增益比

算法构建

算法5.1 信息增益

算法5.2 ID3算法

算法5.3 C4.5生成

算法5.4 树的剪枝

CART

算法5.5 最小二乘回归树生成

算法5.6 CART分类树生成

算法5.7 CART剪枝

python代码实现

习题5.3

同济体育馆自动化预约小软件实现原理

[04] 朴素贝叶斯

zy

Comments | 8条评论

sxihosuyem

rfwinsduye

iwxkpumybh

dsoxkztikn

hzpqzcwcci

btsgahodxr

mmuhipdqje

qovebqhboa

前言

导读

概念

熵

条件熵

经验熵， 经验条件熵

信息增益

信息增益比

算法构建

算法5.1 信息增益

算法5.2 ID3算法

算法5.3 C4.5生成

算法5.4 树的剪枝

CART

算法5.5 最小二乘回归树生成

算法5.6 CART分类树生成

算法5.7 CART剪枝

python代码实现

习题5.3

同济体育馆自动化预约小软件实现原理

[04] 朴素贝叶斯

Comments | 8条评论

你想搜索什么...

经验熵，经验条件熵