决策树（分类决策树）

分类决策树是一种基于树状结构的监督学习模型，主要用于对数据进行分类任务。它通过一系列规则（即树的分支）对输入数据进行递归划分，最终达到预测输出类别（即树的叶节点）的目的。分类决策树以其直观易懂、解释性强的特点被广泛应用在各种领域，如医学诊断、金融风险评估、市场营销策略制定等。下面我们对分类决策树进行更详细描述：

基本原理

分类决策树模拟人类在面对问题时进行逻辑判断和决策的过程。它通过一系列问题（基于数据的特征）逐步缩小决策范围，直至达到一个明确的结论。在数据科学和机器学习的语境下，这个过程表现为：

• 根节点：代表整个数据集，即所有待分类的样本集合。

• 内部节点（决策节点）：每个内部节点表示一个特征测试条件。根据该特征的不同取值，数据被分割成若干子集，并沿着树的分支流向对应的子节点。

• 分支：连接内部节点和子节点的连线，代表特征测试条件的结果导向。

• 叶节点（终端节点）：树的最底层节点，表示分类结果。每个叶节点对应一个类别标签，代表经过从根到该节点路径上的特征测试后，数据样本被归属于该类别的概率或确定性标签。

构建过程

构建分类决策树通常包括以下步骤：

特征选择

在每个内部节点，选择一个最优特征作为划分标准。最优特征通常是指根据这个特征划分后信息增益、基尼指数或类似指标的特征最优的特征，这些指标反映了根据该特征划分数据集后纯度的提升程度。

纯度：对于包含多个类别的数据集，如果类别数越多，则认为这个数据集越不纯。反之则越纯。纯度越高，分类效果越好。

信息增益

首先了解一下信息熵

信息熵

在机器学习中，信息熵（Entropy）是一个核心概念，用于量化随机变量或数据集的“不确定性”或“混乱度”。它衡量了一个随机变量可能取值的期望信息量。具体来说，信息熵越大，代表随机变量的不确定性越高，或者说数据的混乱程度越高，越混乱，证明其中所含有的标签越多，自然也就越混乱。

举个例子：在一个书架上，每本书是一个样本，当我们排列这些书时，如果它们同样高，那么排出来是美观的，如果高度都是参差不齐的，那么排出来就很乱。这就是熵低与高的区别。
熵高 -> 不一样的多 熵低 -> 一样的多

在信息论中，熵被用来衡量一个随机变量出现的期望值。它代表了在被接收之前，信号传输过程中损失的信息量，又被称为信息熵。对于离散随机变量 $X$，其信息熵 $H(X)$ 定义为：

$$H(X)=-\sum _{x\in X}p(x){\log }_{2}p(x)$$

其中，$p(x)$ 是随机变量 $X$ 取值为 $x$ 的概率。这个公式计算了所有可能取值的概率与其对应的信息量（即概率的负对数）的期望值。

信息增益的计算

计算信息增益的步骤如下：

1. 计算父节点的熵：首先，需要计算整个数据集的熵，这代表了数据集的不确定性。父节点的熵的计算公式为：
   $$\text{Entropy}(S)=-\sum _{i=1}^{n}p(i){\log }_{2}p(i)$$
   其中，S代表数据集，p(i)代表数据集中第i个类别出现的概率。

2. 计算子节点的熵以及加权平均：然后，对于每个特征，计算其划分数据集后得到的子节点的熵。这涉及到对数据集按照每个特征的不同取值进行划分，并计算每个子集的熵。

子节点熵的加权平均的公式如下：

$$\text{Weighted Average of Child Entropies}=\sum _{j=1}^m\frac{|S_j|}{|S|}\times \text{Entropy}(S_j)$$

其中：

• ( S ) 是父节点所代表的数据集。
• ( S_j ) 是根据某个特征的第 ( j ) 个取值划分得到的子节点所代表的数据子集。
• ( m ) 是该特征的不同取值的数量，也就是子节点的数量。
• ( |S| ) 和 ( |S_j| ) 分别表示父节点和子节点数据集的大小（即样本数量）。
• ( \text{Entropy}(S_j) ) 是子节点 ( S_j ) 的熵。

3. 计算信息增益：最后，用父节点的熵减去子节点熵的加权平均，得到该特征的信息增益。
   $$\text{Information Gain}(S,\text{feature})=\text{Entropy}(S)-\text{Weighted Average of Child Entropies}$$

通过计算每个特征的信息增益，可以选择信息增益最大的特征作为当前节点的划分标准。这样，每次划分都能最大程度地减少数据的不确定性，从而提高分类模型的性能。

信息增益率（Information Gain Ratio）是信息增益的一个改进版本，它考虑了特征取值数量的影响，以避免选择取值较多的特征(比如读取数据时把id也读取了)。信息增益率的计算公式为：
$$\text{Information Gain Ratio}=\frac{\text{Information Gain}}{\text{Intrinsic Value of Feature}}$$

基尼指数

基尼指数（Gini Index）在机器学习和数据挖掘中，是一个用于衡量数据集合纯度的指标。与熵相似，基尼指数越小，表示集合的纯度越高。在构建决策树时，基尼指数被用来选择划分数据集的最优特征，以便将数据集划分为更纯的子集。

基尼指数的计算公式如下：

$$\text{Gini Index}(S)=1-\sum _{i=1}^m{p}_i^2$$

其中：

• (S) 是要计算基尼指数的数据集。
• (m) 是数据集中类别的数量。
• (p_i) 是数据集中第 (i) 个类别出现的概率。

这个公式衡量的是从数据集中随机选择一个样本，然后错误地将其分类到其他类别的概率。当数据集完全属于一个类别时（即纯度最高），基尼指数达到最小值0；当数据集中的类别分布均匀时，基尼指数达到最大值(1 - \frac{1}{m})。

属性的基尼指数它用于评估按照某个属性（或特征）的不同取值划分数据集后，所得子集的纯度和不确定性。基尼指数越小，表示按照该属性划分后的子集纯度越高。

计算属性的基尼指数的基本步骤如下：

1. 确定数据集：首先，确定要计算基尼指数的数据集，以及用于划分的属性。

2. 划分数据集：根据属性的不同取值，将数据集划分为多个子集（或称为子节点）。

3. 计算每个子集的基尼指数：对于每个子集，计算其基尼指数。基尼指数的计算公式为：

   $$\text{Gini Index}(S)=1-\sum _{i=1}^m{p}_i^2$$

   其中，(S) 是子集，(m) 是子集中类别的数量，(p_i) 是子集中第 (i) 个类别出现的概率。

4. 计算加权基尼指数：由于不同子集的大小（即样本数量）可能不同，因此需要计算加权基尼指数，以考虑不同子集对数据集整体纯度的影响。加权基尼指数是每个子集的基尼指数与其样本数量占数据集总样本数量的比例的乘积之和。

   $$\text{Weighted Gini Index}=\sum _{j=1}^n\frac{|S_j|}{|S|}\times \text{Gini Index}(S_j)$$

   其中，(S_j) 是根据属性划分得到的第 (j) 个子集，(n) 是子集的数量，(|S_j|) 是子集 (S_j) 的样本数量，(|S|) 是数据集的总样本数量。

5. 选择最优属性：比较不同属性的加权基尼指数，选择使得加权基尼指数最小的属性作为划分标准。这样，每次划分都能使得数据集的纯度得到最大提升。

属性的基尼指数在决策树构建过程中起着关键作用，它帮助我们选择能够最大程度提升数据集纯度的属性作为划分依据，从而构建出性能更优的分类模型。

决策树生长

选定我们要分类的特征后，就可以开始构建决策树。决策树的生长过程就是从根节点开始，递归地对数据集进行划分，生成一系列的内部节点和叶节点。

基于选定的最优特征及其阈值（对于连续特征[回归决策树（解决回归问题）]）或类别（对于离散特征的普通决策树），将数据集划分为多个子集，并为每个子集生成新的节点。这一过程递归地在每个子节点上重复，直到满足停止条件为止。常见的停止条件包括：

节点包含的样本数小于预设阈值：当节点内样本数量过少时，继续划分可能带来过拟合风险，此时停止生长。
所有样本属于同一类别：该节点无需再划分，其类别已经一致。
没有更多特征可供划分：所有特征已用于划分，或剩余特征无法有效提高模型性能。
达到预设的最大深度或节点数：防止过深的树导致模型过于复杂，降低泛化能力。

决策树剪枝

生长得到的原始决策树可能存在过拟合现象，即对训练数据拟合得过于复杂，不利于泛化到未知数据。剪枝旨在简化树结构，提高模型的泛化能力。常见的剪枝方法包括：

预剪枝：在生长过程中提前终止树的生长，如设定最大深度、最小样本数等阈值。
后剪枝：先生成完整的决策树，然后自底向上考察各内部节点，若将其替换为叶节点能带来整体性能的提升（如根据验证集计算的精度提高），则进行剪枝。

应用与优势

分类决策树具有以下优点：

易于理解和解释：决策树的结构清晰，决策规则直观，便于非专业人士理解模型的决策逻辑。
无需数据预处理：对于缺失值和非数值型数据有较好的适应性，通常不需要进行复杂的预处理。
可处理多输出问题：通过构建多棵树或扩展单棵树的结构，可以处理多类别或多输出的任务。
支持并行计算：在某些实现中，决策树的构建过程可以并行化，加速训练速度。