补充：

本文是关于《Sklearn 与 TensorFlow 机器学习实用指南》的学习笔记，基于六、决策树 - 【布客】Sklearn 与 TensorFlow 机器学习实用指南 第二版，感谢译者

本文和原文的区别：

本文会更精简、系统地表述书中概念，会对书中未介绍的陌生概念加以解释，每行我都会添加注释，介绍具体做了什么。

后续会持续更新所有章节

正文开始 ~
————————————————

1. 决策树基本概念：

决策树通过树状结构展示数据的特征和结果之间的关系，是一种用于分类和回归的预测模型。

1.1. 工作原理：

- 通过一系列问题将数据逐步分类或回归。
- 每个内部节点对应一个特征，根据特征值将数据分到不同的子树中。

1.2. 决策树类型：

- ID3：使用信息增益作为分裂标准。
- C4.5：基于信息增益率进行分裂。
- CART（本章主要介绍）：用于分类和回归，分别采用Gini指数或均方误差（MSE）。

Scikit-Learn 用的是 CART 算法， 仅产生二叉树：每一个非叶节点总是只有两个子节点（只有是或否两个结果）。然而，像 ID3 这样的算法可以产生超过两个子节点的决策树模型

1.3. 构建过程：

- 特征选择：确定每个节点的最佳分裂特征。
- 分裂节点：根据选定的特征将数据集分成子集。
- 生成子树：递归地在子集中继续构建决策树。
- 停止条件：如达到预设深度、样本数过少等。
- 剪枝：去除不必要的节点以提高泛化能力。

1.4. 与其他模型的关系：

- 随机森林（Random Forest）：基于决策树的集成学习方法，通过组合多个决策树提高性能。
- 梯度提升机（Gradient Boosting Machines, GBDT）：另一种集成方法，利用弱决策树模型进行迭代优化。

2. 决策树的训练和可视化

下面以鸢尾花数据花瓣的长宽和种类的关系为例

from sklearn.datasets import load_iris  # 加载鸢尾花数据集
from sklearn.tree import DecisionTreeClassifier  # 加载决策树分类器
iris = load_iris()  # 加载数据集
X = iris.data[:, 2:]  # 花瓣的长和宽
y = iris.target  # 花瓣所属种类
tree_clf = DecisionTreeClassifier(max_depth=2)  # 决策树分类器的最大深度设置为2
tree_clf.fit(X, y)  # 拟合数据

from sklearn.tree import export_graphviz
export_graphviz(
            tree_clf,
            out_file="iris_tree.dot",
            feature_names=iris.feature_names[2:],
            class_names=iris.target_names,
            rounded=True,
            filled=True
        )  # 生成iris_tree.dot的图形定义文件，可以将一个训练好的决策树模型可视化

利用 graphviz 的dot命令，将.dot文件转换成png，下载安装见：https://www.graphviz.org/download/
命令：dot -Tpng iris_tree.dot -o iris_tree.png

训练实例中，有 50个花瓣长度 ≤ 2.45，100 个花瓣长度＞ 2.45，在这 100 个样例中又有 54 个花瓣宽度≤ 1.75。

value: 该节点对于每一个类别的样例多少

例如：右下角的节点中包含 0 个Setosa，1 个Versicolor和45个Virginica。

Gini: 测量纯度

例如， 深度为 2 的左侧节点基尼指数为：1 - (0 / 54)^2 - (49 / 54)^2 - (5 / 54)^2 = 0.68

3. 开始预测

决策边界

粗的垂直线代表根节点（深度为 0）的决定边界：花瓣长度为 2.45 厘米。
由于左侧区域是纯的（只有 Iris-Setosa），所以不能再进一步分裂。
然而，右边的区域是不纯的，所以深度为 1 的右边节点在花瓣宽度为 1.75 厘米处分裂（用虚线表示）。又由于max_depth设置为 2，决策树在那里停了下来。
如果将max_depth设置为 3，两个深度为 2 的节点，每个都将会添加另一个决策边界（用虚线表示）。

由于决策树内部结构清晰、可解释性强，并且可以通过可视化直观展示模型的决策过程，因此决策树属于白盒模型

1. 白盒模型
 - 白盒模型是指那些内部机制清晰、易于理解的机器学习模型。我们可以通过分析模型的结构和参数，了解其如何对输入数据进行处理并生成输出结果。

特点：
- 可解释性高：模型的行为可以通过数学公式或逻辑规则明确表达。
- 透明度强：可以直观地观察到特征与预测结果之间的关系。

- 易于调试：由于内部机制清晰，可以更容易地发现和修正模型中的问题。

常见白盒模型：
1. 线性回归：通过方程直接描述变量之间的线性关系。
 2. 逻辑回归：用于分类任务，输出概率，基于线性组合的sigmoid函数。
3. 决策树：以树状结构展示特征选择和数据分割的过程。
4. 线性支持向量机（SVM）：在低维空间中可解释性强。

适用场景：
 - 需要模型具有高度可解释性的领域，如金融、医疗等。
 - 数据集较小且模式较为简单的情况。

2. 黑盒模型
- 黑盒模型指的是内部机制不透明、难以理解的机器学习模型。我们只知道输入数据后得到预测结果，但不清楚模型在中间是如何处理这些数据的。

特点：
 - 可解释性低：复杂的内部结构使得难以用简单的规则或公式描述。
- 高灵活性：能够捕捉到复杂的数据模式和非线性关系。
- 强大的表现力：在许多实际应用中表现出色，尤其是深度学习模型。

常见黑盒模型：
1. 神经网络：由多个层次组成，每一层进行复杂的特征提取和变换。
2. 随机森林：集成大量决策树，整体行为难以通过单个树的行为解释。
3. 梯度提升机（如XGBoost、LightGBM*：内部涉及复杂优化过程和特征重要性。
4. 深度学习模型（如CNN、RNN、GAN）：结构复杂，难以直观理解其工作原理。

适用场景：
 - 需要处理高维、非线性数据的复杂任务。
- 对预测准确性要求高于可解释性的领域，如计算机视觉、自然语言处理等。

3. 介于两者之间的模型
在实际应用中，许多模型并不完全属于白盒或黑盒之列。例如：
- 部分可解释的模型：一些复杂的模型虽然内部机制不透明，但可以通过特征重要性分析、LIME（局部解释方法）等技术来提高其可解释性。
- 半透明模型：如某些树集成模型（如梯度提升树），可以通过特征重要性和单棵树的行为部分理解模型。

4. 估计分类概率

tree_clf.predict_proba([[5, 1.5]]) # 待测试的花，花瓣长 5 厘米，宽 1.5 厘米，相应的叶节点是深度为 2 的左节点。
# array([[ 0. , 0.90740741, 0.09259259]])
# Setosa 概率为 0%（0/54），Versicolor 为 90.7%（49/54），Virginica 为 9.3%（5/54）。
tree_clf.predict([[5, 1.5]]) # 预测所属类别
# array([1])
# Versicolor（类别 1）

5. CART 训练算法

通过最小成本函数找到单个特征k和阈值t[k]（例如，特征k=花瓣长度，阈值t[k]=花瓣长度≤2.45cm）将训练集分成两个子集（花瓣长度≤2.45cm、花瓣长度>2.45cm），然后继续使用相同递归式逻辑分割

如果找不到可以继续降低不纯度的分裂方法，CART 训练会停止

超参数能够控制子集的划分。常用的超参数例如：

min_samples_split（最小分割样本数）：
- 定义：指定内部节点（非叶子节点）所需的最小样本数量。当某个内部节点的样本数少于此值时，将停止进一步分裂该节点。
- 影响：通过限制内部节点的分裂条件来减少不必要的分支，防止模型过于复杂。增大此参数会限制树的深度和分支数量，减少模型复杂性，从而降低过拟合的风险。设置得过大可能导致模型过于简单，无法有效捕捉数据模式。

min_samples_leaf（最小叶子样本数）：
- 定义：指定叶子节点所需的最小样本数量。只有当某个分裂操作使得子节点的样本数均不少于此值时，才会继续分裂。
- 影响：则通过保证叶子节点的样本数足够多，避免因小样本导致的噪声影响。增大此参数会减少叶子节点的数量，防止模型对噪声或小数据集的过度拟合。然而，过大的值可能导致某些合理的分支无法保留。

min_weight_fraction_leaf（最小叶子权重比例）：

- 定义：指定叶子节点中样本权重占整体数据集权重的比例下限。确保每个叶子节点都具有足够的代表性和重要性。
- 影响：在加权模型（如处理类别不平衡问题时）中，此参数有助于防止某些类别的过度分割，保持模型的整体平衡。

max_leaf_nodes（最大叶子节点数）：
- 定义：指定树的最大叶子节点数量。达到此上限后，停止进一步的分裂。
- 影响：限制叶子节点的数量直接控制了树的复杂度。合理设置可以防止过拟合，但过大可能导致模型过于简单，无法有效学习数据特征。

在实际应用中，通常需要通过网格搜索（grid search）或随机搜索（random search）等方法来调优这些超参数，以找到最佳的组合，在训练集和验证集之间取得良好的平衡，防止过拟合。

补充：CART 算法是一种贪婪算法
贪婪算法：
- 贪婪算法也称贪心算法是指在每一步选择中都做出在当前状态下最好或最优（即最有利）的选择，希望通过一系列局部 optimal 的选择最终达到全局 optimal。

贪心算法在CART中的体现：
- 每一步选择当前最优的特征进行分裂，而不考虑整体情况。
- 通过不断的选择局部最优的特征，逐步构建整个决策树的结构。

优点与限制：
- 优点：高效、易于实现。
- 限制：可能无法达到全局最优解，但通常在实际应用中表现良好。
因为寻找最优树是一个np完全问题（类似旅行商问题），所以需要一个合理的解而不是最优解（在数量大的时候需要耗费巨大的计算才有可能得到）

6.计算复杂度

遍历决策树：O(log(m)/log(2))
训练决策树：O(n×m log(m))

补充：也可以通过设置 prespars=True 来加速一些情况下的模型训练：
prespars是 Scikit-Learn 中用于控制决策树模型（如 DecisionTreeClassifier、DecisionTreeRegressor）的一个参数，具体含义如下：
1. presort=True预处理特征排序：
- 当 presort=True 时，Scikit-Learn 会在构建决策树之前对每个节点处的特征进行排序。这有助于在选择最佳分割点时更高效地遍历特征值。
2. 影响与权衡：
- 优点：预排序可以加速某些内部计算步骤，尤其是当特征数量较少且需要频繁搜索最优分割点时。
- 缺点：预处理会增加内存使用和计算时间，特别是在大数据集上，可能导致性能下降。
3. 默认设置：
- 默认情况下，presort=False，以避免不必要的资源消耗，尤其是在内存有限的情况下。
4. 适用场景：
- 在特征数量较少且数据集较小时，可以考虑将 prespars=True 以加速模型训练。
- 当需要优化预测速度时，预排序可能有助于后续处理更快地找到分割点。

 

7. 基尼不纯度或是信息熵

生成决策树的两种选择：基尼（gini）指数或熵

熵：源于热力学中分子混乱程度的概念，当分子井然有序的时候，熵值接近于 0。后来逐渐扩展到了各个领域，其中包括香农的信息理论，这个理论被用于测算一段信息中的平均信息密度。
在机器学习中，熵经常被用作不纯度的衡量方式，当一个集合内只包含一类实例时， 称数据集的熵为 0。

基尼（gini）指数或熵的选用，大部分情况都没有多大的差别，区别在于，基尼指数计算稍微快，基尼指数会趋于在树的分支中将最多的类隔离出来，而熵指数趋向于产生略微平衡一些的决策树模型。

8. 正则化超参数

决策树几乎不对训练数据做任何假设（于此相反的是线性回归等模型，这类模型通常会假设数据是符合线性关系的）。

不添加约束的模型（也称为非参数模型）
特点：能够根据训练数据自我调整，根据数据的特性自由生长，使自身能够很好的拟合数据，但这种情况下，大多数会导致模型过拟合。
事先设定好参数的模型
特点：自由度是受限的，减少了过拟合的风险（但是增加了欠拟合的风险）。

对moons数据集（在第 5 章介绍过）进行训练生成的两个决策树模型

左侧的图形对应的决策树使用默认超参数生成（没有限制生长条件），右边的决策树模型设置为min_samples_leaf=4。很明显，左边的模型过拟合了，而右边的模型泛用性更好。 

9. 回归

- 在分类任务中，通常使用信息增益作为特征选择的标准。
- 在回归任务中，则使用均方误差（MSE）来确定最佳的分裂点。

from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor(max_depth=2)  # 最大深度为 2
tree_reg.fit(X, y)  # x, y是二次项数据集

例如，假设x[1] = 0.6，预测流程如下：从根开始遍历树，最终到达预测值等于 0.1106 的叶节点
预测值（value）是与该叶节点相关的 110 个训练实例（samples）的平均目标值。而这个预测结果在对应的 110 个实例上的均方误差（MSE）等于 0.0151
改变深度后，max_depth=3 由 2 变为 3

每个区域的预测值总是该区域中实例的平均目标值（CART 算法不再以最小化不纯度的方式分割训练集，而是以最小化 MSE 的方式分割）

10. 优点缺点

-优点：很容易理解和解释，易于使用且功能丰富而强大
-缺点：决策树很喜欢设定正交化的决策边界（所有边界都是和某一个轴相垂直的）。如图所示，决策树对训练数据的微小变化非常敏感，可能导致模型的泛化能力很差（解决方式：PCA 主成分分析（第八章）、随机森林（第七章））