决策树

决策树是一种基本分类与回归方法。其不要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修建。这些决策树学习的思想主要来源Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及Breiman等人在1984年提出的CART算法。

一、决策树模型与学习

1.决策树模型

分类决策树是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node),内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点：这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试，直至达到叶结点。最后将实例分到叶结点的类中。

2.决策树与if-then规则

可以将决策树看成一个if-then规则，将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则：路径上与内结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。每一条实例都被一条路径或一条规则所覆盖，而且仅被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

3.决策树学习

假设给定训练数据集 $D=\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$
其中, $x_i=(x_i^{(1)},x_i^{(2)},\dots,x_i^{(N)})^T$ 为输入实例（特征向量），n为特征个数， $y_i \in \{1,2,\dots,K\}$ ，N为样本容量。决策树学习的目标是根据给定训练集构建一个决策树模型，使它能够对实例进行正确地分类。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据集进行正确分类的决策树可能有多个），也有可能一个也没有。我们需要的是与一个训练数据矛盾教小的决策树，同时具有很好的泛化能力。

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

当损失函数确定以后，学习问题就变成为在损失函数意义下选择最优决策树的问题，因为从所有可能的决策树选取最优决策树是NP完全问题，所以现实中决策树问题算法通常采用启发式方法，近似求解这一个最优化问题，得到的决策树是次最优的。

二、特征选择

特征选择在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征没有分类能力。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

1.信息增益

为了便于说明，先给出熵与条件熵的定义。
在信息论中，熵(entropy)是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为
$P(X=x_i)=p_i,i=1,2,\dots,n$
则随机变量X的熵定义为
$H(X)=-\sum_{i=1}^Np_i log\,p_i\space(2.1)$
(2.1)式中的对数以2为底或以e为底（自然对数），这时熵的单位分别称为比特(bit)或纳特（nat）。由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可以将X的熵记作H(p)，即
$H(p)=-\sum_{i=1}^n p_i log \space p_i$
熵越大，随机变量的不确定性越大。从定义上可验证
$0 \leq H(p) \leq log \, n$
当随机变量只取1,0是，即X的分布为
$P(X=1)=p,P(X=0)=1-p,0 \leq p \leq 1$
熵为
$H(p) = -plog_2\, p -(1-p)log_2\, (1-p)$

分布为伯努利时熵与概率分关系.png

当p=0或p=1时，H(P)最大，随机变量完全没有不确定性。当p=0.5时，H(p)=1,熵取最大，随机变量不确定性最大。

设随机变量(X,Y)，其联合概率分布为
$P(X=x_i,Y=y_i)=p_{ij},i=1,2,\dots;j=1,2,\dots,m$
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
$\begin{align}H(Y|X)=\sum_{i=1}^N p_i H(Y|X=x_i) \\ =\sum_{x\in X}p(x)\Bigg[-\sum_{y \in Y}p(y|x)log\,p(y|x)\Bigg] \\ =-\sum_{x \in X}\sum_{y \in Y}p(x,y)log\,p(y|x) \end{align}$
这里， $p_i=P(X=x_i),i=1,2,\dots,n$
当熵和条件概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。

信息增益(information gain)表示得知特征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)之差称为互信熵(mutual information)。决策树学习中的信息增益等价于训练数据中类与特征的互信熵
.
决策树学习应用信息增益准则选择特征，给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性，而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D分类的不确定性减少的程度。显然，对数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

设训练数据集为D，|D|表示样本容量，即样本个数。设有K个类 $C_k$ ， $k=1,2,\dots,K,|C_k|$ 表示属于类 $C_k$ 的样本个数， $\sum_{k=1}^K |C_k| = |D|$ 。设特征A有n个不同的取值 ${a_1,a_2,\dots,a_n}$ ，根据特征A的取值将D划分为n个子集， $D_1,D_2,\dots,D_n$ ， $|D_i|$ 表示样本个数， $\sum_{i=1}^n|D_i|=D$ ，记子集 $D_i$ 中属于类 $C_k$ 的样本集合为 $D_{ik}$ ，即 $D_{ik}=D_i \cap C_k$ 为$D_{ik}的样本个数，于是信息增益算法如下
输入：训练数据集D合特征A；
输出：特征A对训练集D的信息增益g(D,A)
(1)计算数据集D的经验熵H(D）
$H(D)=\sum_{i=1}^K\frac{|C_k|}{|D|}log_2 \frac{|C_K|}{|D|}$
(2)特征A对数据集D的经验条件熵
$\begin{align} H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i) \\ =-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}log_2\,\frac{|D_{ik}|}{|D_i|} \end{align}$
(3)计算信息增益
g(D,A)=H(D)-H(D|A)

2.信息增益比

信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。

信息增益比特征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_{i=1}^n\frac{|D_i|}{|D|}log_2\,\frac{|D_i|}{|D|}$ ,n是特征A取值的个数。

3.基尼指数

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

对于二分类问题，若有黑人点属于第1个类的概率是p，则概率分布的基尼指数为
$Gini(p)=2p(1-p)$
对于给定的样本集合D，其基尼指数为
$Gini(D) = 1 - \sum_{k=1}^K\Bigg(\frac{|C_k|}{|D|}\Bigg)^2$
其中， $C_k$ 是属于第k类的样本子集，K是类的个数

如果样本集合D根据特征A是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征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的不确定性。基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。

二分类中基尼指数-熵之半和分类误差率关系.png

三、决策树的生成

1.ID3算法

ID3算法的核心在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，构建决策树：直到所有的特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择。

ID3算法
输入:训练集D，特征集A阈值 $\epsilon$
输出:决策树
(1)若D中所有实例属于同一类 $C_k$ ，则T为单结点树，并将类 $C_k$ 作为该结点的类标记，返回T
(2)若 $A = \varnothing$ ，则T为单结点树，并将D中实例树最大的类 $C_k$ 作为该结点的类标记，返回T
(3)否则，按ID3算法计算各特征对D的信息增益，选择信息增益最大的特征 $A_g$
(4)如果 $A_g$ 的信息增益小于阈值 $\epsilon$ ，则置T为单结点树，并将D中实例数最大的类 $C_k$ 作为该结点的类标记，返回T
(5)否则，对 $A_g$ 的每一个可能值 $a_i$ ，依 $A_g=a_i$ 将D分割为若干非空子集 $D_i$ ，将 $D_i$ 中的类 $C_k$ 作为该结点的类标记，返回T
(6)对第i个子结点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归地调用步(1)~步(5)，得到子树 $T_i$ ，返回 $T_i$

2.C4.5算法

C4.5在生成的过程中，用信息增益比来选择特征。

C4.5算法
输入:训练集D，特征集A阈值 $\epsilon$
输出:决策树
(1)若D中所有实例属于同一类 $C_k$ ，则T为单结点树，并将类 $C_k$ 作为该结点的类标记，返回T
(2)若 $A = \varnothing$ ，则T为单结点树，并将D中实例树最大的类 $C_k$ 作为该结点的类标记，返回T
(3)否则，按C4.5算法计算各特征对D的信息增益，选择信息增益最大的特征 $A_g$
(4)如果 $A_g$ 的信息增益小于阈值 $\epsilon$ ，则置T为单结点树，并将D中实例数最大的类 $C_k$ 作为该结点的类标记，返回T
(5)否则，对 $A_g$ 的每一个可能值 $a_i$ ，依 $A_g=a_i$ 将D分割为若干非空子集 $D_i$ ，将 $D_i$ 中的类 $C_k$ 作为该结点的类标记，返回T
(6)对第i个子结点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归地调用步(1)~步(5)，得到子树 $T_i$ ，返回 $T_i$

3.CART算法

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

（1）回归树生成

假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集
$D=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$
一棵回归树对应着输入空寂（即特征空间）的一个划分及在划分的单位上的输出值，假设已将输入空间划分为M个单元 $R_1,R_2,\dots,R_M$ ，并且每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树表示为
$f(x)=\sum_{m=1}^mc_mI(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)$

最小二乘回归树
问题是怎么样对输入空间进行划分，这里采用启发式方法，选择第j个变量 $x^{(j)}$ 和他的取值s，作为切分变量(splitting variable)和切分点(splitting point)，并定义两个区域
$R_1(j,s) = \{ x |x^{(j)} \leq s \} 和 R_2(j,s) = \{ x |x^{(j)} \geq s \}$
然后寻找最优切分变量j和切分点s，具体地求解
$\mathop{min}_{j,s}\Bigg[ \mathop{min}_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \mathop{min}_{c_2}\sum_{x_i \in R_2(j,s)} (y_i - c_2)^2\Bigg]$
对固定输入j可以划分最优切分点s
$\hat c_1 = ave(y_i|x_i \in R_1(j,s)) 和 \hat c_1 = ave(y_i|x_i \in R_1(j,s))$

遍历所有输入变量，找到最优的切分变量j，构成一对(j,s)。依次将此输入变量划分成两个区域。接着对每个区域重复上述划分过程，直到满足停止条件为止，这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树(least squares regression)

（2）分类树

输入:训练集D，停止计算条件
输出:CART决策树
(1)设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值 $a$ ，根据样本点对 $A=a$ 的测试为"是"或"否"，将D分割成 $D_1和D_2$ 两部分，计算 $A=a$ 此时的基尼指数
(2）在所有可能的特征A以及所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去
(3)对两个子结点递归调用(1),(2)，直至满足停止条件
(4)生成CART决策树

四、决策树剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据却没那么准确，即出现了过拟合现象。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，将训练数据中的噪音也学习了，从而构建出过于复杂的决策树。

在决策树学习中将已生成的树进行简化的过程称为减枝(pruning)，具体地，剪枝从已生成的树减掉一些子树或叶结点，并将其根结点作为新的叶结点从而简化分类树模型。

决策树剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现，设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有 $N_t$ 个样本，其中k类的样本点有 $N_{tk}$ 个， $k=1,2,\dots,K$ ， $H_t(T)$ 为叶结点t上的经验熵， $a \leq 0$ 为参数，则决策树学习的损失函数可以定义为
$C_a(T)=\sum_{t=1}^{|T|}N_tH_t(T)+a|T| \space(4.1)$
其中经验熵为
$H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
在损失函数中，将(4.1)右端的第1项记作
$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t} \space (4.2)$
这时有
$C_a(T)=C(T)+a|T| \space(4.3)$
式(4.3)， $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， $|T|$ 表示模型复杂度，参数 $a \leq 0$ 控制两者之间的影响，较大的 $a$ 促使选择教简单的模型(树)，较小的 $a$ 促使选择教复杂的模型(树)， $a=0$ 意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

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

决策树