决策树

ID3——最大信息增益

信息熵是度量样本集合纯度最常用的一个指标。假定当前样本集合D中第k类样本所占的比利为$p_k(k=1,2,…,|y|)$,则D的信息熵定义为

$$Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k$$

$Ent(D)$的值越小则D的纯度越高。

假定离散属性a有V个可能的取值${a^1,a^2,…,a^V}$，若使用a来对样本集进行划分，则会产生V个分治节点，其中$v$个分治节点包含D中做在属性a上取值为$a^v$的样本，记为$D^v$.则属性a对样本集D进行划分所获得的信息增益为

$$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$

ID3决策树以信息增益为准则选择划分属性。$a*=\arg\max_{a\in A} Gain(D,a)$

C4.5——最大增益率

增益率定义为

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

其中

$$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log2{\frac{|D^v|}{|D|}}$$

C4.5决策树以信息增益率为准则选择划分属性。

CART——最小基尼指数

基尼值是另一个描述数据集D纯度的指标其定义为

$$Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\not=k}p_kp_k'\\ =1-\sum_{k=1}^{|y|}p_k^2$$

$Gini(D)$越小，则数据集D的纯度越高。

属性a的基尼指数定义为

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

CART决策树选择基尼指数最小的属性作为最优划分属性。

剪枝处理

剪枝处理是决策树对付过拟合的主要手段。主要分为预剪枝和后剪枝。

预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性的提升则停止划分并将当前节点表姐为叶节点。后剪枝则是先从训练集生成一颗完整的局册数，然后自地向上对非叶节点进行考察，拖该节点对应的自述替换为叶节点能带来决策树泛化性能的提升，则该子树替换为叶节点。