从决策树到集成学习与随机森林

什么是决策树

事实上，决策树（Decision Tree）这个名字本身就揭示了它的本质：决策树是基于树结构来进行决策的。这正好与人类在面临决策问题时一种很自然的处理机制，决策树算法背后没有复杂的数学推导，更符合人类日常思维方式，理解起来也更为直观。

例如，我们要对 这是好瓜吗? 这样的问题进行决策时，通常会进行一系列的判断或"子决策"，这个过程可以用一棵树来进行可视化：

西瓜问题的一颗决策树

先看它是什么颜色?，如果是 青绿色，则我们再看它的根蒂是什么形态?，如果是蜷缩，我们再判断它敲起来是什么声音?，最后我们得出最终决策：这是个好瓜.

具体来说，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。其中：

叶结点对应于决策结果；
其他每个结点则对应于一个属性测试；
每个结点包含的样本集合根据属性测试的结果被划分到子结点中；
根结点包含样本全集；
从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的就是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循分治策略。

三种基本划分选择

从决策树的原理出发，我们可以看出，要想让一个决策树模型学习出针对某问题得出最好预测/分类结果的一颗决策树，我们需要事先给它有结果标签的数据，换言之决策树模型是有监督学习。
此外，作为机器学习模型，如何划分子树能让类别划分得更好，使得子树尽可能地更“纯粹”，这就是我们需要探讨的问题。

如今已经有了三种最基本的决策树算法（划分选择方法）可以解决我们的问题。

ID3 & 信息增益

信息熵（Information Entropy）是信息论中度量样本集合纯度最常用的一种指标。它被定义为样本信息量的期望。信息熵越大，表示样本的纯度越低，不确定度越高。

对于一个含有 $|\mathcal D|$ 个类别的样本集合 $\cal D$ ，其信息熵可以表示为：

$\text{Ent}(\mathcal D)=-\sum_{k=1}^{|\mathcal D|}p_k\log p_k$

其中， $p_k$ 表示第 $k$ 个类别在 $\cal D$ 中的占比。
特别地，在信息熵计算时，若 $p_k=0$ 则规定： $-p_k\log p_k=0$ 。

假定离散属性/特征 $\alpha$ 有 $V$ 个可能的取值 $\{a_1,a_2,...,a_V\}$ 。当用该特征来对样本集 $\cal D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $\cal D$ 中所有在特征 $\alpha$ 上取值为 $a_v$ 的样本，这个划分的集合记为 ${\cal D}^v$ .

于是，在 $\alpha$ 条件下的信息熵，也就是条件熵可以表示为：

$\begin{aligned}Ent(\mathcal D|\alpha) =&-\sum_{v, k} p\left(\mathcal D_{k}, \alpha_{v}\right) \log p\left(\mathcal D_{k} | \alpha_{v}\right) \\ =& -\sum_{v, k} p\left(\alpha_{v}\right) p\left(\mathcal D_{k} | \alpha_{v}\right) \log p\left(\mathcal D_{k} | \alpha_{v}\right)\\ =& -\sum_{v=1}^{V} p\left(\alpha_{v}\right) \sum_{k=1}^{|\mathcal D|}p\left(\mathcal D_{k} | \alpha_{v}\right) \log p\left(\mathcal D_{k} | \alpha_{v}\right)\\ =&\sum_{v=1}^V\frac{|\mathcal D^v|}{|\mathcal D|}\text{Ent}(\mathcal D^v) \end{aligned}$

而信息增益 $\text{Gain}(\mathcal D,\alpha)$ 的定义就是信息熵与在 $\alpha$ 条件下的信息熵之差，即：

$\begin{aligned} \text{Gain}(\mathcal D,\alpha)&=\text{Ent}(\mathcal D)-\text{Ent}(\mathcal D|\alpha)\\ &=\text{Ent}(\mathcal D)-\sum_{v=1}^V\frac{|\mathcal D^v|}{|\mathcal D|}\text{Ent}(\mathcal D^v) \end{aligned}$

信息增益越大，则意味着使用该特征来进行划分所获得的"纯度提升"越大.
因此，我们可以用使得信息增益最大的特征来进行决策树的划分选择，著名的 ID3 决策树学习算法 [Quinlan 1986] 就是以信息增益为准则来选择划分的。

一次划分结束后，我们又递归地对子树进行同样的划分，直到当前子样本全部属于同一类为止。

ID3算法也存在一些缺陷：

ID3 没有剪枝策略，容易过拟合。考虑极端情况，ID3可能为每一个样本都划分出一个结点，使得训练集准确率到100%；
信息增益准则对可取值数目较多的特征有所偏好。比如，类似“唯一编号”的特征其信息增益接近于1；
只能用于处理离散分布的特征；
没有考虑缺失值。

C4.5 & 增益率

增益率

为减少“信息增益准则对可取值数目较多的属性有所偏好”这种性质可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan 1993] 不直接使用信息增益，而是使用"增益率" (gain ratio) 来选择最优划分属性.

$\begin{aligned} \text{Gain\_ratio}(\mathcal D,\alpha)=\frac{\text{Gain}(\mathcal D,\alpha)}{\text{IV}(\alpha)}\\\\ \text{IV}(\alpha)=-\sum_{v=1}^V\frac{|\mathcal D^v|}{|\mathcal D|}\log\frac{|\mathcal D^v|}{|\mathcal D|} \end{aligned}$

其中， $\text{IV}(\alpha)$ 称为特征 $\alpha$ 的固有值。从其表达式可以看出，这个样本集合中特征 $\alpha$ 的值取 $a_v$ 的概率的信息熵。

当固有值越大，该特征可能的取值就越多，对应信息熵越大，越不利于划分的均衡性。所以用作分母时，定义的增益率就能很好地改善此问题。

当然，特征可能的取值越少，增益率就越高了。即 增益率准则对可取值数目较少的属性有所偏好。因此 C4.5 算法并不是直接选择增益率最大的候选划分特征，而是使用了一个启发式：先从候选划分特征中找出信息增益高于平均水平的属性，再从中选择增益率最高的.

剪枝处理

C4.5算法还给出了解决过拟合的方法：剪枝(pruning).

剪枝的基本策略有预剪枝(prepruning) 和后剪枝(postpruning)。

预剪枝：指在决策树生成的过程中，用验证集对每个结点在划分前后进行评估，若当前结点的划分不能解决树泛化性能提升时，就停止划分将该结点为叶子结点。

后剪枝：先生成一个完整的决策树，用验证集自底向上地对每个分支结点计算泛化性能，如果对某个分支结点替换为叶子结点，泛化性能提高了，则将其替换为叶子结点。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。后剪枝的欠拟合风险很小，泛化性能往往优于预剪枝，但同时其训练时间会大的多。

连续值处理

应对连续属性，C4.5 算法给出了最简单的策略：二分法(bi-partition)：假设 $\alpha$ 在 $\cal D$ 中出现了 $n$ 个不同的取值，对它们进行大小排序后，选取每相邻两个值的中间值 $t$ 作为划分标准，即可将样本集划分为 $D_t^-,\;D_t^+$ 。然后依次计算每种 $t$ 的选取得到的增益，进而得到合适的划分标准，用离散属性的思路继续往下进行。

缺失值处理

为了不放弃某些属性有缺失的样本，C4.5 算法给出了出现缺失值时的处理策略。我们需解决两个问题：

如何在属性值缺失的情况进行划分属性选择？
若样本在给定的划分属性上的值缺失，如何对样本进行划分？

对于问题(1)，我们定义 $\tilde{\mathcal D}$ 为 $\cal D$ 中没有数据缺失的样本集， $\rho$ 为无缺失样本所占的比例，那么定义新的信息增益计算式：

$\text{Gain}(\mathcal D,\alpha)=\rho\times\text{Gain}(\tilde{\mathcal D},\alpha)$

对于问题(2)，当某个样本 $\boldsymbol x$ 的划分属性缺失时，就将其同时划分到所有子结点中去。

C4.5 算法也存在一些缺陷：

剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART & 基尼指数

CART 决策树 [Breiman et al., 1984] 使用"基尼指数" (Gini index) 来选择划分属性。
基尼指数事实上是将基尼系数带入到决策树问题中。

基尼系数

$\begin{aligned} \operatorname{Gini}(\mathcal D) &=\sum_{k=1}^{|\mathcal{D}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}}\\ &=\sum_{k=1}^{|\mathcal{D}|} p_{k}(1-p_k) \\&=1-\sum_{k=1}^{|\mathcal{D}|} p_{k}^{2} \end{aligned}$

上式为基尼系数的定义式，它表明了随机抽取两个样本，类别不一样的概率。因此值越小，纯度越高。而CART算法对每一种属性计算对应的基尼指数：

$\text { Gini\_index}(\mathcal D,\alpha)=\sum_{v=1}^{V} \frac{\left|\mathcal D^{v}\right|}{|\mathcal D|} \operatorname{Gini}\left(\mathcal D^{v}\right)$

采用基尼指数作为划分准则时，既保留了熵的优点，又省去了复杂的对数运算。这是因为： $-\ln x=1-x+o(x)$ ，从而： $p_k\ln p_k\approx p_k(1-p_k)$ 。

剪枝策略

CART算法的剪枝策略与 C4.5 有所不同。CART提出利用正则化后的某个损失函数来评估剪枝前后的效果。

待更：https://www.zhihu.com/question/22697086

回归树

Scikit-Learn实现

scikit-learn 提供了两种决策树模型：

DecisionTreeClassifier --分类决策树，用于分类任务
DecisionTreeRegressor --回归决策树，用于回归任务

参数列表

class sklearn.tree.DecisionTreeClassifier(*, 
				criterion='gini',
				splitter='best',
				max_depth=None,
				min_samples_split=2,
				min_samples_leaf=1,
				min_weight_fraction_leaf=0.0, 
				max_features=None,
				random_state=None, 
				max_leaf_nodes=None,
				min_impurity_decrease=0.0, 
				class_weight=None,
				ccp_alpha=0.0)

下面给出部分参数的主要含义：

参数	DecisionTreeClassifier	DecisionTreeRegressor
特征选择标准criterion	可选项有"gini"和"entropy"，前者代表基尼系数，后者代表信息增益。	可选项有"mse"和"mae"，前者是均方差，后者是和均值之差的绝对值之和。推荐使用默认的"mse"。一般来说"mse"比"mae"更加精确。
特征划分点选择标准splitter	可选项有"best"和"random"。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。默认的"best"适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐"random"
划分时考虑的最大特征数max_features	可以使用很多种类型的值，默认是"None",意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑$log_2N$个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑$\sqrt{N}$个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的"None"就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
决策树最大深max_depth	决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
内部节点再划分所需最小样本数min_samples_split	这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。我之前的一个项目例子，有大概10万样本，建立决策树时，我选择了min_samples_split=10。可以作为参考。
叶子节点最少样本数min_samples_leaf	这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。之前的10万样本项目使用min_samples_leaf的值为5，仅供参考。
叶子节点最小的样本权重和min_weight_fraction_leaf	这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
最大叶子节点数max_leaf_nodes	通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
类别权重class_weight	指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重，或者用“balanced”，如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果你的样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的"None"	不适用于回归树
节点划分最小不纯度min_impurity_split	这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。
数据是否预排序presort	这个值是布尔值，默认是False不排序。一般来说，如果样本量少或者限制了一个深度很小的决策树，设置为true可以让划分点选择更加快，决策树建立的更加快。如果样本量太大的话，反而没有什么好处。问题是样本量少的时候，我速度本来就不慢。所以这个值一般懒得理它就可以了。

示例代码

决策树可视化

`sklearn`的可视化

待更：https://www.cnblogs.com/pinard/p/6056319.html

第三方可视化

待更：https://zhuanlan.zhihu.com/p/443846466

多变量决策树

集成学习

集成学习（ensemble learning） 通过构建并结合多个机器学习器（基学习器，Base learner）来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等. 集成学习往往被视为一种元算法（meta-algorithm）。

其核心思想可以概括为：三个臭皮匠顶个诸葛亮。