引子：决策树模型（Decision Trees，DTs）是一种非参监督式学习模型。它既可以应用于分类问题，也可以应用于回归问题。它的目标是基于数据属性找到决定性规则（decision rules），预测目标值。
概括
优点：
－ 模型解释性好；
－ 训练需要的数据量小；
－ 既可以处理数值变量（numerical var），也可以处理分类变量（categorical var）；
－ 可以解决多目标问题（multi-output）
如果说大部分机器学习都是黑盒子（black box），那么决策树绝对是少有的white box model。
缺点：
在bias-variance tradeoff中，它偏向于低bias，高variance，因此模型容易过度拟合（overfitting），并且不稳定（unstable）。很大一部分原因，在于它的学习过程采用的几乎都是贪婪算法（greedy algorithms）。然而这也是不得不的选择。有证明，寻找最优决策树是一个NP-complete问题（用科普的话说，您的计算能力不足以解决这类问题~），因而，我们找到的也只能是局部最优而非全局最优。（但我个人的理解，要是数据取样好，good class balance，或者是big data，比如GB，TB级别，就不怕局部最优算法的困扰）
不过，机器学习发展至今，过度拟合问题已经可以得到很好的解决。比如与boosting 结合的boost tree（ada boost 等）和ensemble learning 模型 random forest，都可以攻克以上的缺点。因此，决策树及其家族在工业界和学术界都广受推崇，并且有很大的贡献。
下面介绍几种在决策树学习过程中广泛采用的算法。
ID3
全称Iterative Dichotomiser 3的ID3可谓最流行也最古老的算法，其创始人Ross Quinlan在发明了ID3后又扩展出了C4.5，C5.0。深入了解ID3之前，需要先引入一个定义：熵（Entropy）
给定一组数据集群set S，并标记label，即它们可分组到class 1,class 2,......class n。定义pi为class i所占的比例。定义entropy为：
在热力学里，熵越大意味着混乱程度越大；而在统计学里，entropy越大，意味着不确定性uncertainty越大。因此我们希望一个集群S的熵越小越好。而其原理也很简单，看下图fun(p): -p*log(p)就可以解释
如果给定一个规则A，在规则A下，数据点都集中在两个极端，即p->0或者p->1，那么我们就越确定A是一个可信任的规则，而如果数据是spread out evenly的，则我们这个规则很可能是错误的。
ID3的训练原理也就如此顺其自然的得到了：我们根据attributes依次寻找分割条件使得分割后的各个Partition set si的熵的总和是最小的，即最小化：
其中qi是si的权重（proportion weight）。下面是一棵已经生成的树：
之所以level这个attribute会被放在第一层layer 1，是因为基于level后将所有数据进行第一次分割后得到的熵是最小的。紧接着基于上个分割后再进行分割，但显然这是一个贪婪算法，因为这样的顺序下，有一定可能错过一些更优的path。
注：比较多的地方使用的不是minimize entropy而是maximize information gain。而这两者是一回事，因为information gain = entropy_before _split - entropy_after_split。而entropy_before_split是在没有该attribute参与前的分类，对每个attribute而言都是一样的。
C4.5/C5.0
C4.5是对ID3的一些改进，主要在于能处理连续数值和不完整数据，并且通过引入pruning防止overfitting。同时，它引入了一个information gain ratio的概念，是一种类似归一化处理。
其中H(Y)就是上文的entropy before split，H(Y|X)就是上文的entropy after split based on attribute X。而H(X)是仅根据attribute X而不考虑label Y进行分割后的entropy。而其对连续变量的处理，是按照连续变量的大小从小到大进行排序，假设一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连续元素的中点。这样感觉有点暴力搜索。但是也可以做一些优化，比如前后两个值的lable如果是一样的，就可以不再考虑他们的中点
而C5.0在内存上做了一些优化。
CART
CART采用的优化方法略有不同。它计算的不是information entropy，而是gini impurity。
广泛使用的python scikit-learn包采用的就是基于CART算法的决策树。
Random Forest
在RF之前想提一下的是bagging(bootstrap aggregating的简称)。bootstrap是一种常用的方法，其原理也十分简单，就是有放回的随机抽样用于训练。
所谓随机森林，顾名思义，就是一群树。大概有一段时间很流行ensemble learning或者majority voting，从某种程度上可以解决overfitting的问题。随机森林就是拿一群弱学习器（DTs）进行投票。之所以这里的DTs称为弱学习器，是因为往往我们只取部分attributes作为input进行学习。
关于随机森林是不是一种容易过拟合的模型，众说纷纭；但是一致同意的是，从DT到RF，white box已经被洗黑了(black box).
Boosting
boosting 可谓是决策树家族发展最成功的一支。同样，它也有ensemble learning和majority voting的理念。但是和随机森林不同的是，它的子树存在“进化”（evolve）的思想，而且在进化中适应训练数据，这算是它的核心。
Adaboost是boosting类模型中最为有名的。它的训练步骤如下：
假如有N个数据值observation，那么一开始，他们用于评价模型error（步骤b）的weights都是1/N，但是在训练过程中，假如有的数据点（xi，yi）训练不好，对应的wi就会变大（步骤d)，那么它在下一个子树Gm会得到更多重视。最后的投票也不是简单的平均投票，而是根据每个子树的Alpha值权衡。
XGBoost
如果你混迹Kaggle，那么你就不可能没听说过大名鼎鼎的XGBoost。它绝对是帮你上Kaggle排行榜的利器。XGBoost是一个模型，也是一个工具包。它既是boosting算法中比较出类拔萃的，同时工具包提供分布并行计算，可以帮助你加速训练，所以备受欢迎。我在这里提的是该算法的一些核心思想。至于具体工具包的使用，请参照文末的参考链接。
如上所述，boosting的训练是树的“进化”，那么进化的方向就可以有很多，xgboost是其中较为巧妙的。假如第一棵树的训练目标是原始的（x, y)，那么下一棵树就可以用于对上一棵树的修正（x, y-y')，其中y’是上一棵树的预测值，依次类推，相当于每次都在修正“残差”。如果你关注deep learning领域的最新研究结果，也能看到一些类似训练残差的神经网络模型。
理想情况下，模型会收敛，即残差会趋向于零。将每棵树的结果相加，就是对最原始的目标值y的预测。当然这只是基本的训练参数。如果你调整一些参数，比如eta，可以给残差一个权重。同样，类似于其他的决策树，你可以选择什么时候stop（子节点的数据量小于多少threshold）。
参考链接
http://scikit-learn.org/stable/
https://xgboost.readthedocs.io/en/latest/
“Data Science from Scratch”
“The Elements of Statistical Learning”
