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

装订线第四章 决策树(decision tree)决策树也是归纳学习中常用的一种知识表示形式，常用于分类。同时，也是发现概念描述空间的一种有效方法。决策树的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。教学目的：l 掌握决策树学习的概念l 重点掌握ID3学习算法以及决策树的构造l 了解目前常用的决策树改进方法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，其中前三张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。解：取纸牌的一组属性：-花色（Suit）和阶-（Rank），如：梅花4显然，纸牌的示例空间就是所有牌的集合。它是由属性Suit和Rank所定义的，其中，属性的可观察值集合为： -梅花、黑桃、方块、红桃 每个示例就是单张牌。设X是一组确定属性决定的示例空间（如，）；H是定义在X上的假设空间（如，H=梅花4、梅花7、黑桃2、红桃5和黑桃J ），也就是用X的属性按一定的逻辑形式定义的一组概念。Q是定义在X上的目标概念c的示例有限集，我们定义Q的描述空间是由H中适合Q的全部示例的假设构成的集合。如果示例空间是有限的，且目标概念c是H的成员。当新的示例添加到Q中时，Q描述空间将收缩，最终直到仅包含目标概念c，这时称描述空间被穷尽。对描述空间可以用描述图来表示，它是一个无回路的有向图，其中各节点是描述空间的元素。如果从节点p到q有一条弧，当且仅当下面两条性质成立：l p比q特殊；l 不存在节点r，它比p普遍，比q特殊。取PE=梅花4、梅花7、黑桃2为正例；NE=红桃5和黑桃J 为反例。这样对，梅花4是肯定示例，其描述图为这里，cclubs; b-black; n-num; a-any-suit或any-rank。图中从左到右表示suit从特殊到普遍，垂直方向从下到上表示Rank从特殊到普遍；ba表示的概念为 ，即所有黑色的牌。这时增加新的示例，如梅花7，能修剪描述空间。删除三个涉及阶是4的概念，因为它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5可修剪掉aa和an，因为这两个概念覆盖该否定示例；肯定示例黑桃2剪掉梅花，最后由否定示例黑桃J将描述空间缩小到单个概念bn，即黑色数字牌。4.2 决策树学习决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本信息中信息量最大的属性。中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树的内部结点是属性或属性集，称为测试属性；叶结点是所要学习划分的类。先用训练实例集产生决策树，然后用其对未知实例集进行分类。对实例进行分类时，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。例如 一棵基于表1中数据的用于检测网络入侵行为的决策树。这个决策树，用IP端口和系统名称标示内部结点，用入侵和正常表示叶结点，如下图描述。 决策树可转换成如下的规则：（C+表示）If (System name=Artemis) Intrusion=false;Else If (IP port=002210)Intrusion=true; else if (IP port=004020)Intrusion=true; Else if (IP port=000010) Intrusion=false; 根据决策树的各种不同属性，有以下几种不同的决策树： 决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性，也可能是多变量的，即存在包含多个属性的内结点； 根据测试属性的不同属性值的个数，可能使每个内结点有两个或多个分支。如果每个内结点只有两个分支，则称之为二叉树决策树； 每个属性可能是值类型，也可能是枚举类型； 分类结果既可能是两类，也可能是多类。如果二叉决策树的结果只能有两类，则称之为布尔决策树。对布尔决策树可很容易以析取范式的方式表示。如下图为的析取范式。 另外，所有的决策树学习都有一些等价的网络表示形式。如上图的人工神经网络与决策树表达了同一个析取概念，所执行的功能相同。4.3 CLS学习算法概念学习系统（CLS：Concept Learning System）是1966年由Hunt等人提出的，是早期决策树学习算法，后来的决策树学习算法均可视为CLS算法的改进和更新。CLS算法的主要思想是：从一个空的决策树出发，选择某一属性（分类属性）作为测试属性，该测试属性对应决策树中的决策结点，根据该属性值的不同，可将训练样本分成相应的子集。如果该子集为空，或该子集中的样本属于同一类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点。需再选择一个新的分类属性对该子集进行划分，直至所有的子集者为空或属于同一类为止。例如，假设有一组人，眼睛和头发的颜色及所属的人种情况如下表：假设首先选择眼睛颜色作为测试属性，则从该结点引出三个分支图：选择眼睛颜色作为决策属性这三个分支将样本集分成三个子集1，6、2，4，8和3，5，7。但这三个子集中的元素都不属于同一结果类，因此它们都不是叶结点，需要继续划分，即需要添加新的测试结点。如头发颜色，由于头发颜色=黑色，金色，红色，所以从子集中可引出三个新的分支：图：添加头发颜色作为新的决策属性通过增加结点逐步求精，直到生成一棵能正确分类训练样本的决策树。学习算法CLS算法的步骤可描述为： 令决策树T的初始状态只含有一个树根（X，Q），其中X是全体训练实例的集合，Q是全体测试属性的集合； 若T的所有叶结点（）都有如下状态：或者第一个分量中的训练实例都属于同一个类，或者第二个分量为空，则停止执行学习算法，学习的结果为T； 否则，选取一个不具有步骤所述状态的叶结点； 对于，按照一定规则选取测试属性b，设被b的不同取值分为m个不相交的子集，从伸出m个分叉，每个分叉代表b 的一个不同取值，从而形成m个新的叶结点，； 转步骤。从CLS的算法描述可以看出，决策树的构造过程也就是假设特化的过程。但CLS算法并没有规定采用何种测试属性。然而，测试属性集的组成以及测试属性的先后都对决策树的学习有着举足轻重的影响。此外，CLS算法所能处理的学习问题不能太大。4.4 ID3（Iterative Dichotomizer 3）学习算法CLS算法的思路是找出最有分辨能力的属性，把数据库划分为许多子集（对应树的一个分枝），构成一个分枝过程，然后对每个子集递归调用分枝过程，直到所有子集包含同一类型数据。最后得到的决策树能对新的例子进行分类，但CLS的不足是（1）没给出如何选取测试属性b；（2）它处理的学习问题不能太大。为此，Quinlan提出了著名的以属性为分类节点的ID3学习算法，他是以信息熵的下降速度作为选取测试属性的标准，通过窗口来形成决策树。信息熵的下降也就是信息不确定性的下降。1）信息论简介信息论是由C.E.Shannon（信息论的创始人）1948年为解决信息传递（通信）过程问题而提出的以数学的方法来度量并研究信息的理论，也称为统计通信理论。他把一个传递信息的系统视为，由发送端（信源）、接收端（信宿）和连接两者的通道（信道）三者组成。其中，称为信道的传输概率或转移概率，它反映信道的输入与输出关系。可用矩阵来表示，称为转移概率矩阵。 这里，。从此通信模型可看出，在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发什么样的具体信息，也不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性，而且这种不确定性是存在于通信之前的，因此又叫做先验不确定性。在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。但是，在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。换句话说，通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。（1） 如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。（2） 如果后验不确定性的大小等于零，这就表示作宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。下面介绍几个概念：信息（符号）（）的发生概率组成信源数学模型（样本空间或概率空间）： 自信息量：消息发生后所含有的信息量。即在收到事件之前，收信者对信源发出的不确定性，定义为信号符号的自信息量。即其中，为信源发出事件的概率； 信息熵：自信息的数学期望。因为自信息量只能反映符号收到前的不确定性，而信息熵可以用来度量整个信源X整体的不确定性，即信源发出信息前的平均不确定性。定义如下： 其中，r为信源X所有可能的符号数，即用信源每发一个符号所提供的平均自信息量来定义信息熵。上式中，对数底数可为任何正数，不同的取值对应熵的不同单位，但通常取；并规定：当时，。 当对数的底为2时，的单位为比特（bit）； 当对数的底为时，的单位为奈特（nat）； 当对数的底为10时，的单位为哈特（hart）； 1奈特=1.44比特； 1哈特=3.32比特。 的性质如下：l =0时，说明只存在着唯一的可能性，不存在不确定性；l 如果n种可能的发生都具有相同的概率，即对所有的，有，则达到最大值，说明系统的不确定性最大；l 互相越接近，就越大；相差大，则就小。如果信道中无干扰（噪声），信道输出符号与输入符号一一对应，那么接收到传送过来的符号后，就消除了对发送符号的先验不确定性。后验熵一般信道中有干扰存在，信宿接收到符号V后，对信源发出的是什么符号仍有不确定性。对此如何度量？当没有接收到输出符号V时，已知发出符号U的概率分布P(U)，而接收到输出符号后，输入符号的概率分布发生了变化，变成了后验概率分布。那么，接收到输出符号后，关于U的平均不确定性为： 这就是接收到输出符号后关于U的后验熵。即后验熵是当信道接收到输出符号后，关于输入符号U的信息度量。条件熵后验熵在输出符号集V的范围内是个随机量，所以对于后验熵在输出符号集V中求期望，得到条件熵： = （*）这个条件熵称为称为信道疑义度。它表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存在的不确定性（存在疑义）。对U集尚存在的不确定性是由于干扰（噪声）引起的，如果是一一对应，那么接收到符号集V后，对U集的不确定性完全消除，则信道疑义度。在决策分类中，假设是训练样本集，是训练样本数；样本划分为个不同的类，则任意样本属于类的概率为 所以，样本的平均信息熵为 如果为中取有限个不同值的属性，样本集划分为个不同的子集，则由式（*）知，由属性划分的决策树分类的平均条件熵为 若设表示为子集中类的样本数，则。 信息增益：一般，样本分类的熵值发生了变化，即属性对于分类提供了信息，熵的变化量称为属性对于分类的信息增益，则 （证明略）从上式知，测试属性将减少决策数分类的不确定程度。2）ID3学习算法Quinlan的ID3算法就是选择使最大的属性作为测试属性，即选择使最小的属性a作为测试属性。此外，ID3中还引入了窗口方法进行增量学习来解决实例过大问题。具体算法为： 选出整个训练实例集X的规模为W的随机子集；（W称为窗口规模，子集称为窗口） 以使得式（*）的值最小为标准，选取每次的测试属性，形成当前窗口的决策树； 顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外，则训练结束； 组合当前窗口的一些训练实例与某些在中找到的例外，形成新的窗口，转。示例 表4.1给出了一个可能带有噪声的数据集合。它有4个属性：Outlook,Temperature，Humidity和windy。它被分为两类：P和N分别表示正例和反例。试构造决策树将数据进行分类。解：因为初始时刻属于P类和N类的实例个数均为12个，所以初始时刻的熵值为： 如果选取Outlook属性作为测试属性，则由式（*）有 表4.1 样本数据集可以看出，最小，即有关Outlook的信息对于分类有最大的帮助，提供最大的信息量，即最大。所以选择Outlook属性作为测试属性，就可将训练实例集分为三个子集，生成三个叶结点，对每个叶点依次利用上面的过程，则最终生成如下的决策树：3）基于ID3的信息增益的决策树构造算法ID3算法有着广泛的应用，其中较为著名的有C4.5 、C5.0系统。C4.5的新功能是它能将决策树转换为等价的规则表示，并且解决了连续取值的学习问题。（1）ID3算法的基本原理 设是n维有限向量空间，是有限离散符号集，E中的每一元素称为例子，。设PE和NE是E的两个例子集，分别称为正例集和反例集。，则ID3基于如下两种假设： 在向量空间E上的一棵正确决策树，对任意例子的分类概率同E中正例、反例的概率一致； 一棵决策树对一例子做出正确分类判别所需的信息为 如果属性A作为决策树的根且A具有v个值，则A可将E分成v个子集。假设中含有个正例和个反例，那么所需的期望信息是，以属性A为根分类所需的期望熵为 则A根的信息增益为 ID3的思想是选择最大（即最小）的属性作为根结点。其方法可推广到多类情况。（上面只研究正、反两类）设样本集E共有C类样本，每类样本数为，即。若以属性A作为决策树的根，A具有v个值可将E分成v个子集。假设中含有类样本的个数为，。则子集的信息量为 以A为根分类的信息熵为 （*）所以，选择属性使最小。（2）建树的算法步骤 对于任意的选择属性A，假设A有个属性值，对应的概率分别为 以属性A扩展，生成个子结点，是属性A取个值时，按照最小的信息熵原理选择的A的后继属性，分别对应的信息熵为； 根据公式（*）计算； 选择使最小，将作为根属性； 利用步骤的计算结果，建立结点的后继结点； 对所有的，若为叶结点，则停止扩展此结点。否则递归执行的过程。（3）应用实例决策树的构造主要分为两个阶段：建树阶段和调整阶段。例如 下面以某课堂教学评估数据库中的数据挖掘和知识发现为例。该课堂教学评估指标体系表共分为若干项，经研究可归纳为：教学态度（）、教学内容（）、教学方法（）、教学效果（）、评价（）共五项，实际数据见表1所示。由于属性初值为连续值，需进行离散化处理。将属性划分为若干个区段，C1：95100分、C2：8094分、C3：7079分、C4：6069分、C5：60分。见表2所示。解：去掉属性。因为对于结论属性而言，无互信息，亦称无信息增益，即。计算测试集的全部信息量：然后计算各结点的信息量，如 所以， 同理，可计算出信息熵： 故取为根属性。同样对这一分支继续使用ID3方法进一步划分，可得到如图所示的决策树。该决策树完全概括了教师教学评估的三个等级的20个记录。从图中可以看出： 教学是一重要指标。表1或表2中隐藏的知识有如下几种情况：规则1： IF （） THEN （良）规则2： IF （） THEN （中）规则3： IF （） THEN （优）规则4： IF （） THEN （良）即，如果教学内容为良，则课堂教学质量评价等级一定为良；如果教学内容为中，则课堂教学质量评价等级一定为中；如果教学内容和教学效果均为优，则课堂教学质量评价等级一定为优；如果教学内容为优而教学效果为良，则课堂教学质量评价等级为良。因此，从这些规则中，可以归纳出一条重要的知识，就是：教学内容组织好的老师，其课堂教学质量的综合评价成绩较好。4.5 C4.5方法ID3算法在数据挖掘中占有非常重要的地位。但是在应用中，ID3算法存在不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由J.R.Quinlan在1993年提出。C4.5克服了ID3在应用中存在的不足，主要体现在以下几个方面：（1） 用信息增益率来选择属性，它克服了信息增益选择属性时偏向于选择取值较多的属性的不足；（2） 在树构造过程中或者构造完成之后，进行剪枝；（3） 能够完成对连续属性的离散化处理；（4） 能够对于不完整数据进行处理；（5） C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。 4.5.1 构造决策树设T为数据集，类别集合为，选择一个属性V把T分为多个子集。设V有互不重合的个值，则T被分为个子集，这里中的所有实例的取值均为。令 为数据集T的例子数，为的例子数，为类的例子数，为例子中，具有类别的例子数。则有：（1）类别的发生概率：；（2）属性的发生概率：；（3）属性的例子中，具有类别的条件概率：。Quinlan在ID3中使用信息论中的信息增益（Gain）来选择属性，而C4.5采用属性的信息增益率（Gain Ratio）来选择属性。1、类别的信息熵 =2、类别条件熵按照属性V把集合T分割，分割后的类别条件熵为： = =3、信息增益，即互信息 4、属性V的信息熵 5、信息增益率 C4.5对ID3改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率”（C4.5）比采用“信息增益”(ID3)更好，主要是克服了ID3方法选择偏向于取值多的属性的不足。4.5.2 连续属性的处理在ID3中没有处理连续属性的功能。在C4.5中，设在集合T中，连续属性A的取值为，则任何在和之间的任意取值都可以把实例集合分为两部分 和可以看到，一共有种分割情况。对属性A的种分割的任意一种情况，作为该属性的两个离散取值，重新构造该属性的离散值，再按照上述公式计算每种分割所对应的信息增益率，在种分割中，选择最大增益率的分割作为属性A的分枝： 其中，则连续属性A可以分割为：4.5.3 决策树剪枝由于噪声和随机因素的影响，决策树一般会很复杂。因此，需要进行剪枝操作。1、什么时候剪枝？剪枝操作有两种策略：（1） 在树生成过程中判断是否继续扩展决策树。若停止扩展，则相当于剪去该结点以下的分枝；（2） 对于生成好的树剪去某些结点和分枝。C 4 .5采用的是第二种方法。 剪枝之后的决策树的叶结点不再只包含一类实例。结点有一个分布描述，即该叶结点属于某类的概率。2、基于误差的剪枝决策树的剪枝通常是用叶结点替代一个或者多个子树，然后选择出现概率最高的类作为该结点的类别。在C4.5中，还允许用其中的树枝来替代子树。如果使用叶结点或者树枝代替原来的子树之后，误差率若能够下降，则就使用此叶结点或者树枝代替原来的子树。3、误差率的判断设一个叶结点覆盖N个实例，其中E个为错误的。对于具有信任度CF的实例，计算一个2项分布，该2项分布，即实例的误判概率，那么N个实例判断错误的数目为。子树的错误数目为所有叶结点的总和。如：注：（）中为覆盖的实例数目设CF=0.25，则该子数的实例判断错误数目为： 若以一个结点C1代替该子树，则16个实例中有一个错误（C3），误判实例数目为 由于判断错误数目小于上述子树，则以该叶结点代替子树。4.5.4 从决策树抽取规则在C4.5中，从决策树抽取规则需要两个步骤：获得简单规则、精简规则属性。1、获得简单规则对于已生成的决策树，可以直接从中获得规则。从根到叶的每一条路径都可以是一条规则。例如，下面的决策树中可以得到规则决策树： 规则： 2、精简规则属性在上述获得的简单规则中，可能包含了许多无关的属性。在上面的规则中，条件F和G的取值对于结论没有任何影响。在不影响规则的预测效果的情况下，可以删除一些不必要的条件。设规则的形式为R： If A then class C精简之后的规则为： If then class C其中，是从A中删除条件之后的形式。4.6 决策树的改进算法 （1）二叉树算法 Kononenko等人认为Quinlan的熵函数并不理想，有偏向于取值较多的属性的毛病。为了克服这个毛病，Kononenko等人建议限制决策树为二叉树，使得取值多的属性与取值少的属性有同等的机会。此法已在ASSISTANT系统中实现。 改进思想和缺点见 知识发现，史忠植著，清华大学出版社，2002P28-29 （2）按信息比值进行估计的方法 由于每个实例关于属性a的取值，需要做试验，计算等，这是需要付出一定代价的。设属性a取值，它们拥有的实例个数分别为，且，其中n为训练实例属于属性a的总数。Quinlan利用属性a的熵值来定义为了获取实例关于属性a的取值所需要付出的代价： 在属性a提供相同的信息量的同时，的取值越小越好。Quinlan定义了另一种测试属性选取标准： 即选取使得最大的属性a作为测试属性。优点：能有效克服偏向取值多的属性的毛病。缺点：更偏向于选择对统一属性值取值比较集中的属性（即熵值最小的属性），而并不一定是对分类贡献最大最重要的属性。另外，当属性a只有一个取值时，则没意义。 （3）按分类信息估值Cendrowska根据属性为实例分类提供了多少有用信息来选取测试属性。将训练实例分为类。设属性a的取值，取其中所有类，设有m个，定义： Cendrowska认为，应选取使得最大的属性作为测试属性。 （4）按划分距离估值的方法De Mantaras建议利用划分距离的办法来选择测试属性。设待分类属性分别属于个不同的类，如果有一种划分方法能够把X一下分为个子集，其中每个中的实例恰好属于类，这称之为理想划分。另一方面，如果根据某个属性的各个可能取值把X分为子集，这也是一个划分。如果能够在两个划分之间定义一种距离，则可以在由各个属性定义的划分当中选择离理想划分最近的那一个，将此属性定为当前的测试属性。De Mantaras定义的距离也是以信息和熵为基础的。将简记为。设表示X的某种划分，则其信息熵为 设为X的另一种划分，则相应的信息熵为 则划分对于划分的条件熵为 式中，为一个实例既在划分中属于类，又在划分中属于类的概率。De Mantaras定义两个划分的距离为： De Mantaras采用范式距离作为选择测试属性的度量标准，范式距离定义为： 式中，为与的联合熵，定义为 优点：l 上式分子不为零时分母一定不为零；l Quinlan的信息比度量有另外一个缺点，的值常会选择信息含量不大的属性a，在这里也不会出现，因为范式距离的性质可以得到上式的分母绝对不会比分子小，所以当分子小的时候分母也一定很小。l 以划分距离作为信息度量，在某种意义上不倾向于取值较多的属性。4.7 决策树的评价评价决策树的一些量化的评价标准有：过学习、有效性