从实例中归纳决策树

18.3.3 从实例中归纳决策树

布尔决策树的一个实例是由一个输入属性向量X以及一个唯一的布尔输出值y组成的。一个实例集合（X1,y1）,…,（X12,y12）如图18.3所示。其中正例是目标WillWait为真的那些实例（X1,X3,…）；反例是WillWait为假的那些实例（X2, X5, …）。完整的实例集合被称作训练集。

图18.3 餐馆域的实例

找到与训练集相符的决策树的问题看起来也许比较困难，但是实际上存在一个平凡解。我们可以简单地构造一棵决策树，针对每个实例，树中都有一条到达叶节点的路径，其中每条路径都依次测试每个属性，遵循实例得到的值，并且叶节点包含对实例的分类。当再次给定相同的实例时[3]，决策树会得到正确的分类。不幸的是，它对其他情况无法进行判断！

这棵平凡树的问题在于它只记住了所观察到的数据。它没有从实例中抽取出任何模式，所以我们不应该指望它能够对自己没有见到过的实例进行推断。利用奥卡姆剃刀原则，我们应该能够替代地找到与实例一致的最小决策树。不幸的是，对于任何“最小”的合理定义，找到最小树是不可操作的问题。不过利用一些简单的启发过程，我们可以很好地找到“较小的”树。DECISION-TREE-LEARNING （决策树学习）算法背后的基本思想是，首先测试最重要的属性。通过所谓“最重要的”，我们表达的含义是：使得某实例的分类与其他实例最不同的属性。这样，我们希望能够通过较少数量的测试就能得到正确的分类，意味着树中所有的路径都很短，而且整棵树规模比较小。

图18.4显示了这个算法是如何开始的。我们有12个训练实例，分为正例和反例集合。然后我们决定哪个属性用作树中的第一个测试。图18.4（a）显示了Ty p e并不是一个有用的属性，因为它给我们留下4个可能的输出，每个输出中的正例和反例数目相同。另一方面，在图18.4（b）中，我们发现Patrons是一个相当重要的属性，因为如果Patrons的值是None或是Some，就给我们留下可以明确回答的实例集合（即分别回答No或Yes）。如果Patrons的值是Full，会给我们留下一个混合的实例集合。一般来说，在第一个属性测试将实例进行划分之后，每个输出结果本身又都是一个新的决策树学习问题，只是实例个数减少了，而且属性也少了一个。以下是对于这些递归问题要考虑的4种情况：

图18.4 通过属性测试划分实例。（a）根据Type划分并不能更好地区分正例和反例。（b）根据Patrons属性划分则可以很好地分离正例和反例。在根据Patrons划分之后，Hungry是第二个相当好的测试

① 如果存在一些正例和一些反例，那么就要选择划分它们的最佳属性。图 18.4（b）显示了用Hungry来划分剩余的实例。

② 如果所有剩余的都是正例（或都是反例），那么我们已经完成：我们可以回答Ye s或N o。图18.4 （b）则显示了处于None和Some情况下的这样的实例。

③ 如果没有剩下的实例，这意味着没有观察到这样的实例，那么我们则返回一个缺省值，是通过该节点的父节点的主要类别计算得到的。

④ 如果没有剩下的属性，但是还有剩下的正例和反例，那么就出问题了。这意味着这些实例有相同的描述，却属于不同的分类。这种情况发生在某些数据不正确时；我们称在数据中有噪声。

它也发生在属性不能提供完整描述情景的足够信息时，或者该问题实际上是非确定性的时候。

一个简单解决办法是进行多数投票。

DECISION-TREE-LEARNING算法如图 18.5 所示。有关 CHOOSE-ATTRIBUTE（选择属性）方法的细节将会在下一小节中讲述。

图18.5 决策树学习算法

将该算法应用于12个实例的一个数据集而产生的最终树如图18.6所示。尽管所采用的数据实际上是由使用原始树的智能体产生的，但是这棵树显然与图 18.2 中所示的原始树不同。有人可能会因此认为学习算法在学习正确函数方面做的不是很好。然而，这个结论是错误的。学习算法着眼于实例，而不是正确的函数，事实上，它的假设（参见图18.6）不仅与所有实例相符，而且比原始树要简单得多。学习算法没有理由包含对 Raining 和 Reservation 的测试，因为不用它们也能区分所有的实例。而且它还能够检测到一个有趣的、以前没有发现的模式：本书第一作者将在周末等待泰国菜。

图18.6 从12实例训练集归纳出的决策树

当然，如果我们要搜集更多的实例，我们可能会归纳出更接近于原始树的一棵树。图18.6中的树一定会出错；例如，它从来没见到过等候时间是 0～10 分钟而餐馆是满座的情况。在 Hungry 为假的情况下，决策树的判断是不要等候，而我（SR）肯定会等待。这提出了一个显而易见的问题：如果算法从实例中推导出一棵一致但不正确的树，那么这棵树有多不正确？在解释属性选择步骤的细节之后，我们将说明如何实验地分析这个问题。