树模型进化论
1、树模型的进化
ID3->C4.5->CART->RF->boosting->Adaboost->GBDT->xgboost
2、决策树
决策树是一个有监督的分类模型，本质是选择一个能带来最大信息增益的特征值进行分裂，直到到达结束条件或者叶子节点纯度到达一定阈值。决策树的每个非叶子节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出。叶子节点存放一个类别，将存放的类别作为决策结果。
2.1、ID3：以信息增益为准则来选择最优划分属性
信息增益的计算基于信息熵，信息熵用来度量样本集合的纯度
eg:
假设于数据集D上建立决策树，数据有K个类别：
（1）中|Ck|/|D| 表示第k类样本的数据占数据集D样本总数的比例；
（2）H(D|A)表示的是以特征A作为分裂属性，得到的信息熵：Di表示的是以属性A为划分，分成n个分支，第i个分支的节点集合。因此，该公式求的是以属性A为划分，n个分支的信息熵总和
（3）为分割后与分割前的信息熵的差值，也就是信息增益，越大越好。
信息增益模型的缺点：
ID3决策树偏向于取值较多的属性进行分割，存在一定的偏好。为减小这一影响，有学者提出C4.5的分类算法。
2.2、C4.5：基于信息增益率准则选择最优分割属性的算法
信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性。
上式，分子计算与ID3一样，分母是由属性A的特征值个数决定的，个数越多，IV值越大，信息增益率越小，这样就可以避免模型偏好特征值多的属性。
C4.5缺点
- 按照这个规则来分割，模型又会偏向特征数少的特征。
对于连续值属性来说，可取值数目不再有限，因此可以采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到又子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。
2.4、CART：以基尼系数为准则选择最优划分属性，可以应用于分类和回归
CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。
Gini(D)反映了数据集D的纯度，值越小，纯度越高。我们在候选集合中选择使得划分后基尼指数最小的属性作为最优化分属性。
2.5、分类树和回归树
提到决策树算法，很多想到的就是上面提到的ID3、C4.5、CART分类决策树。其实决策树分为分类树和回归树，前者用于分类，如晴天/阴天/雨天、用户性别、邮件是否是垃圾邮件，后者用于预测实数值，如明天的温度、用户的年龄等。
作为对比，先说分类树，我们知道ID3、C4.5分类树在每次分枝时，是穷举每一个特征属性的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的信息增益最大的feature和阈值。按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差--每个人的预测误差平方和除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。
参考网址：