本文着眼讲述经典的3类决策树算法原理，行文框架如下：
- 决策树分类的基本思想：switch-case
- 从ID3到C4.5，如何作出最优的决策？
- 信息熵增益
- 信息熵增益比
- CART树，既可分类又能回归
- 从信息熵到gini指数
- 从多叉树到二叉树
- 从分类树到回归树
01 决策树分类的基本思想：switch-case
决策树算法是机器学习中的一种经典算法，更是很多集成算法的基础。虽说是机器学习，但决策树的基本思想非常符合程序员思维：if-else或者switch-case，即如果满足什么条件则怎么怎么样，否则就另外怎么样。所以，决策树学习的过程就是逐步决策的过程，而决策过程本身则可以绘制成一棵树，当然这里的树是指数据结构与算法中的树。
决策树的基本思想很简单，那么执行决策树的训练过程其实无非就是以下几步：
- 拿什么做决策——最优决策特征选取
- 什么时候停止——决策树分裂的终止条件
- 决策结果如何——最终叶子节点的取值
本文围绕决策树的这3个关键环节展开介绍。
02 从ID3到C4.5，如何作出最优的决策
首先进入大众视野的决策树是ID3（Iterative Dichotomiser 3，即第三代迭代二叉树），这里称之为第三代，但似乎不存在所谓的第一代或第二代的前置版本；另外，虽然叫二叉树，但ID3算法生成的决策树确是一个十足的多叉树。那么，ID3算法是基本原理是怎样的呢？
1）经典ID3算法的基本原理
如前所述，构建一颗决策树首先要明确如何做出最优决策，具体到机器学习场景，那么就是从众多潜在的特征中选择一个最优的特征进行分裂。所以，这里的问题进一步等价于如何定义“最优”的特征。
在ID3算法中，引入了信息熵原理来反映特征重要性。这里，信息熵既是一个通信学上的概念，而其中的熵则要追溯到物理学。来源于何处并不重要，关键的是信息熵可以用于表征一个事件的不确定程度。这里不确定程度用通信学的角度讲，就是蕴含的信息量。当然，为了使得机器学习的结果尽可能准确，我们当然是希望能尽可能的通过一个个的特征消除这种不确定性，或者说不希望它有太多的信息量。
如何理解这里的信息量呢？更具体说，如何通过信息熵来反应信息量？举个例子：比如看一场足球赛事，如果对阵双方实力悬殊，那么我们一般称之为没什么看点——毫无信息量；而如果双方实力在伯仲之间，则比赛结果则会很有看点——信息量丰富！这一事件可抽象为如下数学描述：球队A和球队B，各自胜率分别为pA和pB，显然pA+pB=1（假设该赛事不接受平局结果，必须分出胜负），球队实力悬殊意味着pA>>pB或pA<<pB；实力伯仲之间意味着pA≈pB，进而该事件的信息熵可用如下公式计算：
将上述公式取值随pA在(0, 1)之间变化的取值结果绘制可视化曲线如下
可见，当pA接近0或接近1时，熵的取值也接近为0，意味着信息量较小，结论是几乎确定的；而当pA接近0.5时，pB自然也在0.5左右，意味着二者旗鼓相当，此时熵的取值最大，意味着信息量最大，结论几乎完全不确定。上述结论说明，用信息熵可以刻画一个事件的信息量大小。进一步地，对应到一个机器学习问题，我们的目标就是通过一个个特征将全量样本逐步分裂为多簇小量样本（原全量样本的子集），同时希望这一个个的样本子集内部尽可能的具有小信息量，以期预测结果更具确定性。所以，为达成这一目标，自然是希望优先选取那些能尽可能多地降低这一信息量的特征参与分裂，以期又快又好的达成训练目标。
将上述过程进行数学描述，即为：设选取特征F具有K个取值（特征F为离散型特征），则选取特征F参与决策树训练意味着将原来的样本集分裂为K个子集，在每个子集内部独立计算信息熵，进而以特征F分裂后的条件信息熵为：
其中||Fi||为特征F第i个取值的个数，而||F||则为特征F的总数（即样本集总数）。进而，选取特征F训练带来的信息熵增益（即，带来的不确定性降低）可计算为:
进而，通过遍历各特征逐一计算各自的信息熵增益，增益最大的特征就是当前情况下应当首选的特征。由于在每一轮对选定的特征都进行全分裂，所以对于每个分裂后的样本子集中，该特征列即不再存在。
按照上述流程，即可递归完成一颗决策树的训练过程。那么既然是一个递归过程，就自然存在递归的终止条件，也就是决策树完成训练终止分裂的条件。按照ID3算法的设计，当一颗决策树满足下列条件之一时，即终止分裂：
- 所有特征全部用完；
- 分裂后的样本子集是纯的，即相应分支上的信息熵为0；
- 达到预定的决策树分裂深度，即最大深度；
- 分裂后的样本子集数量少于预定叶子节点样本数时；
- 分裂带来的信息熵增益小于指定增益阈值时
经过上述分裂过程，预期将得到形如下图的一棵多叉树，其中第一轮选取特征F参与训练，得到K个子树，最终分裂终止后得到N个叶子节点。值得指出的是，各叶子节点经历的分裂次数可能是不同的，即有的分支分裂次数多些，有的则可能少一些。
最后，对于分裂得到的每个叶子节点，通过统计该叶子节点中标签占比最多的取值即为最终预测结果，若存在相同则随机选取其中一个。
以上就是经典的ID3算法基本原理，算法思想简单直观，训练效果也不错，但主要存在以下两大局限性：
- 仅支持离散特征，如果是特征连续则首先需要离散化处理；
- 采用信息熵增益选择最优特征参与训练，在同等条件下，取值种类多的特征比取值种类少的特征更占优势。
针对第二个缺陷，C4.5决策算法给出了解决方案。
2）C4.5决策树算法基本原理
ID3算法中，在寻找最优特征参与分裂时，会逐一遍历选取能带来最大信息熵增益的特征，而不考虑该特征的自身情况。这里，特征自身情况是指该特征可能的取值数目和分布情况。所以在C4.5版本决策树中，最大的改进则在于将分裂准则从信息熵增益变为信息熵增益比，即信息熵增益与特征自身信息熵的比值。具体的数据表述即为：
其中，分母部分即为选取特征F自身的信息熵。虽然仅此一处细节改动，但却有效抑制了分裂过程中对取值数目较多特征的偏好，一定程度上保证了决策树训练过程的高效。
另外，C4.5决策树还有其他比较重要的优化设计，例如支持特征缺失值的处理以及增加了剪枝策略等，此处不做展开。
通过以上，我们介绍了决策树的两个经典版本：ID3和C4.5，其中前者作为决策树首个进入大众视野的版本，引入了信息熵原理参与特征的选择和分裂，明确了决策树终止分裂的条件；而C4.5则在ID3的基础上，优化了信息熵增益分裂准则偏好选择取值较多特征的弊端，改用信息熵增益比的准则进行分裂。但同时，C4.5版本决策树仍然存在以下弊端：
- 仍然仅支持离散特征的训练
- 生成的决策树是一个多叉树，从计算机的视角来看不如二叉树简单；
- 无论是信息熵增益还是增益比，都涉及大量的对数计算，计算效率低下；
- 仍然仅可用于分类任务，对于回归预测无能为力。
对此，一个更高级版本的决策树算法应运而生，CART树，也是当前工业界一直沿用的决策树算法。
03 CART树，既可分类又能回归的全能选手
CART（Classification And Regression Tree，顾名思义，分类和回归树）决策树的提出正是为了解决ID3和C4.5版本中存在的局限性，包括不支持连续型特征、对数计算效率低、多叉树更为复杂以及不能用于回归预测任务。CART树给出了全部的解决方案：
- 特征选取准则由信息熵改用gini指数，并由多叉改为二叉，同时避免了对数运算；
- 增加MSE准则，用于回归训练任务
首先介绍第一个大的改进：信息熵到gini指数。
取经于通信学原理，ID3和C4.5均采用信息熵来评判特征的优劣。再看单个事件信息熵的计算公式：
容易理解，该信息熵由事件的各种可能取值对应熵的加和得到，其中每种取值的熵为其概率与概率对数值的乘积得到（由于概率<=1，其对数值<=0），同时为了保证信息熵大于0更易于理解，且信息熵计算结果越大表征更多的信息量，对最终结果取负数作为最终的信息熵增益。那么为了避免对数运算而又不影响计算结果的单调性，将log(p)直接用p替代显然是可行的方案。此时计算过程即为该事件各种取值概率平方的加和，且加和计算结果仍然是取值越大、信息量越大。但此时存在的一个问题是最终结果是负数，不符合常规的信息量的理解，所以进一步将此结果+1，即得到gini指数计算公式如下：
可见，从信息熵演变为gini指数是一个自然的迭代思路，但计算效率将会大大提升。这里，补充信息熵与gini指数取值的可视化对比曲线，仍以前述的球赛结果概率为例：
然后介绍CART树的第二处改进：分裂方式。在改用gini指数替换信息熵解决了对数运算的问题后，CART决策树进一步地调整对每个特征的分裂策略：实现从多叉到二叉，并兼容离散型特征和连续型特征：对每轮选定的特征不再完全执行分裂，而仅依据特征取值是否大于某给定阈值将原数据集分为两类，小于该阈值的为左子树，大于该阈值的则为右子树。显然，这里阈值的选取将直接决定左右子树分裂的结果好坏，所以最优阈值需要寻找而不能随机指定。直观来看，寻找最优阈值的策略，最简单也是最有效的，就是遍历该特征的所有可能阈值取值，以实现所有分裂方案的遍历。具体来说，首先将该特征的所有取值从小到大排列，而后逐一选取相邻两个取值的均值作为阈值（例如，特征有N种取值，则可能的阈值即为N-1个），遍历计算分裂结果的好坏。
正因为这个通过选取阈值将原树节点分为二叉树子树节点的设计，既实现了兼容离散特征和连续特征，也完成了从多叉树到二叉树的过渡，可谓是CART树中的一个核心设计。值得指出，基于CART树中这样的设计，每轮训练后选定的特征实际上并未完全使用，所以在后续训练中仍然可以继续参与分裂，这也是CART树与ID3和C4.5中的一个显著不同。
最后，介绍CART树如何从分类向回归的延伸。从机器学习视角的理解，分类任务和回归任务的唯一区别即在于预测结果是离散标签还是连续取值。而二者对决策树训练过程产生影响的是：如何评价特征选取的优劣，以及分裂结束后如何根据叶子节点中样本的表现得到预测结果。
对于第一个影响，即如何评价特征选取优劣的问题，在分类树中通过信息熵或者gini指数来表征分裂后节点中样本表现的纯度（分类结果越接近，信息量越小），那么在回归树中自然可以联想到类似的表征方式：分裂后节点中样本取值越集中则纯度越高。因为在回归任务中样本取值为连续值，所以表达取值的集中程度自然可联想到用方差来表述，用机器学习语言描述就是用MSE（均方误差）衡量。即对于每轮训练，对各个特征进行逐一遍历，对每个特征的所有可能阈值进行第二层遍历，分别计算分裂后的MSE之和，MSE越小意味着该特征越优秀。对于第二个影响，即根据训练结果如何确定最终回归预测结果的问题，其思路也较为自然：在完成分裂过程后，将每个叶子节点取值的平均值作为后续预测过程的回归值。
至此，CART树便完成了对ID3和C4.5的几个核心问题的改进：既可用于分类也可用于回归任务，同时具有较高的训练效率。此外，CART树也对剪枝过程做了相应的改进，即引入代价复杂度剪枝策略（Cost-Complexity Pruning，CCP），此处也不再展开。
04 小结
决策树是机器学习中的一个经典算法，主要历经了ID3、C4.5和CART树三大版本，算法原理较为直观易懂，改进迭代的过程也容易理解，尤其是以决策树算法为基础更衍生了众多的集成学习算法。除了本文讲述的基本原理外，决策树的另一大核心就是剪枝策略，这将在后续篇幅中予以阐释。
