决策树
决策树(decision tree)是一类常见的机器学习方法。以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这个把样本分类的任务，可看作对“当前样本属于正类吗？”这个问题的“决策”或“判定”过程。顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时的一种很自然的处理机制。例如，我们要对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”：我们先看“它是什么颜色？”，如果是“青绿色”，则我们再看“它的根蒂是什么形态？”，如果是“蜷缩”，我们再判断“它翘起来是什么声音？”，最后我们得出最终决策：这是个好瓜。
显然决策过程的最终结论对应了我们所希望的判定结果，例如“是”或“不是”好瓜；决策过程中提出的每个判定问题都是对某个属性的“测试”，例如“色泽=？”“根蒂=？”；每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围内，例如若出在“色泽=青绿”之后再判断“根蒂=？”，则仅在考虑青绿色瓜的根蒂。
一般的，一个决策树包含一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单直观的“分而治之”策略，算法如下所示，
输入：训练集D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{m}, y_{m}\right)\right\}
属性集A=\left\{a_{1}, a_{2}, \ldots, a_{d}\right\}
过程：函数\text { TreeGenerate }(D, A)
生成节点node. if D中样本全属于同一类别C then 将node标记为C类叶结点：return end if if A=\varnothing
OR D中样本在A上取值相同 then 将node标记为叶结点，其类类别标记为D中样本最多的类：return 从A中选择最优划分属性a_* ； for a_* 的每一个值a_{*}^{v}
do 为node生成一个分支；令D_v 表示D中在a_* 上取值为a_{*}^{v} 的样本子集； if D_v 为空then 将分支节点标记为叶节点，其类别为D中样本最多的类；return else 以TreeGenerate(D_v ，a_* )为分支结点 end if end for 输出：以node为根节点的一颗决策树
显然，决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回：
- 当节点包含的样本全属于同一类别，无需划分
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
- 当前划分节点包含的样本集合为空，不能划分
在第(2)中情况下，我们把当前节点标记为叶节点，并将其类别设定为该类别所含样本最多的类别；在第(3)种倾向下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含最多的类别。注意这两种情形的处理实质不同：情形(2)是在利用当前结点的后验分布，而情形(3)则是把父结点的样本分布作为当前结点的先验分布。