一、决策树
决策树是一种解决分类问题的绝好方法，顾名思义，它正像一棵大树一样，由根部不断生长出很多枝叶；它的优点实在太多，比如可以避免缺失值的影响、可以处理混合预测、模型容易展示等。然而，决策树的实际应用也绝不简单，如果树根稍有不稳、或者枝干略有差池，树就可能会彻底长偏啦，我们总是需要仔细挑选单棵决策树、或适当的组合。
建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法：
1、ID3(Iterative Dichotomiser):使用信息增益/互信息进行特征选择。取值多的属性，更容易使数据更纯，其信息增益更大。
2、C4.5：信息增益率。
3、CART（Classification And Regression Tree）:基尼指数。
注：一个属性的信息增益（率）/gini指数越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。信息增益（率）/gini增加，熵减小，越确定。
二、Bagging,随机森林的区别和联系
加粗字体即为二者区别
Bagging
- 从样本集中有重复的选出n个样本
- 在所有属性上，对这n个样本分别建立分类器**（ID3,C4.5，CART,SVM,Logistic回归等）**
- 重复以上两个步骤m次，即获得了m个分类器
-
将数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类。
随机森林
1.从样本集中用Bootstrap采样选出n个样本
2.从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树
3.重复以上两步m次，即建立了m棵CART决策树
4.这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类。
注：当然可以使用决策树作为基本分类器，但也可以使用SVM,Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。
提升算法
提升是一个机器学习技术，可以用于回归和分类问题，它每一步产生一个弱预测模型（如决策树），并加权累加到总模型中；
如果每一步的弱预测模型生成都是依据损失函数的梯度方向，则称之为梯度提升（Gradient boosting，GDBT）。梯度提升的典型基函数即决策树（尤其是CART）
xgboost与GBDT区别、优势：
- 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
-
xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
Adaboost
AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
具体说来，整个Adaboost 迭代算法就3步：
初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。
Bagging和boosting的区别：
Bagging流派，各分类器之间没有依赖关系，可各自并行，比如随机森林（Random Forest）
Boosting流派，各分类器之间有依赖关系，必须串行，比如Adaboost、GBDT(Gradient Boosting Decision Tree)、Xgboost