本站原创关键词:数据挖掘;决策树;算法
: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)抗噪性差,训练例子中正例和反例的比例较难控制。
于是Quilan改进了ID3,提出了.5算法。.5算法现在已经成为最经典的决策树构造算法,排名数据挖掘十大经典算法之首。
二、决策树的经典构造算法(二)——.5
由于ID3算法在实际应用中存在一些问题,于是Quilan提出了.5算法,严格上说.5只能是ID3的一个改进算法。.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:(1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足。
信息增益率:Gain ratio(X)= Gain(X)/Split _Infox(X);
(2)在树构造过程中进行剪枝。
(3)能够完成对连续属性的离散化处理。
(4)能够对不完整数据进行处理。
.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。具体算法步骤如下;
(1)创建节点N
(2)如果训练集为空,在返回节点N标记为Failure
(3)如果训练集中的所有记录都属于同一个类别,则以该类别标记节点N
(4)如果候选属性为空,则返回N作为叶节点,标记为训练集中最普通的类
(5)for each候选属性attribute_list
(6)if候选属性是联系的then
(7)对该属性进行离散化
(8)选摘自：本科毕业论文答辩www.808so.com
择候选属性attribute_list中具有最高信息增益的属性D
(9)标记节点N为属性D
(10)for each属性D的一致值d
(11)由节点N长出一个条件为D=d的分支
(12)设s是训练集中D=d的训练样本的集合
(13)if s为空
(14)加上一个树叶,标记为训练集中最普通的类
(15)else加上一个有.5(R-{D},C,s)返回的点
三、结束语
决策树技术是一个年轻且充满希望的研究领域,商业立业的强大驱动力将会不停止地促进它的发展,人们对它的研究正日益广泛和深入。尽管如此,决策树算法仍然面临着许多问题和挑战,决策树的运用越来越广,它的优势也得到了充分体现,我们相信,随着这些决策树算法的不断改进,其应用领域将更加广泛。
参考文献:
ZhaoHui Tang,Jamie MacLennan.数据挖掘原理与应用[M].北京:焦贤龙,高升,杨大川.清华大学出版社
马秀红.数据挖掘中决策树的探讨[J].计算机工程与应用
[3]Han Jiawei,Micheline K.数据挖掘:概念与技术[M].范明,孟小峰.北京:北京机械工业出版社