C45算法

C4.5算法介绍《人工智能》一、C4.5算法的概述二、C4.5算法的具体实现三、C4.5算法应用举例C4.5算法介绍一、C4.5算法的概述C4.5算法是由Quinlan于1993年在ID3算法的基础上进一步改进形成的。C4.5算法也是机器学习算法中的一种分类决策树算法,此算法用信息增益率来选择决策属性，其核心算法是ID3算法。它继承了ID3算法的全部优点，并在ID3的基础上增加了对连续属性的离散化、对未知属性的处理和产生规则等功能，克服了ID3算法的不足。C4.5具体在以下几个方面做出了改进:(1)用信息增益率代替信息增益来选择属性;(2)能够完成对连续属性的离散化处理,这是一个很关键的改进;(3)在决策树构造过程中或者构造完成之后,进行剪枝;(4)能够对不完整数据进行处理,如未知的属性值;(5)C4.5可以用决策树形式形成产生式规则。一、C4.5算法的概述二、C4.5算法的具体实现(1)用信息增益率代替信息增益来选择属性;(2)能够完成对连续属性的离散化处理,这是一个很关键的改进;(3)在决策树构造过程中或者构造完成之后,进行剪枝;(4)能够对不完整数据进行处理,如未知的属性值;(5)C4.5可以用决策树形式形成产生式规则。设T为训练数据集,共有k个类别,集合表示为{C1,C2,⋯,Ck},|Cj|为Cj类的例子数,|T|为数据集T的例子数。选择一个属性V,设它有n个互不重合的取值va(1≤a≤n),则T被分为n个子集{T1,T2⋯,Tn},这里Ti中的所有实例的取值均为vi。|Ti|为V=vi的例子数,|Cjv|是V=vi的例子中,具有Cj类别的例子数。则有：(1)类别Cj的发生概率:p(Cj)=|Cj|/|T|;(2)属性V=vi的发生概率:p(vi)=|Ti|/|T|;(3)属性V=vi例子中,具有类别Cj的条件概率:p(Cj|vi)=|Cjv|/|Ti|。类别的信息熵：(1)用信息增益率代替信息增益来选择属性;kjjjkjjjToTCTCCpCpC1212)(inf||||log||||))((log)()(H按照属性V把集合T分割,分割后的类别条件熵为：)(inf)(inf||||)|(log)|()()|(H1112ToToTTvCpvCpvpVCvivniinikjijiji(1)用信息增益率代替信息增益来选择属性;信息增益(Gain)：)(inf)(inf)|()()(GToToVCHCHVainv属性V的信息熵：)(inf_||||log||||))((log)()(H1212VosplitTTTTvpvpVniiiniii(1)用信息增益率代替信息增益来选择属性;信息增益率：)()(_GVHVGainratioainC4.5采用了信息增益率作为对选择分枝属性的分枝准则。信息增益率表示了由分枝产生的有用信息的比率。因此,这个值越大,分枝包含的有用信息越多。(1)用信息增益率代替信息增益来选择属性;与ID3算法相比，ID3算法选择信息增益最大即熵下降最大的属性进行分支的。当有大量不同的属性值和采用标准化的处理程序时,这种启发式方法很有效。而C4.5算法是选择信息增益率最大的属性进行分支的。从局部看，ID3算法每一步都选择最优分支属性，但是从整体上看，有可能使得整个决策树复杂。而C4.5算法从局部看不一定的选择信息增益最大的属性，但是从整体看，分支更明确，获得的有用信息更多。(1)用信息增益率代替信息增益来选择属性;(1)用信息增益率代替信息增益来选择属性;(2)能够完成对连续属性的离散化处理;(3)在决策树构造过程中或者构造完成之后,进行剪枝;(4)能够对不完整数据进行处理,如未知的属性值;(5)C4.5可以用决策树形式形成产生式规则。二、C4.5算法的具体实现C4．5算法将分类范围从分类的属性扩展到数字属性。如果数据集中存在连续型的描述性属性(数字属性)，C4．5算法首先将这些连续型属性的值分成不同的区间，即“离散化”。通常将连续型属性值“离散化”的方法为：①寻找该连续型属性的最小值，并将它赋值给min，寻找该连续型属性的最大值，并将它赋值给max；②设置区间[min，max]中的N个等分断点Ai，其中，i=1,2,⋯,N；③分别计算把(min，Ai)和(Ai,max)(i=1,2,3,⋯,N)作为区间值时的信息增益率（Ratio）值，并进行比较；④选取信息增益率最大的A。作为该连续型属性的断点，将属性值设置为[min，A]和(A，max)两个区间值。(2)能够完成对连续属性的离散化处理离散化处理过程中，C4.5算法是对节点上的每个属性都要计算其信息增益率,然后从中选择信息增益率最大的属性断点。由于在信息增益率计算过程中涉及到对数函数的计算,在计算程序中就得调用库函数,同时随着数据量的增大，计算量也随之增大。这样就增加了计算量时间。因此，在改进的C4.5算法中采用了“Fayyad边界点判定定理”(2)能够完成对连续属性的离散化处理•定义:属性A中的一个值T是一边界点,当且仅当在按A的值排序的实例序列中,存在两个实例e1,e2∈S具有不同的类,使得A(e1)TA(e2),且不存在任何其他的实例e′∈S,使得A(e1)A(e′)A(e2)。A(e)表示实例e的A属性值。S表示实例的集合。•定理:若T使得E(A,T,S)最小,则T是一个边界点。其中,A为属性,S为实例集合,E表示平均类熵,T为某一阈值点。•定理表明,对连续属性A,使得实例集合的平均类熵达到最小值的T,总是处于实例序列中两个相邻异类实例之间。(2)能够完成对连续属性的离散化处理由Fayyad边界点判定定理可知,无需检查每一个阈值点,只要检查相邻不同类别的边界点即可。为了保持与C4.5的一致性,这里边界点选为相邻不同类别的属性值中较小的一个。例如,当排序后的实例属性值为{v1,v2,⋯,v10},其中前3个属于类别C1,中间4个属于类别C2,最后3个属于类别C3,因此只需考察两个边界点v3与v7而无需检查其余7个阈值点,然后选择v3与v7中使得平均类熵最小的那个作为最优阈值。(2)能够完成对连续属性的离散化处理当需要离散化的属性的属性值越多,而所属类别越少时,性能提高越明显;当出现最不理想情况,即每个属性值对应一个类别,改进算法运算次数与未改进算法相同,不会降低算法性能。(2)能够完成对连续属性的离散化处理C4.5分类算法在硕士研究生智育测评中的应用•采用某高校硕士研究生一年级的20名学生的期末考试成绩作为数据集,其中的课程有英语精读、英语听说等英语类课程、自然辩证法、科学社会主义等政治类课程,还有数据挖掘概论、数据库原理、并行计算导论等专业性课程。•在建立决策树的过程中,我们将按以下方式分类:政治成绩(包括自然辩证法和科学社会主义),英语成绩(包括英语精读、英语听说和专业外语),核心专业课成绩(与本专业培养目标最紧密的课程),一般专业课成绩(除核心专业课外的专业课)。•将这四个属性作为决策属性,定义成绩大于等于85分为“优”;大于等于80,小于85分为“良”;大于等于70,小于80为“中”。将四个属性的和作为智育成绩,并按智育测评的标准,将训练样本中智育成绩由高到低按比例分类:10%为优、30%为良、40%为中等、剩余为及格四个标准,并将这四个标准作为分类属性(如表1所示)。三、C4.5算法应用举例表1决策树训练样本集编号政治英语核心专业课一般专业课智育成绩178.6783.3388.1486336.1428183.6794.8686.44345.97383.3391.3390.4387.06352.15481.3382.593.3388.2345.36571.3378.1790.8685.93326.29683.3379.6787.1480330.1477980.839087.32337.1588282.6788.7182.28335.66972.6781.3387.583.13324.631081.3384.8381.2987.78335.23三、C4.5算法应用举例表1决策树训练样本集编号政治英语核心专业课一般专业课智育成绩1177.3380.585.1486.53329.501275.6786.591.1390.41343.711381.338489.3389.56344.221484.3385.679181.53342.53158285.588.1782.26337.931679.678586.8686.89338.42177986.178988.75342.921878.6783.8378.2989.38330.171985.6786.6794.2987.94354.572079.3379.1787.8380.72327.05三、C4.5算法应用举例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算法应用举例(1)当“政治成绩”为优时,I(u11,u21,u31,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-2204log204-2392.1204log204-2所以政治成绩的期望信息量为：387.1),,,(2010),,,(209),,,(I201(E433323134232221241312111uuuuIuuuuIuuuu政治成绩）三、C4.5算法应用举例政治成绩的信息增益为：0.559(),,,(I(G4321政治成绩）政治成绩）Errrrain政治成绩的信息增益率为：0.4029096E((（政治成绩）政治成绩）政治成绩）GainRatio三、C4.5算法应用举例同理,得出决策属性“英语成绩”、“核心专业课成绩”、“一般专业课成绩”的信息增益率分别为:0.144E((（核心专业）核心专业）核心专业）GainRatio0.366E((（英语成绩）英语成绩）英语成绩）GainRatio0.117E((（一般专业课）一般专业课）一般专业课）GainRatio决策属性“政治成绩”的信息增益率最大,因此将此作为决策树的根节点,对于每个分支按上述步骤,根据信息增益率由大到小,建立从根节点到叶节点的决策树。三、C4.5算法应用举例2.3结果分析由此决策树可知:(1)英语成绩为优的情况下,核心专业课成绩全为优,一般专业课成绩为优的概率是71.4%。说明英语水平的提高对计算机专业课程的学习有很大的帮助,对于出色的完成培养目标具有至关重要的作用。(2)核心专业课成绩为优的情况下,一般专业课成绩为优的概率是66.7%。说明核心专业课成绩的提高对一般专业课成绩的提高是正相关的。(3)在智育成绩为“良”以上的同学中,他们的核心专业课成绩都是“优”。说明这种课程设置方式,使智育成绩优异的同学,核心专业课成绩也非常优秀,这是研究生教育管理者最希望看到的结果。(4)政治成绩的好坏,对于英语成绩、专业课成绩的好坏没有必然的联系。这些规则,可以帮助硕士研究生认清课程间的联系,指导他们在学习过程中,做出最有利于自身发展的选择。三、C4.5算法应用举例C4.5具体在以下几个方面做出了改进:(1)用信息增益率代替信息增益来选择