选择属性测试

18.3.4 选择属性测试

应用于决策树学习中的属性选择方案是为了最小化最终树的深度而设计的。挑选属性的思想就是在提供实例的准确分类的方向上走得尽可能远。理想的属性是将实例分为只包含正例或只包含反例的集合。Patrons属性并不理想，但是它还是很不错的。一个确实没用的属性，诸如Type，使得实例集合仍具有和原始集合相同比例的正例和反例。

那么，我们所需要的是一个对“很不错”和“确实没用”的形式化度量，进而我们可以实现图18.5中的CHOOSE-ATTRIBUTE函数。当属性是理想属性时，该度量有最大值；当属性毫无用处时，该度量有最小值。一个比较合适的度量是由属性提供的期望信息量，在这里，我们所采用的是首先由香侬（Shannon）和Weaver（1949）以数学形式定义的术语。为了理解信息的概念，我们认为它为某问题提供了一个答案——例如，硬币是否会正面朝上。答案中包含的信息量取决于人的先验知识。知道的越少，提供的信息越多。信息论用比特（bit，二进制位）度量信息内容。1比特的信息足以回答毫不了解的一个“是/否”问题，比如抛掷一个均匀的硬币。一般来说，如果可能的答案vi的概率是P(vi)，那么实际答案的信息内容I则是：

为了检验这个等式，对于抛掷均匀的硬币问题，我们得到：

如果99％的情况都是硬币正面朝上，我们得到I(1/100, 99/100)=0.08比特，而且当正面朝上的概率趋近于1时，实际答案的信息趋近于0。

对于决策树学习，需要回答的问题是：对于给定的实例，正确分类是什么？一棵正确的决策树将回答这个问题。在所有属性被测试之前，对可能答案的概率估计是由训练集中的正例和反例的比例提供的。对正确答案中所包含信息的一个估计为：

图18.3中的餐馆训练集有p=n=6，则我们需要1比特的信息。

在单一属性A上的测试并不总是能告诉我们这么多的信息，但是可以提供一部分。我们可以通过观察在属性测试之后还需要多少信息，准确度量得到了多少信息。任何属性A都可以根据属性A的值将训练集E划分为几个子集E1, … , Ev，其中A可以有v个不同的值。每个子集Ei包含着pi个正例和ni个反例，所以如果我们沿着这个分支前进，我们将需要额外的I(pi/ (pi+ni), ni/ (pi+ni))比特的信息量来回答这个问题。从训练集合中随机选择具有该属性的第i个值的实例，概率为(pi+ni) / (p+n)，所以平均起来，在测试完属性A之后，我们还需要

比特的信息量对实例进行分类。从属性测试中得到的信息增益是原始的信息需求和新的信息需求之间的差异：

CHOOSE-ATTRIBUTE函数中用到的启发式是选择增益最大的属性。回到图 18.4 中考虑的属性，我们得到：

这证实了我们的直觉，即Patrons是较好的用于划分的属性。实际上，Patrons是所有属性中增益最大的，可以被决策树学习算法选择为根节点。