决策树

[TOC]

决策树概述

用于分类时,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布

决策树场景

决策树是通过不停缩小猜测的范围,最后得到答案

如下图:

dt

决策树的定义

决策树由节点node和有向边(directed edge)组成

node有两类,内部节点和叶节点,内部节点表示一个特征(feature), 叶节点表示一个label

决策树的预测

当需要使用决策树对一个目标进行分类时,从根节点开始,对目标的某一特征开始进行测试,

根据测试结果将该目标分配到某一子节点。每一个子节点对应着该特征的一个取值。dfs到达叶节点

选择该叶节点作为预测label

决策树的术语

信息熵又名信息增益

熵: entropy 指的是体系的混乱程度

信息论:information theory 是一种信息的度量方式,表示信息的混乱程度,也就是说:信息越有序,信息熵越低。例如:火柴有序放在火柴盒里,熵值很低,相反,熵值很高。

信息增益:information gain 在划分数据集前后信息发生的变化称为信息增益

entropy

决策树的种类

针对如何生成决策树一般有三类:

https://zhuanlan.zhihu.com/p/30059442

https://blog.csdn.net/xbinworld/article/details/44660339

ID3

会overfitting 因为id3会尝试将错误率通过分割非常细来达到0

C4.5

c4.5对ID3进行了改进,C4.5中,增加的熵要除以分割太细的代价,这个比值叫做信息增益率,显然分割太细分母增加,信息增益率会降低。除此之外,其他的原理和ID3相同

CART

分类回归树

CART只能将一个父节点分为2个子节点。CART用GINI指数来决定如何分裂

GINI指数:总体内包含的类别越杂乱,GINI指数就越大(跟熵的概念很相似)

选择GINI指数最小的开始分

CART还是一个回归树,回归解析用来决定分布是否终止。理想地说每一个叶节点里都只有一个类别时分类应该停止,但是很多数据并不容易完全划分,或者完全划分需要很多次分裂,必然造成很长的运行时间,所以CART可以对每个叶节点里的数据分析其均值方差,当方差小于一定值可以终止分裂,以换取计算成本的降低。

CART和ID3一样,存在偏向细小分割,即过度学习(过度拟合的问题),为了解决这一问题,对特别长的树进行剪枝处理,直接剪掉。

随机森林

概述

首先,从原始的数据集中采取有放回的抽样,构造子数据集,子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复,同一个子数据集中的元素也可以重复。第二,利用子数据集来构建子决策树,将这个数据放到每个子决策树中,每个子决策树输出一个结果。最后,如果有了新的数据需要通过随机森林得到分类结果,就可以通过对子决策树的判断结果的投票,得到随机森林的输出结果了。如下图,假设随机森林中有3棵子决策树,2棵子树的分类结果是A类,1棵子树的分类结果是B类,那么随机森林的分类结果就是A类。

例子

rf

待选特征的随机选取: 与数据集的随机选取类似,随机森林中的子树的每一个分裂过程并未用到所有的待选特征,而是从所有的待选特征中随机选取一定的特征,之后再在随机选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同,提升系统的多样性,从而提升分类性能。

下图中,蓝色的方块代表所有可以被选择的特征,也就是目前的待选特征。黄色的方块是分裂特征。左边是一棵决策树的特征选取过程,通过在待选特征中选取最优的分裂特征(别忘了前文提到的ID3算法,C4.5算法,CART算法等等),完成分裂。右边是一个随机森林中的子树的特征选取过程。

rf_2

http://www.cnblogs.com/pinard/p/6131423.html

#Ensemble learning集成学习

集成学习概念

<pre class="mermaid">graph TD; 个体学习器A1-->强学习器B; 个体学习器A2-->强学习器B; 个体学习器A3-->强学习器B; 个体学习器A4-->强学习器B;</pre>

集成学习是通过训练出若干个个体学习器,通过一定的结合策略,最终形成一个强学习器,达到博采众长的目的

集成学习需要解决的两个问题

1.如何得到若干个个体学习器

2.如何选择一种结合策略,将这些个体学习器集成一个强学习器

个体学习器

个体学习器强依赖关系,需要串行--boosting算法

个体学习器不存在强依赖关系,可以并行—bagging和rf

Boosting

boosting

从图中可以看出,Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1,根据弱学习的学习误差率表现来更新训练样本的权重,使得之前弱学习器1学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.,如此重复进行,直到弱学习器数达到事先指定的数目T,最终将这T个弱学习器通过集合策略进行整合,得到最终的强学习器。

Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)

Bagging

bagging

从上图可以看出,bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样,我们就可以得到T个采样集,对于这T个采样集,我们可以分别独立的训练出T个弱学习器,再对这T个弱学习器通过集合策略来得到最终的强学习器。

对于这里的随机采样有必要做进一步的介绍,这里一般采用的是自助采样法(Bootstap sampling),即对于m个样本的原始训练集,我们每次先随机采集一个样本放入采样集,接着把该样本放回,也就是说下次采样时该样本仍有可能被采集到,这样采集m次,最终可以得到m个样本的采样集,由于是随机采样,这样每次的采样集是和原始训练集不同的,和其他采样集也是不同的,这样得到多个不同的弱学习器。

随机森林是bagging的一个特化进阶版,所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上,又加上了特征的随机选择,其基本思想没有脱离bagging的范畴。

结合策略

平均法

最终的预测是各个弱学习器的平均值

如果弱学习器有权重,则是一个加权平均

投票法

投票法可以有少数服从多数法,绝对票数,以及加权投票

学习法

上两节的方法都是对弱学习器的结果做平均或者投票,相对比较简单,但是可能学习误差较大,于是就有了学习法这种方法,对于学习法,代表方法是stacking,当使用stacking的结合策略时, 我们不是对弱学习器的结果做简单的逻辑处理,而是再加上一层学习器,也就是说,我们将训练集弱学习器的学习结果作为输入,将训练集的输出作为输出,重新训练一个学习器来得到最终结果。

在这种情况下,我们将弱学习器称为初级学习器,将用于结合的学习器称为次级学习器。对于测试集,我们首先用初级学习器预测一次,得到次级学习器的输入样本,再用次级学习器预测一次,得到最终的预测结果。

boosting算法需要解决的问题

  1. 如何计算学习误差率e
  2. 如何得到弱学习器权重系数a
  3. 如何更新样本权重d
  4. 使用何种结合策略

#Adaboosting

  • 样本权重

    • 没有先验知识的情况下,初始的分布为等概分布,即计算集如果有N个样本,每个样本的分布概率为1/N

    • m每次循环后提高误分样本的分布概率,误分样本在训练集中所占的权重增大,使得下一次循环的弱学习器能够集中力量对这些误分样本进行判断

    • 准确率越高的弱学习机权重较高

M1算法

ada

前向逐步递增

优缺点

Adaboost的主要优点有:

1)Adaboost作为分类器时,分类精度很高

2)在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。

3)作为简单的二元分类器时,构造简单,结果可理解。

4)不容易发生过拟合

Adaboost的主要缺点有:

1)对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

GBDT(Gradient Boosting Decision Tree)

GBDT也是集成学习Boosting家族的成员,但是却和传统的Adaboost有很大的不同。回顾下Adaboost,我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重,这样一轮轮的迭代下去。GBDT也是迭代,使用了前向分布算法,但是弱学习器限定了只能使用CART回归树模型,同时迭代思路和Adaboost也有所不同。

在GBDT的迭代中,假设我们前一轮迭代得到的强学习器是ft−1(x)ft−1(x), 损失函数是L(y,ft−1(x))L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)ht(x),让本轮的损失函数L(y,ft(x)=L(y,ft−1(x)+ht(x))L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说,本轮迭代找到决策树,要让样本的损失尽量变得更小。

GBDT的思想可以用一个通俗的例子解释,假如有个人30岁,我们首先用20岁去拟合,发现损失有10岁,这时我们用6岁去拟合剩下的损失,发现差距还有4岁,第三轮我们用3岁拟合剩下的差距,差距就只有一岁了。如果我们的迭代轮数还没有完,可以继续迭代下面,每一轮迭代,拟合的岁数误差都会减小。

从上面的例子看这个思想还是蛮简单的,但是有个问题是这个损失的拟合不好度量,损失函数各种各样,怎么找到一种通用的拟合方法呢?

GBDT的负梯度拟合

GBDT回归算法

GBDT主要的优点有:

  1. 可以灵活处理各种类型的数据,包括连续值和离散值。

  2. 在相对少的调参时间情况下,预测的准确率也可以比较高。这个是相对SVM来说的。

3)使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

GBDT的主要缺点有:

1)由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行

Gradient Boosting

用一个弱学习器近似负梯度

XGBoost

有用的资料

http://codewithzhangyi.com/2018/06/01/XGBOOST%E4%BD%BF%E7%94%A8%E8%AF%B4%E6%98%8E/

https://zxth93.github.io/2017/09/29/XGBoost%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86/index.html

https://www.bilibili.com/video/av26088803?from=search&seid=4150235187907599632

https://www.bilibili.com/video/av24476653?from=search&seid=11865982546931463007 (非常好的视频,不过适合有基础的看)

https://www.jiqizhixin.com/articles/2018-03-18-4 (非常好的讲xgboost的直方图和lgb的GOSS算法对比)