2、的决策树学习算法大多数已开发的决策树学习算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法（Quinlan1986）和后继的C4.5算法（Quinlan1993）的基础。下面将给出决策树学习的基本算法，大致相当于ID3算法。基本的ID3算法通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根结点被测试？”这个问题开始的。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根结点的测试。然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是，样例的该属性值对应的分支）之下。然后重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索（greedysearch），也就是算法从不回溯重新考虑以前的选择。下表描述了该算法的一个简化版本专门用来学习布尔值函数（即概念学习）。表1-1专用于学习布尔函数的ID3算法概要ID3是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样
3、例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。ID3(Examples，Target_attribute，Attributes)Examples即训练样例集。Target_attribute是这棵树要预测的目标属性。Attributes是除目标属性外供学习到的决策树测试的属性列表。返回能正确分类给定Examples的决策树。创建树的Root结点如果Examples都为正，那么返回label=+的单结点树Root如果Examples都为反，那么返回label=-的单结点树Root如果Attributes为空，那么返回单结点树Root，label=Examples中最普遍的Target_attribute值否则AAttributes中分类Examples能力最好*的属性Root的决策属性A对于A的每个可能值vi在Root下加一个新的分支对应测试A=vi令为Examples中满足A属性值为vi的子集ivExamples如果为空i在这个新分支下加一个叶子结点，
4、结点的label=Examples中最普遍的Target_attribute值否则在这个新分支下加一个子树ID3（,ivExamplesTarget_attribute,Attributes-A）结束返回Root*根据公式的定义，具有最高信息增益（informationgain）的属性是最好的属性。1.2序列覆盖算法序列覆盖算法它的学习规则集的策略为：学习一个规则，移去它覆盖的数据，再重复这一过程。这样的算法被称为序列覆盖（sequentialcovering）算法。想象我们已有了一个子程序learn-one-rule，它的输入为一组正例和反例，然后输出单个规则，它能够覆盖许多正例，并且覆盖很少的反例。我们要求这一输出的规则有较高的精确度，但不必有较高的覆盖度。较高的精确度说明它所做出的预测应为正确的。可接受较低的覆盖度，表示它不必对每个训练样例都作出预测。有了这样一个学习单个规则的learn-one-rule子程序，要学习规则集，一个明显的方法是在所有可用训练样例上执行learn-one-rule，再移去由其学到的规则覆盖的正例，再在剩余的训练样
5、例上执行它以学习第二个规则。该过程可重复若干次，直到最后学习到析取规则集，它们共同覆盖正例，覆盖程度达到所希望的比例。算法被称为序列覆盖算法是因为它按次序学习到一组规则，它们共同覆盖了全部正例。最终的规则集可被排序，这样分类新实例时可先应用精度最高的规则。序列覆盖算法的一个原型在表1-2中陈述。序列覆盖算法是广泛使用的学习析取规则集算法的其中之一。它将学习析取规则集的问题化简为一系列更简单的问题，每个子问题只需学到单个合取规则。由于它执行的是一种贪婪搜索，形成序列化的规则且没有回溯，所以它不能保证找到能覆盖样例的最小的或最佳的规则。如何设计learn-one-rule程序以达到序列覆盖算法的要求？我们需要一个算法能够形成有较高精度的规则，但不必覆盖所有的正例。在本节中展示了各种算法，并描述了它们在学术研究上已探索的主要差别。本节只考虑命题规则。后面的节中将把这些算法扩展到一阶Horn子句。表1-2学习析取的规则集的序列覆盖算法。learn-one-rule必须返回单个的能覆盖某些Examples的规则。performance是用户提供的子程序，以评估规则的质量。
6、当算法再也不能学习到一个性能超过给定阈值Threshold的规则时，该算法终止。Sequential-covering(Target_attribute,Attributes,Examples,Threshold)Learned_rulesRulelearn-one-rule(Target_attribute,Attributes,Examples)当performance(Rule,Examples)Threshold，做：Learned_rulesLearned_rules+RuleExamplesExamples-被Rule正确分类的样例Rulelearn-one-rule(Target_attribute,Attributes,Examples)Learned_rules按照在Examples上的performance排序的Learned_rules返回Learned_rules1.3一般到特殊柱状搜索实现learn-one-rule的一个有效途径是将假设空间搜索过程设计为与ID3算法中相似的方式，但在每
7、一步只沿着最有希望的分支向下。如图1-3所示的搜索树，搜索开始于最一般的规则前件（即能匹配所有实例的空测试），然后贪婪地加入那些在训练样例上性能改进最大的属性测试。一旦该测试被加入，该过程重复，贪婪地加入第二个属性测试，依此类推。如ID3那样，该过程通过贪婪地增加新的属性测试来获得假设，直到该假设的性能到达一可接受的程度。与ID3不同的是，此learn-one-rule的实现在每一步沿着单个分支即产生最佳性能的属性-值对，而不是用增长子树的办法覆盖所选属性的所有可能值。这种实现learn-one-rule的途径执行的是对可能存在的规则的一般到特殊搜索，以得到一个有较高精度但不一定完全覆盖数据的规则。如在决策树学习中那样，有许多方法可以定义选择“最佳”分支的度量标准。与在ID3中类似，我们可定义最佳分支为它覆盖的样例有最低的熵（）。图1-3Learn-one-rule从一般到特殊过程中的规则前件搜索在每一步，最佳规则的前件被以各种可能方式特化。规则后件是由满足前件的样例所决定的。该图显示的是宽度为1的柱状搜索。上面推荐的一般到特殊搜索是一种不带回溯
8、的贪婪深度优先搜索。如其他贪婪搜索一样，它所带来的危险是每一步可能作出了次优的选择。为减小这种风险，可将此算法扩展为一种柱状搜索（beamsearch），即每一步算法保留k个最佳候选的列表，在每一搜索步对这k个最佳候选生成分支（特化），并且结果集再被削减至k个最可能成员。柱状搜索跟踪当前最高分值假设的最有希望的替代者，以使每一步中它们的所有后继都被考虑到。该一般到特殊柱状搜索用于CN2程序，它由Clark&Niblett（1989）提出。该算法在表1-3中描述。表1-3learn-one-rule的一种实现是一般到特殊柱状搜索。当前假设的边缘表示为变量Candidate_hypotheses。该算法与Clark&Niblett（1989）描述的CN2程序相类似。Learn-one-rule(Target_attribute,Attributes,Examples,k)返回一个覆盖若干样例的规则。实施一般到特殊贪婪柱状搜索以得到最佳规则，由performance度量来引导。初始化Best_hypothesis为最一般的假设初