概念
决策树(Decision Tree)分为两大类，回归树(Regression Decision Tree)和分类树(Classification Decision Tree)。前者用于预测实数值，如明天的温度、用户的年龄、网页的相关程度；后者用于分类标签值，如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面。这里要强调的是，前者的结果加减是有意义的，如10岁+5岁-3岁=12岁，后者则无意义，如男+男+女=到底是男是女？下面先介绍分类树，决策树一般情况下指的是分类树。
分类树是一种非线性有监督分类模型，随机森林是一种非线性有监督分类模型。线性分类模型比如说逻辑回归，可能会存在不可分问题，但是非线性分类就不存在。决策树是机器学习中最接近人类思考问题的过程的一种算法，通过若干个节点，对特征进行提问并分类（可以是二分类也可以使多分类），直至最后生成叶节点（也就是只剩下一种属性）。
分类树是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
信息熵：熵代表信息的不确定性，信息的不确定性越大，熵越大；比如“明天太阳从东方升起”这一句话代表的信息我们可以认为为0；因为太阳从东方升起是个特定的规律，我们可以把这个事件的信息熵约等于0；说白了，信息熵和事件发生的概率成反比：数学上把信息熵定义如下：H(X)＝H(P1，P2，…，Pn)＝-∑P(xi)logP(xi)
互信息：指的是两个随机变量之间的关联程度，即给定一个随机变量后，另一个随机变量不确定性的削弱程度，因而互信息取值最小为0，意味着给定一个随机变量对确定一另一个随机变量没有关系，最大取值为随机变量的熵，意味着给定一个随机变量，能完全消除另一个随机变量的不确定性。
一、分类决策树
一个简单的决策树示意图：
有人找我借钱（当然不太可能。。。），借还是不借？我会结合根据我自己有没有钱、我自己用不用钱、对方信用好不好这三个特征来决定我的答案，即分成两类。
转到更普遍一点的视角，对于一些有特征的数据，如果我们能够有这么一颗决策树，我们也就能非常容易地预测样本的结论。所以问题就转换成怎么求一颗合适的决策树，也就是怎么对这些特征进行排序。
在对特征排序前先设想一下，对某一个特征进行决策时，我们肯定希望分类后样本的纯度越高越好，也就是说分支结点的样本尽可能属于同一类别。
所以在选择根节点的时候，我们应该选择能够使得“分支结点纯度最高”的那个特征。在处理完根节点后，对于其分支节点，继续套用根节点的思想不断递归，这样就能形成一颗树。这其实也是贪心算法的基本思想。那怎么量化“纯度最高”呢？熵就当仁不让了，它是我们最常用的度量纯度的指标。其数学表达式如下：
其中N表示结论有多少种可能取值，p表示在取第k个值的时候发生的概率，对于样本而言就是发生的频率/总个数。（注意log是以2为底。）比如有20个样本(X)的二分类问题，有15个样本是狗，5个样本不是狗，那么此时的熵为：
H(X)=-(0.75xlog0.75+0.25xlog0.25)=0.811；如果20个样本全部是一类，那么该样本的熵为0；如果20个样本每类10个此时熵最大。样本分布越均匀越混乱，熵越大。熵越小，说明样本越纯。扩展一下，样本X可能取值为n种（x1。。。。xn）。可以证明，当p（xi）都等于1/n 时，也就是样本绝对均匀，熵能达到最大。当p（xi）有一个为1，其他都为0时，也就是样本取值都是xi，熵最小。
1.1 决策树算法
ID3
假设在样本集X中，对于一个特征a，它可能有（a1，a2。。。an）这些取值，如果用特征a当根节点对样本集X进行划分，肯定会有n个分支结点。刚才提了，我们希望划分后，分支结点的样本越纯越好，也就是分支结点的“总熵”越小越好。由于每个分支结点的样本个数不一样，因此我们计算“总熵”时应该做一个加权，假设第i个结点样本个数为W(ai)，其在所有样本中的权值为W(ai) / W(X)。所以我们可以得到一个总熵：
这个公式代表含义一句话：加权后各个结点的熵的总和。这个值应该越小，分类后的样本纯度越高。
这时候，我们引入一个名词叫信息增益G（X，a），意思就是a这个特征给样本带来的信息的提升。公式就是：
由于对一个样本而言，H(X)是一个固定值，因此信息增益G应该越大越好。寻找使得信息增益最大的特征作为目标结点，并逐步递归构建树，这就是ID3算法的思想。
以一个简单的例子来说明信息增益的计算：
上面的例子，我们计算一下如果以特征1作为目标结点的信息增益：
首先计算样本的熵H（X）：
再计算所有分支结点的总熵，可以看到特征1有3个结点A、B、C，其分别为6个、6个、5个样本。所以A的权值为6/17, B的权值为6/17, C的为5/17。因为我们希望划分后结点的纯度越高越好，即总熵最小，因此还需要再分别计算结点A、B、C的熵。
特征1=A：样本有3个是、3个否，其熵为：
特征1=B：2个是、4个否，其熵为0.918；特征1=C：4个是、1个否，其熵为0.722。这样分支结点的总熵就等于：
特征1的信息增益G就等于0.998-0.889=0.109
类似地，我们也能算出其他的特征的信息增益，最终取信息增益最大的特征作为根节点。
C4.5
在ID3算法中其实有个很明显的问题。如果有一个样本集，它有一个叫id或者姓名之类的（唯一的）的特征，那就完蛋了。设想一下，如果有N个样本，id这个特征肯定会把这个样本也分成N份，也就是有N个结点。由于每个结点只有一个值，那每个结点的熵就为0。就是说所有分支结点的总熵为0，那么这个特征的信息增益一定会达到最大值。因此如果此时用ID3作为决策树算法，根节点必然是id这个特征。这显然这是不合理的。一般情况下，如果一个特征对样本划分的过于稀疏，这个也是不合理的（取值特别多的特征不适合做根节点）。
为了解决这个问题，C4.5算法采用了信息增益率来作为特征选取标准。所谓信息增益率，是在信息增益基础上，除了一项split information,来惩罚值更多的属性。
而这个split information其实就是特征个数的熵H（A）。还以上面的例子说明，如果以特征1作为结点，可以分为A B C三种结点，那么：
H(A)=H(特征1)=-(6/17xlog(6/17)x2+5/17(log(5/17))).
为什么这样可以减少呢，以上面id的例子来理解一下。如果id把n个样本分成了n份，那id这个特征的取值的概率都是1/n，文章引言已经说了，样本绝对均匀的时候，熵最大。
因此这种情况，以id为特征，虽然信息增益最大，但是惩罚因子split information也最大，以此来拉低其增益率，这就是C4.5的思想。
CART（Classification And Regression Tree，分类与回归树）
决策树的目的最终还是寻找到区分样本的纯度的量化标准。在CART决策树中，采用的是基尼指数来作为其衡量标准。基尼系数（和基尼指数有区别的）直观的理解是，从集合中随机抽取两个样本，如果样本集合越纯，取到不同样本的概率越小。这个概率反应的就是基尼系数。因此如果一个样本有K个分类，假设样本的某一个特征a有n个取值的话，那么以a为根节点会有n个子节点，其某一个结点下取到不同样本的概率为：
而基尼指数，则是对所有结点的基尼系数进行加权处理
计算出来后，我们会选择基尼指数最小的那个特征作为最优划分特征。
1.2 过拟合解决办法
剪枝
剪枝的目的其实就是防止过拟合，它是决策树防止过拟合的最主要手段。决策树中，为了尽可能争取的分类训练样本，所以我们的决策树也会一直生长。但是呢，有时候训练样本可能会学的太好，以至于把某些样本的特有属性当成一般属性。这时候就我们就需要主动去除一些分支，来降低过拟合的风险。
剪枝一般有两种方式：预剪枝和后剪枝。
预剪枝
一般情况下，只要结点样本已经100%纯了，树才会停止生长。但这个可能会产生过拟合，因此我们没有必要让它100%生长，所以在这之前，设定一些终止条件来提前终止它。这就叫预剪枝，这个过程发生在决策树生成之前。
一般我们预剪枝的手段有：
1、限定树的深度
2、节点的子节点数目小于阈值
3、设定结点熵的阈值
后剪枝
顾名思义，这个剪枝是在决策树建立过程后。后剪枝算法的算法很多，有些也挺深奥，这里提一个简单的算法的思想Reduced-Error Pruning (REP)。该剪枝方法考虑将树上的每个节点都作为修剪的候选对象，但是有一些条件决定是否修剪，通常有这几步：
1、删除其所有的子树，使其成为叶节点。
2、赋予该节点最关联的分类
3、用验证数据验证其准确度与处理前比较
如果不比原来差，则真正删除其子树。然后反复从下往上对结点处理。这个处理方式其实是处理掉那些“有害”的节点。
1.3 随机森林
构建大量的决策树组成森林来防止过拟合；虽然单个树可能存在过拟合，但通过广度的增加就会消除过拟合现象。随机森林（Random forest）：生成多颗决策树，投票选举的原则。
集成学习的概念：
图中可以看到，每个个体学习器（弱学习器）都可包含一种算法，算法可以相同也可以不同。如果相同，我们把它叫做同质集成，反之则为异质。
随机森林则是集成学习采用基于bagging策略的一个特例。
从上图可以看出，bagging的个体学习器的训练集是通过随机采样得到的。通过n次的随机采样，我们就可以得到n个样本集。对于这n个样本集，我们可以分别独立的训练出n个个体学习器，再对这n个个体学习器通过集合策略来得到最终的输出，这n个个体学习器之间是相互独立的，可以并行。
Baggging 与 Boosting
Baggging 和Boosting都是模型融合的方法，可以将弱分类器融合之后形成一个强分类器，而且融合之后的效果会比最好的弱分类器更好。
Baggging
随机森林使用的是baggging，即从原始样本集中抽取训练集，每轮使用 bootstraping 的方法抽取 n 个训练样本，然后放回（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。经过 k 轮抽取，得到 k 个训练集（k个训练集之间是相互独立的）。每次使用一个训练集得到一个模型，k 个训练集共得到 k 个模型。由于是随机采样，这样每次的采样集是和原始样本集不同的，和其他采样集也是不同的，这样得到的个体学习器也是不同的。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等。）
随机森林最主要的问题是有了 k 个模型，怎么设定结合策略，主要方式也有这么几种：
- 加权平均法
当学习器的权值都为1/n时，这个平均法叫简单平均法。
- 投票法
对分类问题：将上步得到的 k 个模型采用投票的方式得到分类结果。投票法类似我们生活中的投票，如果每个学习器的权值都是一样的。有绝对投票法，也就是票数过半；相对投票法，少数服从多数。如果有加权，依然是少数服从多数，只不过这里面的数是加权后的。
Boosting
AdaBoosting方式每次都使用全部的样本，每轮训练改变样本的权重。下一轮训练的目标是找到一个函数 f 来拟合上一轮的残差。当残差足够小或者达到设置的最大迭代次数则停止。Boosting会减小在上一轮训练正确的样本的权重，增大错误样本的权重。（对的残差小，错的残差大）梯度提升的Boosting方式是使用代价函数对上一轮训练出的模型函数f的偏导来拟合残差。
二者之间的区别
样本选择
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。样例权重
Bagging：使用均匀取样，每个样例的权重相等。
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。预测函数
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。并行计算
Bagging：各个预测函数可以并行生成。
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。下面是将决策树与这些算法框架进行结合所得到的新的算法：
- Bagging + 决策树 = 随机森林
- AdaBoost + 决策树 = 提升树
- Gradient Boosting + 决策树 = GBDT
提升树和GBDT，下面会分别介绍。
1.4 例子
以一个简单的二次函数的代码来看看决策树怎么用吧。
训练数据是100个随机的真实的平方数据，不同的深度将会得到不同的曲线；测试数据也是随机数据，但是不同深度的树的模型，产生的预测值也不太一样，如图：
这幅图的代码如下：
我的是python 3.6环境，需要安装numpy、matplotlib、sklearn这三个库，需要的话直接pip install，大家可以跑跑看看，虽然简单但挺有趣。
# -*- coding:utf-8 -*-
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
if __name__ == "__main__":
# 准备训练数据
N = 100
x = np.random.rand(N) * 6 - 3
x.sort()
y = x*x
x = x.reshape(-1, 1)
mpl.rcParams['font.sans-serif'] = ['SimHei']
mpl.rcParams['axes.unicode_minus'] = False
# 决策树深度及其曲线颜色
depth = [2, 4, 6, 8, 10]
clr = 'rgbmy' # 实际值
plt.figure(facecolor='w')
plt.plot(x, y, 'ro', ms=5, mec='k', label='实际值')
# 准备测试数据
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
# 构建决策树
dtr = DecisionTreeRegressor()
# 循环不同深度情况下决策树的模型，并用之测试数据的输出
for d, c in zip(depth, clr):
# 设置最大深度（预剪枝）
dtr.set_params(max_depth=d)
# 训练决策树
dtr.fit(x, y)
# 用训练数据得到的模型来验证测试数据
y_hat = dtr.predict(x_test)
# 画出模型得到的曲线
plt.plot(x_test, y_hat, '-', color=c, linewidth=2, markeredgecolor='k', label='Depth=%d' % d)
# 一些画图的基本参数
plt.legend(loc='upper center', fontsize=12)
plt.xlabel('X')
plt.ylabel('Y')
plt.grid(b=True, ls=':', color='#606060')
plt.title('二次函数决策树', fontsize=15)
plt.tight_layout(2)
plt.show()
二、回归决策树
2.1 回归树
首先看看回归树是如何工作的。下面我们以对人的性别判别/年龄预测为例来说明，每个instance都是一个我们已知性别/年龄的人，而feature则包括这个人上网的时长、上网的时段、网购所花的金额等。
作为对比，先说分类树，我们知道C4.5分类树在每次分枝时，会选取信息增益率最大的特征，按照该标准分枝得到新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是和熵有关的标准，而是最小化均方差--即（每个人的年龄-预测年龄）平方和除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。
2.2 提升树
提升树以回归树为基分类器。它的idea在于，第一个回归树预测的效果可能一般，但是第二个回归树把第一个预测错的残差作为输入。也就是说，如果一个点的值被预测错误，那么在下一个回归树里面的模型的权值会变大。通过这个方式，来提高模型的效果。
举个例子：
训练提升树的步骤：
- step1 构建第一个回归树T1(x)
如何构建回归树T1(x)？
a. 从数据集里面找到一个切分点s，将数据集分成两个部分。
b. 对于每个部分，找到一个值c，使得内部的y到所有的平方损失函数最小。
(遍历所有可能的切分点s，找到最好的效果。那么问题又来了，如何判断一个点的切分的效果好与坏？） - 在上一颗回归树回归的基础上，把残差作为下一棵回归树的任务，继续构造回归树。
- 不断循环这个过程
计算c的公式是：
判断一个点s，切分效果的好与坏的评价标准的时候：
下面，我们带入这个具体的例子里面进行分析。假设，现在的切分点是s=1.5 ， 那么数据集就会被分成两个部分，一个是R1={1} ， R2={2, 3 , ..., 10} 。对于切分的两个部分里面，求c1和c2。根据上面的公式，c1=5.56 , c2=7.50 。那么，在我们这个例子里面，m(s)的值是：
如果，遍历所有可能的切分点，对于每一个切分点都会有一个值。
也就说，当在s=6.5的时候，切分的效果是最好的。
也就是说，我们现在得到了第一颗回归树，T1（x）。对于小于6.5的数据，我们把他预测成6.24，对于大于等于6.5的数据，我们把它预测成8.91。然后，就到了最重要的一步，将残差数据放入下一个回归树进行训练。
下面去训练下一个学习器：
判断的终止条件是：
对于求出的第一个回归树：
对于求出的第二个回归树：
依次类推：
最后：
2.3 梯度提升树GBDT
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
GBDT的核心在于累加所有树的结果作为最终结果，就像前面对年龄的累加（-3是加负3），而分类树的结果显然是没办法累加的，所以GBDT中的树都是回归树，不是分类树，这点对理解GBDT相当重要（尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树）。
GBDT主要由三个概念组成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一个重要演进分枝，目前大部分源码都按该版本实现）。搞定这三个概念后就能明白GBDT是如何工作的，要继续理解它如何用于搜索排序则需要额外理解 RankNet 概念，之后便功德圆满。
算法原理
GBDT的原理和提升树差不多，但是提升树在某些时候不方便求残差，梯度提升树则是用损失函数的负梯度方向值来近似拟合残差。GBDT很好的结合了回归树与提升树的思想，并将它们推广到更一般的情形。例如提升树中第三步计算残差是在损失函数为平方损失函数来计算的，如果损失函数为对数函数，则计算残差 变得不是很方便，以及在第四步训练回归树时，计算节点输出值 c_m 也变得不容易进行。
算法过程如下：
以上算法将回归树和提升树的算法结合起来，在第5步中求解 ，如果损失函数为平方损失函数，则解法与前面的回归树一致，直接取均值即可。如果是其他损失函数，则需要具体进行求解。具体而言，就是取导数为零来解等式。
不过对于分类情况，由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。
GBDT损失函数
对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种:
- 如果是指数损失函数，则损失函数表达式为：
- 如果是对数损失函数，分为二元分类和多元分类两种：
二元：
多元：
对于回归算法，常用损失函数有如下4种:
均方差，这个是最常见的回归损失函数：
绝对损失，这个损失函数也很常见：
Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。
分位数损失。它对应的是分位数回归的损失函数。
