决策树

什么是决策树？

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

构造过程

递归查找，当遇到三种情况时返回：

• 节点包含的样本同属一个类别，标记叶节点，设为对应类别
• 属性集为空，或再各属性上的取值相同，无法划分，标记叶节点，设为样本数量最多的类别
• 包含的样本集合为空，不能划分，该点标记为叶节点，设为父节点中所含样本最多的类别

三种算法

决策树依据不同的属性划分算法，得出不同的分支结构，算法目标是让各子节点尽可能地纯（这样分支少，耗时短），依据不同的量化纯度的方法，可划分为三种常见算法：

ID3

信息熵

度量样本结合纯度的常用指标，假定当前样本集合D中第k类样本所占比例为$p_k$ ，则集合样本D信息熵定义为：

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

其中 $|y|$ 代表类别的总数，$lo{g}_2$ 是信息论的标准形式（信息论中熵的单位是比特），取负号是因为要确保结果为 非负数

ID3算法就是要计算分支前后的熵差，选择信息增益最大的特征作为分支节点

Note

为什么熵值如此定义？

式子中 $p_k$ 作为事件发生概率，$lo{g}_2{p}_k$ 表示当遇到这个事件，要用多少比特位来描述其不确定性，所有的事件加和，可以看作是所有可能性下需要用多少比特位来衡量系统的不确定性

假设产生了V个节点，当节点包含的样本越多，表示其影响力越大，计算出划分后相对原始数据集D获得的信息增益(information gain)如下：

$$\text{Gain}(D,A)=\mathrm{Ent}(D)-\sum _v\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$$

表示对于原始D的熵值，减去 选择某种方法划分的结果 的每个熵值的加权平均，得到信息增益，选择最大的那一种分支的特征。

Note

为什么加权平均？

熵值的定义里只是计算这个集合的熵值，而无法反映不同集合数量大小对整个系统熵值的影响，所以要先做一个数量上的占比计算，来考虑每个子集合对整体的影响

C4.5

解决连续值和属性缺失问题

连续值与缺失值处理

连续值

连续值属性需要离散化处理，常用的方法是二分，将样本集分为 $\le t$ 和 $>t$ 的值

1. 将 属性 $\alpha$ 所有取值按升序排列，所有相邻属性的均值($\frac{{\alpha }_i+{\alpha }_{i+1}}{2})$作为候选划分点(n-1个， n为在样本D中 $\alpha$ 的取值数目)
2. 当作离散值，分别计算每个划分点划分集合D后的信息增益
3. 选择最大信息增益的划分点作为最优划分点

缺失值

解决属性缺失需要解决两个问题，即：

• 如果属性中有些数值缺失了，如何进行划分属性的选择？
• 如果可以划分，那么对于缺失该属性值的样本，又要如何进行划分？

定义公式如下：

$$\rho =\frac{{\sum }_{x\in \tilde{D}}{w}_x}{{\sum }_{x\in D}{w}_x},$$ $${\tilde{p}}_k=\frac{{\sum }_{x\in {\tilde{D}}_k}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x},(1\le k\le |\mathcal{Y}|),$$ $${\tilde{r}}_v=\frac{{\sum }_{x\in {\tilde{D}}_v}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x},(1\le v\le V).$$

其中$\tilde{D}$ 表示缺失$D$中没有缺失样本的子集，可以仅根据$\tilde{D}$来判断属性的优劣，直观看来，$\rho$ 表示无缺失值样本所占的比例，${\tilde{p}}_k$ 表示无缺失值样本在第k类中所占的比例，${\tilde{r}}_v$表示无缺失值样本中在属性 $\alpha$ 上取值为 ${\alpha }^v$ 的样本所占的比例，将这些比例与信息增益式子相结合，可以得到推广式：

$$\text{Gain}(D,a)=\rho \times \text{Gain}(\tilde{D},a)$$ $$=\rho \times \left(\text{Ent}(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_v\text{Ent}({\tilde{D}}^v)\right),\text{\hspace{1em}(4.12)}$$

其中由式 (4.1)，有：

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

这个推广式子适用于缺失与非缺失。

对于第二个问题则规定：

• 若x对划分属性的取值已知，则划分进与其取值对应的节点，保持样本权重 $w_x$
• 若未知，则划分进所有的子节点，并调整样本权重$r_v\cdot w_x$ ，直观来看就是让同一个样本以不同概率划入到不同的子节点

除此之外，ID3算法还偏向于将划分种类数量多的属性 如果存在一个标识可以将每个样本自己归为一个分支，这样信息熵就是0，但是对分类并无实际作用（无用解）

Link to original

增益率

在C4.5中使用了“增益率(gain ratio)“来选择划分属性:

1. 使用ID3算法计算信息增益高于平均水平的候选属性
2. 接着计算这些属性的增益率
3. 选择增益率最高的属性

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

其中：

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

可以看到当 $\alpha$ 划分结果的取值越多时，$\text{IV}(a)$ 的值越大，避免了无用解的问题，这是一种启发式的查找，利于快速找到优解

CART

采用 基尼指数(Gini) 来选择划分属性，基尼指数是反映样本集D中抽取两个样本，其类别标志不一致的概率，直观来看 Gini(D)越小越好，基尼指数定义如下：

$$1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2$$

• $D$：当前数据集
• $\mathcal{Y}$：类别集合
• $p_k$：样本属于类别$k$的概率

划分的计算指标规定如下：

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

取基尼指数最小的属性进行划分

剪枝

决策树通过剪枝(pruning)来应对过拟合，其策略如下两种：

• 预剪枝(prepruning) 在构造过程中先评估，再考虑是否分支
• 后剪枝(post-pruning) 在构造好一颗完整的决策树中，自底向上，评估分支的必要性

评估指的是性能度量，即决策树的泛化性能。可以使用测试来近似学习器的泛化性能

• 对于预剪枝，对一个系欸但考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，如果分支对性能没有提升，那么不分支（剪枝）
• 后剪枝表示构造好一颗完整的决策树后，从最下面的结点开始考虑节点分支对模型的性能是否有提升，若无，则剪枝，即将点标记为叶子节点，类别标记为样本最多的类别

预剪枝

完整树

后剪枝

其中:

• 预剪枝使得决策树大多分支被剪掉，大大降低了训练时间开销，降低过拟合风险
• 但是由于其贪心本质，分支的展开被阻止，带来了欠拟合的风险
• 后剪枝保留了更多分支，性能往往更优
• 自底向上遍历了所有节点来计算性能变化，训练时间开销更大

连续值与缺失值处理

连续值

连续值属性需要离散化处理，常用的方法是二分，将样本集分为 $\le t$ 和 $>t$ 的值

1. 将 属性 $\alpha$ 所有取值按升序排列，所有相邻属性的均值($\frac{{\alpha }_i+{\alpha }_{i+1}}{2})$作为候选划分点(n-1个， n为在样本D中 $\alpha$ 的取值数目)
2. 当作离散值，分别计算每个划分点划分集合D后的信息增益
3. 选择最大信息增益的划分点作为最优划分点

缺失值

解决属性缺失需要解决两个问题，即：

• 如果属性中有些数值缺失了，如何进行划分属性的选择？
• 如果可以划分，那么对于缺失该属性值的样本，又要如何进行划分？

定义公式如下：

$$\rho =\frac{{\sum }_{x\in \tilde{D}}{w}_x}{{\sum }_{x\in D}{w}_x},$$ $${\tilde{p}}_k=\frac{{\sum }_{x\in {\tilde{D}}_k}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x},(1\le k\le |\mathcal{Y}|),$$ $${\tilde{r}}_v=\frac{{\sum }_{x\in {\tilde{D}}_v}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x},(1\le v\le V).$$

其中$\tilde{D}$ 表示缺失$D$中没有缺失样本的子集，可以仅根据$\tilde{D}$来判断属性的优劣，直观看来，$\rho$ 表示无缺失值样本所占的比例，${\tilde{p}}_k$ 表示无缺失值样本在第k类中所占的比例，${\tilde{r}}_v$表示无缺失值样本中在属性 $\alpha$ 上取值为 ${\alpha }^v$ 的样本所占的比例，将这些比例与信息增益式子相结合，可以得到推广式：

$$\text{Gain}(D,a)=\rho \times \text{Gain}(\tilde{D},a)$$ $$=\rho \times \left(\text{Ent}(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_v\text{Ent}({\tilde{D}}^v)\right),\text{\hspace{1em}(4.12)}$$

其中由式 (4.1)，有：

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

这个推广式子适用于缺失与非缺失。

对于第二个问题则规定：

• 若x对划分属性的取值已知，则划分进与其取值对应的节点，保持样本权重 $w_x$
• 若未知，则划分进所有的子节点，并调整样本权重$r_v\cdot w_x$ ，直观来看就是让同一个样本以不同概率划入到不同的子节点

除此之外，ID3算法还偏向于将划分种类数量多的属性 如果存在一个标识可以将每个样本自己归为一个分支，这样信息熵就是0，但是对分类并无实际作用（无用解）

Refer

• 西瓜书
• 西瓜书学习笔记(4)—决策树 - Heywhale.com