陈群贤 上海电机学院高职学院

1 决策树（decision tree)

1.1 决策树算法的描述

决策树是分类和预测的挖掘方法中应用较为广泛的模式之一，是一种由内部结点、分叉及叶结点构成的，用来表示决策树规则的树结构，其中，内部结点表示某种检验属性，分叉表示检验的结果，叶结点表示类或某一类的分类，而顶点称为根结点。在构建的决策树中，从根节点到叶结点的一条路径就对应着一条分类规则，其构建的过程，取决于检验属性的选择以及分叉点的确定。不同决策树算法采用的属性分割法不同，常用的决策树算法主要有：ID3、C4.5、GINT等。

1.2 决策树构造过程所遵循的原则

如果把一个节点（非叶子节点）看做是提一个问题，那么原则就是：尽可能先提最重要的问题，通过最少的问题得到最多的信息。所以对于决策树来说，就是希望从根节点走到叶节点的决策路径越短越好。如果说把决策树中每一个非叶子节点看做是对样本的某个特征进行提问。那么我们可以这样认为：构造决策树，就是要正确地选择特征，使得决策树尽可能地矮。

如何用贪心法来构造一颗“矮”的决策树？我们在构造决策上并选择特征的时候，为了缩短决策路径，就需要让测试样本的不确定性尽可能地少。建立规则的过程如下：首先利用数据集根据特征属性计算信息增益，然后选择具有最大信息增益的特征属性作为根节点，以该特征属性的每个数值作为一个分支，最后根据特征属性的每个数值划分的数据集只包含一个数值或者只包含一个特征属性为止。……