ID3/C4.5/CART决策树算法推导

一、ID3决策树

二、C4.5决策树

三、CART决策树

四、总结

信息熵——度量样本集合纯度最常用一种指标，其定义如下：

信息熵

其中， $D={(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})}$ 表示样本集合，|y|表示样本类别总数， $p_{k}$ 表示第K类样本所占的比例，且 $0\leq p_{k} \leq 1$ 。

p_{k}

占比率

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

求解信息熵的最大值，证明： $0\leq Ent(D)\leq 1$

若令 $|y| = n，p_{k} = x_{k}$ ，那么信息熵 $Ent(D)$ 就可以看做是一个n元实值函数，也即 $Ent(D) = f(x_{1},x_{2},...,x_{n} ) = -\sum_{k=1}^nx_{k}\log_2 x_{k}$ ，其中 $0\leq x_{k} \leq 1$ ， $\sum_{k=1}^nx_{k} =1$ ，下面考虑求最值。

如果不考虑 $0\leq x_{k} \leq 1$ ，仅考虑 $\sum_{k=1}^nx_{k} =1$ ，对 $f(x_{1},x_{2},...,x_{n} )$ 求最大值等价于如下最小化问题

问题转换

经观察，（1）等价于n个 $x*\log_2 x$ ，由于 $0\leq x\leq 1$ ，因此目标函数 $x*\log_2 x$ 一定是凸函数（或对目标函数二阶求导，判断其hessian矩阵的正定性，来证明其目标函数是凸函数）。由于函数（2）是线性约束，目标函数（1）又是凸函数，因此整个优化问题就是个凸优化求解过程。而凸优化问题来说，满足KKT条件的点即为最优解。由于此最小化问题仅含等式约束，那么能令其拉格朗日函数的一阶导数为0的点，即为满足KKT条件的点。

拉格朗日函数：

$L(x_{1},......,x_{n},\lambda ) = \sum_{k=1}^nx_{k}\log_2 x_{k} +\lambda (\sum_{k=1}^nx_{k} -1)$ ，其中 $\lambda$ 为拉格朗日乘子。

对拉格朗日函数分别关于 $x_{1}... x_{n},\lambda .$ 求一阶偏导数，并令偏导数等于0可得

最优解推导

至此， $\frac{1}{n}$ 即为当前最小化问题的最小值点，同时也是 $f(x_{1},...,x_{n} )$ 函数的最大值点。将

$x_{1} = x_{2} =...= x_{n} = \frac{1}{n}$ 代入 $f(x_{1},...,x_{n} )$ 中可得 $f(\frac{1}{n},...\frac{1}{n} ) = -\sum_{k=1}^n\frac{1}{n} \log_2 \frac{1}{n} = -n.\frac{1}{n}\log_2 \frac{1}{n} =\log_2 n$ ，所以 $f(x_{1},...,x_{n} )$ 在满足约束条件 $0\leq x_{k} \leq 1$ 和 $\sum_{k=1}^nx_{k} =1$ 时的最大值是 $\log_2 n$ 。

令 $x_{k}$ =1 ， $x_{1}= x_{2}=x_{k}=x_{k+1}=x_{n}=0$ 一定是 $f(x_{1},...,x_{n} )$ 在满足约束条件 $0\leq x_{k} \leq 1$ 和 $\sum_{k=1}^nx_{k} =1$ 的最小值点，其最小值是0。说明只有一类样本时，其他类样本数为0时，信息熵最小，样本纯度最高。

条件熵——在已知样本属性a的取值情况下，度量样本集合纯度的一种指标 $H(D|a) =\sum_{v=1}^v \frac{|D^v |}{|D| } Ent(D^v )$ ，其中a表示某个样本属性，假定属性a有V个可能的取值

{ $a^1,a^2,...,a^V$ }，样本集合D中在属性a上取值为 $a^v$ 的样本记为 $D^v$ ， $Ent(D^v )$ 表示样本集合 $D^v$ 的信息熵。 $H(D|a)$ 值越小，纯度越高。

信息增益

小结: 信息增益= 信息熵-条件熵，选择信息增益最大的属性作为划分属性，因为信息增益越大，则意味着使用该属性来进行划分获得的“纯度提升”越大。

以信息增益为划分准则的ID3决策树对可取值数目较多的属性有所偏好（存在严重过拟合现象，模型泛化能力差），因此产生了C4.5决策树。

C4.5决策树——以信息增益率为标准来选择划分属性的决策树

信息增益率： $Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$

其中， $IV(a) =-\sum_{v=1}^V\frac{|D^v| }{|D|}\log_2 \frac{|D^v| }{|D|}$ 作为惩罚项。

C4.5对信息增益超过平均水平的所有属性，对它们使用惩罚项后，再选择信息增益率最高的属性作为划分属性。

CART决策树——以基尼指数为准则来选择划分属性的决策树

基尼指数与基尼值

基尼值：就是从样本集合D中随机抽取两个样本，且不是同一样本的概率值。

CART决策树分类算法：

1、根据基尼指数公式

基尼指数

找出基尼指数最小的属性 $a_{*}$

2、计算属性 $a_{*}$ 的所有可能取值的基尼值 $Gini(D^v)$ ， $v=1,2,...,V$ ，选择基尼值最小的取值 $a_{*}^v$ 作为划分点，将集合D划分为 $D_{1}$ ， $D_{2}$ 两个集合（节点），其中 $D_{1}$ 集合的样本为 $a_{*}$ = $a_{*}^v$ 的样本， $D_{2}$ 集合为 $a_{*} \neq a_{*}^v$ 。