2 合适的划分

合适的划分应当使得每个 node 所包含的待划分数据集纯度越来越高。

信息增益

如何衡量集合的纯度（purity）？常用信息熵（information entropy）来衡量。

假设样本集合 $D$ 共有 $|\mathcal{Y}|$ 类，其中第 $k$ 类的占比为 $p_k$ ，则 $D$ 的信息熵定义为 $$ H(D)=Ent(D):=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k $$ $Ent(D)$ 越小， $D$ 的纯度就越高。

注

若 $p=0$ ，约定 $p\log p=0$
$Ent(D)$ 的最小值为 0，最大值为 $\log_2|\mathcal{Y}|$

现在我们选择某个属性 $a$ （比如西瓜数据集中的颜色）对当前未划分节点 $D$ 进行划分。假设 $a$ 有 $V$ 种取值（比如深绿、浅绿等），分别记为 $a^1,...,a^V$ ，则用 $a$ 来划分 $D$ 要产生 $V$ 个子节点。我们需要计算按此划分后，前后的信息熵之差。

由于划分之后各子节点 $D^v$ 的样本数量不同，在计算划分后的信息熵差时，需要给每个子节点一个权重。 $$ Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) $$ 所以这个信息增益实际上是信息熵减少量（所以是信息的增加量）。

信息熵减少得越多，说明信息增益越大，意味着使用 $a$ 做划分的纯度提升越大，所以选择就是 $$ a_*={\arg\max}_{a\in A}Gain(D,a) $$ 这种划分度量被 ID3 决策树所采用。

信息增益率

用信息增益来选择划分可能导致一个窘境：样本可能具有唯一标识，如果我们考虑这个唯一标识，则划分后的信息增益非常大（每个节点只有一个样本了），这样不符合实际。信息增益准则偏好那些可取值较多的属性。

如何度量一个属性的可取值方面的情况呢？类似信息熵，引入固有值（Intrinsic Value）这一概念： $$ IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|} $$ 根据经验来说，如果 $V$ 越大， $IV$ 的值通常越大，于是可提出信息增益率 $$ GainRatio(D,a)=\frac{Gain(D,a)}{IV(a)} $$ 其减小了属性可取值方面的影响。但是增益率准则对可取值较少的属性有所偏好，所以算法一般先从候选属性中找 Gain 高于平均值的那些属性，再从这里面选 Gain_ratio 最高的。

这种划分度量被 C4.5 决策树所采用。

Gini 指数

另一种度量纯度的方法是使用 Gini 值和 Gini 指数。

Gini 值是对于某个集合来定义的，其定义为 $$ Gini(D):=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k\neq k'}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 $$ 也就是说从数据集 $D$ 中随机选两个样本，其类别不一致的概率。显然，这个概率越低， $D$ 的纯度越高。

Gini 指数是对于某个属性来定义的，其定义为 $$ GiniIndex(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v) $$ 在所有候选属性中，选择 Gini 指数最小的那个属性作最优划分，即 $$ a_*={\arg\min}_{a\in A}GiniIndex(D,a) $$ 这种划分度量被 CART 决策树所采用。

本文阅读量