数据分析培训系列—分类算法之决策树（二）

从零开始学挖掘——分类算法之决策树（二）

2 如何建立决策树

原则上，对于给定的属性集，可以构造的决策树的数目达到指数级。尽管某些决策树比其他决策树更准确，但是由于搜索空间是指数规模的，找出最佳决策树在计算上是不可行的。尽管如此，人们还是开发了一些有效的算法，能否在合理的时间内构造出具有一定准确率的次最优决策树。这些算法通常都采用贪心策略，在选择划分数据的属性时，采取一系列局部最优决策来构造决策树，hunt算法就是一种这样的算法。它是许多决策树算法的基础，包括ID3、C4.5和CART。本节讨论hunt算法并解释它的一些设计问题。

在hunt算法中，通过将训练记录相继划分成为较纯的子集，以递归方式建立决策树。设Dt是与节点t相关联的训练记录集，而y={y1,y2……yc}是类标号，hunt算法的递归定义如下。

• 如果Dt中所有记录都属于同一类yt，则t是叶结点，用yt标记。
• 如果Dt中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女节点，并根据测试结果将Dt中的记录分布到子女节点中。然后，对于每个子女节点，递归地调用该算法。

例如，我们来预测贷款申请者是否会按时归还贷款。数据如下表所示

该分类问题的初始决策树只有一个结点，类标号为“拖欠贷款者=否”，如图a，意味着大多数贷款这都按时归还贷款。然而，该树需要进一步的细化，因为根结点包含两个类的记录。根据“有房者”测试条件，这些记录被划分为较小的子集，如图b。选取属性测试条件的理由稍后讨论，目前，我们假定此处这样选是划分数据的最优标准。接下来，对根结点的每个子女递归hunt算法。上表中数据显示，有房的贷款者都按时偿还了贷款，因此，根结点的左子女为叶结点，标记为“拖欠贷款者=否”。对于右子女，我们需要继续递归调用hunt算法，直到所有的记录都属于同一类为止。每次递归调用所形成的决策树显示在图c和图d中。

如果属性集的每种组合都在训练数据中出现，并且每种组合都具有惟一的类标号，则hunt算法是有效的。但是对于大多数实际情况，这些假设太苛刻了，因此，需要附加的条件来处理以下的情况。

• 算法的第二步所创建的子女节点可能为空，即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合，这种情况就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记录中的多数类。
• 在第二步中，如果与Dt相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点，其标号为与该节点相关联的训练记录中的多数类。

下面，我们和大家讨论一下决策树归纳的学习算法必须解决下面两个问题

• 如果分裂训练记录，树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分为较小的子集。为了实现这个步骤，算法必须提供为不同类型的属性制定测试条件的方法，并且提供评估每种测试条件的客观度量。
• 如何停止分裂过程，需要有结束条件，以终止决策树的生长过程，一个可能的策略是分裂结点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但是还可以使用其他的标准提前终止树的生长过程。提前终止的优点我们在后续继续讨论。

3表示属性测试条件的方法

决策树归纳算法必须为不同类型的属性提供表示属性测试条件和其对应输出的方法。

二元属性：此种测试条件产生两个可能的输出。

标称属性：有多个属性值，它的测试条件可以用两种方法表示，第一种方法，对于多路划分，该属性有多少个不同的属性值就有多少个输出；第二种方法，k个属性可以生成2^k-1-1个二元划分。

序数属性：也可以产生二元或多路划分，只要不违背序数属性值得有序性，就可以对属性值进行分组。

连续属性：对于连续属性来说，测试条件可以是具有二元输出比较测试（A<v）或者（A>=v），也可以是具有形如vi<=A<=vi+1(i=1……k)输出的范围查询产生二元或多路划分，只要不违背序数属性值得有序性，就可以对属性值进行分组。对连续性属性使用离散策略，每个离散化区域赋予一个新的序数值，只要保持有序性，相邻的值还可以聚集成较宽的区间。

本节中我们介绍了决策树的构造方式，以及各种属性测试条件的对应输出方法，对于决策树来说，另一个重要问题则是，选择什么度量来确定划分记录的最佳方式，即选择最佳划分的度量，我们将在第三节中详细介绍。