树模型-01-ID3, C4.5, CART

ID3：基于信息增益（越大越好），信息增益衡量了特征带来的信息减少量，即通过选择特征 $A$，数据集的熵减少多少。
C4.5：基于信息增益比（越大越好），通过对比信息增益与特征自身的固有信息，避免偏向具有较多取值的特征。
CART：
- 回归树：最小化平方误差（MSE），通过减小预测误差来选择最佳分裂特征。
- 分类树：最小化基尼指数（越小越好），通过选择能最大程度提高数据集纯度的特征进行分裂。

先验知识

自信息

自信息(Self-Information)度量了某个事件发生的不确定性大小。
假设某个事件发生的概率为 $p$ ，那么该事件的自信息定义为：

$I(x) = - \log_2 p(x)$

熵(数据集 $S$ 自信息的期望)

熵(Entropy)度量了数据集中的不确定性（或者说是纯度）。
给定的一个数据集 $S$ ，其熵越高，数据集的不确定性越大。数据集 $S$ 的熵定义为：

$Entropy(S) = - \sum_{i=1}^{k} p_i \log_2 p_i$

其中，$p_i$ 是类别 $i$ 在数据集 $S$ 中的概率分布。

信息增益

信息增益(Information Gain)用于衡量，given某一特征 $A$ 带来的不确定性减少量。
假设特征 $A$ 有 $k$ 种不同的取值，根据特征 $A$ ，一定条件下的数据集 $S$ 可以分为 $k$ 个子集 ${S1,…,Sk}$ ，因此，given特征 $A$ 的数据集 $S$ 的信息熵(不同分裂情况下的期望熵)可以按照如下方式计算：

$Entropy_A(S)=\sum_{i=1}^{k} \frac{|S_i|}{|S|} \cdot Entropy(S_i)$

信息增益定义为数据集 $S$ 在选择特征 $A$ 后的熵变化量：

$Gain(S, A) = Entropy(S) - Entropy_A(S)$

信息增益的本质是通过计算特征 $A$ 分裂前后的熵差来度量特征 $A$ 对目标变量不确定性的减少程度。选择信息增益最大的特征作为决策树节点。

信息增益比

信息增益比(Gain Ratio)C4.5避免了ID3中由于某些特征取值过多导致信息增益较大而偏向这些特征的问题。C4.5选择信息增益比最大且具有较好“分散性”的特征进行分裂：

$GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}$

固有信息(Intrinsic Information)或分割信息(Split Information)表示了特征 $A$ 自身的分裂能力，即特征 $A$ 可能分裂成多少个子集。固有信息的计算方式如下：

$SplitInfo(S, A) = - \sum_{i=1}^{k} \frac{|S_i|}{|S|} \cdot \log_2 \frac{|S_i|}{|S|}$

该公式衡量了特征 $A$ 分裂数据集 $S$ 时的“均匀性”。特征 $A$ 取值越多，$SplitInfo(S, A)$ 越大。

平方误差MSE(回归树)——二叉树

回归问题中，CART算法的目标是最小化数据集的平方误差(MSE):

$MSE(S) = \frac{1}{|S|} \sum_{i=1}^{|S|} (y_i - \hat{y})^2 $$其中，$y_i$ 是样本 $i$ 的真实标签，$\hat{y}$ 是该样本预测的值。对于回归树来说，选择使得**样本预测误差最小的特征**作为分裂标准。 > 回归树不断拟合残差，直到拟合训练数据的误差平方和小于某个阈值时作为结束条件 ### 基尼指数(Gini Index)——二叉树分类问题中，CART算法使用基尼指数(Gini Index)来衡量数据集的不纯度。基尼指数越小，表示数据集的纯度越高。基尼指数定义如下：$

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

$$其中，$p_i$ 是类别 $i$ 在数据集 $S$ 中的概率分布。基尼指数通过计算每个类别的平方概率和，反映了类别之间的“混乱程度”。

示例

假设我们有以下一个简单的数据集，用于决策树构建：

天气	温度	湿度	风速	是否出去
晴天	热	高	强	否
晴天	热	高	弱	是
阴天	热	高	强	否
阴天	凉	高	强	是
小雨	凉	高	弱	是
小雨	凉	低	强	否
小雨	热	低	弱	是
阴天	凉	低	弱	是

目标是根据天气、温度、湿度和风速预测是否可以出去。