决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶子节点代表一种分类结果。
决策树学习的三个步骤：特征选择
通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。
树的生成
决策树的生成往往通过计算信息增益或其他指标，从根结点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征，或将训练集分割为能够基本正确分类的子集。
树的剪枝
由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。
常用的特征选择准则：（1）信息增益（ID3）
样本集合\(D\)对特征\(A\)的信息增益定义为：
\[g(D, A)=H(D)-H(D|A) \]