决策树是一种类似于流程图的树结构，其中，每个内部节点(非树叶节点)表示一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶节点(或终端节点存放一个类标号)。树的最顶层节点是根节点。下图是一个典型的决策树(来自《数据挖掘：概念与技术》[韩家炜]（中文第三版）第八章)：

　　在构造决策树时，使用属性选择度量来选择将元祖划分成不同类的属性。这里我们介绍三种常用的属性选择度量-----信息增益、信息增益率和基尼指数。这里使用的符号如下。设数据分区\(D\)为标记类元组的训练集。假设类标号属性具有\(m\)个不同的值，定义了\(m\)个不同的类\(C_i (i=1,2,...,m)\)。设\(C_{i,D}\)是\(D\)中\(C_i\)类元祖的集合，\(|D|\)和\(|C_{i,D}|\)分别是\(D\)和\(C_{i,D}\)中元祖的个数。

决策树之ID3、C4.5、C5.0 、CART