机器学习 - 决策树

1. 什么是决策树？

决策树是一种基础的分类与回归方法。顾名思义，它是一种树状结构的分类模型。

• 内部结点 (Internal Node): 代表对某个属性的“测试”(test)或“判断”。
• 分支 (Branch): 代表该测试的一种可能结果，即属性的某个取值。
• 叶结点 (Leaf Node): 代表一个“预测结果”或“类别标签”。

决策树示例：判断是否购买电脑

下面是一个经典的“是否购买电脑”决策树的例子（具体树结构未在PPT中完整画出，但概念清晰）： 训练数据集（示例）：

年龄	收入	学生	信用等级	是否买电脑
<=30	high	no	fair	no
<=30	high	no	excellent	no
31…40	high	no	fair	yes
>40	medium	no	fair	yes
>40	low	yes	fair	yes
>40	low	yes	excellent	no
31…40	low	yes	excellent	yes
<=30	medium	no	fair	no
<=30	low	yes	fair	yes
>40	medium	yes	fair	yes
<=30	medium	yes	excellent	yes
31…40	medium	no	excellent	yes
31…40	high	yes	fair	yes
>40	medium	no	excellent	no

决策树的工作流程

1. 学习过程 (建模阶段 - Tree Construction):

   • 通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）。
   • 所有训练样本最初都位于根节点。
   • 基于一定的指标（如信息增益、基尼系数等）选择最佳划分属性。
   • 根据选择的属性，递归地划分训练样本到子节点。
   • 剪枝 (Tree Pruning): 识别并删除可能由噪声或异常值导致的不太可靠的分支，以防止过拟合。

2. 预测过程:

   • 将测试示例从根结点开始。
   • 沿着划分属性所构成的“判定测试序列”下行。
   • 直到到达某个叶结点，该叶结点的预测结果即为测试示例的预测类别。

2. 决策树算法核心

基础算法思想 (贪心算法)

决策树的构建是一个递归过程，采用分治 (Divide and Conquer) 的思想，自顶向下进行。

1. 属性类型: 属性应当是离散的。如果遇到连续型数据，需要先进行离散化处理。
2. 开始: 所有训练样本都位于根节点。
3. 属性选择: 基于某种统计学指标或启发式方法（如信息增益、基尼系数）来选择当前节点的最优划分属性。
4. 划分: 根据选择的属性的不同取值，将当前节点的样本划分到新的子节点中。
5. 递归: 对每个子节点重复步骤 3 和 4，直到满足停止条件。

停止划分的条件

递归过程在以下任一情况发生时停止，当前节点成为叶节点：

1. 纯净节点: 当前节点内的所有样本都属于同一个类别。
2. 无剩余属性: 所有的属性都已经被用于之前的划分，没有属性可以继续划分。此时，该叶子节点的类别通常由该节点中样本最多的类别（多数投票）决定。
3. 无训练数据: 当前节点不包含任何样本（例如，某个属性值在父节点样本中不存在）。此时，类别通常由其父节点中样本最多的类别决定。

3. 决策树相关算法发展

• CLS (Concept Learning System): 由 Hunt, Marin 和 Stone 于1966年研制，是早期的决策树学习系统。
• ID3 (Iterative Dichotomiser 3): 由 Quinlan 于1979年提出，是决策树学习算法的典型，使用信息增益进行属性选择。
• ID4, ID5: 对ID3的改进，支持增量式学习。
• C4.5: Quinlan 于1993年对ID3的进一步发展，使用增益率克服ID3的缺点，能处理连续属性和缺失值，并进行剪枝。
• CART (Classification and Regression Trees): 由 Breiman 等人于1984年提出，可用于分类和回归。CART树是二叉树，分类时使用基尼指数，回归时使用平方误差。

4. CLS (Concept Learning System) 算法

CLS是许多决策树算法的基础。

CLS基本思想

1. 从一棵空决策树和包含所有训练样本的集合开始。
2. 选择某一属性作为测试属性（决策节点）。
3. 根据该属性的不同值，将训练样本分成相应的子集：
   • 如果子集为空，或子集中的样本属于同一个类，则该子集对应的分支成为叶节点。
   • 否则，该子集对应的节点为内部节点，需要为该子集选择一个新的测试属性进行递归划分。
4. 重复此过程，直到所有子集都为空或属于同一类。

CLS算法的问题

CLS算法没有明确规定如何选择“最佳”测试属性。实践表明，测试属性的选择顺序对最终生成的决策树的结构和性能有显著影响。不同的属性选择顺序可能导致复杂度不同、泛化能力也不同的决策树。

示例：膳食结构与缺钙调查

（PPT中通过一个膳食结构的例子说明，选择不同属性（如“鸡肉”或“牛奶”）作为第一个划分属性，会得到完全不同的决策树。）

5. ID3 算法：基于信息增益

ID3算法主要解决了CLS中属性选择的问题，它使用信息增益 (Information Gain) 作为选择测试属性的标准。

信息论基础

熵 (Entropy):

熵是度量随机变量不确定性的指标。熵越大，不确定性越大。对于一个有 $k$ 个可能取值的离散随机变量 $X$，其概率分布为 $P(X=x_i) = p_i$，则其熵定义为：

$$H(X) = - \sum_{i=1}^{k} p_i \log_2 p_i$$

其中，约定 $0 \log_2 0 = 0$。

例如，抛一枚均匀硬币，正反面概率各为0.5，熵为：

$H(X) = - (0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1$ bit.

当 $p=0.5$ 时，熵最大，不确定性最高。

条件熵 (Conditional Entropy):

给定随机变量 $X$ 的情况下，随机变量 $Y$ 的不确定性，记为 $H(Y|X)$：

$$H(Y|X) = \sum_{x \in X} P(x) H(Y|X=x) = - \sum_{x \in X} P(x) \sum_{y \in Y} P(y|x) \log_2 P(y|x)$$

也可以表示为：

$$H(Y|X) = - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log_2 P(y|x)$$

联合熵 (Joint Entropy): 两个随机变量 $X$ 和 $Y$ 同时发生的不确定性：

$$H(X,Y) = - \sum_{x \in X} \sum_{y \in Y} P(x,y) \log_2 P(x,y)$$

它们之间的关系： $H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$

互信息 (Mutual Information) / 信息增益 (Information Gain):

互信息衡量了两个变量之间的相关度，或者说，知道一个变量后另一个变量不确定性减少的程度。在决策树中，我们关心的是知道一个属性 $A$ 后，类别 $C$ 的不确定性减少了多少。这就是信息增益：

$$\text{Gain}(C, A) = I(C;A) = H(C) - H(C|A)$$

其中：

• $H(C)$ 是数据集 $D$ 中类别 $C$ 的熵（划分前）。
• $H(C|A)$ 是在已知属性 $A$ 的条件下，数据集 $D$ 中类别 $C$ 的条件熵（划分后）。属性 $A$ 有 $v$ 个可能的取值 $\{a_1, a_2, ..., a_v\}$，它将数据集 $D$ 划分为 $v$ 个子集 $D_1, D_2, ..., D_v$。 $$H(C|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} H(C_j)$$ 其中 $H(C_j)$ 是子集 $D_j$ 中类别 $C$ 的熵。

ID3算法选择使得信息增益最大的属性作为划分属性。

6. C4.5 算法：基于增益率

ID3算法有一个缺点：它倾向于选择具有较多取值的属性。因为取值越多的属性，越有可能将数据集划分为多个“纯”的子集，从而获得较高的信息增益。

C4.5算法通过使用增益率 (Gain Ratio) 来克服这个问题。增益率是对信息增益进行正则化。

分裂信息 (Split Information / Intrinsic Value): 属性 $A$ 的分裂信息定义为：

$$\text{SplitInfo}_A(D) = - \sum_{j=1}^{v} \frac{|D_j|}{|D|} \log_2\left(\frac{|D_j|}{|D|}\right)$$

其中 $D_j$ 是属性 $A$ 取第 $j$ 个值时的样本子集，$|D|$ 是总样本数。

如果一个属性的取值很多，且每个取值对应的样本数很少，$\text{SplitInfo}_A(D)$ 的值会比较大。

增益率 (Gain Ratio):

$$\text{GainRatio}(D,A) = \frac{\text{Gain}(D,A)}{\text{SplitInfo}_A(D)}$$

C4.5选择具有最大增益率的属性进行划分。

"收入"属性的增益率

假设“收入”属性将14个样本分为：low (4个), medium (6个), high (4个)。

$\text{Gain}(C, \text{收入}) \approx 0.029$ (前面已算)

$\text{SplitInfo}_{\text{收入}}(D) = -\left( \frac{4}{14}\log_2\frac{4}{14} + \frac{6}{14}\log_2\frac{6}{14} + \frac{4}{14}\log_2\frac{4}{14} \right) \approx 1.557$

(PPT中给出的值为0.926，这里根据收入的3个取值重新计算，PPT中可能是用了另一个例子或计算方式，请以PPT为准或重新核对数据分布)

如果按照PPT中 $\text{SplitInfo}_{\text{收入}}(D) = 0.926$:

$\text{GainRatio}(C, \text{收入}) = \frac{0.029}{0.926} \approx 0.031$

注意：C4.5通常会先计算所有属性的信息增益，然后只对那些信息增益高于平均值的属性计算增益率，以避免分裂信息很小（例如属性只有一个主要取值）导致增益率过大的问题。

7. CART 算法：基于基尼指数

CART (Classification and Regression Trees) 算法既可以用于分类也可以用于回归。CART生成的是二叉树。

基尼指数 (Gini Index) - 用于分类

基尼指数衡量了数据集 $D$ 的不纯度。假设有 $K$ 个类别，第 $k$ 个类别的概率为 $p_k$，则基尼指数定义为：

$$\text{Gini}(D) = \sum_{k=1}^{K} p_k (1-p_k) = 1 - \sum_{k=1}^{K} p_k^2$$

基尼指数越小，数据集的不纯度越低（越纯）。

对于给定的属性 $A$ 的某个二元划分（将数据集 $D$ 分为 $D_1$ 和 $D_2$），划分后的基尼指数为：

$$\text{Gini}_{\text{split}}(D, A) = \frac{|D_1|}{|D|} \text{Gini}(D_1) + \frac{|D_2|}{|D|} \text{Gini}(D_2)$$

CART选择使得划分后基尼指数最小的属性及其划分点。

"是否买电脑"的基尼指数

数据集 $D$：9个“yes”，5个“no”。

$\text{Gini}(D) = 1 - \left( \left(\frac{9}{14}\right)^2 + \left(\frac{5}{14}\right)^2 \right) = 1 - (0.413 + 0.128) = 1 - 0.541 = 0.459$

以属性“收入”的二元划分为例：

假设将“收入”划分为 {low} 和 {medium, high}。

• $D_1$ (收入=low): 4个样本 (1 yes, 3 no) $\text{Gini}(D_1) = 1 - ( (\frac{1}{4})^2 + (\frac{3}{4})^2 ) = 1 - (0.0625 + 0.5625) = 1 - 0.625 = 0.375$
• $D_2$ (收入=medium or high): 10个样本 (8 yes, 2 no) (PPT中是6 yes, 4 no，这里根据PPT的后续计算反推) 假设 $D_2$: 6 yes, 4 no $\text{Gini}(D_2) = 1 - ( (\frac{6}{10})^2 + (\frac{4}{10})^2 ) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48$

$\text{Gini}_{\text{split}}(D, \text{收入}_{\{\text{low}\}, \{\text{medium,high}\}}) = \frac{4}{14} \text{Gini}(D_1) + \frac{10}{14} \text{Gini}(D_2)$

$= \frac{4}{14}(0.375) + \frac{10}{14}(0.48) \approx 0.107 + 0.343 = 0.450$

(PPT中给出的值为0.450，但其 $D_1$ (收入=low) 和 $D_2$ (收入=medium or high) 的yes/no分布与表格不完全一致，这里按PPT的计算结果展示)

处理连续值属性 (ID3, C4.5, CART)

对于连续值属性 $A$：

1. 将 $A$ 的所有 $N$ 个观测值进行排序： $a_1, a_2, ..., a_N$。
2. 生成 $N-1$ 个可能的候选分裂点。每个分裂点是相邻两个值的平均值： $\frac{a_i + a_{i+1}}{2}$。
3. 对每个候选分裂点，计算其信息增益、增益率或基尼指数。
4. 选择最佳分裂点作为该连续属性的二元划分点。

CART 分类树生成算法

1. 输入： 训练数据集 $D$，停止计算条件。

2. 输出： CART分类树。

3. 从根节点开始，递归地对每个节点进行以下操作：

   a. 设当前节点数据集为 $D'$。对于 $D'$ 中的每个特征 $A$ 及其每个可能的二元切分点 $a$（对于离散属性，是 $A=a$ vs $A \neq a$；对于连续属性，是 $A \le a$ vs $A > a$），将 $D'$ 分为 $D'_1$ 和 $D'_2$。

   b. 计算该切分的基尼指数 $\text{Gini}_{\text{split}}(D', A, a)$。

   c. 在所有特征 $A$ 及所有可能的切分点 $a$ 中，选择基尼指数最小的特征和切分点作为最优划分。

   d. 根据最优划分，将数据集分配到两个子节点中。

   e. 对两个子节点递归调用步骤 a-d，直到满足停止条件（如节点样本数小于阈值，或基尼指数小于阈值，或树达到最大深度等）。

4. 生成CART树。

8. 从决策树中提取规则

决策树具有很好的可解释性，可以方便地转换为 IF-THEN 形式的规则：

• 从根节点到每个叶节点的每一条路径都对应一条规则。
• 路径上内部节点的属性测试构成了规则的 IF 部分（前提条件，通过 AND 连接）。
• 叶节点的类别是规则的 THEN 部分（结论）。

9. 回归树 (CART for Regression)

当目标变量 $y$ 是连续值时，可以使用回归树。

回归树模型

假设输入空间被划分为 $M$ 个单元（区域） $R_1, R_2, ..., R_M$，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$。回归树可以表示为：

$$f(x) = \sum_{m=1}^{M} c_m I(x \in R_m)$$

其中 $I(\cdot)$ 是指示函数。

划分准则：平方误差最小化

我们使用平方误差 $\sum (y_i - f(x_i))^2$ 来衡量预测误差。 对于一个固定的区域 $R_m$，最优的 $c_m$ 是该区域内所有样本 $y_i$ 的均值：

$$\hat{c}_m = \text{ave}(y_i | x_i \in R_m)$$

启发式划分方法： 选择第 $j$ 个变量 $x^{(j)}$ 和它取的值 $s$，作为切分变量和切分点，定义两个区域：

$R_1(j,s) = \{ x | x^{(j)} \le s \}$ 和 $R_2(j,s) = \{ x | x^{(j)} > s \}$

寻找最优的切分变量 $j$ 和切分点 $s$，使得下式最小：

$$\min_{j,s} \left[ \min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right]$$

其中 $c_1 = \text{ave}(y_i | x_i \in R_1(j,s))$ 和 $c_2 = \text{ave}(y_i | x_i \in R_2(j,s))$。

回归树生成算法 (最小二乘回归树)

1. 输入： 训练数据集 $D = \{(x_1, y_1), ..., (x_N, y_N)\}$。

2. 输出： 回归树 $f(x)$。

3. 递归地将每个区域划分为两个子区域并决定每个子区域上的输出值：

   a. 选择最优切分变量 $j$ 与切分点 $s$，求解：

   $$\min_{j,s} \left[ \sum_{x_i \in R_1(j,s)} (y_i - \hat{c}_1)^2 + \sum_{x_i \in R_2(j,s)} (y_i - \hat{c}_2)^2 \right]$$

   遍历所有变量 $j$，对固定的 $j$ 扫描所有可能的切分点 $s$，找到使上式最小的 $(j,s)$ 对。

   b. 用选定的 $(j,s)$ 对划分区域并决定相应的输出值：

   $$R_1(j,s) = \{x | x^{(j)} \le s\}, R_2(j,s) = \{x | x^{(j)} > s\}$$

   $\hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i$, for $m=1,2$

   c. 继续对两个子区域调用步骤 a、b，直至满足停止条件（如节点样本数小于阈值，或区域内平方误差减小量小于阈值）。 d. 将输入空间划分为 $M$ 个区域 $R_1, ..., R_M$，生成决策树：

   $$f(x) = \sum_{m=1}^{M} \hat{c}_m I(x \in R_m)$$

10. 模型评估

• 划分数据集： 通常将数据集划分为训练集、验证集（可选，用于调参和剪枝）和测试集。
• 交叉验证 (Cross-Validation): 例如，$K$-折交叉验证。
  1. 将数据集分成 $K$ 个互不相交的子集（折）。
  2. 进行 $K$ 次训练和测试：每次选择 $K-1$ 个子集用于训练，剩下的1个子集用于测试。
  3. 最终性能是 $K$ 次测试结果的平均值。

课后作业

答案（仅供参考）

总样本数 $|D| = 5$ 活动“是”的样本数 = 3 活动“否”的样本数 = 2

计算整个数据集D的熵 ($Entropy(D)$)

$Entropy(D) = - \left( P(\text{是}) \cdot \log_2(P(\text{是})) + P(\text{否}) \cdot \log_2(P(\text{否})) \right)$

$P(\text{是}) = \frac{3}{5}$

$P(\text{否}) = \frac{2}{5}$

$Entropy(D) = - \left( \frac{3}{5} \cdot \log_2\left(\frac{3}{5}\right) + \frac{2}{5} \cdot \log_2\left(\frac{2}{5}\right) \right)$ $Entropy(D) = - \left( 0.6 \cdot (-0.736965594) + 0.4 \cdot (-1.321928095) \right)$

$Entropy(D) = - \left( -0.4421793564 - 0.528771238 \right)$ $Entropy(D) = - ( -0.9709505944 )$ $Entropy(D) \approx 0.971$

计算属性“天气”的信息增益 ($Gain(D, \text{天气})$)

属性“天气”有三个取值：晴、多云、雨。

• 天气 = 晴 ($D_{\text{晴}}$): 2个样本 (否, 否)
  • $P(\text{是}) = \frac{0}{2} = 0$
  • $P(\text{否}) = \frac{2}{2} = 1$
  • $Entropy(D_{\text{晴}}) = - \left( 0 \cdot \log_2(0) + 1 \cdot \log_2(1) \right) = 0$ (约定 $0 \cdot \log_2(0) = 0$)
• 天气 = 多云 ($D_{\text{多云}}$): 1个样本 (是)
  • $P(\text{是}) = \frac{1}{1} = 1$
  • $P(\text{否}) = \frac{0}{1} = 0$
  • $Entropy(D_{\text{多云}}) = - \left( 1 \cdot \log_2(1) + 0 \cdot \log_2(0) \right) = 0$
• 天气 = 雨 ($D_{\text{雨}}$): 2个样本 (是, 是)
  • $P(\text{是}) = \frac{2}{2} = 1$
  • $P(\text{否}) = \frac{0}{2} = 0$
  • $Entropy(D_{\text{雨}}) = - \left( 1 \cdot \log_2(1) + 0 \cdot \log_2(0) \right) = 0$

计算按“天气”划分后的条件熵:

$Entropy(D|\text{天气}) = \frac{|D_{\text{晴}}|}{|D|} \cdot Entropy(D_{\text{晴}}) + \frac{|D_{\text{多云}}|}{|D|} \cdot Entropy(D_{\text{多云}}) + \frac{|D_{\text{雨}}|}{|D|} \cdot Entropy(D_{\text{雨}})$

$Entropy(D|\text{天气}) = \frac{2}{5} \cdot 0 + \frac{1}{5} \cdot 0 + \frac{2}{5} \cdot 0$

$Entropy(D|\text{天气}) = 0$

信息增益 $Gain(D, \text{天气})$:

$Gain(D, \text{天气}) = Entropy(D) - Entropy(D|\text{天气})$

$Gain(D, \text{天气}) = 0.971 - 0$

$Gain(D, \text{天气}) = 0.971$

计算属性“湿度”的信息增益 ($Gain(D, \text{湿度})$)

属性“湿度”有两个取值：高、中。

• 湿度 = 高 ($D_{\text{高}}$): 3个样本 (否, 否, 是)
  • $P(\text{是}) = \frac{1}{3}$
  • $P(\text{否}) = \frac{2}{3}$
  • $Entropy(D_{\text{高}}) = - \left( \frac{1}{3} \cdot \log_2\left(\frac{1}{3}\right) + \frac{2}{3} \cdot \log_2\left(\frac{2}{3}\right) \right)$
  • $Entropy(D_{\text{高}}) = - \left( \frac{1}{3} \cdot (-1.584962501) + \frac{2}{3} \cdot (-0.584962501) \right)$
  • $Entropy(D_{\text{高}}) = - \left( -0.5283208337 - 0.3899750007 \right)$
  • $Entropy(D_{\text{高}}) = - ( -0.9182958344 )$
  • $Entropy(D_{\text{高}}) \approx 0.918$
• 湿度 = 中 ($D_{\text{中}}$): 2个样本 (是, 是)
  • $P(\text{是}) = \frac{2}{2} = 1$
  • $P(\text{否}) = \frac{0}{2} = 0$
  • $Entropy(D_{\text{中}}) = - \left( 1 \cdot \log_2(1) + 0 \cdot \log_2(0) \right) = 0$

计算按“湿度”划分后的条件熵:

$Entropy(D|\text{湿度}) = \frac{|D_{\text{高}}|}{|D|} \cdot Entropy(D_{\text{高}}) + \frac{|D_{\text{中}}|}{|D|} \cdot Entropy(D_{\text{中}})$ $Entropy(D|\text{湿度}) = \frac{3}{5} \cdot 0.918 + \frac{2}{5} \cdot 0$

$Entropy(D|\text{湿度}) = 0.6 \cdot 0.918 + 0$ $Entropy(D|\text{湿度}) \approx 0.551$

信息增益 $Gain(D, \text{湿度})$:

$Gain(D, \text{湿度}) = Entropy(D) - Entropy(D|\text{湿度})$

$Gain(D, \text{湿度}) = 0.971 - 0.551$

$Gain(D, \text{湿度}) = 0.420$

比较两个属性的信息增益：

• $Gain(D, \text{天气}) = 0.971$
• $Gain(D, \text{湿度}) = 0.420$

由于 $Gain(D, \text{天气}) > Gain(D, \text{湿度})$，属性“天气”的信息增益更大。因此，根据ID3算法，属性“天气”更适合作为根节点。