信息增益的计算方法
https://blog.csdn.net/it_beecoder/article/details/79554388
决策树--信息增益，信息增益比，Geni指数的理解
https://www.cnblogs.com/muzixi/p/6566803.html
熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。
(1)ID3算法---信息增益
做法：计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
缺点：信息增益偏向取值较多的特征
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集(极端：每个特征值只有1个)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。
(2)C4.5算法--信息增益比
信息增益比 = 惩罚参数 * 信息增益
惩罚参数：数据集D以特征A作为随机变量的熵的倒数
缺点：信息增益比偏向取值较少的特征
原因：当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
(3)CART树--基尼指数
https://www.jianshu.com/p/b90a9ce05b28
https://www.cnblogs.com/yonghao/p/5135386.html
表示在样本集合中一个随机选中的样本被分错的概率。
Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
Xgboost
全名：eXtreme Gradient Boosting
https://www.cnblogs.com/zongfa/p/9324684.html
XGBoost是以分类回归树(CART树)进行组合
模型预测：
损失函数：
其中表示第k颗树的正则项；K代表树的总个数。
每次往模型中加入一棵树，其损失函数便会发生变化。另外在加入第t棵树时，则前面第t-1棵树已经训练完成，此时前面t-1棵树的正则项和训练误差都成已知常数项。
如果损失函数采用均方差时，其目标损失函数变为：
对于其中每一棵回归树，其模型可以写成：
其中w为叶子节点的得分值，q(x)表示样本x对应的叶子节点，T为该树的叶子节点个数。
树的复杂度
泰勒展开式：
令：，
去除常数项，得
令：，
对wj求偏导，令导函数=0，则：
其目标函数为：
根据目标函数分裂样本数据
Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少。叫做结构分数(structure score)。这个代替gini系数，更加一般地对树结构进行打分的函数。
xgboost&gbdt区别
https://blog.csdn.net/wolf963/article/details/78508858
1）增加处理缺失值的方案（通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向）
2）实现了利用分捅/分位数方法，实现了全局和局部的近似分裂点算法，降低了计算量，并且在eps参数设置合理的情况下，能达到穷举法几乎一样的性能
3）xgboost损失函数是误差部分是二阶泰勒展开，GBDT 是一阶泰勒展开。因此损失函数近似的更精准。
4）XGB加了正则项，普通GBDT没有。为了防止过拟合
完毕。
