决策树

特点

if-then的集合

损失函数最小化

可读性，速度快

启发式解决NP完全问题

信息增益

特征选择通过信息增益：

熵： $H(X)=-\sum_{i=1}^n p_{i} log p_{i}$ （2或者e为底），熵越大，随机变量的不确定性越大。（当p=0/1，即完全确定，此时熵最小，得0；p=0.5时，熵最大，得1）

条件熵： $H(Y|X)=\sum_{i=1}^n p_{i} H(Y|X=x_{i})$ ，表示在已知随机变量X的条件下随机变量Y的不确定性。

注：规定0log0=0。

信息增益=类与特征的互信息=g(D,A)=H(D)-H(D|A) （D为数据集，A为特征）

信息增益比： $g_{R}(D,A)=\frac{g(D,A)}{H(D)}$ ，表示为信息增益g(D,A)与训练数据集D的经验熵H(D)的比值。这是为了矫正训练数据集经验熵大小对于信息增益的影响。

ID3算法

决策树基础——在决策树各个结点上应用最大信息增益的原则选择特征，构建决策树。从根结点开始，计算全部可能的特征的信息增益，选择最大的特征作为节点分类的特征，分类，形成子结点；递归，直到信息增益均很小或者没有特征可以选择为止。ID3相当于极大似然估计法进行概率模型的选择。

注：每个特征只能用一次作为分类特征。

缺点：容易过拟合。

C4.5算法

在ID3的基础上用信息增益比来选择特征，克服了用信息增益选择属性是偏向选择取值多的属性的不足。

剪枝（pruning）

通过剪枝来简化决策树，防止过拟合。剪枝（当 $\alpha$ 确定时）通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。

损失函数： $C_{\alpha }(T)=\sum_{t=1}^T N_{t}H_{t}(T)+\alpha|T|$

其中经验熵： $H_{t}(T)=-\sum_{k} \frac{N_{tk}}{N_{t}}log\frac{N_{tk}}{N_{t}}$

将等式 $C_{\alpha }(T)$ 右边第一项记为： $C(T)=-\sum_{t=1}^{|T|} \sum_{k=1}^{K} N_{tk}log\frac{N_{tk}}{Nt}$

此时 $C_{\alpha }(T)=C(T)+\alpha|T|$ ，C(T)表示训练数据的预测误差，|T|表示模型复杂度， $\alpha$ 用来平衡两者的影响。 $\alpha$ 越大越倾向于选择简单的模型树。

注：|T|为树T的叶结点个数，t是叶结点（上有 $N_{t}$ 个样本点，其中k类的样本点有 $N_{tk}$ 个， $k\in [1,K]$ ）， $H_{t}(T)$ 是叶结点t上的经验熵， $\alpha \geq 0$ 为参数。

剪枝算法流程：输入T和 $\alpha$ ，输出修剪后的子树 $T_{\alpha}$ 。

1）计算每个节点的经验熵。

2）递归地从叶结点向上回缩。设一组叶结点回缩到其父结点之前和之后的整体树分别为 $T_{B}$ 和 $T_{A}$ ，对应的损失函数值 $C_{\alpha}(T_{B})$ 和 $C_{\alpha}(T_{A})$ ，如果 $C_{\alpha}(T_{A})\leq C_{\alpha}(T_{B})$ ，则剪枝，将父结点变为新的叶结点。

3）返回2），直至不能继续为止，得到 $C_{\alpha}$ 最小的子树 $T_{\alpha}$ 。

注：剪枝的过程的损失函数计算是局部的，所以可以用动态规划方法解决。

CART算法

CART——分类与回归树（Classification And Regression Tree），既可用于分类，也可用于回归。最大的特点是决策树是二叉树，内部结点特征的取值为“是”或“否”，递归地二分每个特征，将输入空间（即特征空间）划分为有限个单元，在单元上确定预测的概率分布。

步骤：

1）决策树生成：尽量大的生成树。

2）决策树剪枝：用验证数据集对树进行剪枝。

一、CART决策树生成

——递归地构建二叉决策树的过程。

特征选择

- 回归树：平方误差最小化方法。

- 分类树：基尼指数（Gini index）最小化方法。

1、回归树生成

输入数据集：D={(x1,y1),(x2,y2),……,(xn,yn)}，X是输入变量，Y是输出连续变量。

输出：回归树f(x)

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

1）选择最优切分变量j与切分点s，求解 $min_{j,s}[min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{I}-c_{1})^{2}+min_{c_{2}}\sum_{x_{i}\in R_{2}(j,s)}(y_{I}-c_{2})^{2}]$ 。遍历变量j，对固定的切分变量j扫描切分点s，选择使该式达到最小值的对(j,s)。

2）用选定的对(j,s)划分区域并决定相应的输出值： $R_{1}(j,s)=\left\{ x|x^{(j)}\leq s \right\}, \ R_{2}(j,s)=\left\{ x|x^{(j)}>s \right\}\\ \hat{c}_{m}=\frac{1}{N_{m}}\sum_{x_{i}\in R_{m}(j,s)}y_{i},\ \ x\in R_{m},\ \ m=1,2$

3）继续对两个子区域调用步骤1）～2），直至满足停止条件。

4）将输入空间划分为M个区域 $R_{1},R_{2},……,R_{M}$ ，生成决策树： $f(x)=\sum_{m=1}^M \hat{c}_{m} I(x\in R_{m})$ 。

2、分类树生成

基尼指数：假设有K个类，样本点属于第k类的概率为 $p_{k}$ ，则概率分布的基尼指数定义为 $Gini(p)=\sum_{k=1}^K p_{k} (1-p_{k})=1-\sum_{k=1}^{K} p_{k}^{2}$ 。

对于二分类问题，若样本点属于第一个类的概率是p，则Gini(p)=2p(1-p)。

对于给定的样本集合D， $Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_{k}|}{|D|} )^{2}$ ，其中 $C_{k}$ 是D中属于第k类的样本子集，K是类的个数。

如果D根据特征A是否取某一可能只a被分割成D1和D2两部分，即 $D_{1}=\left\{ (x,y)\in D | A(x)=a \right\},\ \ \ D_{2}=1-D_{1}$ ，则在特征A的条件下，集合D的基尼指数定义为： $Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+ \frac{|D_{2}|}{|D|}Gini(D_{2})$ 。

Gini(D)表示集合D的不确定性，Gini(D,A)表示经过A=a分割后集合D的不确定性，与熵相似，Gini越大，样本的不确定性越强。

生成分类树算法：

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

输出：CART决策树。

从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树。

1）计算现有特征对该数据集的基尼指数，再对每一个特征A，取可能的a，根据样本点对A=a的测试将D分割为D1和D2，计算A=a时的基尼指数。

2）在所有可能的特征A及其切分点a中，选取基尼指数最小的特征&切分点作为最优，依此将现结点生成两个子结点。

3）递归地对子结点调用1）和2），直至满足停止条件。

4）生成CART决策树。

注：停止条件一般为结点中的样本个数小于预定阈值或者样本集的基尼指数小于预定阈值（说明此时样本基本属于同一类），或者没有更多特征。

以图为例：

数据集D

题目&CART树特征选择

二、CART决策树剪枝

步骤

1、剪枝--->形成子树序列 $T_{0},T_{1},……,T_{n}$

损失函数 $C_{\alpha}(T)=C(T)+\alpha|T|$ ，在 $\alpha$ 固定时，一定存在使 $C_{\alpha}(T)$ 最小的子树。递归的方法进行剪枝，将 $\alpha$ 从0增大至 $+\infty$ ，产生一系列的区间 $[a_{i},a_{i+1})$ ，剪枝得到的最优子树序列 $\left\{ T_{0},T_{1},T_{2},……,T_{n} \right\}$ 。具体地，从 $T_{0}$ 开始剪枝，对内部结点t，以t为单结点的损失函数是 $C_{\alpha}(t)=C(t)+\alpha$ ，而以t为根结点的子树 $T_{t}$ 的损失函数为 $C_{\alpha}(T_{t})=C(T_{t})+\alpha|T_{t}|$ 。当 $\alpha$ 很小时， $C_{\alpha}(T_{t})<C_{\alpha}(t)$ ，增大的过程中会存在 $C_{\alpha}(T_{t})=C_{\alpha}(t)$ 的一刻，之后不等式翻转。所以当 $\alpha=\frac{C(t)-C(T_{t})}{|T_{t}|-1}$ 时，Tt和t具有相同的损失函数值。为此，对T0种每一个内部结点t，计算 $g(t)=\frac{C(t)-C(T_{t})}{|T_{t}|-1}$ ，这表示剪枝后整体损失函数减少的程度。在T0中减去g(t)最小的Tt，得到的子树为T1，同时将最小的g(t)设为 $\alpha_{1}$ ，T1则是 $[\alpha_{1},\alpha_{2})$ 区间的最优子树。

2、对子树序列进行交叉验证选取最优子树 $T_{\alpha}$ ：利用独立的验证数据集，测试子树序列中各棵子树的平方误差/基尼指数，最小的决策树被认为是最优的子树，对应的 $\alpha$ 也随之确定了，即得到了最优决策树 $T_{\alpha }$ 。

CART剪枝算法

输入：CART生成决策树T0。

输出：最优决策树 $T_{\alpha}$ 。

1）设k=0，T=T0， $\alpha=+\infty$ 。

2）自下而上地对内部结点t计算C(Tt)，|Tt|以及g(t)和 $\alpha=min(\alpha,g(t))$ 。

3）自上而下地访问内部结点t，如果有 $g(t)=\alpha$ ，则剪枝，并对t以多数表决的形式决定类，得到树T。

4）k=k+1， $\alpha_{k}=\alpha$ ， $T_{k}=T$ 。

5）如果T不是由根结点单独构成的树，回到4）。

6）交叉验证 $\left\{ T_{0},T_{1},T_{2},……,T_{n} \right\}$ 选取最优子树 $T_{\alpha}$ 。

预剪枝/后剪枝

预剪枝：在树的构建过程（只用到训练集），设置一个阈值（样本个数小于预定阈值或GINI指数小于预定阈值），使得当在当前分裂节点中分裂前和分裂后的误差超过这个阈值则分列，否则不进行分裂操作。

后剪枝：在用训练集构建好一颗决策树后，利用测试集进行的操作。

比较：

1）前剪枝的阈值设定很敏感，小变动会引起整颗树大变动，难设定。

2）前剪枝生成比后剪枝简洁的树。

3）一般用后剪得到的结果比较好。

常见后剪枝算法

REP（Reduced-Error Pruning 错误率降低剪枝）：对于完全决策树中的每一个非叶子节点的子树，采取多数表决的原则尝试着把它替换成一个叶子节点，然后比较简化后的决策树和原树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，那么该子树就可以替换成叶子节点。该算法自底向上遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。缺点是可能过度修剪（这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过）。因此，如果训练集较小，不使用REP。

PEP（Pessimistic-Error Pruning 悲观剪枝）：无需测试数据集，应用于C4.5决策树。

CCP（Cost-Complexity Pruning 代价复杂度剪枝）：无需测试数据集，应用于CART决策树。

MEP（Minimum-Error Pruning 最小错误剪枝）

CVP（Critical-Value Pruning）

OPP（Optimal Pruning）

CSDTP（Cost-Sensitive Decision Tree Pruning）

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

决策树

特点