机器学习：决策树算法原理详解
决策树（Decision Tree）是机器学习中最直观、最易于理解的监督学习算法之一，兼具分类与回归能力。其'树形结构'与人类'if-then'决策逻辑高度一致，使得模型不仅在预测时效率极高，更具备天然的可解释性。从核心思想 → 数学原理 → 算法变种 → 应用场景的路径理解决策树，是掌握树模型（如随机森林、GBDT）乃至整个集成学习理论的基石。
通俗地说，决策树模仿了人类在面对复杂决策时逐步拆解问题的过程。例如，要判断'明天是否适合打网球'，我们可能会先看'天气'，若是晴天，再考虑'湿度'是否小于 70%；若是雨天，则看'风力'是否过大。这种层层递进的判断逻辑，正是决策树的核心。
上图是一个经典的分类决策树，每个内部节点代表对一个特征的判断，每个分支代表判断的结果，而每个叶子节点则代表最终的分类或回归输出。决策树的学习目标，就是基于已知数据，自动构建出这样一棵'最合适'的树，即确定在哪些节点用哪些特征做判断，以及判断的阈值如何设定。
ID3 树
ID3（Iterative Dichotomiser 3）是决策树最经典的算法之一，由 Ross Quinlan 于 1986 年提出。它采用信息增益（Information Gain）作为特征选择的标准，以递归地构建决策树。
熵（Entropy）
熵是信息论中度量系统不确定性的核心概念。一个系统越混乱、越不确定，其熵值就越高。在决策树中，我们用熵来衡量数据集的'不纯度'。
假设当前数据集 $D$ 中，样本属于第 $k$ 类的概率为 $p_k$，则数据集 $D$ 的熵定义为：
$$ H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k $$
其中 $K$ 为类别总数。当所有样本属于同一类别时（最'纯'），熵为 0；当样本均匀分布在所有类别时（最'乱'），熵取得最大值 $\log_2 K$。
信息熵与条件熵
信息熵 $H(D)$ 衡量了数据集 $D$ 本身的不确定性。而当我们引入某个特征 $A$ 对数据集进行划分后，我们可以计算划分后各子集的不确定性，并求其加权平均，这就是条件熵（Conditional Entropy）。
假设特征 $A$ 有 $V$ 个可能的取值 ${a_1, a_2, ..., a_V}$，根据 $A$ 的取值将 $D$ 划分为 $V$ 个子集 ${D_1, D_2, ..., D_V}$。条件熵 $H(D|A)$ 表示在已知特征 $A$ 的条件下，数据集 $D$ 的不确定性：
$$ H(D|A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} H(D_v) $$
其中 $|D_v|$ 是子集 $D_v$ 的样本数，$|D|$ 是总样本数。
信息增益（Information Gain）
信息增益衡量了引入特征 A 进行划分后，数据集不确定性减少的程度。它定义为数据集原始的信息熵与划分后的条件熵之差：
$$ Gain(D,A) = H(D) - H(D|A) $$
ID3 算法的核心：在构建树的每一个节点，算法会遍历所有可用特征，计算每个特征的信息增益，然后选择信息增益最大的那个特征作为当前节点的划分特征。因为信息增益越大，意味着使用该特征划分后，数据的'纯度'提升得越多。
举例说明
假设我们有一个关于'是否打网球'的数据集，特征包括天气（晴、雨、阴）、湿度（高、正常）等。标签为'是'或'否'。
- 首先，计算整个数据集的熵 $H(D)$。
- 然后，分别计算按'天气'划分后的条件熵 $H(D|天气)$，以及按'湿度'划分后的条件熵 $H(D|湿度)$。
- 接着，计算信息增益：$Gain(D,天气)=H(D)-H(D|天气)$，$Gain(D,湿度)=H(D)-H(D|湿度)$。
最后，比较哪个特征的信息增益更大，就选择哪个特征作为根节点。
