2.2　构造决策树

构造决策树是一个递归的过程，从整个数据集开始，根据条件将数据集分割为两个互补的子集。这个条件构成了树的分支节点，称为节点的 分支条件 。对于两个子数据集，我们递归地进行分割操作，分别形成节点的左右子树。当数据集被分割为仅包含单一类别的元素集合时，递归分割就终止了，这些不能继续分割的集合是叶节点。对于要分类的样本，可以根据样本特征值从根节点按照分支条件向下走，最终到达的叶节点类别就是样本的类别，这就是利用决策树进行分类的过程。构造决策树的过程可以形象地看作树木生长，从根节点开始分支，逐渐开枝散叶。因此决策树的构造算法也叫作树生长算法。

在构造决策树的过程中，选取分支条件非常重要，它决定了树的形态。如果我们随意选取样本特征和值作为分支条件，极有可能得到一棵非常深而且非常宽的决策树。这样的决策树显然要占据更多的存储空间，同时也要耗费更多的计算资源，因为在到达叶节点之前，我们需要做更多的判断。除了这些表面问题之外，一棵庞大复杂的决策树极有可能过拟合样本。由于每一次分类需要更多的前置条件，它极有可能采纳一些无关紧要的条件，而无法捕捉到最为关键的分类依据。这样的决策树“记住”了已知样本中太多次要细节，不利于识别没有出现过的新样本。比如，将动物分类决策树用于区分猫和狗，如果大量分支用于识别毛色、体重、四肢和尾巴长度等非关键信息，也许可以准确地识别出数据集中的已知样本，但是对于未知样本就很容易陷入错误。

这样看来，决策树的大小是成功构建决策树的重要参考依据，而构造一棵更小的决策树的关键是选择合适的分支条件，如图2.1所示。下面我们看如何用昆兰提出的ID3算法来解决这个问题。