机器学习之旅—决策树(3)

作者: zidea | 来源:发表于2019-11-16 16:04 被阅读0次

dt_cover.png

从 ID3 到 C4.5

ID3 定义

ID3 算法的核心是在决策树各个子节点上应用信息增益准则选择特征，递归的构建决策树，具体方法是:从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归调用以上方法，构建决策树。

我们通过一个具体实例来讲解如何通过 ID3 算法来选择节点。

求职问题

dt_015.jpg

第一列表示待遇高低 1 表示高 0 表示低
标准第二列表示岗位是否有五险一金 1 表示有五险一金 0 如果没有公积金只有五险用 2 来表示
1 表示接受 offer 0 表示没有接受 offer

1. 1 1 => 1
2. 1 2 => 1
3. 0 0 => 0
4. 0 0 => 0
5. 1 1 => 1
6. 0 0 => 0
7. 1 2 => 1
8. 1 1 => 1
9. 0 2 => 0
10. 1 0 => 0

先复习一下什么是信息熵

熵概念: 信息熵是用来描述信息的混乱程度或者信息的不确定度。信息熵是可以反映集合的纯度

我们要计算纯度也就是计算其不确定度，不确定度大其纯度就低。例如 A 和 B 两个事件的概率都是 30% 50%，A 事件的不确定性(也就是信息熵) 要大。算法目的通过不断决策树来将信息熵降低下来
我们先将公式推出。

$Ent(D) = \sum_{k=1}^m p_k \log_2 \frac{1}{p_k} = - \sum_{k=1}^m p_k \log_2 p_k$

信息增益 $Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$
信息增益率
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$

分析实例

我们以招聘为例，从样本看接受 offer 和没有接受 offer 各占 50% 所以他们概率分别是

$\begin{cases} P_{recive} = \frac{1}{2} \\ P_{refuse} = \frac{1}{2} \end{cases}$
$- ( \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{2} \log_2 \frac{1}{2}) = 1$

-(0.5 * math.log(0.5,2) + 0.5 * math.log(0.5,2))

划分条件为待遇情况

我们希望分支之后信息熵是降低的，我么选择条件 C 后这两个节点，我们回去查表看看高薪岗位的有几个，一共有 6 个岗位。那么是高薪招聘到人是 5

	招聘到人	没有招聘到人
D1	$\frac{5}{6}$	$\frac{1}{6}$
D2	0	1

$Ent(D_1) = - (\frac{5}{6} \log \frac{5}{6} + \frac{1}{6} \log \frac{1}{6} ) \approx 0.65$

-(5/6.0* math.log((5/6.0),2)) - 1/6.0 * math.log((1/6.0),2)

$Ent(D_2) = 1 * \log_2^1 + 0 * \log_2^0 = 0$

$1 - (\frac{6}{10} * 0.65 + \frac{4}{10} * 0) = 0.61$

分类	数量	比例
0	$\frac{4}{10}$	$0 \rightarrow 4, 1 \rightarrow 0$
1	$\frac{3}{10}$	$0 \rightarrow 0, 1 \rightarrow 3$
2	$\frac{3}{10}$	$0 \rightarrow 1, 1 \rightarrow 2$

信息增益越大越好
$\frac{3}{10} \times \left( -\frac{1}{3} \log \frac{1}{3} - \frac{2}{3} \log \frac{2}{3} \right) = 0.27$

$1 - 0.27 = 0.73$

>>> -1/3.0 * math.log(1/3.0,2) - 2/3.0 * math.log(2/3.0,2)
0.9182958340544896
>>> 0.9182958340544896 * 0.3
0.27548875021634683
>>> 1 - 0.28
0.72

在 ID3 我们根据信息增益(越大越好)来选择划分条件，但是有一个问题有关是否高薪我们有两种结果为是高薪或者不是高薪，而对于待遇我们是有三种结果0 代表没有五险一金待遇，1 代表有五险没有一金，2 代表五险一金俱全的。

也就是划分后条件，我们再极端点按 id 进行划分那么每一都是确定所以所有信息熵都是 0 然后 1 - 0 就是 1 ，那么按 id 划分信息增益最高但是没有任何作用，使用信息熵天生对多路分类进行偏好所以。新来一个数据我们按 id 划分是无法预测新数据类别的，而且按 id 进行划分说明我们的模型比较复杂。复杂模型就很容易出现过拟合现象。为了解决这个问题引入信息增益率*

$- 1 * \ln 1 = 0$
$\sum_{i=1}^n (-ln1) = 0$

C4.5 算法

信息增益率
信息增益率是在信息增益基础上除以信息熵，也就是给我们增加分类追加了一个代价。也就是分类多了其分母就会变大从而将数值降低下来。
$Gain_ratio(D,C) = \frac{Gain(D,C)}{Ent(C)}$

$Ent(C) = - \sum_{i=1}^k \frac{N(D_i)}{N} \log_2 \frac{N(D_i)}{N}$

我们回头从新整理一下公式

划分条件为薪资
$Gain(D C_1) = 0.61$
$Ent(C_1) = - (\frac{6}{10} \log \frac{6}{10} + \frac{4}{10} \log \frac{4}{10}) = 0.971$

- (6/10.0 * math.log(6/10.0,2) + 4/10.0 * math.log(4/10.0,2))

$Gain_{ratio}(C_1) = 0.61 \div 0.971 = 0.63$

划分条件为福利待遇
$Gain(D C_2) = 0.72$
$Ent(C_2) = - (\frac{3}{10} \log \frac{3}{10} + \frac{3}{10} \log \frac{3}{10} + \frac{4}{10} \log \frac{4}{10}) = 1.571$

-(3/10.0 * math.log(3/10.0,2) + 3/10.0*math.log(3/10.0,2)+4/10.0*math.log(4/10.0,2))

$Gain_{ratio}(C_2) = 0.72 \div 1.571 = 0.46$

如果我们仅信息增益就会选择C2(按待遇进行划分),而按信息增益率来计算我们就会选择C1(按薪酬划分）。

CART 算法(Classification And Regression Tree)

CART 算法不但可以处理分类问题还可以处理回归问题。CART 算法与ID3 算法思路是相似的，但是具体实现上和应用场景略有不同。
CART 算法采用基尼指数（分类树）以及方差（回归树）作为纯度的度量，而ID3 系列算法采用信息熵作为纯度的度量。
CART 算法只能建立二叉树，而ID3系列算法能够建立多叉树。

分类树

$Gini(D) = \sum_{k=1}^m p_k(1-p_k) = 1 - \sum_{k=1}^m p_k^2$
基尼指数越小越好
$\Delta Gini = Gini(D) - \sum_{i=1}^2 \frac{N(D_i)}{N} Gini(D_i)$
我们用根节点的基尼指数减去按条件划分后基尼指数，也就是结果越大那么说明这个划分条件越好。

回归树

对于连续型我们通过方差来考虑，方差越小纯度越高
$V(D) = \frac{1}{N-1} \sum_{i=1}^N(y_i(D) - \hat{y}(D))^2$
同样我们用根节点方差减去划分后方差，结果越大说明划分条件越好
$\Delta V = V(D) - \sum_{i=1}^2 \frac{N(D_i)}{N} V(D_i)$

优化以及总结

	C5.0 系列	CART
是否支持多路划分	多重(有多少类别数量就有多少)	二叉树
连续目标	否	是
决策树分割标准	信息增益(ID3)/信息增益率(C4.5)	Gini 系数(分类）/方差(回归树)
剪枝	误差估计	误差代价——复杂度
代价敏感矩阵	支持	支持
Boosting	支持	支持

我们来思考一个问题，我们通过不断细分一定可以把数据划分为我们想要结果。但是这个树并不是我们想要的模样，因为上面我们已经知道了，复杂模型带来就是过拟合问题。那么我们如何评估一个决策树设计好坏呢?
所以我们就需要对决策树进行调整和删减不必要节点，这个过程我们称为剪枝，剪枝又分为预剪枝和后剪枝，在预剪枝很简单，必须保证分裂后节点必须保证有我们事先定义好的样本量，如果节点样本量少于指定的样本量，我们就不进行分支。这就是预剪枝，也就是生成节点如果不满足一定条件我们就将其减掉，这个过程就是预剪枝，有了预剪枝当然也就有后剪枝。

后剪枝

我们用训练集构建决策树，然后我们用测试评估决策树，通过测试集后，假如父节点的误差大于分支后误差就说明划分是对的，相反就会减掉这个分支
而在C5.0会采用其他策略进行评估，C5.0 会考虑代价。

机器学习之旅—决策树(3)

从 ID3 到 C4.5

ID3 定义

求职问题

分析实例

划分条件为待遇情况

C4.5 算法

CART 算法(Classification And Regression Tree)

分类树

回归树

优化以及总结

后剪枝

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

深度学习

深度学习-推荐系统-CV-NLP