李宏毅机器学习任务八

决策树

决策树：是一种基本的分类与回归方法，在分类问题中，表示基于特征对实例进行分类的过程，它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。

决策树学习通常包含 3 个步骤：

特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准
决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止
决策树剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模

损失函数

决策树学习的损失函数通常是正则化的极大似然函数，策略是以损失函数为目标函数的最小优化。

递归思想

决策树学习的算法通常是一个递归地选择最优特征，不断的选择子集的最优特征来进行划分更小的子集。直到所有训练数据子集被基本正确分类，或者没有合适的特征为止，这就生成了一棵决策树。

过拟合

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对于未知的测试数据的分类却没有那么准确，即出现过拟合的现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

剪枝

在决策树学习中将已生成的树进行简化的过程称为剪枝。具体地，剪枝从已生成的树上裁掉一些子树或者叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类数模型。决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数来实现。

决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行了更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树的剪枝学习整体的模型。

前剪枝（Pre-Pruning）：在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使可以继续减低熵，也停止继续创建分支。

后剪枝（Post-Pruning）：后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，在剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识。

决策树模型结构

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持	支持
CART	分类/回归	二叉树	基尼系数，均方差	支持	支持	支持

信息增益

特征A对训练数据集D的信息增益 $g(D, A)$ ，定义为集合D的经验熵 $H(D)$ 与特征A给定条件下D的经验条件熵 $H(D|A)$ 只差，即：
$g(D, A)=H(D)-H(D | A)$

$H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

$H(Y | X)=-\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right)$

信息增益比

特征A对训练数据集D的信息增益比 $g_{R}(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集D的经验熵之比：
$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$
其中训练数据集D关于特征值A的熵为：
$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}，n是特征A取值的个数$

为什么有信息增益了还需要信息增益比？

不仅仅应该只从极限情况下考虑，极限时讨论仅仅是极度不满足大数定律的特例而已。样本数越少，根据大数定律（反向利用），用频率对概率的估计结果的方差就越大，进一步导致该取值下的类别错估计为非均匀分布，而非均匀分布，导致该取值下的熵更小（对应熵的函数图像，在p=0.5时，取最大值）。
当数据集非常大，或者说那些取值多的特征并没有多到很夸张时，信息增益并没有多大的偏向性。

c4.5为什么使用信息增益比来选择特征？ - 夕小瑶的回答 - 知乎

ID3 算法

优点：

简单易实现

缺点：

没有考虑连续特征
无法处理有缺失值的数据
没有剪枝过程，生成的树容易产生过拟合
采用信息增益作为特征选择的依据。但其存在一个很明显的缺点，在相同条件下，取值比较多的特征比取值少的特征信息增益更大。（极端情况下，特征值数等于样本数时，条件熵为0）

C4.5 算法

需注意的一点：

增益率也可能产生一个问题就是，对可取数值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择使用增益率最大的候选划分属性，而是使用了一个启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

优点：

对连续属性进行离散化
能够对不完整数据进行处理
增加剪枝过程
用信息增益比作为特征选择的依据

缺点：

只能处理分类问题，不能处理回归问题
计算信息熵时会涉及到大量的对数运算，如果是连续值还需要进行排序，寻找最优离散划分点，这些都会增大模型的计算量

连续值处理

给定训练集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大排序。
取相邻两个点的均值，作为划分点，这样可以取 n-1 个划分点
确定哪个划分点的信息增益最大

待补充：连续值处理是C4.5 中提出的，但为什么连续值处理中不是用信息增益比？

缺失值处理

包括三个问题：

如何在属性值缺失的情况下选择最优划分属性？

信息增量：无缺失值样本所占的比例乘以无缺失值样本子集的信息增量
选定了划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？

对每个样本引入权重的概念，样本默认权重为1，对于无缺失值的样本，划分到子集时其权重保持不变。对于缺失值的样本，将缺失值样本按不同的概率划分到所有分支中，而概率则等于无缺失值样本在每个分支中所占的比例
决策树构造完成后，如果测试样本的属性值不完整，该如何确定该样本的类别？

下面链接有具体的例子（如何计算），容易理解：

机器学习笔记（7）——C4.5决策树中的缺失值处理

决策树（decision tree）（四）——缺失值处理

上述算法的剪枝

剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树 $T$ 的叶节点数为 $|T|$ ， $t$ 是树 $T$ 的叶节点， $\alpha \geqslant 0$ 为参数，则决策树学习的损失函数可以定义为：
$C_{\alpha}(T)=\sum_{t=1}^{|T|} N_{t} H_{t}(T)+\alpha|T|$
其中经验熵为：
$H_{t}(T)=-\sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}}$
将损失函数第一部分用符号表示，可简化为：
$C_{\alpha}(T)=C(T)+\alpha|T|$
其中， $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程序， $|T|$ 表示模型复杂度。注意观察的话，可以发现 $C(T)$ 其实就是条件熵，即信息增量中的第二部分，信息增量中第一部分对于特定数据集是个定值，所以挑选信息增量最大的特征时，相当于挑选使条件熵最小的特征。（疑问：为什么ID3算法中不直接计算条件熵然后进行比较，非要多此一举计算信息增量然后再进行呢？？？）

剪枝过程

输入：生成算法产生的整个数T，参数 $\alpha$

输出：修剪后的子树 $T_{\alpha}$

计算每个结点的经验熵
递归从树的叶节点向上回缩

叶节点回缩到其父节点之前与之后的整体树分别为 $T_{B}$ 和 $T_{A}$ ，其损失函数如果满足：
$C_{\alpha}\left(T_{A}\right) \leqslant C_{\alpha}\left(T_{B}\right)$
则进行剪枝，即将父节点变成新的叶节点
返回第二步，直至不能继续为止，得到损失函数子树的子树 $T_{\alpha}$

CART 算法

分类与回归树（CART）同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

回归树生成

假设使用平方误差来表示回归树对于训练数据的预测误差

通俗理解：每次遍历所有特征，然后遍历每个特征的所有可能取值，在遍历的过程中每次计算把每个值当做切分点（此时数据集会分成两部分）时总体的平方误差之和，找出使其最小的取值，进行划分，以此类推。

输入：训练数据集D

输出：回归树 $f(x)$

选择使下式达到最小值时的最优切分遍历 $j$ 和切分值 $s$
$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$
用选定的 $(j, s)$ ，划分数据集并决定其相应的输出值

$\begin{aligned} R_{1}(j, s) &=\left\{x | x^{(j)} \leqslant s\right\}, \quad R_{2}(j, s)=\left\{x | x^{(j)}>s\right\} \\ \hat{c}_{m} &=\frac{1}{N_{m}} \sum_{x \in R_{m}(j, s)} y_{i}, \quad x \in R_{m}, \quad m=1,2 \end{aligned}$

对子集继续执行上述两个步骤，直到满足停止条件
将输入空间划分为M个区域 $R_{1},R_{2},R_{3},...R_{M}$ ，生成决策树：

$f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \in R_{m}\right)$

分类树生成

基尼指数

分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_{k}$ ，则概率分布的基尼指数为：
$\operatorname{Gini}(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$
对于给定样本集合 $D$ ，其基尼指数为：
$\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$
如果样本集合 $D$ 根据特征 $A$ 是否取一可能值 $a$ 被分割成 $D_{1}$ 和 $D_{2}$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数为：
$\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$
使用基尼指数的优点：计算快，因为熵会涉及到大量的对数运算

为什么决策树中经常用熵作为判别条件而不是基尼不纯度？ - 微调的回答 - 知乎

理解：

基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数值越大，集合样本的不确定性也就越大，与熵类似。还代表模型的不纯度，基尼指数越小，则不纯度越低，特征越好。

根据基尼指数的图像，当概率 $p$ 接近于 0 和 1时，基尼指数越小，此时对于数据的分类，如果是二分类，说明只有一小部分属于其中一类，而大多数属于另外一类。

输入：训练数据集 $D$ ，停止计算的条件

输出： CART决策树

设节点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。遍历所有特征和每个特征的所有值。
选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。生成两个子节点，划分数据到对应的节点中
对两个子节点递归上述操作，直到满足停止条件
生成CART决策树

CART剪枝

核心思想：首先从生成算法产生的决策树 $T_{0}$ 低端开始不断剪枝，知道 $T_{0}$ 的根节点，形成一个子树序列 $\{T_{0},T_{1},...,T_{n}\}$ ；然后通过交叉验证法在独立的验证数据集上对子树序列进行预测从中选择最优子树

核心计算：

从整体树 $T_{0}$ 开始剪枝，对 $T_{0}$ 的任意内部节点 $t$ ，以 $t$ 为单结点树的损失函数为：
$C_{\alpha}(t)=C(t)+\alpha$
以 $t$ 为根节点的子树 $T_{t}$ 的损失函数为：
$C_{\alpha}\left(T_{t}\right)=C\left(T_{t}\right)+\alpha\left|T_{t}\right|$
当 $\alpha = 0$ 及其充分小时，有不等式：
$C_{\alpha}\left(T_{t}\right)<C_{\alpha}(t)$
当 $\alpha$ 增大时，在某一 $\alpha$ 有：
$C_{\alpha}\left(T_{t}\right)=C_{\alpha}(t)$
当 $\alpha$ 再增大时，上述不等式反向，只要 $\alpha=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$ , $T_{t}$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少，因此 $t$ 比 $T_{t}$ 更可取，对 $T_{t}$ 进行剪枝

输入：CART算法生成的决策树

输出：最优决策树

自上而下地对各内部节点 $t$ 计算下式，然后使 $\alpha$ 等于最小的 $g(t)$ 值
$g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$
自上而下地遍历内部节点 $t$ ，如果有 $g(t) = \alpha$ ，进行剪枝，并对叶节点 $t$ 以多数表结法决定其类，得到树 $T$
对树 $T$ 重复上述操作，将得到一个子树序列
采用交叉验证法在子树序列中选取最优子树

参考链接

决策树算法原理(上)

决策树算法原理(下)

代码

HomeWork

最后编辑于：2019.06.17 16:32:53

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 221,695评论 6赞 515
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,569评论 3赞 399
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 168,130评论 0赞 360
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,648评论 1赞 297
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,655评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,268评论 1赞 309
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,835评论 3赞 421
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,740评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,286评论 1赞 318
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,375评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,505评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,185评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,873评论 3赞 333
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,357评论 0赞 24
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,466评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,921评论 3赞 376
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,515评论 2赞 359