称为例子.其中Vj∈Fj,j=1,2,…,n1设PE和NE是E的2个例子集,分别叫正例集和反例集.假设向量空间E中的正例集PE和反例集NE的大小分别为P、N,由决策树的基本思想知ID3算法是基于如下2种假设:(1)在向量空间E上的一棵正确决策树对任意例子的分类概率同E中的正反例的概率一致.(2)一棵决策树对一例子做出正确类别判断所需的信息量为:
I(p,n)=-pp+n
log2
pp+n
-
np+n
log2
np+n
(1)
如果以属性A作为决策树的根,A具有V个值{V1,V2,V3,…,Vv},它将E分成V个子集{E1,E2,…,Ev},假设Ei中含有Pi个正例和Ni个反例,那么子集Ei所需的期望信息是I(Pi,Ni),以属性A为根,所需的期望熵为:
v
Pi+Ni(2)E(A)=∑I(Pi,Ni)
i=1P+N
以A为根的信息增益是:
收稿日期:2005—08—10
作者简介:刘慧巍(1979-),男,辽宁锦州市人,助教,主要从事计算机教学研究.
24辽宁师专学报2005年第4期
(3)gain(A)=I(p,n)-E(A)
33
ID3选择gain(A)最大,也就是E(A)最小的属性A作为根结点,对A的不同取值对应的E的V个子
3
集Ei递归调用上述过程生成A的子结点B1,B2,…,Bv.
ID3是一个典型的决策树学习系统,它以信息熵作为分离目标评价函数,采用自顶向下,分而治之不可返回的策略,确保决策树的建立最简单,每次需要测试的数据最小.ID3算法构造出的决策树平均深度较小,分类速度较快.
212 ID3算法的缺点
ID3算法总的来说是一个很有实用价值的示例学习算法,它的基础理论清晰,算法较简单,但也存在着一些缺点:
(1)算法往往偏向于选择取值较多的属性,而在很多情况下取值较多的属性并不总是最优的属性,即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中却并不那么重要.例如:在股票市场中个股的选择.
(2)在建树时,每个结点仅含一个特征,是一种单变元的算法,特征间的相关性不够紧.虽然在一棵树上连在一起,但联系还是松散的.
(3)ID3对燥声比较敏感,不容易除去燥声,也就是特征值取错或类别给错.
(4)当训练集增加时,ID3决策树随之变化.在建树过程中,各特征的相互信息会随例子的增加而改变,决策树也随之变化,这对变化的数据集的学习是不适合的.
(5)ID3算法虽然理论清晰,但它的计算比较复杂,在学习和训练数据集的过程中机器内存占用率比较大,比较耗费资源,影响数据学习的时间和成本.3 算法的改进
从上面的讨论可知,Quinlan的ID3算法是把信息熵作为选择测试属性的标准,即树结点的选择策略.但在计算基于属性的信息熵时,公式比较复杂,计算量较大,相应的复杂度也高,当数据量很大的时候很耗费硬件资源,计算花费的时间较长.在对于实例集中的每一个属性,所提供的信息量是具有一定的规律,特别是当某个属性发生时,其某例别结果发生的条件概率提供给我们属性对某例的信息量,基于这个原因,可以考虑采用属性对某例的条件概率提供的分类信息量来构造决策树.311 算法的理论基础
借用概率统计知识并由此延伸出以下定义:定义:设A、B是事件,称P(B|A)为事件A发生时事件B会发生的条件概率,并称这个条件概率P(B|A)为训练实例集A发生后,事件B对训练集中某例别的影响度.
(4)P(B|A)=P(AB)/P(A)
对于实例集中的各个属性,首先计算所有属性值的影响度,然后进行比较,可以知道影响度越大的属性值相对应的属性提供给分类的信息量就越大,依次比较,就可以确定属性对分类的影响程度大小,因此可以根据此大小来构造决策树的生成算法.312 举例分析
从前面的理论分析知,条件概率决策树算法是直接把实例各属性与类别结果相联系,计算在分类为某例条件下,属性不同取值对分类条件的概率,通过比较概率的大小判断属性对分类所提供的信息大小. 通过以下的例子来说明条件概率决策树算法能有效降低计算的复杂性. 表1
表1的样本数据集实例按人员所属类别分为C1、C2两个类别,并利用IDAgeSalaryClass
基于条件概率的决策树算法建立决策树,对表1的实例集进行分类.表1中1
YouthHighC1
所给的数据集中决定人员类别有两个属性:Age和Salary,其中Age的属性值2YouthLowC2分为Old和Youth两个属性值;Salary属性有High和Low两个属性值.对于类3YouthLowC2别字段,将人员所属类别(Class)分为C1和C2两个类别集.下面分别计算各4OldHighC2
5YouthLowC2属性值相对于C1的影响度.
YouthLowC2在表1的数据集中,实例集大小为9,Age取值为Old的记录有3条,6
OldLowC1取值为Youth的记录有6条;Salary取值为High的记录有5条,取值为Low7
8YouthHighC1
的记录有4条.把人员所属类别(Class)看作一个随机变量X,以Youth
9OldHighC2
(Old)表示Age为Youth(Old)的事件;以High(Low)表示Salary为High(下转71页)(Low)的事件.
陈海舰高职学生体育意识培养的调查与对策 71
业余俱乐部,俱乐部可以根据学生的个体差别组织不同水平间的比赛.体育教师要把课内与课外结合起
来、把增强体质与提高运动能力和体育意识的培养结合起来、把理论与实践结合起来,把高职体育的重点
(责任编辑 放在变被动参与型为积极主动参与型.刘国忠,于 海)(上接24页)
设P(Youth|Age)表示年龄属于Youth的事件发生的概率;P(C1,Youth|Age)为年龄属于Youth且类别为C1的事件发生的概率;P(C1ΠYouth|年龄)为年龄属于Youth,人员所属类别(Class)为C1的条件概率,其余类推,由条件概率的概念可知:P(Youth|Age)=6Π9;P(Old|Age)=3Π9;P(High|Salary)=4Π9;P(Low|Salary)=5Π9;P(C1,Youth|Age)=2Π9;P(C1,Old|Age)=1Π9;P(C1,High|Salary)=2Π9;P(C1,Low|Salary)=1Π9.
根据公式(4)有:P(+|正)=P(+,正)ΠP(正),可以知道每个属性对分类为C1的影响度:P(C1/High|Salary)=P(C1,High|Salary)ΠP(High|Salary)=1Π2同理:P(C1/Low|Salary)=1Π5;P(C1/Youth|Age)=1Π3;P(C1/Old|Age)=1Π3;比较可得:P(C1/High|Salary)>P(C1/Youth|Age)
由上面的分析可知:Salary为High时提供分类的信息量大,其次是Age.故必须先选Salary属性对实例集进行分类,接着才是Age.可得出决策树如图1所示,图中的数字表示表1中的ID号.
在图1中对结点1而言,根据上面的计算理论可同理计算其条件概率:P(C1/Youth|Age)=1;P(C1/Old|Age)=0在图1中对结点2而言:P(C1/Youth|Age)=0;P(C1/Old|Age)=1,由上可得到决策树如图2所示.
313 分析与比较
实例证明,在分类问题中采用条件概率决策树算法能够极大地降低计算复杂性,快速生成决策树,可以很直观地得到决策规则,达到简化决策过程,它是直接把属性值和类别结果相联系,通过比较某一属性的取值对分类结果的影响大小,再比较所有的属性对分类结果的影响大小,很直观地构造出决策树,在这个计算过程中,计算的复杂性很大程度上得到了缓解,对计算机的硬件要求也相应降低,使得决策树思想在数据挖掘等领域的发展受计算机硬件的较小.4 结束语
本文通过分析ID3算法的基本原理,针对该算法的计算较复杂的缺点提出采用属性对例别结果的条件概率提供的分类信息量来构造决策树.并通过实例展示了该算法的简洁、计算效率高等特性.从而可以在计算机硬件配置较低、资源消耗较少的条件下来快速生成决策树,得到相应的决策规则.但该算法对大量的数据的实现还有待下一步的工作去验证.
参考文献:
[1]谭旭,等.利用决策树发掘分类规则的算法研究[J].云南大学学报,2000,22(6):415-419.[2]唐华松,姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究,2001,(8):18-22.
[3]QuinlanJR1SimplifyingDecisionTrees[J].InternationalJournalofMan-MachineStudies,1987,27(3):221-234.[4]QuinlanJR1Inductionofdecisiontree[J].MachineLearning,1986,(1):81-106.
[5]尹阿东,等.增量决策树算法及复杂度分析[J].北京科技大学学报,2004,26(2):202-205.[6]史忠植.知识发现[M].北京:清华大学出版社,2002.22-28.
(责任编辑 [7]史忠植.高级人工智能[M].北京:科学出版社,1998.李树东,王 巍)
