机器学习导论4 决策树 [待修订]

分类:Machine Learning, 发布于:2019-03-20 16:00:00, 更新于:2019-04-19 00:12:14。 评论

基本流程

决策树基于树结构来进行预测

决策树停止划分的三个条件:

  • 当前节点包含的样本全部属于同一类别(没必要分了)
  • 当前属性集为空,或所有样本在所有属性上取值相同(没法分了)
  • 当前节点包含的样本集合为空($\emptyset$

划分选择

决策树学习的关键在于如何选择最优化分属性。我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的纯度(purity)越来越高。

经典的属性划分方法:

  • 信息增益
  • 增益率
  • 基尼指数

信息增益

“信息熵”是度量样本集合纯度最常用的一种指标。社当前样本集合$\mathcal{D}$中第$k$类样本所占的比例为$p_k$,则$\mathcal{D}$的信息熵定义为$\text{Ent}(\mathcal{D})$ $$\text{Ent}(\mathcal{D}) = - \sum\limits_{k=1}^{|\mathcal{y}|} p_k \log_2 p_k$$ 值越小,则$\mathcal{D}$的纯度越高。

计算信息熵时约定:$p=0$, $\text{Ent} = 0$$\text{Ent}(\mathcal{D})$的最小值为0,最大值为$\log_2|ay|$

信息增益

离散属性$a$$V$个可能的取值,有$a$来进行划分,会产生$V$个分直接点,第$v$个分支节点记为$\mathcal{D}^v$。可计算出用属性$a$对样本集$\mathcal{D}$进行划分所得的信息增益: $$\text{Gain} = \text{Ent}(\mathcal{D})-\sum\limits_{v \in V} \dfrac{\mathcal{|D^v|}}{\mathcal{|D|}} \text{Ent}(\mathcal{D^v})$$ 信息增益越大,信息纯度的提升越大。

存在的问题:若把编号也作为划分属性,则其信息增益一般远大于其他属性。倾向于可取值数目较多的属性。

增益率

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

其中 $$\text{IV}(a) = - \sum\limits_{v \in V}\dfrac{|\mathcal{D^v}|}{|\mathcal{D}|} \log_2 \dfrac{|\mathcal{D^v}|}{|\mathcal{D}|}$$

存在的问题:倾向于可取值数目较少的属性。

基尼指数

$$\text{Gini}(\mathcal{D}) = \sum\limits_{k=1}^{|y|} \sum\limits_{k' \neq k} p_kp_{k'} = 1 - \sum\limits_{k = 1}^{|y|}p_k^2$$

$\text{Gini}(\mathcal{D})$越小,数据集$\mathcal{D}$的纯度越高。

属性$a$的基尼指数定义为 $$\text{Gini\_index}(\mathcal{D}, a) = \dfrac{|\mathcal{D^v}|}{|\mathcal{D}|} \red{???????}$$

剪枝处理

为什么剪枝

  • “剪枝”是决策树学习算法对付“过拟合”的主要手段
  • 可通过剪枝来一定程度避免因决策分之过多,以至于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合

基本策略

  • 预剪枝
    • 降低过拟合风险,显著减少训练时间和测试时间开销;
    • 有欠拟合风险:预剪枝基于“贪心”本质禁止一些分支展开,带来了欠拟合风险。
  • 后剪枝
    • 欠拟合风险小,泛化性能往往优于预剪枝决策树;
    • 训练时间开销大。

判断决策树泛化性能是否提升的方法

  • 留出法:预留一部分数据用作“验证集”进行性能评估

连续与缺失值

连续属性离散化(二分法)

$$T_a = \left\lbrace \dfrac{a^i + a^{i+1}}{2} | 1 \leqslant i \leqslant n-1 \right\rbrace$$

把区间$[a^i, a^{i+1})$的中间点作为候选划分点。

缺失值处理

如果有样本缺失,样本不计入信息熵、增益、基尼指数的计算。

  • 无缺失样本所占的比例$\rho$
  • 无缺失样本在第$k$类所占的比例$r$
  • 无缺失样本

评论