决策树
Swift Lv6

决策树的定义和示例见西瓜书P73~P74,下面主要介绍决策树的构造算法:

信息熵

信息熵是衡量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k(k=1,2,\cdots,|\gamma|)$ ,那么 $D$ 的信息熵为:

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

构造算法

ID3

$V$ 表示属性 $a$ 的取值范围。信息增益越大,表示使用属性 $a$ 进行划分所获得的“纯度提升”越大。

根据 ID3 算法的核心思想,只要在每次决策树非叶子节点划分之前,计算出每一个属性所带来的信息增益,选择最大信息增益的属性来划分,就可以让本次划分更优,因此整个 ID3 实际上是一个贪心算法。

以西瓜数据集2.0来说,“纹理”的信息增益最大,于是它被选为划分属性。后续对其它属性进行特征选择。

C4.5

C4.5 对 ID3 算法最大的改进就是在获取最优分类特征的时候,将 ID3 所使用的信息增益换成了信息增益比。

如果我们将每个西瓜样本的“编号”作为候选划分属性,那么它的信息增益最大。因为“编号”将产生17个分支,每个分支仅包含一个样本,这些分支结点的纯度达到最大。但这样的决策树不具有泛化能力,无法对新样本有效预测。

实际上,信息增益准则对取值较多的属性有所偏好,为了减少这种偏好带来的不利影响,C4.5采用“增益率”来选择最优划分属性:

$IV(a)$ 称为属性 $a$ 的“固有值”。$V$ 越大,$IV(a)$ 越大。

需注意的是,增益率对 $V$ 较小的属性 $a$ 有所偏好。因此,C4.5算法并不直接选择增益率最大的候选划分属性,而使用了一个启发式策略:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。

CART

CART决策树使用“基尼指数”来选择划分属性。数据集 $D$ 的纯度可用基尼值来度量:

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

属性 $a$ 的基尼指数定义为:

在候选属性集合 $A$ 中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即:


参考

Powered by Hexo & Theme Keep
Unique Visitor Page View