2018-03-05

决策树

algorithm

ID3

基于熵做分类

熵

熵：度量样本集合不确定度的指标。代表随机变量的复杂度。用来评价整个随机变量x的平均信息量。(反比例)

公式：是每一类的出现概率p的logP倍和

取log是因为从观测角度。两个变量的信息量单独观察和一起观察应该是一样的是+，而从概率角度，两个独立的随机变量P（X,Y）=P（X）*P(y)。所以选择log函数

信息增益

表示得知属性 a 的信息而使得样本集合不确定度减少的程度

信息增益 = 熵 - 条件熵
缺点

ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。

意思就是，集合中拥有这个属性的样本有很多

C4.5

基于信息增益率做切分

公式

信息增益/属性a的固有值-IV（a）

IV（a）,选取该属性，分成的V类别数越大，IV(a)就越大，如果仅仅只用信息增益来选择属性的话，那么我们偏向于选择分成子节点类别大的那个特征。
比ID3好的原因
1. 3可取值数目较多的属性有所偏好。
2. 看到增益率准则其实对可取类别数目较少的特征有所偏好！毕竟分母越小，整体越大。
3. 仅仅只用信息增益来选择属性的话，那么我们偏向于选择分成子节点类别大的那个特征。
  
  按照增益率来划分节点，分成的类别数目越多，增益率的值越大
4. C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降
  
  c4.5可以多分叉
信息增益率指的是信息增大的比率，而不再是取决于数量

Gini

公式

这个样本被选中的概率乘以它被分错的概率

对不同分类属性，比如男女，去算gini?
表示的意义

表示一个随机选中的样本在子集中被分错的可能性
终止条件
分析步骤
1. 多路分叉

distinction

	ID3	C4.5	CART
分类结果		分类	分类，回归
子节点		多分	二叉子节点
数据类型？	离散	离散，连续	连续

Category

DT

CART

classification and regression tree

特点
- 分类回归树是一棵二叉树，且每个非叶子节点都有两个孩子，所以对于第一棵子树其叶子节点数比非叶子节点数多1。
CART与ID3的区别
- CART中用于选择变量的不纯性度量是Gini指数
- 如果目标变量是标称的，并且是具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别（双化）；
  
  标量：定类变量，比如男女
  
  超类别？
- 如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。
- 模型如此设计的原因
  
  选择gini的原因
  
  ID3，C4.5 大量的log计算。gini
  
  cart，只对某个特征进行二分原因
  
  简化gini计算，模型是二叉树也更优雅

Regression DT

衡量标准：最小化平方差
1. 每一个节点都有预测值
2. 被预测出错的人数越多，错的越离谱，平方误差就越大

Boosting DT

是迭代多棵回归树，多棵。是指迭代中的多棵还是多个，多个怎么计算。提升树即是整个迭代过程生成的回归树的累加

一个数拟合好后，以残差再拟合一棵树，通过另一个属性再迭代
以残差拟合一个分类器
1. 有同质，异质
作用：提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数时平方损失和指数损失函数时，每一步的优化很简单。
过程。提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树
主要是优化学习过程
优化的方法。加快优化过程

GBDT

梯度提升决策树

GBDT是回归树，做处理也可用于分类
区别于分类树，树的每一个节点都有一个预测值。等于所有值的平均
衡量最好的标准是最小化平方差-分支依据
预测出错的人数越多，错的越离谱，平方误差就越大
分支终止条件是：唯一或者达到设定的终止条件

采用的是加法模型
每轮迭代产生一个弱分类器，通过不断降低偏差来提高最终分类器的精度。（弱分类器前提是低方差和高偏差）
弱分类器一般选择CART
总分类器是每轮训练得到的弱分类器加权求和得到的
与bdt的区别。bdt使用平方差比较好计算方差

但是一般的损失函数不容易计算，使用负梯度得到残差的近似值。计算简单

GBDT和随机森林的相同点：

1、都是由多棵树组成

2、最终的结果都是由多棵树一起决定

GBDT和随机森林的不同点：

1、组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成

2、组成随机森林的树可以并行生成；而GBDT只能是串行生成

3、对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来

4、随机森林对异常值不敏感，GBDT对异常值非常敏感

随机是对数据一视同仁，gbdt是弱分类器的权值集成

5、随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成

6、随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能

？

Random Tree

生成方法

1.从样本集中通过重采样的方式产生n个样本

2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点

3.重复m次，产生m棵决策树

4.多数投票机制来进行预测

（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）

AdaBoost

AdaBoost的实现是一个渐进的过程，从一个最基础的分类器开始，每次寻找一个最能解决当前错误样本的分类器。用加权取和(weighted sum)的方式把这个新分类器结合进已有的分类器中。
它的好处是自带了特征选择（feature selection），只使用在训练集中发现有效的特征(feature)。这样就降低了分类时需要计算的特征数量，也在一定程度上解决了高维数据难以理解的问题
Adaboost

过程

1）给数据中的每一个样本一个权重

2）训练数据中的每一个样本，得到第一个分类器

3）计算该分类器的错误率，根据错误率计算要给分类器分配的权重（注意这里是分类器的权重）

4）将第一个分类器分错误的样本权重增加，分对的样本权重减小（注意这里是样本的权重）

5）然后再用新的样本权重训练数据，得到新的分类器，到步骤3

6）直到步骤3中分类器错误率为0，或者到达迭代次数

7）将所有弱分类器加权求和，得到分类结果（注意是分类器权重）作者：刘开心_8a6c链接：https://www.jianshu.com/p/a6426f4c4e64來源：简书著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

xgboost

xgboost是Gradient Boosting的一种高效系统实现，并不是一种单一算法。xgboost里面的基学习器除了用tree(gbtree)，也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。

xgboost

显式地将树模型的复杂度作为正则项加在优化目标
公式推导里用到了二阶导数信息，而普通的GBDT只用到一阶
允许使用column(feature) sampling来防止过拟合，借鉴了Random Forest的思想，sklearn里的gbm好像也有类似实现。

Realization process

Relation know

分类树与回归树的区别

分类树以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1)，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。

回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

gbdt和xgboost的区别

传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）

列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。