决策树之特征选择

疏理一下决策树的特征选择的方法，即决策树的节点划分。

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高。

1. 符号声明

假设当前样本集合$D$中第$k$类样本所占的比例为$p_k:(k=1,2,...,|\mathcal Y|))$，离散属性$a$有$V$个可能的取值${a^1,a2,...,a^{V}$，若使用$a$来对样本集$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a}v$的样本，记作$D^v$。

样本集合$D$的信息熵定义为 $$Ent(D)=-\sum_{k=1}^\mathcal{|Y|} p_k\log_2{p_k}$$

2. 信息增益

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

实际上，信息增益准则对可取数目较多的属性有所偏好。

3. 增益率

$C4.5$决策树算法选择增益率(gain ratio)来选择最优划分属性。

$$ \begin{aligned} Gain_ratio(D, a)=\frac{Gain(D,a)}{IV(a)} \ s.t. \quad IV(a)=-\sum_{v=1}^{V}\frac{|Dv|}{|D|}\log_2\frac{|D^v|}{|D|} \end{aligned} \tag{2} $$

$IV(a)$称作属性$a$的固有值(intrinsic value)。

需注意的是，增益率准则对可取值较少的属性有所偏好，因此，$C4.5$算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4. 基尼指数

$$ \begin{aligned} \text{数据集$D$的纯度：} \ Gini(D) &= \sum_{k=1}^{\mathcal{|Y|}}\sum_{k' \neq k}p_k p_{k'}\ &= 1-\sum_{k=1}^{{\mathcal{|Y|}}p_k} \end{aligned} $$

直观来讲，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，则数据集$D$的纯度越高。

属性$a$的基尼指数：

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

于是，我们在候选属性集合$A$中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即： $$a_* = \underset{a\in A}{\arg \min}: Gini_index(D,a)$$