决策树的生成有多种算法，这里先回顾ID3算法和C4.5算法。

1. ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择。

ID3算法

输入：训练数据集D，特征集A阈值ε；

输出：决策树T。

2. C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。

C4.5算法

输入：训练数据集D，特征集A阈值ε；

输出：决策树T。

参考文献

【1】统计学习方法（第2版），李航著，清华大学出版社