西瓜书学习笔记

James

2019-05-22

决策树

信息熵，信息增益，信息增益率和基尼系数

信息熵(Information Entropy)是度量样本级和纯度最常用的一种指标。假设当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $pk\ (k=1,2,\dots,n)$, 则 $D$ 的信息熵定义为 $$Ent(D)=-\sum{k=1}^{n}p_k\log{p_k}$$

信息熵的值越小，纯度越高。

假设离散属性$a$有$V$个可能的取值${a^1,a^2,\dots,a^V}$,若使用$a$来对样本集$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。

信息增益定义为： $$Gain(D,a)=Ent(D-\sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)$$
信息增益率定义为： $$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$ 其中 $$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log{\frac{|D^v|}{|D|}}$$

基尼系数定义为： $$Gini(D)=\sum{k=1}^{N}\sum{k'\neq k}pkp{k'}=1-\sum_{k=1}^Np_k^2$$ 属性$a$的基尼指数定义为 $$Gini_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

ID3决策树采用信息增益作为划分标准。

C4.5采用信息增益率作为划分标准。

CART决策树采用基尼系数作为划分标准。

剪枝是决策树算法应对过拟合的主要手段。剪枝基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。

预剪枝是指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将当前结点标记为叶子结点。

后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。

由于连续属性可取值数目不再有限，我们不能够直接更具连续属性的可取值来对节点进行划分，此时需要使用离散化技术将连续属性离散化。

最简单的策略是采用二分法（bi-partition）对连续属性进行处理，二分法也是C4.5所采用的方法。二分法将小于某一特定值的属性划为一类，将大于某一特定值的属性划分为另一类，之后便可以使用离散值的划分标准进行判断。

不考虑当前属性有缺失值的样本，对剩余样本进行划分。

确定划分结果后，当前属性有缺失值的样本按比例加入到各分支进行进一步的划分。