决策树分类法

树的节点：
1.根节点：没有入边但有零条或多条出边
2.内部节点：恰有一条入边和两条或多条出边
3.叶节点：恰有一条入边，没有中边
工作原理：
每个叶节点都赋予一个类标号。非终结点则包含属性测试条件，用以分开具有不同特性的记录

决策树的建立

Hunt算法
思想：通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。
递归定义：设Dt是与节点t相关联的训练记录集，而y={y1,y2,…,yc}是类标号
(1)如果Dt中所有记录都属于同一个类yt。则t是叶结点，用yt标记；
(2)如果Dt中包含属于多个类的记录，则选择一个属性测试条件,将记录划分成较小的子集。对于测试条件的每个输出，创造一个子女节点，并根据测试结果将Dt中的记录分布到子女结点中。然后，对于每个子女结点。递归地调用该算法

决策树归纳地设计问题

(1)如何分裂训练记录

树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集
为了实现这个步骤，算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量

(2)如何停止分裂过程

需要有结束条件，已终止决策树的生长过程。一个可能的策略是分裂结点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的。但是还可以使用其他的标准提前终止树的生长过程。