决策树

2020-12-17 本文已影响0人 cornbig

1. 信息增益，增益率

输入：训练集 $D =$ { $(x_1, y_1), ..., (x_m, y_m)$ } ；

属性集 $A =$ { ${a_1, ..., a_d}$ }

过程：函数 $TreeGenerate（D，A）$

信息熵是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为

$p_k(k = 1, 2,...,\vert y \vert)$ ,则 $D$ 的信息熵定义为 $Ent(D) = -\sum_{k=1}^{\vert y \vert }$ $p_k log_2p_k$

$Ent(D)的值越小，D的纯度越高$

$Gain(D,a) = Ent(D) - \sum_{v=1}^V$ $\frac{\vert D^v \vert }{D}$ $Ent(D^v)$ （1）

从A中选择最优划分属性 $a_*$ , $a_* = arg$ $min_{a\in A}$ $Gain(D,a)$

ID3 决策树学习算法以信息增益为准则来划分属性。如果把编号加入到决策树中，根据（1）计算出编号属性的信息增益为0.998，远大于其他候选划分属性。可以理解， ”编号“将产生17个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已达到最大，然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。

实际上信息增益准则对可取数目比较多的属性有所偏好，为减少这种偏好带来的不利影响，C4.5决策算法不直接用信息增益，而使用“增益率”（gain ratio）来选择最优划分属性，增益率定义为：

$Gain ratio (D,a) =$ $\frac{Gain(D,a)}{IV(a)}$ , 其中 $IV(a) = -\sum_{v=1}^V \frac{\vert D^v \vert }{D}$ $log_2$ $\frac{\vert D^v \vert }{D}$

属性a 取值数目越多（V越大），则IV（a）的值通常会越大，增益率准则对可取值数目较少的属性有所偏好，因此 C4.5 并不是直接选择增益率最大的候选划分属性，而是使用一种启发式：

先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2. 基尼指数

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

$Gini(D) =$

上一篇下一篇

猜你喜欢

热点阅读