决策树模型分析与应用

定义4.1决策树　决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点表示一个特征或属性；叶结点表示一个类。用决策树分类，从根结点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点，这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点；最后将实例分到叶结点的类中。图4－1所示为一个决策树模型的示意图，图中圆和方框分别表示内部结点和叶结点。

图4－1　决策树模型

为了解释决策树分类的基本原理，这里举一个脊椎动物分类的示例。假设科学家发现了一个新的物种，怎么判断它是哺乳动物还是非哺乳动物呢?一种方法是针对物种的特征提出一系列问题。第一个问题可能是，该物种是变温动物还是恒温动物?如果它是变温的，则该物种肯定不是哺乳动物，否则它或者是某种鸟，或者是某种哺乳动物。如果它是恒温的，需要接着问:该物种是由雌性产崽进行繁殖的吗?如果是，则它肯定为哺乳动物，否则它有可能是非哺乳动物(鸭嘴兽和针鼹这些产蛋的哺乳动物除外)。

上面的示例说明，通过提出一系列精心构思的关于检验记录属性的问题，可以解决分类问题。每当一个问题得到答案，后续的问题将随之而来，直到得到记录的类标号。这一系列的问题和这些问题的可能回答可以组织成决策树的形式。决策树是一种由结点和有向边组成的层次结构。图4－2所示为哺乳类动物分类问题的决策树，树中包含三种结点如下:

根结点，它没有入边，但有零条或多条出边；(www.xing528.com)

内部结点，恰有一条入边和两条或多条出边；

叶结点或终结点，恰有一条入边，但没有出边。

在决策树中，每个叶结点都被赋予一个类标号。非终结点(包括根结点和内部结点)包含属性测试条件，用于分开具有不同特性的记录。例如，在图4－2中，在根结点处，使用体温这个属性把变温脊椎动物和恒温脊椎动物区别开来。因为所有的变温脊椎动物都是非哺乳动物，所以用一个类名称为非哺乳动物的叶结点作为根结点的右子女。如果脊椎动物是恒温的，则接下来用胎生这个属性来区分哺乳动物与其他恒温动物(主要是鸟类)。

图4－2　哺乳动物分类问题的决策树

一旦构造了决策树，对检验记录进行分类就相当容易了。从树的根结点开始，将测试条件用于检验记录，根据测试结构选择适当的分支。沿着该分类或者到达另一个内部结点，使用新的测试条件，或者到达一个叶结点。到达叶结点之后，叶结点的类名称就被赋值给该检验记录。