比较决策树，GBDT，XGBOOST和LightGBM
一、决策树
决策树是一个树结构的分类器，其中每个非叶子节点表示一个特征属性上的测试条件。在决策树构建过程中，最重要的部分就是决定分类特征和分类值，特征既可以是离散值也可以是连续值。
特征的选择一般有两种算法ID3和C4.5，下面依次介绍。
ID3
ID3的核心算法是使用信息增益来选择分裂的特征。在信息论中，熵表示随机变量的不确定性，条件熵表示在一定条件下的随机变量的不确定性，所以熵-条件熵就是信息增益，可以直观的理解为，在一定条件下，随机变量的不确定性减少了多少。
假设数据集D中有m个类别，那么D的熵定义为：
如果将D按属性A进行划分，那么划分后的D的条件熵变为：
而信息增益即为两者的差值：
C4.5
ID3算法存在一个问题，即倾向于选择多值的属性，例如存在一个唯一的id用于标识训练数据，ID3倾向于选择这个属性，而这个属性对分类没有任何帮助，为了克服ID3算法的这个缺点，C4.5提出了使用信息的增益率选择分类特征。
为了计算信息增益率，首先定义分裂信息：
增益率被定义为：
二、GBDT
GBDT 的全称是 Gradient Boosting Decision Tree，GBDT可以看成是多棵树组成的加法模型，其中每棵树都是一颗回归树，叶子节点会给出预测值，所有树的结论累加起来就是最终的预测值。
在分裂点的选择上，不再使用信息增益而是使用均方误差，选择特征的某个分裂点，使得均方误差最小。回归树的每一个节点都有一个预测值，这个预测值为分类到这个节点下所有样本的均值。在训练过程中，首先训练第一棵树，然后根据第一棵树在训练样本上的残差，训练第二棵树，在训练第n棵树的时候，会考虑前n-1棵树的预测结果。
举个例子，样本A对应的真实值为9，在第一棵树上的预测值为7，残差为9-7=2，那么在训练第二棵树的时候，会以2作为样本A的真实值来训练。
三、XGBOOST
XGBOOST算法是对传统GBDT算法的改进。
首先，引入了树的复杂度定义，对于每一棵树t，复杂度定义为：
T为叶子节点个数，w为叶子节点对应的向量值。
XGBOOST与GBDT比较
- XGBOOST的基分类器，可以是非树的其他线性分类器
- 在优化时，不止使用了一阶导数信息，还考虑二阶导数信息
- XGBOOST显示的加入正则项到优化目标中，防止过拟合
- 学习率衰减
- 列抽样
- 对缺失值自动处理，学习出分裂方向
- 工程上的优化，在选取特征阶段，支持并行计算
在处理缺失值时，只考虑没有缺失值的样本，选择最优分类点，然后考虑将有缺失值的样本分裂到左子树和右子树，分别计算，选择损失小的作为缺失值默认处理方法，如果训练样本中没有出现缺失值，测试样本中出现缺失值，则指定默认分裂方向为右侧
四、LightGBM
xgboost的缺点
- 每轮迭代时，都需要遍历整个训练数据集多次，因为要寻找最优分裂点
- 预排序算法，空间消耗巨大
- 对cache不友好
LightGBM
- 基于histogram的决策树算法
- 带有深度限制的Leaf-wise叶子生长策略，取代level-wise树生长策略