统计学习方法笔记之决策树

更多文章可以访问我的博客Aengus | Blog

决策树的概念比较简单，可以将决策树看做一个if-then集合：如果“条件1”，那么...。决策树学习的损失函数通常是正则化后极大似然函数，学习的算法通常是一个递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。可以看出，决策树算法一般包含特征选择，决策树的生成与决策树的剪枝过程。

特征选择

信息增益

熵和条件熵

在了解信息增益之前需先给出熵和条件熵的定义。

熵代表随机变量不确定性的度量，设在一个有限个值的离散随机变量，其概率分布为
$P(X=x_i) = p_i, i=1,2,\cdots,n$
则随便变量 $X$ 的熵定义为
$H(X) = - \sum^n_{i=1}p_i \log p_i$
如果 $p_i=0$ ，则定义 $0\log 0=0$ ；对数一般取以2为底或者以 $e$ 为底，这时候熵的单位分别称作比特（bit）和纳特（nat）。由定义可知，熵只依赖于 $X$ 的分布，而和 $X$ 的取值无关，因此也可以将 $X$ 的熵记作 $H(p)$ ，即：
$H(p) = - \sum^n_{i=1}p_i \log p_i$
熵越大，随机变量的不确定性就越大，根据定义可以得到：
$0 \leq H(p) \leq \log n$
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下，随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵 $H(Y|X)$ ，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y|X) = \sum^n_{i=1}p_iH(Y|X=x_i)$
其中， $p_i=P(X=x_i), i=1,2, \cdots, n$ 。

当熵和条件熵中的概率由数据估计（尤其是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。

定义

信息增益表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

特征 $A$ 对训练集 $D$ 的信息增益 $g(D,A)$ ，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即
$g(D|A) = H(D)-H(D|A)$
一般来说，熵 $H(Y)$ 与条件熵 $H(Y|X)$ 之差称作互信息。

根据信息增益选择特征的方法是选择信息增益最大的特征。

信息增益算法

对于给定的训练集 $D$ 和特征 $A$ ，计算特征 $A$ 对于训练集 $D$ 的信息增益 $g(D,A)$ 一般有以下步骤：

（1）计算数据集 $D$ 的经验熵 $H(D)$ ：
$H(D) = - \sum^K_{k=1} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$
（2）计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$ ：
$H(D|A)=\sum^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=- \sum^n_{i=1}\frac{|D_i|}{|D|}\sum^K_{k=1}\frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$
（3）计算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以校正这一问题。

定义

对于给定的训练集 $D$ 和特征 $A$ ，特征 $A$ 对于训练集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比，即：
$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$
其中， $H_A(D)=- \sum^n_{i=1} \frac{|D_i|}{|D|} \log_2\frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的个数。

决策树的生成

ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益选择特征，递归的构建决策树。ID3相当于用极大似然法进行概率模型的选择。

假设输入训练数据集 $D$ ，特征集 $A$ 和阈值 $\varepsilon$ ，按照以下步骤求得决策树 $T$ ：

（1）如果 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（2）若 $A=\varnothing$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（3）否则，按照信息增益的算法计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；

（4）如果 $A_g$ 的信息增益小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类作为该结点的类标记，返回 $T$ ；

（5）否则，对 $A_g$ 的每一个可能值 $a_i$ ，依 $A_g=a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；

（6）对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A-\{A_g \}$ 为特征集，递归地调用（1）~（5）步，得到子树 $T_i$ 并返回；

C4.5算法

C4.5算法和ID3算法类似，不过是用信息增益比替换掉了信息增益；

假设输入训练数据集 $D$ ，特征集 $A$ 和阈值 $\varepsilon$ ，按照以下步骤求得决策树 $T$ ：

（1）如果 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（2）若 $A=\varnothing$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；

（3）否则，按照信息增益比的算法计算 $A$ 中各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_g$ ；

（4）如果 $A_g$ 的信息增益比小于阈值 $\varepsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类作为该结点的类标记，返回 $T$ ；

（6）对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A-\{A_g \}$ 为特征集，递归地调用（1）~（5）步，得到子树 $T_i$ 并返回；

可以看到两个算法除了加粗的部分，其他部分都一样。

决策树的剪枝

决策树生成算法递归的产生决策树直到不能继续下去为止，这样的树往往对训练数据分类比较准确，但是对未知的测试数据往往没那么精准，即出现过拟合现象。对于这种情况可以将决策树进行简化，也被称为决策树的剪枝。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树 $T$ 的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k=1, 2, \cdots, K$ ， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha \geq0$ 为参数，则决策树学习的损失函数可以定义为：
$C_\alpha (T) = \sum^{|T|}_{t=1}N_t H_t(T)+\alpha |T|$
其中经验熵为：
$H_t(T) = -\sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$
在损失函数中，将损失函数右端的第一项记作
$C(T) = \sum^{|T|}_{t=1}N_t H_t(T) = -\sum^{|T|}_{t=1} \sum^K_{k=1}N_{tk} \log \frac{N_{tk}}{N_t}$
这时有
$C_\alpha(T) = C(T)+\alpha|T|$
剪枝就意味着当 $\alpha$ 确定时，选择损失函数最小的模型，即损失函数最小的子树（ $\alpha$ 较大时促使选择比较简单的模型，较小时促进选择复杂的模型）。

剪枝算法

输入生成的决策树 $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），直至不能继续为止，得到损失函数最小的子树 $T_\alpha$ ；

CART算法

分类与回归树（classification and regression tree, CART）模型是应用广泛的决策树学习方法，CART同样由特征选择、树的生成以及剪枝组成，既可以用于分类也可以用于回归。

CART是在给定输入随机变量 $X$ 的条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值是“是”或“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。CART算法由以下两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准；

CART生成

对于回归树用平方误差最小化准则，对分类树用基尼指数最小化准则进行特征选择，生成二叉树。

回归树的生成

一颗回归树对应着输入空间的一个划分以及在划分单元上的输出值。假设将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为：
$f(x) = \sum^M_{m=1}c_m I(x \in R_m)$
当输入空间的划分确定时，可以用用平方误差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知单元 $R_m$ 上的 $c_m$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
$\hat{c}_m = ave(y_i|x_i \in R_m)$
问题是怎样对输入空间进行划分，也就是如何选择划分结点：

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

（1）选择第 $j$ 个变量 $x^{(j)}$ 和它取的值 $s$ 作为划分变量和划分点，并定义两个区域：
$R_1(j,s) = \{ x|x^{(j)} \leq s \},R_2(j,s)=\{ x|x > s \}$
然后寻找最优划分变量 $j$ 和最优划分点 $s$ ，具体的，求解：
$\min_{j,s} \left[ \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 \right]$
遍历变量 $j$ ，对固定的划分变量 $j$ 扫描切分点 $s$ ，选择式上式达到最小值的 $(j,s)$ ；

（2）用选定的 $(j,s)$ 划分区域 $R_1,R_2$ 并决定相应的输出值：
$R_1(j,s) = \{ x|x^{(j)} \leq s \},R_2(j,s)=\{x|x^{(j)} > s\}$

$\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）继续对 $R_1,R_2$ 两个子区域调用步骤（1），（2），直到满足停止条件；

（4）将输入空间划分为 $M$ 个区域 $R_1,R_2,\cdots,R_M$ ，生成决策树：
$f(x) = \sum^M_{m=1}\hat{c}_m I(x \in R_m)$

分类树的生成

基尼指数：在分类问题中，假设有 $k$ 个类，样本点属于第 $k$ 类的概率是 $p_k$ ，则概率分布的基尼指数定义为：
$Gini(p) = \sum^K_{k=1}p_k(1-p_k) = 1 - \sum^K_{k=1}p_k^2$
对于二分类问题，若样本点属于第一个分类的概率为 $p$ ，则概率分布的基尼指数为：
$Gini(p) = 2p(1-p)$
对于给定的样本集合 $D$ ，其基尼指数为：
$Gini(D) = 1-\sum^K_{k=1}(\frac{|C_k|}{|D|})^2$
这里， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。

如果样本集合 $D$ 根据特征 $A$ 是否取值 $\alpha$ 被分割成 $D_1$ 和 $D_2$ 两部分，即：
$D_1 = \{ (x,y) \in D|A(x)=\alpha \},D_2 = D - 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=\alpha$ 分割后集合 $D$ 的不确定性。基尼指数越大代表不确定性程度越大。

假设输入训练数据集 $D$ 以及停止计算的条件，根据训练集，从根结点开始，递归地对每个结点进行以下操作，构建决策树：

（1）计算现有特征对训练数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $\alpha$ ，根据样本点对 $A=\alpha$ 的测试为“是”或“否”，将 $D$ 分为 $D_1$ 和 $D_2$ 两部分，利用上式计算 $A=\alpha$ 的基尼指数；

（2）对所有可能的特征 $A$ 以及他，他们所有可能的切分点 $\alpha$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练集依特征分配到两个子结点去；

（3）对两个子结点递归调用（1）和（2）步骤，直至满足停止条件；

（4）生成CART决策树；

算法停止的条件是结点中样本个数小于预定阈值或者样本的基尼指数小于预定阈值（此时此结点上的样本基本属于同一类），或者没有更多特征。

CART剪枝

输入为CART算法生成的决策树 $T_0$ ，输出为最优决策树 $T_\alpha$ ，步骤如下：

（1）设 $k=0,T=T_0$ ；

（2）设 $\alpha= + \infty$

（3）自下而上地对各内部结点 $t$ 计算 $C(T_t)$ ， $|T_t|$ 以及
$g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1} \\ \alpha = \min (\alpha, g(t))$
这里， $T_t$ 表示以 $t$ 为根结点的子树， $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 是 $T_t$ 的叶结点个数；

（4）对 $g(t)=\alpha$ 的内部结点 $t$ 进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ ；

（5）设 $k=k+1,\alpha_k=\alpha,T_k=T$ ；

（6）如果 $T_k$ 不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则令 $T_k=T_n$ ；

（7）采用交叉验证法在子树序列 $T_0,T_1,\cdots,T_n$ 中选取最优子树 $T_\alpha$ ；

参考

李航《统计学习方法（第二版）》第五章

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