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)$$

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