参考：ysu老师课件+西瓜书

1.决策树的基本概念

【决策树】：决策树是一种描述对样本数据进行分类的树形结构模型，由节点和有向边组成。其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

理解：它是一个树状结构，其中每个节点代表一个特征属性的判断，每个分支代表这个判断的结果，而每个叶节点（叶子）代表一种类别或回归值。

关于决策树要掌握的概念：

  1. 根节点（Root Node）： 包含整个数据集，并通过某个特征属性进行判断。

  2. 分支（Branch）： 从根节点出发的每个路径，代表在某个特征属性上的判断结果。

  3. 内部节点（Internal Node）： 在决策路径上的非叶节点，表示对某个特征属性的判断。

  4. 叶节点（Leaf Node）： 在决策路径上的末端节点，表示最终的类别或回归值。

决策树的优缺点：

优点：

  • 易于理解和解释： 决策树的图形化表示使得结果容易理解，可以可视化地表示整个决策过程。

  • 无需特征缩放： 不需要对特征进行标准化或归一化。

  • 处理混合数据类型： 可以处理既有连续型特征又有离散型特征的数据。

  • 能够捕捉特征之间的相互关系： 可以捕捉特征之间的非线性关系。

缺点：

  • 过拟合（Overfitting）： 在处理复杂问题时容易生成过于复杂的树，导致在训练数据上表现良好但在未知数据上泛化能力差。

  • 对噪声敏感： 对数据中的噪声和异常值较为敏感。

  • 不稳定性： 数据的小变化可能导致生成完全不同的树。

2.决策树的生成过程

决策树模型涉及到三个关键过程：

一是特征变量的选择，根据某个指标（如信息增益、基尼指数等）选择当前最佳的特征属性作为判断依据。

二是决策树的生成，常用的决策树算法有ID3、C4.5、CART等算法；

三是决策树的剪枝，通过剪枝来避免过拟合，提升对数据的预测效果。

2.1 特征变量的选择

最常用的三种特征选择策略：信息增益、信息增益比、Gini指数

2.1.1 信息增益

首先引入【信息量】。

消息中所包含的信息量大小与该消息所表示的事件出现的概率相关，如果一个消息所表示的事件是必然事件（发生概率100%），则该消息所包含的信息量为0；如果一个消息表示的不可能事件（发生概率极低），则该消息的信息量为无穷大。

比如：某同事跑过来和你说：“小王，明早太阳会从东方升起”。（概率为1，信息量为0）

信息量应该随着概率单调递减：某事件的概率越大，则信息量越小。

再引入【信息熵】。

“信息熵”用来表示信息不确定性的一种度量。熵越高表示越混乱，熵越低表示越有序。

（类比高中学的分子状态混乱程度，熵越大越混乱）

再引入【信息增益】。

“信息增益”表示在知道某个特征之后使得不确定性减少的程度（知道某个特征前的熵与知道某个特征之后的熵之差）。

根据某个变量将样本数据分割为多个子集，分割前与分割后样本数据的熵之差为信息增益，信息增益越高，表示该变量对样本数据的分类效果越好。

2.1.2 信息增益比

再引入【信息增益比】

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，因此通过引入了【信息增益比】来解决该问题。

比如：以user_id为特征变量，由于每个人的user_id是唯一的，在每个user_id下可以完美地进行准确分类，但是这种情况显然是无意义的。

注：只有在不同变量分裂出不同个数子节点的情况下，信息增益比才会起作用。如果每个变量允许分裂相同个数的子节点，那么信息增益比并不起作用。

2.1.3 Gini指数

Gini指数也是衡量随机变量不纯度的一种方法，Gini指数越小，则表示变量纯度越高，Gini指数越大，表示变量纯度越低。

理解：

Gini指数表示在样本集合中随机抽取两个样本，其类别不一致的概率。因此Gini指数越小，分类越纯。

2.2 决策树的生成

常用的决策树算法有：ID3、C4.5、CART

先介绍决策树生成时的三个【终止条件】：

  1. 当前节点包含的样本全部属于同一类别
  2. 当前节点已经没有样本，不能再继续划分
  3. 所有特征已经使用完毕

2.2.1 ID3——信息增益

ID3（Iterative Dichotomiser 3）是一种基于信息增益的决策树生成算法。

其主要步骤包括：

  1. 计算信息熵： 对每个特征计算数据集的信息熵，用于度量数据的不确定性。

  2. 计算信息增益： 对每个特征计算信息增益，选择信息增益最大的特征作为当前节点的划分特征。

  3. 划分数据集： 使用选择的最佳特征对数据集进行划分，生成相应的子集。

  4. 递归生成子树： 对每个子集递归地应用上述步骤，生成子树。

  5. 停止条件： 在递归生成子树的过程中，设置停止条件，例如树的深度达到预定值、节点包含的样本数小于某个阈值等。

【专业描述】

2.2.2 C4.5——信息增益比

C4.5算法整体上与ID3算法非常相似，不同之处是C4.5以信息增益比为准则来选择分枝变量。

2.2.3 CART——Gini指数

CART（Classification and Regression Trees）是一种基于Gini指数的决策树生成算法，可用于分类和回归任务。

其主要步骤包括：

  1. 计算Gini指数： 对每个特征计算数据集的Gini指数，用于度量数据的不纯度。

  2. 选择最小Gini指数的特征： 选择Gini指数最小的特征作为当前节点的划分特征。

  3. 划分数据集： 使用选择的最佳特征对数据集进行划分，生成相应的子集。

  4. 递归生成子树： 对每个子集递归地应用上述步骤，生成子树。

  5. 停止条件： 在递归生成子树的过程中，设置停止条件，例如树的深度达到预定值、节点包含的样本数小于某个阈值等。

【专业描述】

注意：

CART是一种二叉树，即将所有问题看做二元分类问题。

由于CART是二叉树，在遇到连续变量或者多元分类变量时，存在寻找最优切分点的情况。

【补充】

CART的缺点

  1. 二元划分： CART算法每次划分只能选择一个特征的一个切分点进行二元划分，这可能导致树的结构相对较深，对某些问题可能不够简洁。

  2. 贪婪算法： CART是一种贪婪算法，它在每一步选择最优划分，但这并不一定会导致全局最优的决策树。有时候，全局最优的决策树需要考虑多步划分的组合，而CART只考虑当前最优的一步。

  3. 对于不平衡数据集的处理： 在处理不平衡数据集时，CART可能会偏向那些具有较多样本的类别，导致对于少数类的划分不够精细。

  4. 非平滑性： CART生成的树是非平滑的，对于输入空间的微小变化可能产生较大的输出变化，这使得CART对于输入空间的局部变化较为敏感。

两种决策的对比

  • 信息增益（ID3）： 用于分类问题，通过选择能够最大程度降低不确定性的特征。

  • 基尼不纯度（CART）： 适用于分类和回归问题，通过选择能够最小化不纯度的特征。

2.3 决策树的剪枝

决策树的剪枝是为了防止过拟合，即过度依赖训练数据而导致在未知数据上表现不佳。

剪枝通过修剪决策树的一部分来达到简化模型的目的。

剪枝分为预剪枝（Pre-pruning）和后剪枝（Post-pruning）两种类型。

2.3.1 预剪枝

在决策树生成的过程中，在每次划分节点之前，通过一些预定的规则判断是否继续划分。若当前结点的划分不能使决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别。

预剪枝的一些常见条件包括：

  • 树的深度限制： 设置树的最大深度，防止树过于复杂。
  • 节点样本数量限制： 当节点中的样本数量小于某个阈值时停止划分。
  • 信息增益或基尼不纯度阈值： 当划分节点后的信息增益或基尼不纯度低于设定的阈值时停止划分。

预剪枝的优缺点

优点：

  • 降低过拟合风险
  • 显著减少训练时间和测试时间开销

缺点：

  • 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险

2.3.2 后剪枝

在决策树生成完成后，通过递归地从底部向上对节点进行判断，决定是否剪枝。

具体过程如下：

  • 从叶子节点开始： 递归地向上考察每个叶子节点。

  • 计算剪枝前后的性能： 对于每个叶子节点，计算剪枝前后在验证集上的性能差异。

  • 剪枝决策： 如果剪枝可以提高性能（如准确率、F1分数等），则进行剪枝，将该节点变为叶子节点。

  • 重复： 重复上述过程，直到找到合适的剪枝点或不再发生性能提升。

后剪枝相对于预剪枝更为灵活，因为它在生成完整的树之后才进行剪枝决策，可以更准确地评估每个子树的性能。

后剪枝的优缺点：

优点：

  • 后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树

缺点

  • 训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察

3.代码实践

# 导入必要的库from sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.tree import DecisionTreeClassifier, export_textfrom sklearn import treeimport matplotlib.pyplot as plt# 加载示例数据集（鸢尾花数据集）iris = load_iris()X = iris.datay = iris.target# 将数据集划分为训练集和测试集X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)# 创建决策树模型clf = DecisionTreeClassifier()# 训练模型clf.fit(X_train, y_train)# 使用模型进行预测y_pred = clf.predict(X_test)# 输出模型的准确率accuracy = clf.score(X_test, y_test)print(f"Model Accuracy: {accuracy:.2f}")# 输出决策树的规则tree_rules = export_text(clf, feature_names=iris.feature_names)print("Decision Tree Rules:\n", tree_rules)# 可视化决策树fig, ax = plt.subplots(figsize=(12, 8))tree.plot_tree(clf, feature_names=iris.feature_names, class_names=iris.target_names, filled=True, ax=ax)plt.show()