特征选择（节点划分）

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

符号声明

假设当前样本集合 $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}$

1. 信息增益

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

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

2. 增益率

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

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

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

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

3. 基尼指数

$\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}$