数据挖掘与知识发现(讲稿4---决策树学习技术)

┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1第四章决策树(decisiontree)决策树也是归纳学习中常用的一种知识表示形式，常用于分类。同时，也是发现概念描述空间的一种有效方法。决策树的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。教学目的：掌握决策树学习的概念重点掌握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]归纳学习是符号学习中研究得最为广泛的一种方法。思想是：给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊2泛化和特化。泛化用来扩展某一假设的语义信息，使其能包含更多的正例，应用于更多的情况；特化是泛化的相反操作，用于限制概念描述的应用范围。[示例]假设我们被要求从一副扑克牌中选择一张牌，如果选到好牌就可以获奖。已知前面被抽出的牌有：梅花4、梅花7、黑桃2、红桃5和黑桃J，其中前三张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。解：取纸牌的一组属性：1V---花色（Suit）和阶2V---（Rank），如：梅花4显然，纸牌的示例空间21VV就是所有牌的集合。它是由属性Suit和Rank所定义的，其中，属性21,VV的可观察值集合为：},,,lub{1heartsdiamondsspadesscV---梅花、黑桃、方块、红桃},,,10,9,8,7,6,5,4,3,2,1{2KQJV每个示例就是单张牌。设X是一组确定属性决定的示例空间（如，21VV）；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表示的概念为)()(rankanyRankblacksuit，即所有黑色的牌。┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊3这时增加新的示例，如梅花7，能修剪描述空间。删除三个涉及阶是4的概念，因为它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5可修剪掉aa和an，因为这两个概念覆盖该否定示例；肯定示例黑桃2剪掉梅花，最后由否定示例黑桃J将描述空间缩小到单个概念bn，即黑色数字牌。4.2决策树学习决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本信息中信息量最大的属性。中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树的内部结点是属性或属性集，称为测试属性；叶结点是所要学习划分的类。先用训练实例集产生决策树，然后用其对未知实例集进行分类。对实例进行分类时，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。[例如]一棵基于表1中数据的用于检测网络入侵行为的决策树。这个决策树，用IP端口和系统名称标示内部结点，用入侵和正常表示叶结点，如下图描述。决策树可转换成如下的规则：（C++表示）If(Systemname=Artemis)┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊4{Intrusion=false;}Else{If(IPport=002210){Intrusion=true;}else{if(IPport=004020){Intrusion=true;}Else{if(IPport=000010){Intrusion=false;}}}根据决策树的各种不同属性，有以下几种不同的决策树：①决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性，也可能是多变量的，即存在包含多个属性的内结点；②根据测试属性的不同属性值的个数，可能使每个内结点有两个或多个分支。如果每个内结点只有两个分支，则称之为二叉树决策树；③每个属性可能是值类型，也可能是枚举类型；④分类结果既可能是两类，也可能是多类。如果二叉决策树的结果只能有两类，则称之为布尔决策树。对布尔决策树可很容易以析取范式的方式表示。如下图为)()(14323XXXXX的析取范式。另外，所有的决策树学习都有一些等价的网络表示形式。如上图的人工神经网络与决策树表达了同一个析取概念)()(14323XXXXX，所执行的功能相同。4.3CLS学习算法概念学习系统（CLS：ConceptLearningSystem）是1966年由Hunt等人提出的，是早期决策树学习算法，后来的决策树学习算法均可视为CLS算法的改进和更新。CLS算法的主要思想是：从一个空的决策树出发，选择某一属性（分类属性）作为测试属性，该测试属性对应决策树中的决策结点，根据该属性值的不同，可将训练样本分成相应的子集。如果该子集为空，或该子集中的样本属于同一类，则该┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊5子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点。需再选择一个新的分类属性对该子集进行划分，直至所有的子集者为空或属于同一类为止。例如，假设有一组人，眼睛和头发的颜色及所属的人种情况如下表：假设首先选择{眼睛颜色}作为测试属性，则从该结点引出三个分支图：选择眼睛颜色作为决策属性这三个分支将样本集分成三个子集{1，6}、{2，4，8}和{3，5，7}。但这三个子集中的元素都不属于同一结果类，因此它们都不是叶结点，需要继续划分，即需要添加新的测试结点。如{头发颜色}，由于{头发颜色}={黑色，金色，红色}，所以从子集中可引出三个新的分支：图：添加头发颜色作为新的决策属性通过增加结点逐步求精，直到生成一棵能正确分类训练样本的决策树。学习算法CLS算法的步骤可描述为：①令决策树T的初始状态只含有一个树根（X，Q），其中X是全体训练实例的集合，Q是全体测试属性的集合；②若T的所有叶结点（'',QX）都有如下状态：或者第一个分量'X中的训练┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊6实例都属于同一个类，或者第二个分量'Q为空，则停止执行学习算法，学习的结果为T；③否则，选取一个不具有步骤②所述状态的叶结点),(''QX；④对于'Q，按照一定规则选取测试属性b，设'X被b的不同取值分为m个不相交的子集miXi1,'，从),(''QX伸出m个分叉，每个分叉代表b的一个不同取值，从而形成m个新的叶结点}){,(''bQX，mi1；⑤转步骤②。从CLS的算法描述可以看出，决策树的构造过程也就是假设特化的过程。但CLS算法并没有规定采用何种测试属性。然而，测试属性集的组成以及测试属性的先后都对决策树的学习有着举足轻重的影响。此外，CLS算法所能处理的学习问题不能太大。4.4ID3（IterativeDichotomizer3）学习算法CLS算法的思路是找出最有分辨能力的属性，把数据库划分为许多子集（对应树的一个分枝），构成一个分枝过程，然后对每个子集递归调用分枝过程，直到所有子集包含同一类型数据。最后得到的决策树能对新的例子进行分类，但CLS的不足是（1）没给出如何选取测试属性b；（2）它处理的学习问题不能太大。为此，Quinlan提出了著名的以属性为分类节点的ID3学习算法，他是以信息熵的下降速度作为选取测试属性的标准，通过窗口来形成决策树。信息熵的下降也就是信息不确定性的下降。1）信息论简介信息论是由C.E.Shannon（信息论的创始人）1948年为解决信息传递（通信）过程问题而提出的以数学的方法来度量并研究信息的理论，也称为统计通信理论。他把一个传递信息的系统视为，由发送端（信源）、接收端（信宿）和连接两者的通道（信道）三者组成。其中，)|(XYP称为信道的传输概率或转移概率，它反映信道的输入与输出关系。可┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊7用矩阵来表示，称为转移概率矩阵。)|()|()|()|()|()|()|()|()|()|(212222111211rqrrqquvPuvPuvPuvPuvPuvPuvPuvPuvPXYP这里，riuvPqjij,,2,1,1)|(1。从此通信模型可看出，在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发什么样的具体信息，也不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性，而且这种不确定性是存在于通信之前的，因此又叫做先验不确定性。在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。但是，在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。换句话说，通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。（1）如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。（2）如果后验不确定性的大小等于零，这就表示作宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。下面介绍几个概念：信息（符号）iu（ri,,2,1）的发生概率)(iup组成信源数学模型（样本空间或概率空间）：)()()(],[2121rrupupupuuuPX①自信息量：消息iu发生后所含有的信息量。即在收到iu事件之前，收信者对信源发出iu的不确定性，定义为信号符号iu的自信息量)(iuI。即┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊