Vol.26 No.2 尹阿东等：增量决策树算法及复杂度分析 ·205· 记录，所以停止决策树的拓展 集，由增量决策树算法生成的决策树的形态与传 (3)当训练数据集新增第3条记录时，由于节 统的D3算法生成的决策树的形态完全一致，说 点分类属性“身高”与候选属性“眼睛颜色”有相 明两种算法具有相同的准确率， 同的信息熵值0，根据公式a-经E可 Ibb,+2+lbe 知，am=0,所以当新增一条记录后，将导致候选 4结论 属性“眼睛颜色”替代原先的分类属性“身高”，此 增量决策树算法利用两个辅助定理，处理增 时的决策树的形态如图1所示. 量数据集的决策树构造问题，解决了传统D3算 (4)依次类推，当训练数据集新增第48条记 法无法处理增量数据集的缺点，通过对增量决策 录的过程中，根据增量决策树算法可以得到相应 树算法复杂度的分析可以发现，虽然增量算法在 的增量决策树.最终根据训练数据集中的8条记 构造决策树时，需要较大的计算费用，但是利用 录，利用增量决策树算法生成的决策树的形态如 增量算法可以一次完成决策树的构造，避免了对 图2所示. 数据集的重复扫描，而且可以构造出与D3算法 经过对比分析发现，利用表1中的训练数据 准确率基本相同的决策树， 眼睛颜色 参考文献 蓝色0，] 棕色[0,2] 1 Schlimmer J C,Fisher D.A case study of incremental con- 是 身高 cept induction [A].Proceedings of AAAI-86 [C].Philad- elphia,1986 矮0,1] 高[0,1] 2 Utgoff P E.Incremental Induction of Decision Trees [J]. Mach Learn,1989(4):161 否 否 3 Utgoff P E.An improved algorithm for incremental induc- 图1三条记录时决策树的形态 tion of decision trees [A].Proceedings of the Eleventh Int. Fig.1 Decision trees of three training instances Conference on Machine Learning [C].New Jersey,1994. 318 头发颜色 4 Kalles D,Morris T.Efficient incremental induction of de- 金色[2,2 红色[1,0] cision trees [J].Mach Learn,1996(1):1 黑色0,3 眼晴颜色 5 Kalles D,Papagelis A.Stable decision trees:Using local 是 蓝色2,01 棕色[0,2] anarchy for efficient incremental learning [J].Int J Artif 眼睛颜色 Intell Tools,2000,9(1):79 身高 身高 蓝色[0,2]/ 棕色[0,1】 6 Piater JH,Riseman E M.Interactively training pixel clas- \高0,1] sifiers []Int J Patter Recognit Artif Intell,1999,13(2): 矮0,1y 高[1,0] 171 否 7 Elomaa T,Kaariainen M.An analysis of reduced error pru- 是 否 否 ning[J].J Artif Intell Res,2001,15:163 图2增量算法生成决策树的最终形态 8 Wang X Z,Chen B,Qian G L,et al.On the optimization Fig.2 Final decision trees of eight training instances offuzzy decision trees [J].Fuzzy Sets Syst,000,112:117 An Incremental Alogrithm for Inducing Decision Trees and Its Complexity YIN Adong,GONG Yu,WU Shengli,WU Sen,GAO Xuedong,LI Yongjun Management School,University of Science and Technology Beijing,Beijing 100083,China ABSTRACT An incremental algorithm for inducing decision trees is presented based on ID3 algorithm.The com- plexity of the incremental algorithm is analyzed in terms of instance-count additions and e-score calculations.The same training instance shows that the incremental algorithm can induce decision trees equivalent to those forms by ID3 algorithm. KEY WORDS decision trees;incremental algorithm;complexityV心1 . 2 6 N 0 . 2 尹 阿东等 : 增 量决策 树算 法及 复杂 度分 析 一 2 0 5 . 记录 , 所 以停 止决 策树 的拓 展 , (3 ) 当训 练数 据集 新 增第 3 条记 录 时 , 由于节 点分 类属 性 “ 身 高 ” 与 候选 属 性 “ 眼睛 颜色 ” 有 相 集 , 由增量 决 策树算 法 生成 的决 策树 的形 态与 传 统 的 ID 3 算 法 生成 的 决策 树 的形 态完 全 一 致 , 说 明两种 算 法 具有 相 同 的准确 率 . 同 的信 息 嫡值 。 , 根据 公式 am 。 一 史拱实兽任军卫可 I U竹 丁 ` 不 i U` 知 , am ax = O , 所 以 当新增 一 条 记录 后 , 将 导致 候 选 属 性 “ 眼睛 颜色 ” 替代 原 先 的分类属 性 “ 身高 ” . 此 时 的决策 树 的形 态如 图 1 所示 . (4 )依 次类 推 , 当训练 数 据 集新 增 第 4一 8 条记 录 的过 程 中 , 根 据增 量 决策树 算 法可 以得 到相应 的增量 决 策树 . 最 终 根据 训 练数 据集 中的 8 条记 录 , 利用 增 量决 策树 算法 生成 的 决策树 的形 态如 图 2 所 示 . 经过 对 比分 析 发现 , 利 用表 1 中的 训练 数据 眼睛颜色 蓝罗/ 映 , 2 ’ 身高 一 / 准 【。 , 1」 否 否 图 1 三条 记录 时决 策树 的形 态 F ig . l D e c is i o n t r e e s o f t h r e e t r a in i n g in s t a n c e s 头发颜色 眼睛颜色 蓝色 l州冷 【0 , 2 , 否 否 图 2 增 量算 法生 成决 策树 的最终 形 态 F ig . 2 F i n a l d e c is i o n t r e e s o f e i g h t t r a i n i n g i n s t a n e e s 4 结论 增量 决策 树 算法 利 用两 个辅 助 定理 , 处 理 增 量 数据 集 的决 策树 构 造 问题 , 解 决 了传统 ID 3 算 法无 法 处理增 量数 据 集 的缺 点 . 通 过对 增量 决 策 树算法 复杂度 的分 析 可 以发现 , 虽 然增 量算 法在 构造 决 策树 时 , 需要 较大 的计 算费用 , 但 是 利用 增量算 法 可 以一次 完成 决策 树 的构 造 , 避免 了对 数据 集 的重 复 扫描 , 而且 可 以构 造 出 与 ID 3 算法 准 确 率 基本 相 同 的决策 树 . 参 考 文 献 1 S e h l im m e r J C , F i s h e r D . A c a s e s ut 勿 o f i n e er m e n t a l e o n · e e Pt i n d u e t i o n [ A ] . Pr o e e e d ing s o f A A A I 一 8 6 [C」 . P h i l a d - e lP h i a , 19 8 6 2 U tg o任 P E . In e r e m e n t a 1 In du e t i o n o f D e e i s i o n rT e e s [J」 . M a c h L e am , 19 89 ( 4 ) : 1 6 1 3 U tg o f P E . A n 而P r o v e d a l g o r i thm fo r i n c r e m e in a l i n d u c - ti o n o f d e e i s i o n etr e s [A ] . Por c e e di n g s o f ht e E l e v e n t h l n t . C o n fe r e n e e o n M a e h i n e L e anr i n g [C ] . N e w J e r s e y, 1 9 9 4 . 3 1 8 4 K a ll e s D , M o r i s .T E if c i e in in e er m e n t a 1 i n d u e ti o n o f d e - c i s i o n etr e s [J] . M ac h L e anr , 1 9 9 6 ( l ) : l 5 K a ll e s D , P ap ag e l i s A . S at bl e d e e i s i o n tr e e s : U s i n g l o c a l a n ar c hy fo r e if c i e n t i n c r e m e nt a l l e anr i n g [ J] . I in J A rt if I nt e l l oT o l s , 2 0 0 0 , 9 ( l ) : 7 9 6 P iat e r J H , Ri s e m an E M . I nt e r a c t i v e ly tr a i n i n g Pi x e l e l a s - s i if e r s [J] . I n t J P a t em eR e o gn i t A rt if lin e l l , 19 9 9 , 13 ( 2 ) : 1 7 1 7 E l o m a T, K ar i a i n e n M . nA an a ly s i s o f er du e e d e r o r Pur - n i n g [J ] . J A rt l f lin e ll R e s , 2 0 0 1 , 1 5 : 1 6 3 8 从a/ n g X Z , C he n B , Q i a n G L , e t a l . O n ht e o Pt im iatZ i o n o f fu Z yZ d e c i s i o n tr e e s [J I . F u Z y s e t s s y s t , 2 0 0 0 , 1 1 2 : 1 1 7 A n I n e r e m e n t a l A l o g r it h m fo r I n d u c i n g D e c i s i o n rT e e s a n d I t s C o m P l e x iyt 1了N A do ng, G O N G ,uY 附 U hS e喇砚砰 U eS n , G月口 Xu e ` lo ng, IL oY ” 乡 un M an ag e m e n t S e h o o l , U n i v c r s ity o f s c i e n e e an d eT e hn o l o gy B e ij i n g , B e ij in g 10 0 0 8 3 , C h in a A B S T R A C T A n i n e r e m e n t a l a lg o ir t h n l of r i n du e i n g d e e i s i o n tr e e s 1 5 P re s e in e d b a s e d o n ID 3 a l g o ir t hj m . hT e e o m - P l e x ity o f ht e i n e r e m e in a l a l g o ir t 加rn 1 5 an ly z e d in t e rm s o f in s t an e e 一 c o u n t a d dit i o n s an d e 一 s e o re e a l c u l at i o n s . hT e s am e atr l n i n g l n s t an e e s h o w s ht at ht e i cn re m e in a l a lg o ir t 加rn e an in du e e d e e i s i o n tre e s e qu i v a l ent t o ht o s e of rm s 勿 ID 3 a l g o ir t知rn . K E Y W O R D S d e e i s i o n tr e e s ; i n e r e m e nt a l a lg o ir t h m ; e o m Pl e x i ty