决策树是十大机器学习算法之一，可用于分类和回归问题。最初的决策树包括ID3和C4.5，后来慢慢发展到随机森林和作为梯度提升算法的基学习器模型，例如GBM算法和Xgboost。单一的决策树算法由于模型比较简单效果不是很好，后来引入Bagging和Boosting后模型效果大为改善。今天我们就来了解一下关于决策树的相关内容。
回归树
决策树用于分类比较容易理解，因为满足某条件归为一类，不满足归为另一类，那么在回归问题中是怎么工作的呢？我们先看一下决策树的基本结构。如下图
决策树算法类似于树的生长，有一个根节点生出两个枝，然后每个枝节点再生长，依次循环，将预测变量空间划分为N个不重叠的区域，节点的划分采用的是一种自上而下的贪婪算法，在回归树中，节点分裂可以用数学式表示为：
其分裂的依据是最小化成本函数，其数学表达式如下
最终节点分裂完成后，预测值为落在该节点所有值的平均。
分类树
分类树与回归树类似，在分类树中，其节点分裂准则通过基尼系数或者交叉熵来衡量。基尼系数计算公式如下：
交叉熵计算公式如下：
当节点分裂完成以后，预测值为落在该节点的所有类别最多的一类。
Bagging
Bagging是一种集成学习方法，通过降低模型方差提高模型效果，其核心思想是通过bootstrap的方法从数据集中有重复的抽取N个数据子集，然后用这N个子集训练N个基学习器模型，最后将N组预测结果平均或者投票法得到最终结果。其模型融合表达式为：
Boosting
Boosting与Bagging类似，Boosting通过迭代残差学习，当前模型学习目标为上一次学习误差，最终将得到的N个基学习模型组合得到最终模型。每个基学习器模型的训练数据是一样的，Boosting算法中有三个重要的参数，分别为：
树的数量(B)：与套袋和随机森林不同，如果B太大，Boosting会过度拟合。一般使用交叉验证来选择适当数量的树。
收缩参数(alpha)：控制Boosting的学习率。通常设定为0.01或0.001。
每棵树中的分裂数量(d)：该参数控制了模型的复杂性。也被称为交互深度，如下图所示，一般分裂数量选为1。
随机森林
随机森林是决策树和Bagging的集合，通过Bagging算法构建多颗决策树，在每次分裂时，从所有p个预测变量中选择m个预测变量的随机样本。一般m和p的关系为
为什么这个关系是最优的呢？其测试结果如下
本次简单介绍关于决策树的一些算法，决策树目前比较热门的算法有Xgboost、Lightgbm以及Catboost，在一些数据竞赛中运用十分广泛，大家感兴趣可以了解一下。
参考
https://towardsdatascience.com/everything-you-need-to-know-about-decision-trees-8fcd68ecaa71
