参考
决策树原理详解
机器学习算法系列（十七）-决策树学习算法

决策树

决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系，以树形数据结构来展示决策规则和分类结果。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

基本思想是通过一系列条件判断将数据从根节点逐步划分到叶子节点。每个节点代表一个特征或属性，每个分支代表一个特征的取值。决策树通过不断选择特征来“分裂”数据集，使得每个子集的纯度（或不纯度）逐渐提高。

选择当前条件下的最优属性划分

信息增益（Information Gain）

信息增益是决策树算法（如 ID3）中的关键指标，用于衡量一个特征对样本集合的分类能力。其计算公式如下：

$IG(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \cdot Entropy(S_v)$

其中：

  • $IG(S, A)$ 是特征 $A$ 的信息增益。
  • $S$ 是当前的数据集，$A$ 是某个特征，$Values(A)$ 是特征 $A$ 的所有可能取值。
  • $S_v$ 是在特征 $A$ 取值为 $v$ 时的数据子集。
  • $Entropy(S)$ 是数据集 $S$ 的信息熵。

随机变量的不确定性（也就是混乱程度）。

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

增益比（Gain Ratio）

信息增益虽然在理论上可以找到最优的划分属性，但在某些情况下会存在问题。信息增益比较偏好可取值较多的属性，比如我们的样本有一个属性叫序号，每一个样本都具有一个单独的序号，因此使用序号划分后，每个子结点只有一个样本，熵为0。这样的话信息增益最大，算法就会以此属性作为最优划分属性。这显然与我们的意愿不同。因此引申出了增益比的思想。
可以这么说，增益比就是为了矫正信息增益偏好的问题。为了使算法不偏向可取值较多的属性。

决策树的增益比（Gain Ratio） 是一种用于评估特征选择质量的度量，主要用于改进经典的 信息增益（Information Gain）方法。信息增益在构建决策树时用于选择最优的划分特征，但它有一个缺点：偏向选择取值数目较多的特征。增益比通过引入一个归一化步骤来解决这个问题，使得特征选择更加公平和合理。

信息增益是决策树算法（如 ID3）中的关键指标，用于衡量一个特征对样本集合的分类能力。

增益比通过对信息增益进行归一化，来避免偏向取值较多的特征。它的计算方式是：

$GR(S, A) = \frac{IG(S, A)}{SplitInfo(S, A)}$

其中：

  • $IG(S, A)$ 是特征 $A$ 的信息增益。
  • $SplitInfo(S, A)$ 是特征 $A$ 的分割信息，衡量特征 $A$ 对数据集 $S$ 的划分复杂度。它的计算公式为：

$SplitInfo(S, A) = - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \cdot \log_2 \left( \frac{|S_v|}{|S|} \right)$

基尼指数（Gini Index）

基尼指数衡量一个数据集的纯度（或不纯度）。如果数据集的基尼指数越小，意味着数据集中的样本越趋向于属于同一类别。基尼指数的值范围是 $[0, 1]$，其中：

  • 0 表示完全纯净的节点（即所有样本属于同一类别）。
  • 1 表示最大的不纯度（即每个样本的类别完全随机）。

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

$$
Gini(S) = 1 - \sum_{i=1}^{C} p_i^2
$$

其中：

  • $Gini(S)$ 是数据集 $S$ 的基尼指数。
  • $C$ 是数据集中类别的数量。
  • $p_i$ 是类别 $i$ 在数据集 $S$ 中的概率（即类别 $i$ 样本数占数据集总样本数的比例）。

基尼指数用于决策树构建

在决策树的构建过程中，基尼指数常用于评估每个特征的划分效果。具体步骤如下：

  • 对于每个特征的每个取值，我们计算该特征划分后的子集的基尼指数。
  • 然后，我们计算加权平均基尼指数（加权平均是基于每个子集的样本数），选择基尼指数最小的特征作为分裂点。

这种方法用于 CART（Classification and Regression Trees） 算法中的分类任务。

决策树回归（Decision Tree Regression）

决策树回归是基于决策树的一种回归方法，与分类决策树的原理类似，区别在于目标变量是连续的而不是离散的类别。决策树回归通过递归地分割数据集，并在每个叶子节点预测目标值的平均值，最终实现对连续目标变量的预测。

决策树回归的基本原理

  • 递归划分：决策树通过在特征空间中选择最佳分裂点，将数据集分割成若干个子集。
  • 叶子节点输出：每个叶子节点的输出值是该区域内样本目标值的均值。
  • 目标：预测目标变量的连续值。

决策树回归的损失函数

决策树回归通常使用 均方误差（MSE） 来评估每个分裂点的好坏。MSE 的公式如下：

$$
MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2
$$

其中：

  • $y_i$ 是第 $i$ 个样本的真实值。
  • $\hat{y}_i$ 是第 $i$ 个样本的预测值，通常是该节点所有样本的平均值。

决策树回归算法步骤

  1. 选择最佳分裂点：选择一个特征和该特征的某个取值作为分裂点，划分数据集，使得每个子集内目标变量的均值最接近该子集的所有样本目标值。
  2. 递归划分：对每个子集继续递归地选择最佳分裂点，直到满足某个停止条件（如树的最大深度、叶子节点样本数目最小等）。
  3. 预测：对于一个新的样本，决策树会根据它的特征值找到它所在的叶子节点，并输出该节点的预测值。

优缺点

优点：

  • 非线性建模：决策树能够处理非线性关系，而不像线性回归只适用于线性数据。
  • 无需特征缩放：决策树不依赖于特征的缩放或归一化。
  • 易于理解和解释：决策树的结构简单，可以清晰地展示特征与输出之间的关系。

缺点：

  • 过拟合：决策树容易过拟合，尤其是在数据中存在噪声时。
  • 对噪声敏感：噪声可能导致树结构过于复杂，影响泛化能力。
  • 局部最优：决策树每次分裂选择局部最优的特征，容易陷入局部最优，影响性能。