机器学习算法深度总结(6)-决策树

Decision Trees (DTs) 是一种用来classification和regression的无参监督学习方法。其目的是创建一种模型从数据特征中学习简单的决策规则来预测一个目标变量的值。

分类决策树由节点和有向边组成, 结点有内部结点和叶结点. 内部结点表示一个特征或属性, 叶结点表示一个类.

例如，在下面的图片中，决策树通过if-then-else的决策规则来学习数据从而估测数一个正弦图像。决策树越深入，决策规则就越复杂并且对数据的拟合越好。

决策树的优势:

便于理解和解释。树的结构可以可视化出来。
训练需要的数据少。其他机器学习模型通常需要数据规范化，比如构建虚拟变量和移除缺失值,不过请注意，这种模型不支持缺失值。
由于训练决策树的数据点的数量导致了决策树的使用开销呈指数分布(训练树模型的时间复杂度是参与训练数据点的对数值)。
= 能够处理数值型数据和分类数据。其他的技术通常只能用来专门分析某一种变量类型的数据集。详情请参阅算法。
能够处理多路输出的问题。
使用白盒模型。如果某种给定的情况在该模型中是可以观察的，那么就可以轻易的通过布尔逻辑来解释这种情况。相比之下，在黑盒模型中的结果就是很难说明清楚地。
可以通过数值统计测试来验证该模型。这对事解释验证该模型的可靠性成为可能。
即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好。

决策树的缺点包括:

决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。
决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解
在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。
有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。
如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

主要的决策树算法有ID3算法、C4.5算法和CART算法。

分类:
例如, 用经典数据集iris训练决策树, 预测鸢尾花卉种类:

回归:
决策树也可以用来解决回归问题, 预测结果为概率值:

决策树学习算法通常包含特征选择, 决策树生成和剪枝三个步骤.

1. 特征选择

特征选择的准则是信息增益或信息增益比, 特征选择决定用哪个特征划分特征空间.
几个基本概念:
信息增益
熵表示随机变量的不确定性度量, 随机变量X(离散, 且 $P(X=x_i)=p_i$ 的熵定义为:
$H(X) = H(P) = -\sum_{i=1}^np_i\log p_i$
若上式 $\log$ 以2为底, 单位比特; 熵越大, 随机变量不确定性越大; p=0.5时, 熵最大(=1), 不确定性最大

条件熵:
条件熵 $H(Y|X)$ 表示随机变量X的条件下Y的不确定性, 定义为X条件下Y的条件概率分布的熵对X的数学期望:
$H(Y|X)= \sum_{i=1}^np_iH(Y|X = x_i)$

经验熵和经验条件熵
若H(X)和H(Y|X)中的概率若用极大似然估计得到, 则分别称为经验熵和经验条件熵.

信息增益
熵和条件熵之差称为信息增益, 表示得知特征X,则Y的不确定性减少的程度. 注, 决策树中默认熵和条件熵分别是经验熵和经验条件熵, 下同.

特征A对训练集D的信息增益g(D,A):
$g(D,A) = H(D)-H(D|A)$

信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。
信息增益比表示特征A对训练数据集D的信息增益比。gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即：
$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$

基尼系数
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼系数定义为：
$Gini(p) = \sum_{k=1}^kp_k(1-p_k) = 1-\sum_{k=1}^kp_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 = \{(x,y) \in D|A(x) = a\}, 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的不确定性，表示经A=a分割后集合D的不确定性。基尼系数越大，样本集合的不确定性越大，与熵类似。
从下图可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率。

信息增益计算方法
设训练集为D, |D|表示样本个数, 设有K个类 $C_k$ , $k=1,2,\cdots, K$ , $|C_k|$ 为属于类 $C_k$ 的样本个数, $\sum_{k=1}^k|C_k|=|D|$ ,.
设特征A有n个不同的取值 $\{a_1, a_2, \cdots, a_n\}$ , 根据特征A取值, 将D划分为n个子集 $D_1, D_2, \cdots, D_n$ , $|D_i|$ 为 $D_i$ 的样本个数, $\sum_{i=1}^n|D_i|=|D|$ .
记子集 $D_i$ 中属于类 $C_k$ 的样本集合为 $D_{ik}$ , 即 $D_{ik}=D_i \bigcap C_k$ , $|D_{ik}|$ 为 $D_{ik}$ 的样本个数, 于是信息增益的算法如下:

(1) 计算数据集D的经验熵H(D)
$H(D) = -\sum_{k=1}^k\frac{|C_k|}{|D|}log2\frac{|C_k|}{|D|}$
(2) 计算特征A对数据集D的经验条件熵H(D|A)
$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|}$
(3) 计算信息增益
$g(D,A) = H(D)-H(D|A)$
根据信息增益准则的特征选择方法是: 对训练数据集D, 计算每个特征的信息增益, 并比较他们的大小, 选择信息增益最大的特征.

2. 决策树的生成

常见的决策树算法: ID3, C4.5, C5.0 和 CART, 所有种类的决策树算法有哪些以及它们之间的区别？

ID3（Iterative Dichotomiser 3）由 Ross Quinlan 在1986年提出。该算法创建一个多路树，找到每个节点（即以贪心的方式）分类特征，这将产生分类目标的最大信息增益。决策树发展到其最大尺寸，然后通常利用剪枝来提高树对未知数据的泛化能力。

C4.5 是 ID3 的后继者，并且通过动态定义将连续属性值分割成一组离散间隔的离散属性（基于数字变量），消除了特征必须被明确分类的限制。C4.5 将训练的树（即，ID3算法的输出）转换成 if-then 规则的集合。然后评估每个规则的这些准确性，以确定应用它们的顺序。如果规则的准确性没有改变，则需要决策树的树枝来解决。

C5.0 是 Quinlan 根据专有许可证发布的最新版本。它使用更少的内存，并建立比 C4.5 更小的规则集，同时更准确。

CART（Classification and Regression Trees （分类和回归树））与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构造二叉树。

1. ID3算法

ID3算法核心: 在决策树各节点上用信息增益准则选择特征, 递归地构建决策树.
从根节点开始, 对结点计算所有可能的信息增益, 选择信息增益最大的特征作为结点特征,由该结点不同却只建立子结点; 再对子节点递归调用以上方法构建决策树, 知道所有特征的信息增益均很小或没有特征可以选择为止. 最后, 得到一个决策树.
ID3相当于用极大似然法进行概率模型的选择.

算法步骤如下:

ID3算法只有树的生成, 生成的树容易过拟合.

2. C4.5算法

与ID3算法相似，C4.5算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征.

3. CART

分类树与回归树（classification and regression tree，CART）模型（Breiman）既可用于分类也可用于回归。

CART是给定输入随机变量X条件下输出Y的条件概率分布的学习方法, 主要分决策树生成和决策树剪枝.

决策树生成: 是递归构建二叉决策树的过程
特征选择: 回归树用平方误差最小化准则, 分类树用基尼系数最小化准则, 禁行特征选择, 生成二叉树.

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

(1) 选择最优切分变量j与切分点s，求解
$J_s = \underset{j,s}{\min} [\underset{c1}{\min}\sum_{x_j \in R_1(j,s)}(y_i-c_1)^2 + \underset{c_2}{\min}\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) = \{x|x^{(j)} \le s \}, \ R_2(j,s) = \{ x|x^{(j)} > s \}$
各单元上的最优值:
$\hat{c_1} = \frac {1}{N_1}\sum_{x_i \in R_1(j,s)} y_i, \ \hat{c_2} = \frac {1}{N_2}\sum_{x_i \in R_2(j,s)} y_i$
(3) 继续对两个子区域调用步骤(1),(2), 直至满足停止条件。
(4)将输入空间划分为M个区域 $R_1,R_2,\cdots,R_M$ ，生成决策树：
$f(x)= \begin{cases} \hat c_1 & x \le s \\ \hat c_2 & x > s \end{cases}$
每一轮计算, 求解出决策树 $f(x)$ 和训练数据的残差: $r_i = y_i - f(x_i)$ , 假设此时残差满足要求, 则算法停止, 此时的f(x)即为所求的回归树.

分类树生成:
对分类树用基尼系数（Gini index）最小化准则，进行特征选择，生成二叉决策树，其具体步骤如下：

(1) 设节点的训练数据集为, 计算现有特征对该数据集的基尼系数, 对每个特征A, 对其可能的每个取值a, 根据样本点对 $A=a$ 的测试为"Y"或者"N"将D分成 $D_1$ 和 $D_2$ , 计算 $A=a$ 时的基尼系数.
(2) 在所有可能的特征A及它们所有可能的切分点a中, 选择基尼系数最小的特征及其对应的切分点作为最有特征和最有切分点. 从现结点生成两个子结点,将训练数据集根据特征分配到两个子结点中去.
(3) 对两个子结点递归调用(1)(2), 知道满足停止条件.
(4)生成CART决策树.

算法停止的条件时节点中的样本个数小于预定阈值, 或样本集的基尼系数小于预定阈值(即样本基本属于同一类), 或者没有更多的特征.

3. 决策树剪枝

剪枝: 决策树学习中, 将已生成的过于复杂的树进行简化的过程称为剪枝(pruning).
过拟合: 决策树的过拟合指的是学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。

剪枝可以解决决策树过拟合问题, 具体: 去掉细分的叶结点, 使其回退到父结点甚至更高节点, 然后将父结点或更高节点改为新的叶结点.
决策树的生成对应于模型的局部选择, 只考虑局部最优; 决策树的剪枝对应于模型的全局选择, 需考虑全局最优.

决策树剪枝通常通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)实现.

决策树整体损失函数:

设数T的叶结点有 $|T|$ 个, t是树T的叶结点, 该叶结点上游 $N_t$ 个样本点, 其中k类样本点有 $N_tk$ 个, $k=1,2,\cdots,K$
$H_t(T)$ 为叶结点t上的经验熵, $\alpha \ge 0$ 为参数, 则决策树的损失函数定义为:
$C_\alpha(T) = \sum_{t=1}^{|T|}N_t H_t(T) + \alpha|T| \ \ (1)$
其中, 经验熵 $H_t(T)$ :
$H_t(T)= - \sum_{k=1}^K \frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t} \ \ (2)$
将(1)中右边第一项记作 $C(T)$ :
$C(T) = \sum_{t=1}^{|T|}N_t H_t(T) = - \sum_{t=1}^{|T|} \sum_{k=1}^K \frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t} \ \ (3)$
将(3)带入(1), 得决策树学习的损失函数:
$C_\alpha(T) = C(T) + \alpha|T|$
上式 $C_\alpha(T)$ 表示模型对训练数据的预测误差(拟合程度), $|T|$ 表示模型复杂度, 损失函数表示了二者的平衡.
参数 $\alpha \ge 0$ 控制二者间的影响:
(1) 较大的 $\alpha$ 促使选择较简单的模型
(2) 较小的 $\alpha$ 促使选择较复杂的模型
(3) $\alpha=0$ 意味着只考虑模型数据拟合程度, 不考虑模型复杂度
(4) $\alpha$ 确定时, 子树越大, 模型和数据拟合越好, 但模型复杂度高; 反之, 子树越小, 模型复杂度低, 但和数据拟合不好

剪枝说明:

决策树生成只考虑了提高信息增益(或信息增益比), 而决策树剪枝通过优化损失函数, 还考虑了减小模型复杂度.
决策树生成学习局部模型, 决策树剪枝学习整体模型.
上式定义的损失函数极小化等价于正则化的极大似然估计, 所以, 利用损失函数最小原则剪枝就是用正则化的极大似然估计进行模型选择.

树的剪枝算法:

输入: 生成算法产生的整个树, 以及参数 $\alpha$ ;
输出: 修剪后的子树 $T_\alhp$ .
(1) 计算每个结点的经验熵;
(2) 递归地从树的叶结点向上回缩;
设一组叶结点回缩到其父节点前后的整体树分别为 $T_B$ 和 $T_A$ , 对应的损失函数值分别为 $C_\alpha(T_B)$ 和 $C_\alpha(T_A)$ , 假如:
$C_\alpha(T_A) \le C_\alpha(T_B) \ \ (4)$
则进行剪枝, 将父节点变为新的叶结点.
(3) 返回(2), 直至不能继续为止, 得到损失函数最小的子树 $T_\alpha$

注意, 式(4)决策树剪枝只需要考虑两个数的损失函数之差(), 其计算可在局部进行,故可用动态规划算法实现.

决策树剪枝示意图:

决策树的剪枝

最后编辑于：2018.10.09 01:34:38

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