2022年数据挖掘与知识发现分享 .pdf

《2022年数据挖掘与知识发现分享 .pdf》由会员分享，可在线阅读，更多相关《2022年数据挖掘与知识发现分享 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘与知识发现讲稿主讲：刘以安装订线1 第四章决策树 (decision tree) 决策 树 也 是归纳 学习中常用的一种知识表示形式，常用于分类。同时，也是 发 现 概念描述空间的一种有效方法。决策树的主要优点 是描述简单，分类速度快，特别适合大规模的数据处理。教学目的：掌握决策树学习的概念重点掌握ID3 学习算法以及决策树的构造了解目前常用的决策树改进方法4.1 概念描述空间的归纳学习归纳学习旨在从大量的经验数据中归纳抽取出一般的规则和模式，因而成为知识获取的主要手段，在专家系统、模式识别、图像处理、语音识别等领域都有重要应用。归纳学习是机器学习最核心、最成熟的分支。示例 数字识别应

2、用：假设有三类数字，即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 归纳学习是符号学习中研究得最为广泛的一种方法。思想是 ：给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则， 发现新的理论。它的一般操作名师资料总结 - - -精品资料

3、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线2 是泛化和特化 。泛化 用来扩展某一假设的语义信息，使其能包含更多的正例，应用于更多的情况； 特化 是泛化的相反操作，用于限制概念描述的应用范围。示例 假设我们被要求从一副扑克牌中选择一张牌，如果选到好牌就可以获奖。已知前面被抽出的牌有： 梅花 4、梅花 7、黑桃 2、红桃 5 和黑桃 J，其中前三张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。解：取纸牌的

4、一组属性：1V- 花色（ Suit ）和阶2V- （Rank ） ，如：梅花 4 显然，纸牌的示例空间21VV就是所有牌的集合。它是由属性Suit和 Rank所定义的，其中，属性21,VV的可观察值集合为：,l u b1h ea r t sd i a m o n d ss p a d e sscV-梅花、黑桃、方块、红桃,10,9,8,7,6,5,4,3,2,12KQJV每个示例就是单张牌。设 X 是一组确定属性决定的示例空间 （如，21VV） ；H 是定义在 X 上的假设空间 （如， H=梅花 4、梅花 7、黑桃 2、红桃 5 和黑桃 J ） ，也就是用 X 的属性按一定的逻辑形式定义的一组

5、概念。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是肯定示例，其

6、描述图为这里，cclubs; b-black; n-num; a-any-suit 或 any-rank 。图中从左到右表示suit从特殊到普遍，垂直方向从下到上表示Rank从特殊到普遍； ba表示的概念为)()(r a n kanyRankblacksuit，即所有黑色的牌。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线3 这时增加新的示例， 如梅花 7，能修剪描述空间。 删除三个涉

7、及阶是4 的概念，因为它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5 可修剪掉 aa和 an，因为这两个概念覆盖该否定示例；肯定示例黑桃2 剪掉梅花，最后由否定示例黑桃 J将描述空间缩小到单个概念bn，即黑色 数字牌 。4.2 决策树学习决 策 树是 用 样本的属性 作为结点，用属性的取值 作为分支的树结构。它是利 用 信 息论原理 对大量样本的属性进行分析和归纳而产生的。决策树的根结点是 所 有 样本信息中信息量最大的属性。中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决 策 树学 习 是以实例为基础的归纳学习算法。它着眼于从一

8、组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在 决 策 树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的 分 枝 ，在决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条 合取 规则，整棵决策树就对应着一组析取 表达式规则。决策 树 的 内部 结点是属性或属性集，称为测试属性 ；叶结点是所要学习划分的类。先用训练实例集产生决策树，然后用其对未知实例集进行分类。对实例进行分类时， 由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。例如 一棵基于表 1 中数据的用于

9、检测网络入侵行为的决策树。这个决策树，用 IP 端口和系统名称标示内部结点，用入侵和正常表示叶结点，如下图描述。决策树可转换成如下的规则：（C+表示）If (System name=Artemis) Intrusion=false; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线4 Else If (IP port=002210) Intrusion=true; else if (IP

10、 port=004020) Intrusion=true; Else if (IP port=000010) Intrusion=false; 根据决策树的各种不同属性，有以下几种不同的决策树：决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性，也可能是多变量的，即存在包含多个属性的内结点；根据测试属性的不同属性值的个数，可能使每个内结点有两个或多个分支。如果每个内结点只有两个分支，则称之为二叉树决策树；每个属性可能是值类型，也可能是枚举类型；分类结果既可能是两类，也可能是多类。如果二叉决策树的结果只能有两类，则称之为布尔决策树。对布尔决策树可很容易以析取范式的方式表示。如下图

11、为)()(14323XXXXX的析取范式 。另外，所有的决策树学习都有一些等价的网络表示形式。如上图的人工神经网络与决策树表达了同一个析取概念)()(14323XXXXX，所执行的功能相同。4.3 CLS 学习算法概念学习系统（ CLS：Concept Learning System）是 1966 年由 Hunt等人提出的，是早期决策树学习算法，后来的决策树学习算法均可视为CLS 算法的改进和更新。CLS 算法的主要思想是：从一个空的决策树出发，选择某一属性（分类属性）作为测试属性，该测试属性对应决策树中的决策结点，根据该属性值的不同，可将训练样本分成相应的子集。如果该子集为空，或该子集中的样

12、本属于同一类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点。需再选择一个名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线5 新的分类属性对该子集进行划分，直至所有的子集者为空或属于同一类为止。例如，假设有一组人，眼睛和头发的颜色及所属的人种情况如下表：假设首先选择 眼睛颜色 作为测试属性，则从该结点引出三个分支图：选择眼睛颜色作为决策属性这三个分支将样本集分成三个子集1

13、，6 、2，4，8 和3，5，7 。但这三个子集中的元素都不属于同一结果类，因此它们都不是叶结点，需要继续划分，即需要添加新的测试结点。如 头发颜色 ，由于 头发颜色 = 黑色，金色，红色 ，所以从子集中可引出三个新的分支：图：添加头发颜色作为新的决策属性通过增加结点逐步求精，直到生成一棵能正确分类训练样本的决策树。学习算法 CLS 算法的步骤可描述为：令决策树 T 的初始状态只含有一个树根 （X，Q） ，其中 X 是全体训练实例的集合， Q 是全体测试属性的集合；若 T 的所有叶结点 （,QX）都有如下状态：或者第一个分量X中的训练实例都属于同一个类， 或者第二个分量Q为空，则停止执行学习算

14、法， 学习的结果为 T；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线6 否则，选取一个不具有步骤所述状态的叶结点),(QX；对于Q，按照 一定规则 选取测试属性 b，设X被 b 的不同取值分为m 个不相交的子集miXi1 ,，从),(QX伸出 m个分叉，每个分叉代表 b 的一个不同取值，从而形成m个新的叶结点),(bQX，mi1；转步骤。从 CLS 的算法描述可以看出， 决策树的构造

15、过程也就是假设特化的过程。但 CLS算法并没有规定采用何种测试属性。然而，测试属性集的组成以及测试属性的先后都对决策树的学习有着举足轻重的影响。此外，CLS 算法所能处理的学习问题不能太大。4.4 ID3（Iterative Dichotomizer 3 ）学习算法CLS 算法的思路 是找出最有分辨能力的属性，把数据库划分为许多子集（对应树的一个分枝），构成一个分枝过程，然后对每个子集递归调用分枝过程，直到所有子集包含同一类型数据。最后得到的决策树能对新的例子进行分类，但CLS 的不足是（1）没给出如何选取测试属性b；（2）它处理的学习问题不能太大。为此，Quinlan提出了著名的以 属性为分

16、类节点的 ID3 学习算法，他是以信息熵的 下 降 速度 作为选取测试属性的标准，通过窗口来形成决策树。信息熵的下降也就是信息不确定性的下降。1）信息论简介信息论是由 C.E.Shannon （信息论的创始人） 1948年为解决信息传递（通信）过程问题而提出的 以数学的方法来度量并研究信息的理论，也称为统计通信理论。他把 一 个 传 递信 息的系统 视为，由发送端（信源） 、接收端（信宿）和连接两者的通道（信道）三者组成。其中，)|(XYP称为信道的传输概率或转移概率，它反映信道的输入与输出关系。可用矩阵来表示，称为转移概率矩阵。名师资料总结 - - -精品资料欢迎下载 - - - - - -

17、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线7 )|()|()|()|()|()|()|()|()|()|(212222111211rqrrqquvPuvPuvPuvPuvPuvPuvPuvPuvPXYP这里，riuvPqjij,2, 1,1)|(1。从此通信模型可看出，在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发什么样的具体信息，也不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性，而且这种不确定性是

18、存在于通信之前的，因此又叫做 先验不确定性。在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。但是，在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。换句话说，通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。（1）如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根

19、本没有收到信息。（2）如果后验不确定性的大小等于零，这就表示作宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量的大小，由所消除的不确定性的大小来计量。下面介绍几个概念：信息（符号）iu（ri,2,1）的发生概率)(iup组成信源数学模型（样本空间或概率空间）：)()()(,2121rrupupupuuuPX 自信息量 ：消息iu发生后所含有的信息量。即在收到iu事件之前，收信者对信源发出iu的不确定性，定义为信号符号iu的自信息量)(iuI。即)(log)(1log)(22iiiuPuPuI其中，)(iuP为信源发出iu事件的概率；名师资料总结 - - -精品资料欢迎下载

20、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线8 信息熵 ： 自信息的数学期望。 因为自信息量只能反映符号收到前的不确定性，而信息熵可以用来度量整个信源X 整体的不确定性， 即信源发出信息前的平均不确定性。定义如下：riiirruPuPuIuPuIuPuIuPXE122211)(l o g)()()()()()()()(其中， r 为信源 X 所有可能的符号数ruuu,21，即用信源每发一个符号所提供的平均自信息量来定义信息熵

21、。上式中，对数底数b可为任何正数，不同的取值对应熵的不同单位，但通常取2b；并规定：当0)(iup时，0)(log)(ibiuPup。当对数的底为 2 时，)(iuI的单位为比特（ bit） ；当对数的底为e时，)(iuI的单位为奈特（ nat） ；当对数的底为 10时，)(iuI的单位为哈特（ hart） ；1 奈特=1.44 比特；1 哈特=3.32 比特。)( XE的性质如下：)( XE=0时，说明只存在着唯一的可能性，不存在不确定性；如果 n种可能的发生都具有相同的概率， 即对所有的iu， 有nuPi/1)(，则)( XE达到最大值n2log，说明系统的不确定性最大；)(iuP互相越接

22、近，)( XE就越大；)(iuP相差大，则)( XE就小。如果信道中无干扰（噪声） ，信道输出符号与输入符号一一对应，那么接收到传送过来的符号后，就消除了对发送符号的先验不确定性。后验熵一般信道中有干扰存在，信宿接收到符号V 后，对信源发出的是什么符号仍有不确定性。对此如何度量？当没有接收到输出符号V 时，已知发出符号 U 的概率分布 P(U)，而接收到输出符号jvV后，输入符号的概率分布发生了变化，变成了后验概率分布)|(jvUP。那么，接收到输出符号jvV后，关于 U 的平均不确定性为：ijijijvuPvuPvUE)|(1l o g)|()|(2名师资料总结 - - -精品资料欢迎下载

23、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线9 这就是接收到输出符号jv后关于 U 的后验熵 。即后验熵是当信道接收到输出符号jv后，关于输入符号U 的信息度量。条件熵后验熵在输出符号集V 的范围内是个随机量，所以对于后验熵在输出符号集V中求期望，得到条件熵：jjjvUEvPVUE)|()()|(=jijijijvuPvuPvP)|(1log)|()(2（* ）这个条件熵称为称为信道疑义度 。它表示在输出端收到全部输出符号V

24、 后，对于输入端的符号集U 尚存在的不确定性（存在疑义） 。对 U 集尚存在的不确定性是由于干扰（噪声）引起的，如果是一一对应，那么接收到符号集V 后，对 U 集的不确定性完全消除，则信道疑义度0)|(VUE。在决策分类中，假设X是训练样本集，| X是训练样本数；样本划分为n个不同的类nCCC,21，则任意样本X属于类iC的概率为|)(XCXPii所以，样本X的平均信息熵为1221|(|,)(l o g)|niiniCCEXCCCXX如果a为X中取有限个不同值maaa,21的属性，样本集X划分为m个不同的子集,21mXXX，则由式（ *）知，由属性a划分的决策树分类的平均条件熵为mjjjaXE

25、XpaXE1)|()()|(mjnijijijXCpXCpXp112)|(l o g)|()(若设|ijX表示为子集jX中类iC的样本数，则|)|(XXXCPijji。 信息增益 ：一般)()|(XEaXE，样本分类的熵值发生了变化，即属性a对于分类提供了信息，熵的变化量称为属性a对于分类的信息增益)(aGain，则0)|()()(aXEXEaG a i n（证明略）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - 数据挖掘与知

26、识发现讲稿主讲：刘以安装订线10 从上式知，测试属性将减少决策数分类的不确定程度。2）ID3 学习算法Quinlan的 ID3 算法就是选择使)(aGain最大的属性作为测试属性，即选择使)|(aXE最小的属性a 作为测试属性。此外，ID3 中还引入了窗口方法进行增量学习来解决实例过大问题。具体算法为： 选出整个训练实例集X的规模为 W的随机子集1X； （W称为窗口规模， 子集称为窗口） 以使得式（ *）的值最小为标准，选取每次的测试属性，形成当前窗口的决策树； 顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外，则训练结束； 组合当前窗口的一些训练实例与某些在中找到的例外，形成新的窗

27、口，转。示 例 表 4.1 给出 了 一 个可 能 带 有噪 声的数据集合。它有4 个属性：Outlook,Temperature ，Humidity和 windy。它被分为两类： P 和 N 分别表示正例和反例。试构造决策树将数据进行分类。解：因为初始时刻属于P 类和 N 类的实例个数均为12 个，所以初始时刻的熵值为：12412log24122412log2412)( XH如果选取 Outlook 属性作为测试属性，则由式（*）有5 5 2 8.0)77l o g77(247)87log8781log81(248)95log9594log94(249)|(OutlookXH6 7 3 9.

28、0)51l o g5154l o g54(245)117log117114log114(2411)84log8484log84(248)|(TempXH9183.0)128log128124log124(2412)128log128124log124(2412)|(HumiXH1)105log105105log105(2410)63log6363log63(246)85log8584log84(248)|(WindyXH表 4.1 样本数据集名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

29、 第 10 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线11 可以看出，)|(OutlookXH最小，即有关 Outlook的信息对于分类有最大的帮助，提供最大的信息量， 即);(OutlookXI最大。所以选择 Outlook 属性作为测试属性，就可将训练实例集分为三个子集，生成三个叶结点，对每个叶点依次利用上面的过程，则最终生成如下的决策树：3）基于 ID3 的信息增益的决策树构造算法ID3 算法有着广泛的应用， 其中较为著名的有C4.5 、C5.0 系统。C4.5 的新功能是它能将决策树转换为等价的规则表示，并且解决了连续取值的学习问题。

30、（1）ID3 算法的基本原理设nFFFE21是 n维有限向量空间，jF是有限离散符号集， E 中的每一元素),(21nvvve称为例子 ，njFvjj,2, 1,。设 PE和 NE 是 E 的两个例子集，分别称为正例集和反例集。nNEpPE| ,|，则 ID3 基于如下两种假设：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线12 在向量空间 E 上的一棵正确决策树，对任意例子的分类概

31、率同E 中正例、反例的概率一致； 一棵决策树对一例子做出正确分类判别所需的信息为npnnpnnppnppnpI22loglog),(如果属性 A 作为决策树的根且A 具有 v 个值，则A 可将 E 分成 v 个子集,21vEEE。假设iE中含有ip个正例和in个反例，那么iE所需的期望信息是),(iinpI，以属性 A 为根分类所需的期望熵为viiiiinpInpnpAE1),()(则 A 根的信息增益为)(),()(AEnpIAg a i nID3 的思想 是选择)( Again最大（即)( AE最小）的属性*A作为根结点。其方法可推广到多类情况。（上面只研究正、反两类）设样本集 E 共有

32、C 类样本，每类样本数为ip，ci,2, 1，即ciipE1|。若以属性 A 作为决策树的根， A 具有 v 个值可将 E 分成 v 个子集,21vEEE。假设iE中含有j类样本的个数为ijp，cj,2,1。则子集iE的信息量为cjiijiijiEpEpEI12|log|)(以 A 为根分类的信息熵为viiiEIEEAE1)(|)(（* ）所以，选择属性*A使)( AE最小。（2）建树的算法步骤 对于任意的选择属性A， 假设 A有v个属性值，对应的概率分别为vppp,21以属性 A 扩展，生成v个子结点,21vEEE，iE是属性 A 取i个值时，按照 最 小 的 信 息 熵 原 理 选 择 的

33、A 的 后 继 属 性 ， 分 别 对应 的 信 息熵 为)(,),(),(21vEIEIEI； 根据公式（ * ）计算()EA；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线13 选择*A使*()EA最小，将*A作为根属性； 利用步骤的计算结果，建立结点*A的后继结点,21vEEE； 对所有的iE， 若为叶结点，则停止扩展此结点。 否则递归执行的过程。（3）应用实例决策树的构造主要

34、分为两个阶段：建树阶段和调整阶段。例如 下面以某课堂教学评估数据库中的数据挖掘和知识发现为例。该课堂教学评估指标体系表共分为若干项，经研究可归纳为：教学态度（6A） 、教学内容（7A） 、教学方法（8A） 、教学效果（9A） 、评价（10A）共五项，实际数据见表 1 所示。由于属性初值为连续值，需进行离散化处理。将属性划分为若干个区段，C1：95100 分、C2 ：8094 分、C3：7079 分、C4 ：6069 分、C5 ：60 分。见表 2所示。解 ：去掉属性1A。因为1A对于结论属性而言，无互信息，亦称无信息增益，即0)(1Again。计算测试集的全部信息量：7928.0202log2

35、02203log2032015log2015)(22210AI然后计算各结点的信息量)(iEI，如6A1 5 2 1.3151log151150log1501514log1514)(222良I9168.030log3032log3231log31)(222中I0)(优I所以，50162.2)(202)(203)(2015)(6优中良IIIAE7 0 5 3 4.1)()()(6106AEAIAgain同理，可计算出987,AAA信息熵：5 5 0 1.0)(,411.0)(,65876.0)(987AgainAgainAgain名师资料总结 - - -精品资料欢迎下载 - - - - - -

36、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线14 故取7A为根属性。同样对1C这一分支继续使用ID3方法进一步划分，可得到如图所示的决策树。该决策树完全概括了教师教学评估的三个等级的20个记录。从图中可以看出：教学7A是一重要指标。表 1 或表 2 中隐藏的知识有如下几种情况：规则 1： IF （27CA） THEN （良）规则 2：IF （37CA） THEN （中）规则 3：IF （1917CACA）THEN （优）规则 4：IF （2917

37、CACA）THEN （良）即，如果教学内容为良，则课堂教学质量评价等级一定为良；如果教学内容为中，则课堂教学质量评价等级一定为中；如果教学内容和教学效果均为优，则课堂教学质量评价等级一定为优；如果教学内容为优而教学效果为良，则课堂教学质量评价等级为良。因此，从这些规则中，可以归纳出一条重要的知识，就是：教学内容组织好的老师，其课堂教学质量的综合评价成绩较好。4.5 C4.5 方法ID3 算法在数据挖掘中占有非常重要的地位。但是在应用中，ID3 算法 存在 不能 够 处 理连 续属性、计算信息增益时偏向于选择取值较多的属性等不足 。C4.5名师资料总结 - - -精品资料欢迎下载 - - - -

38、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线15 是在 ID3 基础上发展起来的决策树生成算法，由 J.R.Quinlan 在 1993年提出。C4.5 克服了 ID3 在应用中存在的不足，主要体现在以下几个方面：（1）用信 息增 益率来选择属性，它克服了信息增益选择属性时偏向于选择取值较多的属性的不足；（2）在树构造过程中或者构造完成之后，进行剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据进行处理；（5）C4.5

39、 采用的知识表示形式为决策树，并最终可以形成产生式规则。4.5.1 构造决策树设 T 为数据集，类别集合为 kCCC,21， 选择一个属性 V 把 T 分为多个子集。设 V 有互不重合的n个值,21nvvv，则 T 被分为n个子集nTTT,21，这里iT中的所有实例的取值均为iv。令| T为数据集 T 的例子数，|iT为ivV的例子数，),(|TCfreqCjj为jC类的例子数，|vCj为ivV例子中，具有jC类别的例子数。则有：（1）类别jC的发生概率：|),(|)(TTCfreqTCCpjjj；（2）属性ivV的发生概率：|)(TTvpii；（3）属性ivV的例子中，具有类别jC的条件概率

40、：|)|(ijijTvCvCp。Quinlan在 ID3 中使用信息论中的信息增益（Gain ）来选择属性，而C4.5 采用属性的信息增益率（Gain Ratio）来选择属性。1、类别的信息熵jjjjjjTCTCCpCpCH)|(l o g|)(log)()(22=)(inf)|),(log|),(21ToTTCfreqTTCfreqjkjj2、类别条件熵按照属性 V 把集合 T 分割，分割后的类别条件熵为：jiijijjvCpvCpvpVCH)|(l o g)|()()|(2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

41、精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线16 =jiivjivjjTCTCTT|log|2=niviiToToTT1)(inf)(inf|3、信息增益，即互信息)()(i n f)(i n f)|()(),(Vg a i nToToVCHCHVCIv4、属性 V 的信息熵iniiiiiVos p l i tTTTTvpvpVH122)(i n f_)|(l o g|)(log)()(5、信息增益率)(i n f_/)()(/),(_Vos p l i tVg a i nVHVCIr a t i

42、 og a i nC4.5 对 ID3 改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率” （C4.5）比采用“信息增益” (ID3)更好，主要是克服了 ID3 方法选择偏向于取值多的属性的不足。4.5.2 连续属性的处理在 ID3 中没有处理连续属性的功能。在C4.5 中，设在集合 T 中，连续属性 A 的取值为,21mvvv，则任何在iv和1iv之间的任意取值都可以把实例集合分为两部分|1ivAtT和|2ivAtT可以看到，一共有1m种分割情况。对属性 A 的1m种分割的任意一种情况，作为该属性的两个离散取值，重新构造 该 属 性 的 离 散 值 ， 再 按 照 上 述 公

43、式 计 算 每 种 分 割 所 对 应 的 信息 增益 率)(_ivr a t i og a i n，在1m种分割中，选择最大增益率的分割作为属性A 的分枝：kvVT h r e s h o l d)(其中，)(_max)(_ikvratiogainvratiogain，则连续属性 A 可以分割为：4.5.3 决策树剪枝名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线17 由于噪声和随

44、机因素的影响，决策树一般会很复杂。因此，需要进行剪枝操作。1、什么时候剪枝？剪枝操作有两种策略：（1）在树生成过程中判断是否继续扩展决策树。若停止扩展， 则相当于剪去该结点以下的分枝；（2）对于生成好的树剪去某些结点和分枝。 C 4 .5采用的是第二种方法。剪枝之后的决策树的叶结点不再只包含一类实例。结点有一个分布描述，即该叶结点属于某类的概率。2、基于误差的剪枝决策树的剪枝通常是用叶结点替代一个或者多个子树，然后选择出现概率最高的类作为该结点的类别。在C4.5 中，还允许用其中的树枝来替代子树。如果使用叶结点或者树枝代替原来的子树之后，误差率若能够下降， 则就使用此叶结点或者树枝代替原来的子

45、树。3、误差率的判断设一个叶结点覆盖N 个实例，其中 E 个为错误的。对于具有信任度CF 的实例，计算一个 2 项分布，),(NEUCF，该 2 项分布，即实例的误判概率， 那么 N 个实例判断错误的数目为),(NEUNCF。子树的错误数目为所有叶结点的总和。如：注： （）中为覆盖的实例数目设 CF=0.25，则该子数的实例判断错误数目为：273.3750.01143.09206.06)1,0(1)9,0(9)6,0(625.025.025.0UUU若以一个结点 C1 代替该子树，则 16 个实例中有一个错误（ C3） ，误判实例数目为512.2157.016)16,1(1625.0U由于判断

46、错误数目小于上述子树，则以该叶结点代替子树。4.5.4 从决策树抽取规则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线18 在 C4.5 中，从决策树抽取规则需要两个步骤：获得简单规则、精简规则属性。1、获得简单规则对于已生成的决策树， 可以直接从中获得规则。 从根到叶的每一条路径都可以是一条规则。例如，下面的决策树中可以得到规则决策树：1:10:010:001:111:10:010

47、:00c l a aKc l as sKJcl a ssJGc l a ssGFc l a ssKc l a ssKJc l a s sJF规则：11,1,0, 1c l a s st h e nKJGFif2、精简规则属性在上述获得的简单规则中， 可能包含了许多无关的属性。 在上面的规则中， 条件F 和 G 的取值对于结论没有任何影响。在不影响规则的预测效果的情况下，可以删除一些不必要的条件。设规则的形式为 R：If A then class C 精简之后的规则为R：If Athen class C 其中，A是从 A 中删除条件之后的形式。4.6 决策树的改进算法（1）二叉树算法Konone

48、nko等人认为 Quinlan的熵函数并不理想， 有偏向于取值较多的属性的毛 病 。为了克服这个毛病， Kononenko 等人建议限制决策树为二叉树，使得取值多的属性与取值少的属性有同等的机会。此法已在ASSISTANT 系统中实现。改进思想和缺点见知识发现， 史忠植著，清华大学出版社， 2002P28-29 （2）按信息比值进行估计的方法由于每个实例关于属性a 的取值，需要做试验，计算等，这是需要付出一定代名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 -

49、 - - - - - - - - 数据挖掘与知识发现讲稿主讲：刘以安装订线19 价 的 。 设属性a 取值kaaa,21，它们拥有的实例个数分别为knnn,21，且nnkii1，其中 n 为训练实例属于属性a 的总数。 Quinlan利用属性 a 的熵值),(aXV来定义为了获取实例关于属性a 的取值所需要付出的代价：kiiinnnnaXV1l o g),(在属性 a提供相同的信息量),(aXI的同时，),(aXV的取值越小越好。 Quinlan定义了另一种测试属性选取标准：),(),(),(aXVaXIaXE即选取使得),(aXE最大的属性 a 作为测试属性。优点：能有效克服偏向取值多的属性

50、的毛病。缺点：更偏向于选择对统一属性值取值比较集中的属性（即熵值最小的属性），而并不一定是对分类贡献最大最重要的属性。另外，当属性a 只有一个取值时，0),(aXV，则),(aXE没意义。（3）按分类信息估值Cendrowska 根据属性为实例分类提供了多少有用信息来选取测试属性。将训练实例分为l类lCCC,21。设属性 a 的取值kaaa,21，取其中所有0|iC类，设有 m个，定义：mikjijiCpaaCpkmaXF11)()|(l o g1),(Cendrowska认为，应选取使得),(aXF最大的属性a作为测试属性。（4）按划分距离估值的方法De Mantaras 建议利用划分距离的