Task03 详读西瓜书 + 南瓜书第 4 章

1 决策树基本流程

• 概念：基于树结构来进行决策，体现人类在面临决策问题时一种很自然的处理机制

• 具备条件：

  1. 每个非叶节点表示一个特征属性测试
  2. 每个分支代表这个特征属性在某个值域上的输出
  3. 每个叶子节点存放一个类别
  4. 每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集

• 基本算法：

  输入： 训练集 $D=\{(x_1,y_1),(x_2,y_2),\cdot ,(x_m,y_m)\}$; 属性集 $A=a_1,a_2,\cdot ,a_d$

  过程：

函数 TreeGenerate($D$,$A$)

(1) 生成结点 node

(2) if $D$ 中样本全属于同一类别 $C$ then

(3) 将 node 标记为 $C$ 类叶节点; return

(4) end if

(5) if $A=\mathrm{\varnothing }$ OR $D$ 中样本在 $A$ 上取值相同 then

(6) 将 node 标记为叶结点，其类别标记为 $D$ 中样本数最多的类；return

(7) end if

(8) 从 $A$ 中选择最优化分属性 $a_{\ast }$;

(9) for $a_{\ast }$ 的每一个值 $a_{\ast }^v$ do

(10) 为 node 生成一个分支；令 $D_v$ 表示 $D$ 中在 $a_{\ast }$ 上取值为 $a_{\ast }^v$ 的样本子集;

(11) if $D_v$ 为空 then

(12) 将分支结点标记为叶结点，其类别标记为 $D$ 中样本最多的类; return

(13) else

(14) 以 TreeGenerate($D_v$, $A\mathrm{\setminus }\{a_{\ast }\}$) 为分支结点

(15) end if

(16) end for

输出： 以 node 为根结点的一棵决策树

• 决策树构造
  1. 当前结点包含的样本全部属于同一类，直接将该结点标记为叶结点，其类别设置该类
  2. 当属性集为空，或所有样本在所有属性上取值相同，无法进行划分，将该结点标记为叶结点，其类别设置为其父结点所含样本最多的类别
  3. 当前结点包含的样本集合为空，不能划分，将该结点标记为叶结点，其类别设置为其父结点所含样本最多的类别

2 划分选择

2.1 信息增益

• 信息熵：度量样本集合纯度最常用的一种指标
• 信息熵定义：

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,\dots ,|\mathcal{Y}|)$，则 $D$ 的信息熵表示为

$$\text{Ent}(D)=-\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k$$

$\text{Ent}(D)$ 值越小，则 $D$ 的纯度越高。

• 信息增益定义： 假定使用属性 $a$ 对样本集 $D$ 进行划分，产生了 $V$ 个分支节点，$v$ 表示其中第 $v$ 个分支节点，易知：分支节点包含的样本数越多，表示该分支节点的影响力越大，可以计算出划分后相比原始数据集 $D$ 获得的“信息增益”（information gain）。

$$\text{Gain}(D,\alpha )=\text{Ent}(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}\text{Ent}(D^v)$$

信息增益越大，使用属性 $a$ 划分样本集 $D$ 的效果越好。

• ID3 决策树学习算法是以信息增益为准则

2.2 增益率

• 作用：用于解决属性信息熵为 0，或远高于其他属性的信息熵问题
• 定义：

$$\text{Gain\_ratio}(D,\alpha )=\frac{\text{Gain}(D,\alpha )}{\text{IV}(\alpha )}$$

其中

$$\text{IV}(\alpha )=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$

当 $\alpha$ 属性的取值越多时，$\text{IV}(\alpha )$ 值越大

• C4.5 算法是以增益率为准则

2.3 基尼指数

• CART 决策树使用“基尼指数”（Gini index）来选择划分属性
• 作用：表示从样本集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此 $\text{Gini}(D)$ 越小越好
• 定义：

$$\begin{array}{rl}\text{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}\\ & =1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$

• 属性选择： 使用属性 $\alpha$ 划分后的基尼指数为：

$$\text{ Gini\_index }(D,\alpha )=\sum _{v=1}^V\frac{|D^v|}{|D|}\text{Gini}(D^v)$$

故选择基尼指数最小的划分属性。