C45算法-文档资料

1、1C4.5C4.5算法介绍算法介绍人工智能2一、C4.5算法的概述二、C4.5算法的具体实现三、C4.5算法应用举例C4.5算法介绍算法介绍3一、C4.5算法的概述 C4.5C4.5算法是由算法是由QuinlanQuinlan于于19931993年在年在ID3ID3算法算法的基础上进一步改进形成的。的基础上进一步改进形成的。 C4.5 C4.5算法也是机器学习算法中的一种分类算法也是机器学习算法中的一种分类决策树算法决策树算法, , 此算法用此算法用信息增益率信息增益率来选择决策来选择决策属性，其核心算法是属性，其核心算法是ID3ID3算法。它继承了算法。它继承了ID3ID3算算法的全部优点，

2、并在法的全部优点，并在ID3ID3的基础上增加了对连续的基础上增加了对连续属性的属性的离散化离散化、对未知属性的处理和产生规则、对未知属性的处理和产生规则等功能，克服了等功能，克服了ID3ID3算法的不足。算法的不足。4C4.5具体在以下几个方面做出了改进: (1)(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性; ; (2)(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理, ,这是这是一个很关键的改进一个很关键的改进; ; (3)(3)在决策树构造过程中或者构造完成之后在决策树构造过程中或者构造完成之后, ,进行剪枝进行剪枝; ; (4)(4)能够

3、对不完整数据进行处理能够对不完整数据进行处理, ,如未知的属如未知的属性值性值; ;(5) C4.5(5) C4.5可以用决策树形式形成产生式规则。可以用决策树形式形成产生式规则。一、C4.5算法的概述5二、C4.5算法的具体实现(1)(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性; ; (2)(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理, ,这是这是一个很关键的改进一个很关键的改进; ; (3)(3)在决策树构造过程中或者构造完成之后在决策树构造过程中或者构造完成之后, ,进行剪枝进行剪枝; ; (4)(4)能够对不完整数据进行处理能够对不完

4、整数据进行处理, ,如未知的属如未知的属性值性值; ;(5) C4.5(5) C4.5可以用决策树形式形成产生式规则。可以用决策树形式形成产生式规则。6 设设T T 为训练数据集为训练数据集, ,共有共有k k 个类别个类别, ,集合表示为集合表示为 C C1 1 ,C,C2 2 , , ,Ck ,Ck , | | Cj Cj | |为为Cj Cj 类的例子数类的例子数, , | | T T | |为数据集为数据集T T 的例子数。的例子数。 选择一个属性选择一个属性V, V, 设它有设它有n n个互不重合的取值个互不重合的取值va va ( ( 11a an) ,n) ,则则T T 被分为被

5、分为n n个子集个子集 T T1 1,T,T2 2 ,Tn , ,Tn , 这里这里Ti Ti 中的所有实例的取值均为中的所有实例的取值均为vivi。| |TiTi| |为为V V = =vi vi 的例子数的例子数, , | |CjvCjv| |是是V V = =vi vi 的例子中的例子中, ,具有具有Cj Cj 类别的类别的例子数。则有：例子数。则有： (1)类别类别Cj Cj 的发生概率的发生概率: p (Cj) : p (Cj) = |= |CjCj| |/ /| |T T| |; ; ( (2 2) )属性属性V V = = vi vi 的发生概率的发生概率:p (vi) :p (

6、vi) =|=|TiTi| |/ /| |T T| |; ; ( (3 3) )属性属性V V = = vi vi 例子中例子中, ,具有类别具有类别Cj Cj 的条件概率的条件概率: : p(Cj p(Cj | | vi ) vi ) = |= |Cjv Cjv | | / / | | Ti Ti | |。 类别的类别的信息熵：信息熵：(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性;kjjjkjjjToTCTCCpCpC1212)(inf|log|)(log)()(H7按照属性按照属性V V 把集合把集合T T分割分割, ,分割后的分割后的类别条件熵类别条件熵为：

7、为：)(inf)(inf|)|(log)|()()|(H1112ToToTTvCpvCpvpVCvivniinikjijiji(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性;8信息增益信息增益( (Gain)Gain) ：)(inf)(inf)|()()(GToToVCHCHVainv属性属性V V的信息熵：的信息熵：)(inf_|log|) )(log)()(H1212VosplitTTTTvpvpVniiiniii(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性;9信息增益率：信息增益率：)()(_GVHVGainratioainC4.

8、5 C4.5 采用了信息增益率作为对选择分枝属性的分枝采用了信息增益率作为对选择分枝属性的分枝准则。信息增益率表示了由分枝产生的有用信息的准则。信息增益率表示了由分枝产生的有用信息的比率。因此比率。因此, ,这个值越大这个值越大, , 分枝包含的有用信息越多。分枝包含的有用信息越多。(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性;10与与ID3ID3算法相比，算法相比，ID3ID3算法选择信息增益最大即熵下降最算法选择信息增益最大即熵下降最大的属性进行分支的。当有大量不同的属性值和采用标大的属性进行分支的。当有大量不同的属性值和采用标准化的处理程序时准化的处理程序时

9、, , 这种启发式方法很有效。而这种启发式方法很有效。而C4.5C4.5算算法是选择信息增益率最大的属性进行分支的。从局部看，法是选择信息增益率最大的属性进行分支的。从局部看，ID3ID3算法每一步都选择最优分支属性，但是从整体上看，算法每一步都选择最优分支属性，但是从整体上看，有可能使得整个决策树复杂。而有可能使得整个决策树复杂。而C4.5C4.5算法从局部看不一算法从局部看不一定的选择信息增益最大的属性，但是从整体看，分支更定的选择信息增益最大的属性，但是从整体看，分支更明确，获得的有用信息更多。明确，获得的有用信息更多。(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选

10、择属性;11(1)(1)用信息增益率代替信息增益来选择属性用信息增益率代替信息增益来选择属性; ; (2)(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理; ;(3)(3)在决策树构造过程中或者构造完成之后在决策树构造过程中或者构造完成之后, ,进行剪枝进行剪枝; ; (4)(4)能够对不完整数据进行处理能够对不完整数据进行处理, ,如未知的属如未知的属性值性值; ;(5) C4.5(5) C4.5可以用决策树形式形成产生式规则。可以用决策树形式形成产生式规则。二、C4.5算法的具体实现12 C4 C45 5算法将分类范围从分类的属性扩展到数字属性。算法将分类范围从分类的属性

11、扩展到数字属性。如果数据集中存在连续型的描述性属性如果数据集中存在连续型的描述性属性( (数字属性数字属性) )，C4C45 5算法首先将这些连续型属性的值分成不同的区间，算法首先将这些连续型属性的值分成不同的区间，即即“离散化离散化”。通常将连续型属性值。通常将连续型属性值“离散化离散化”的方法为：的方法为：寻找该连续型属性的最小值，并将它赋值给寻找该连续型属性的最小值，并将它赋值给minmin，寻找，寻找该连续型属性的最大值，并将它赋值给该连续型属性的最大值，并将它赋值给maxmax；设置区间设置区间minmin，maxmax中的中的N N个等分断点个等分断点AiAi，其中，其中，i=1,

12、2,i=1,2, ,N,N；分别计算把分别计算把(min(min，Ai)Ai)和和(Ai,max)(i=1,2,3, (Ai,max)(i=1,2,3, ,N),N)作为区作为区间值时的信息增益率（间值时的信息增益率（RatioRatio）值，并进行比较；）值，并进行比较；选取选取信息增益率最大的信息增益率最大的A A。作为该连续型属性的断点，将属性。作为该连续型属性的断点，将属性值设置为值设置为minmin，AA和和(A(A，max)max)两个区间值。两个区间值。(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理13 离散化处理过程中，离散化处理过程中，C4.5C4.5算法

13、是对节点上的每个算法是对节点上的每个属性都要计算其信息增益率属性都要计算其信息增益率, ,然后从中选择信息增益然后从中选择信息增益率最大的属性断点。由于在信息增益率计算过程中涉率最大的属性断点。由于在信息增益率计算过程中涉及到对数函数的计算及到对数函数的计算, ,在计算程序中就得调用库函数在计算程序中就得调用库函数, ,同时随着数据量的增大，计算量也随之增大。这样就同时随着数据量的增大，计算量也随之增大。这样就增加了计算量时间。因此，在改进的增加了计算量时间。因此，在改进的C4.5C4.5算法中采用算法中采用了了“Fayyad Fayyad 边界点判定定理边界点判定定理”(2)能够完成对连续属

14、性的离散化处理能够完成对连续属性的离散化处理14 定义定义 : 属性属性A 中的一个值中的一个值T 是一边界点是一边界点, 当且仅当在按当且仅当在按A 的值排序的实例序列中的值排序的实例序列中, 存在两个实例存在两个实例e1 , e2 S 具有不同的类具有不同的类, 使得使得A ( e1 ) T A( e2 ) , 且不存在且不存在任何其他的实例任何其他的实例eS , 使得使得A( e1 ) A ( e) A ( e2 ) 。A ( e) 表示实例表示实例e 的的A属性值。属性值。S 表示实例的表示实例的集合。集合。 定理定理 : 若若T 使得使得E ( A , T , S ) 最小最小, 则

15、则T 是一个边界点。是一个边界点。其中其中, A 为属性为属性, S 为实例集合为实例集合, E表示平均类熵表示平均类熵, T 为为某一阈值点。某一阈值点。 定理表明定理表明, 对连续属性对连续属性A , 使得实例集合的平均类熵达使得实例集合的平均类熵达到最小值的到最小值的T , 总是处于实例序列中两个相邻异类实例总是处于实例序列中两个相邻异类实例之间。之间。(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理15 由由Fayyad 边界点判定定理可知边界点判定定理可知, 无需检查每一个阈无需检查每一个阈值点值点, 只要检查相邻不同类别的边界点即可。为了保持与只要检查相邻不同类别

16、的边界点即可。为了保持与C4.5 的一致性的一致性, 这里边界点选为相邻不同类别的属性值这里边界点选为相邻不同类别的属性值中较小的一个。例如中较小的一个。例如, 当排序后的实例属性值为当排序后的实例属性值为 v1 , v2 , , v10 , 其中前其中前3 个属于类别个属于类别C1 , 中间中间4 个属于类别个属于类别C2 , 最后最后3个属于类别个属于类别C3 , 因此只需考察两个边界点因此只需考察两个边界点v3 与与v7而无需检查其余而无需检查其余7 个阈值点个阈值点, 然后选择然后选择v3 与与v7 中使得平中使得平均类熵最小的那个作为最优阈值。均类熵最小的那个作为最优阈值。(2)能够

17、完成对连续属性的离散化处理能够完成对连续属性的离散化处理16 当需要离散化的属性的属性值越多当需要离散化的属性的属性值越多, , 而所属类别而所属类别越少时越少时, , 性能提高越明显性能提高越明显; ; 当出现最不理想情况当出现最不理想情况, , 即每个属性值对应一个类即每个属性值对应一个类别别, , 改进算法运算次数与未改进算法相同改进算法运算次数与未改进算法相同, , 不会降低不会降低算法性能。算法性能。(2)能够完成对连续属性的离散化处理能够完成对连续属性的离散化处理17C4.5分类算法在硕士研究生智育测评中的应用分类算法在硕士研究生智育测评中的应用采用某高校硕士研究生一年级的采用某高

18、校硕士研究生一年级的20名学生的期末考试成绩作为数名学生的期末考试成绩作为数据集据集,其中的课程有英语精读、英语听说等英语类课程、自然辩其中的课程有英语精读、英语听说等英语类课程、自然辩证法、科学社会主义等政治类课程证法、科学社会主义等政治类课程,还有数据挖掘概论、数据库还有数据挖掘概论、数据库原理、并行计算导论等专业性课程。原理、并行计算导论等专业性课程。在建立决策树的过程中在建立决策树的过程中,我们将按以下方式分类我们将按以下方式分类:政治成绩政治成绩(包括自包括自然辩证法和科学社会主义然辩证法和科学社会主义) ,英语成绩英语成绩(包括英语精读、英语听说包括英语精读、英语听说和专业外语和专

19、业外语) ,核心专业课成绩核心专业课成绩(与本专业培养目标最紧密的课程与本专业培养目标最紧密的课程) ,一般专业课成绩一般专业课成绩(除核心专业课外的专业课除核心专业课外的专业课) 。将这四个属性作为决策属性将这四个属性作为决策属性,定义成绩大于等于定义成绩大于等于85分为分为“优优”;大大于等于于等于80,小于小于85分为分为“良良”;大于等于大于等于70,小于小于80为为“中中”。将。将四个属性的和作为智育成绩四个属性的和作为智育成绩,并按智育测评的标准并按智育测评的标准,将训练样本中将训练样本中智育成绩由高到低按比例分类智育成绩由高到低按比例分类: 10%为优、为优、30%为良、为良、4

20、0%为中为中等、剩余为及格四个标准等、剩余为及格四个标准,并将这四个标准作为分类属性并将这四个标准作为分类属性(如表如表1所示所示) 。三、C4.5算法应用举例18 表表1决策树训练样本集决策树训练样本集编号 政治 英语 核心专业课 一般专业课 智育成绩 1 78. 67 83. 33 88. 14 86 336. 14 2 81 83. 67 94. 86 86. 44 345. 97 3 83. 33 91. 33 90. 43 87. 06 352. 15 4 81. 33 82. 5 93. 33 88. 2 345. 36 5 71. 33 78. 17 90. 86 85. 93

21、326. 29 6 83. 33 79. 67 87. 14 80 330. 14 7 79 80. 83 90 87. 32 337. 15 8 82 82. 67 88. 71 82. 28 335. 66 9 72. 67 81. 33 87. 5 83. 13 324. 6310 81. 33 84. 83 81. 29 87. 78 335. 23三、C4.5算法应用举例19 表表1决策树训练样本集决策树训练样本集编号 政治 英语 核心专业课 一般专业课 智育成绩11 77. 33 80. 5 85. 14 86. 53 329. 5012 75. 67 86. 5 91. 13 9

22、0. 41 343. 7113 81. 33 84 89. 33 89. 56 344. 2214 84. 33 85. 67 91 81. 53 342. 5315 82 85. 5 88. 17 82. 26 337. 9316 79. 67 85 86. 86 86. 89 338. 4217 79 86. 17 89 88. 75 342. 9218 78. 67 83. 83 78. 29 89. 38 330. 1719 85. 67 86. 67 94. 29 87. 94 354. 5720 79. 33 79. 17 87. 83 80. 72 327. 05三、C4.5算法

23、应用举例20 2. 2建立决策树建立决策树 智育成绩中达到优、良、中等、及格四类标准的子集数分别为: r1 = 2、r2 = 6、r3 = 8、r4 = 4,首先计算 集合T分类的信息熵: I(r1 、r2 、r3 、r4,)=I(2,6,8,4) = =1. 9464393 然后计算每个决策属性的期望信息量(即熵值) ,以决策属性“政治成绩”为例,分别计算它为优、良、中三个类别时的期望信息量,最终得出它的信息增益率。202log202-2206log206-2208log208-2204log204-2三、C4.5算法应用举例21当“ 政治成绩 ” 为优时, I( u11 , u21 , u

24、31 , u41 ) = I(1, 0, 0, 0) =0.225;(2) 当“ 政治成绩 ” 为良时 ,I ( u12 , u22 , u32 , u42 ) = I (1, 4, 4, 0)(3) 当“ 政治成绩 ” 为中时 ,三、C4.5算法应用举例522. 1204log204204log204202log202)4 , 4 , 2 , 0(),( I22243332313 Iuuuu201log201-2204log204-2392 . 1204log204-222所以政治成绩的期望信息量为：387.1),(2010),(209),( I201(E433323134232221241

25、312111uuuuIuuuuIuuuu政治成绩）三、C4.5算法应用举例政治成绩的信息增益为：0.559(),( I(G4321政治成绩）政治成绩）Errrrain政治成绩的信息增益率为：0.4029096E(（政治成绩）政治成绩）政治成绩）GainRatio23三、C4.5算法应用举例 同理同理, ,得出决策属性得出决策属性“ 英语成绩英语成绩 ” 、 “核心核心专业课成绩专业课成绩 ” 、 “一般专业课成绩一般专业课成绩 ” 的信息增的信息增益率分别为益率分别为: :0.144E(（核心专业）核心专业）核心专业）GainRatio0.366E(（英语成绩）英语成绩）英语成绩）GainRa

26、tio0.117E(（一般专业课）一般专业课）一般专业课）GainRatio24 决策属性决策属性“政治成绩政治成绩 ” 的信息增益率最大的信息增益率最大, ,因此因此将此作为决策树的根节点将此作为决策树的根节点, ,对于每个分支按上述步骤对于每个分支按上述步骤, ,根据信息增益率由大到小根据信息增益率由大到小, ,建立从根节点到叶节点的建立从根节点到叶节点的决策树。决策树。三、C4.5算法应用举例2526 2 . 3 结果分析 由此决策树可知由此决策树可知: (1) 英语成绩为优的情况下英语成绩为优的情况下 ,核心专业课成绩全为优核心专业课成绩全为优 ,一般专业课一般专业课成绩为优的概率是成

27、绩为优的概率是 71 . 4%。说明英语水平的提高对计算机专业课程。说明英语水平的提高对计算机专业课程的学习有很大的帮助的学习有很大的帮助 ,对于出色的完成培养目标具有至关重要的作用。对于出色的完成培养目标具有至关重要的作用。 (2) 核心专业课成绩为优的情况下核心专业课成绩为优的情况下 ,一般专业课成绩为优的概率一般专业课成绩为优的概率是是 66 . 7%。说明核心专业课成绩的提高对一般专业课成绩的提高是。说明核心专业课成绩的提高对一般专业课成绩的提高是正相关的。正相关的。 (3) 在智育成绩为在智育成绩为“ 良良 ” 以上的同学中以上的同学中 ,他们的核心专业课成他们的核心专业课成绩都是绩都是“ 优优 ” 。说明这种课程设置方式。说明这种课程设置方式 ,使智育成绩优异的同学使智育成绩优异的同学 ,核心专业课成绩也非常优秀核心专业课成绩也非常优秀 ,这是研究生教育管理者最希望看到的结这是研究生教育管理者最希望看到的结果。果。 (4) 政治成绩的好坏政治成绩的好坏 ,对于英语成绩、对于英语成绩、 专业课成绩的好坏没有必专业课成绩