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

作者: 易码当先 | 来源:发表于2019-12-20 19:14 被阅读0次

从cart决策树到XGBoost
决策树和随机森林
05 决策树 - 生成算法 ID3、C4.5、CART
day10-决策树
2019-04-26
数挖——基本分类
分类（1）：决策树与模型评估
决策树基本要点及方法对比
（14）监督学习-分类问题-决策树
经典决策树对比

一、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$ 。

3、对集合 $D_{1}$ 和 $D_{2}$ 重复步骤1和2，直至满足停止条件。

CART决策树分类算法：

1、根据以下公式找出最优划分特征 $a_{*}$ 和最优划分点 $a_{*}^v$ :

CART分类函数

其中 $D_{1} (a,a^v )$ 表示属性a上取值小于等于 $a^v$ 的样本集合， $D_{2} (a,a^v )$ 表示属性a上取值大于 $a^v$ 的样本集合。 $c_{1}$ 表示 $D_{1}$ 的样本输出均值， $c_{2}$ 表示 $D_{2}$ 的样本输出均值。

2、根据划分点 $a_{*}^v$ 将集合划分为 $D_{1} 和D_{2}$ 两个集合（节点）。

3、对集合 $D_{1}$ 和 $D_{2}$ 重复步骤1和2，直至满足停止条件。

总结：本文对决策树的三种算法决策原理进行了简单分析推导。

从cart决策树到XGBoost
一. cart决策树简述我们知道决策树算法有ID3、C4.5和cart三种，ID3和C4.5是基于信息增益和信息...
决策树和随机森林
随机森林和GBDT算法的基础是决策树而建立决策树的算法由很多，ID3，C4.5,CART等， ID3：ID3算法...
05 决策树 - 生成算法 ID3、C4.5、CART
ID3 提出了初步的决策树算法；C4.5 提出了完整的决策树算法；CART (Classification And...
day10-决策树
今天学了决策树的基本知识。基于信息论的决策树算法有：ID3, CART, C4.5等算法。 ID3 算法是根...
2019-04-26
决策树离散型数据ID3 连续型数据C4.5 分类与回归树算法(CART) CART算法就是将决策树中用于判断特征...
数挖——基本分类
构造决策树有多种算法：1、Hunt算法 (决策树归纳算法框架)2、CART3、ID3, C4.5 (重点)4、SL...
分类（1）：决策树与模型评估
一、如何建立决策树 1、Hunt算法 Hunt算法是许多决策树算法的基础，包括ID3、C4.5、CART。Hunt...
决策树基本要点及方法对比
决策树的生产，基本方法有ID3、C4.5、CART。基于基础决策树学习器，可进一步构建提升树。 ID3 ID3算法...
（14）监督学习-分类问题-决策树
决策树算法分为ID3，C4.5，CART几种。其主要区别在于特征选择的方法不同。 1、 ID3 特征选择方法...
经典决策树对比
关于经典决策树算法ID3、C4.5及CART树的部分细节梳理。决策树决策树可以从两个视角理解。 If-Then...