第四章 决策树(decision tree)
决策树也是归纳学习中常用的一种知识表示形式，常用于分类。同时，也是发现概念描述空间的一种有效方法。决策树的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。
教学目的：
? 掌握决策树学习的概念
? 重点掌握ID3学习算法以及决策树的构造 ? 了解目前常用的决策树改进方法
4.1 概念描述空间的归纳学习
归纳学习旨在从大量的经验数据中归纳抽取出一般的规则和模式，因而成为知识获取的主要手段，在专家系统、模式识别、图像处理、语音识别等领域都有重要应用。归纳学习是机器学习最核心、最成熟的分支。
[示例] 数字识别应用：假设有三类数字，即0，1，2。每类有两个例子，每个例子有四个属性描述，即孔数（#hole）、端点数（#end）、交叉点数（#cross）、右上弧数（#right-arc）。如表所示。
可归纳产生三类数字的如下规则： 0类：[#hole=1][#cross=0] 1类：[#hole=0][#right-arc=0] 2类：[#end=2][#right-arc=1]
归纳学习是符号学习中研究得最为广泛的一种方法。思想是：给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。
归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是
泛化和特化。泛化用来扩展某一假设的语义信息，使其能包含更多的正例，应用于更多的情况；特化是泛化的相反操作，用于限制概念描述的应用范围。
[示例] 假设我们被要求从一副扑克牌中选择一张牌，如果选到好牌就可以获奖。已
知前面被抽出的牌有：梅花4、梅花7、黑桃2、红桃5和黑桃J，其中前三张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。
解：取纸牌的一组属性：V1---花色（Suit）和阶V2---（Rank），如：梅花4
显然，纸牌的示例空间V1?V2就是所有牌的集合。它是由属性Suit和Rank所定义的，其中，属性V1,V2的可观察值集合为：
V1?{clubs,spades,diamonds,hearts}---梅花、黑桃、方块、红桃 V2?{1,2,3,4,5,6,7,8,9,10,J,Q,K} 每个示例就是单张牌。
设X是一组确定属性决定的示例空间（如，V1?V2）；H是定义在X上的假设空间（如，H={梅花4、梅花7、黑桃2、红桃5和黑桃J }），也就是用X的属性按一定的逻辑形式定义的一组概念。Q是定义在X上的目标概念c的示例有限集，我们定义Q的描述空间是由H中适合Q的全部示例的假设构成的集合。
如果示例空间是有限的，且目标概念c是H的成员。当新的示例添加到Q中时，Q描述空间将收缩，最终直到仅包含目标概念c，这时称描述空间被穷尽。
对描述空间可以用描述图来表示，它是一个无回路的有向图，其中各节点是描述空间的元素。如果从节点p到q有一条弧，当且仅当下面两条性质成立：
? p比q特殊；
? 不存在节点r，它比p普遍，比q特殊。
取PE={梅花4、梅花7、黑桃2}为正例；NE={红桃5和黑桃J }为反例。 这样对，梅花4是肯定示例，其描述图为
这里，c—clubs; b---black; n---num; a---any-suit或any-rank。图中从左到右表示suit从特殊到普遍，垂直方向从下到上表示Rank从特殊到普遍；ba表示的概念为
(suit?black)?(Rank?any?rank)，即所有黑色的牌。
这时增加新的示例，如梅花7，能修剪描述空间。删除三个涉及阶是4的概念，因为它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5可修剪掉aa和an，因为这两个概念覆盖该否定示例；肯定示例黑桃2剪掉梅花，最后由否定示例黑桃J将描述空间缩小到单个概念bn，即黑色数字牌。 4.2 决策树学习
决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本信息中信息量最大的属性。中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。
决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。
决策树的内部结点是属性或属性集，称为测试属性；叶结点是所要学习划分的类。
先用训练实例集产生决策树，然后用其对未知实例集进行分类。
对实例进行分类时，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。
[例如] 一棵基于表1中数据的用于检测网络入侵行为的决策树。
这个决策树，用IP端口和系统名称标示内部结点，用入侵和正常表示叶结点，如下图描述。
决策树可转换成如下的规则：（C++表示）
If (System name=Artemis)