C4。5算法对ID3算法改进.docVIP

C4。5算法对ID3算法改进摘要:决策树是最受欢迎的数据挖掘技术,本文介绍了两种决策树算法的思想以及它们的优缺点,以及对它们的改进。 关键词:数据挖掘;决策树;算法 中图分类号:TP301.6 文献标识码:A 文章编号:1007-9599 (2012) 13-0000-02 数据挖掘指的是分析数据使用自动化或半自动化的工具来挖掘隐含的模式,是商务智能(Business Intelligence,BI)产品系列中的关键成员。数据挖掘中常用的算法有贝叶斯算法,决策树算法等。 决策树可能是最受欢迎的数据挖掘技术。构造决策树的过程为:首先寻找初始分裂。整个训练集作为产生决策树的集合,训练集每个记录必须是已经分好类的。决定哪个属性域作为目前最好的分类指标。一般的做法是穷尽所有的属性域,对每个属性域分裂的好坏做出量化,计算出最好的一个分裂。建决策树,就是根据记录字段的不同取值建立树的分支,以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值,会使划分出来的记录子集不同,影响决策树生长的快慢以及决策树结构的好坏,从而导致找到的规则信息的优劣。 一、决策树的经典构造算法(一)——ID3 1.ID3算法是1986年由Quilan提出的,它是一个从上到下、分而治之的归纳过程。ID3算法的核心是:在决策树各级结点上选择属性时,通过计算信息增益来选择属性,以使得在每一个非叶结点进行测试时,能获得关于被测试记录最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。 2.ID3算法思想描述如下:(1)初始化决策树T为只含一个树根(X,Q),其中X是全体样本集,Q为全体属性集。(2)if(T中所有叶节点(X,Q’)都满足X属于同一类或Q为空)then算法停止;(3)else{任取一个不具有(2)中所述状态的叶节点(X,Q’)(4)for each Q’中的属性A do计算信息增益gain(A,X);(5)选择具有最高信息增益的属性B作为节点(X,Q’)的测试属性;(6)for each B的取值bi do{从该节点(X,Q’)伸出分支,代表测试输出B=bi;求得X中B值等于bi的子集Xi,并生成相应的叶节点(Xi,Q’-{B});}(7)转(2); 3.ID3算法举例:某市高中一年级(共六个班)学生上学期期末考试成绩数据库。其中学生考试成绩属性有:学籍号、语文、数学、英语、物理、化学,本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定。 第一步:对数据进行规范化处理。将上表中的数据规范化,用0表示成绩小于60分,1表示成绩大于或等于60分。 第二步:选取训练实例集。从所有学生中进行抽样,将抽样数据作为训练集,共计有161条记录。经统计,在这161条记录的训练集中单科成绩及格人数和不及格人数。 第三步:利用信息增益度选取最能区别训练集中实例的属性。 由此可以看出所有课程当中数学是最能区别训练集中决定物理成绩与否的课程。 第四步:创建一个树结点,并创建该结点的子链,每个子链代表所选属性的一个唯一值。使用子链的值进一步细化子类。当出现以下两种情形之一时可以停止分类:1.一个结点上的数据都是属于同一类别;2.没有属性可以再对属性进行分割。 根据各个课程的信息增益度,应该选择数学作为所建决策树的根结点。经统计,可构建出数据的决策树,如下所示: 第五步:将其它成绩作为检验集。并用来检验所生成的决策树的准确度。 由该决策树可以得出下列规则: (2)IF学生的数学及格且化学成绩不及格, (3)IF学生的数学成绩及格且化学成绩及格 我们也可这样描述:学生数学的学习程度将直接影响着其对物理的学习效果。化学的学习对物理的学习也有一定的影响。因此高中教师在进行物理教学时。应考虑学生的数学基础。数学程度较好而物理程度一般的学生应更重视化学的学习。 4.ID3算法是决策树的一个经典的构造算法,在一段时期内曾是同类研究工作的比较对象,但通过近些年国内外学者的研究,ID3算法也暴露出一些问题,具体如下: (1)信息增益的计算依赖于特征数目较多的特征,而属性取值最多的属性并不一定最优。 (2)ID3是非递增算法。 (3)ID3是单变量决策树(在分枝节点上只考虑单个属性),许多复杂概念的表达困难,属性相互关系强调不够,容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。 (4)抗噪性差,训练例子中正例和反