决策树之特征选择

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

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

1. 符号声明

假设当前样本集合$D$中第$k$类样本所占的比例为$p_k\:(k=1,2,...,|\mathcal Y|))$，离散属性$a$有$V$个可能的取值$\{a^1,a^2,...,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{|D^v|}{|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^{2} \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)$$