ID3：最大信息增益，只能处理离散特征，只能做分类，多叉树，不能处理缺失值。
C4.5：最大信息增益率，可以对连续型变量划分分割点变为连续型变量进而进行处理，只能做分类，多叉树，可以处理缺失值。
CART：全称Classification and Regression Tree 可以做分类也可以做回归，做分类时使用Gini系数，做回归时用均方误差，二叉树，可以处理缺失值。
对于ID3，多叉树的生成：
step 1: 求出数据集的经验熵
step 2: 求出每个特征的经验条件熵
step 3: 经验熵 - 经验条件熵 = 信息增益
step 4: 找到具有最大信息增益的特征，该特征有几个类别，就生成几叉树。
step 5: 在生成第一层树的基础上重复1-4步。
step 6: 这样下去的话存在三个停止分裂的条件：1 子节点中的样本属于同一类 2 子节点中没有样本了 3 特征用完了
step 7: 停止分裂时，对应的就是叶子节点了，取叶子节点里概率最大的类别为最终的类别
step 8: 预测时，从根节点开始，从上至下遍历，直到叶子节点，预测类别即为叶子节点的值。
补充：要想得到预测概率的话对于叶子节点中，每个类别的占比就是预测的概率。
来源于官方文档：
The class probability of a single tree is the fraction of samples of the same class in a leaf.
对于CART 二叉树的生成：
与ID3不同的逻辑在于：它是遍历样本中每个特征的每一个值，按照该值把样本分为左右两个分支，以回归为例就是分别计算两边集合的mse，找到两边mse之和最小的那个分割点。由此就得到了 最佳分裂特征和最佳分割点。回归时叶子节点的输出是叶子节点中真实值的平均值。
GBDT的基学习器都是CART回归树。做分类用的也是回归树。
GBDT拟合的是负梯度。对于回归比较好理解，计算均方误差后，求导即是负梯度。
对于分类问题，二分类的话，计算logloss。多分类的话，计算softmax。
XGBoost与GBDT的迭代方面的区别在于：XGBoost本质上不是靠拟合上一轮的残差进行迭代的，它其实有自己的一套Gain分裂方式。可以理解为XGB每一轮并不需要去拟合值，而是根据xgb特有的gain构造树结构。
XGBoost为什么要进行二阶泰勒展开：
xgb是用到了loss 在当前模型下的 1-2阶梯度，目的是为了近似表示loss，这样可以求得解析解，求得Gain，生成树。如果不求二阶导的话 很多损失函数没法求导进而推导出Gain。
换句话说：xgboost官网上说，用泰勒级数展开是因为损失函数的梯度并不总是容易求得。方便实现应该是最直接的原因。
此外有种说法二阶展开可以带来效果的提升：
二阶信息本身就能让梯度收敛更快更准确。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。
