о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



һʽжѧϰ㷨INDUCE
桡־Ǭ
ժҪINDUCE㷨Զжɵѧϰн׳ԺáЧʸߺȷʸߵŵ㣬ѧϰԶ̬Ĳ.㷨˹Թɵ˼룬ѧϰµӣʹռЧʵõ.ʵINDUCEкܺõӦǰ.
ؼʡжѧϰԹɣ
ͼšTP18
INDUCE: AN INCREMENTAL DECISION TREE ALGORITHM
LUO Bin, ZHOU Zhi-Hua, CHEN Zhao-Qian, and CHEN Shi-Fu
(State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing210093)
AbstractINDUCE is a version of top-down induction of decision trees. It has the merit of being robust, efficient and precise, and it is capable of incremental learning, so as to modify concept description dynamically. INDUCE also employs the idea of constructive induction, which improves the efficiency of searching in concept description space by generating new descriptors. Successful applications of INDUCE indicate that it has a bright future.
Key wordsdecision tree, incremental learning, constructive induction, neural network
1
жڼලѧϰһֳ÷ѧϰжʽʾȡĸȽдԵCLS1ݣID32ݵ.ǣЩж㷨޷ԣҲ߱ѧϰʹӦܵ˽ϴ.
INDUCEʽͶȡ㷨IHMCAP3ݵķѧϰ֣һʽжѧϰ㷨.ֵԱʾʽѧϰĲͨӿڣ߱˴ԵѧϰЧʽϸߣݴԽϺ.⣬㷨˹Թɵ˼룬ѧϰдµӣӶֲ˱֪ʶĲ.㷨Windows95Visual C++ 4.2ʵ̨֣Ԥϵʵõ˳ɹӦ.
2INDUCE㷨
2.1
1. E={e|e=c,a1,,ancCaiAi}
ǳEΪʾCΪAiΪԣnΪʾEԸ|C|ΪʾEĸ|E|ΪʾʾeĵһcΪֵΪe.CeaiΪeAiϵȡֵΪe.Ai.
ĸֵΪʾEMFC(most favorable concept)

2. RL={X,V|X{C,A1,,An},VX}.RLΪ򼯺ϣX,VΪ.
3. T={i,r,E|iN+rRLEΪʾ}ΪжT
ii,r1,E1T, 2i+1,r2,E2T2i+2,r3,E3T
ii,r1,E1T, 2i+2,r2,E2T2i+1,r3,E3T
i2i+1,r1,E1T, 2i+2,r2,E2Ti,r3,E3T
s,tT,aTaΪst.
ǳԪ顴i,r,EΪ˶Ľ㣬硴i,C,{cx},EĽΪҶ㣬ǲԽ.
2.2ѡ
ID3ѡΪԱ׼ֵͬӼ.ַ޹ֵ֦ʧ.INDUCEõĲһ߼ʽʽʽΪe.Ai{vi1,vi2,,vim},e.AiʾeAiϵȡֵvi1,vi2,,vimAiܵȡֵ.ʾڲֻС桱͡١ȡֵINDUCEɵһ綨3ʾĶж.ʾEڲȡֵΪʾֵӼE+뵽E-.INDUCEĲѡ׶νУѡAiѡAiֵvi1,vi2,,vim.ѡвοϢصĸ.ѡʱԵȡֵÿһϢѡСΪ˴λֵAi.AiĸֵֿܽкϲѡȡϢСֺϲʽ.
2.3ӿ
жһ֮󣬲ѡܻ.ʾеɢԶΪԣֺҲµĻ޷.ʱINDUCEѰҾȲҪҶдֵЩʾĿϢתΪѵ-ģʽԣԱڸҶģͣɽһѧϰĹ.ִʽһ̶Ͻѧϰߵ⣬ʹINDUCEѧϰԣж㷨÷Χ.
2.4Թ
ѧϰϵͳʾռԤȶõģѧϰб̶ֹ.ʾɵõĸǴʾѡȡʵʾ.ֹɷʽΪѡԹ.ѡԹһľԣֻеԭʼѧϰĸֱʱѧϰܹ˳.Թɣ4ͨ˷һޣͬʱԹɻͨ޸ġɾԭķʹԭʼʾռ䷢תĿΪ˴ѧϰЧʺͽ͸ϵĸӶ.ѧϰһڸռнḶ́Թתԭʼռ䣬ʹһСķΧڽУѧϰЧ.ͬʱ룬رԭʼγɵ룬Լѧϰıʾʽ.Ϊ˵õõĻINDUCE˹Թɵ˼룬ڹɹдµӣֲ֪ʶĲ.
INDUCEݲe.Ai{vi1,vi2,,vim}Ai=PA(Ai,{vi1,vi2,,vim})={vdefaultvother}.AiֵvdefaultAiеvi1,vi2,,vimֵϲvotherAiеȡֵϲ.AiAi֮ͶӰϵǳAiΪAiӰ(shadow attribute).
2.5ѧϰ
жѧϰ㷨߱ѧϰԭ仮ֺĴʽ.ֺǴϿǵǰʾѡĲԽֿ.ԣµʾʱԭеĲѾܷӳʾֺòɨʾѡµĲԣжҲҪӸʼ¹.ʹжѧϰ㷨ѧϰҪĽжɹ̣ʹڻµʾʱֻҪ޼ԭжͿʹ֮ӳʾı仯.ΪﵽһĿģǿԿжɵĹϸһЩϢЩϢԲɨʾܼŲ.
˼룬INDUCEµʽ5ݣʾжƥ䣬ֱҶΪֹ.жܹԸʾȷ࣬򱣳жԭ̬ʾڵҶ㾫ǷûָľȣȸжҲ޸ģȵҪԸýл.ʱ޷ҵʵĻԣпµ.ѧϰƻʹINDUCEһ6ݣƪ׸.
3INDUCE㷨
㷨1. INDUCE
룺ʾeжT.
жT.
 IF (T=) THEN T{0C{e.C}{e}} STOP
 iC{cx}CEdeduce(eT)
 IF (cx=e.C) THEN STOP
 T(T-{iC{cx}CE})generateTree(iC{cx}CE)
INDUCE㷨ʹdeducegenerateTree㷨.deduceʾжƥ䣬deducef:E{T}TgenerateTreeжgenerateTreef:T{T}.
㷨2. deduce
룺ʾeжT.
Ҷ㡴i,r,E.
 ѡTĽڵ㡴irE.
 WHILE (2i+1r䣬E䡵T) DO
(i) T(T-{irE}){irE{e}}
(ii) IF check(e,r) THEN
irE2i+1r䣬E䡵
ELSE
irE2i+2r壬E塵
 T(T-{irE}){irE{e}}
 RETURN irE{e}
checkжʾڲȡֵ㷨checkf:ERLBOOLEAN.
generateTreeʵϿΪһûжѧϰ㷨ؿһжѧϰ㷨ҪĻֱ׼ֹҶҪ.㷨INDUCE봦ƥdeduce㷨ϣ;߱ѧϰ.generateTree㷨еõformula㷨ĿľΪɻֱ׼.
formulaɵĹrΪʱζżзŴ޷жȣӦòҶϵʾѧϰ.
㷨3. generateTree
룺Ҷ㡴iC{cx}CE.
жT.
 T{iC{cx}CE}
 WHILE (accuracy(T)Pr) DO
(i) NoC{cj}Eselect(T)rformula(E)
(ii) IF void(r) THEN resorttoann
(iii) E+{e|eEcheck(e,r)}E-{e|eEĩcheck(e,r)}
(iv) T(T-{NoC{cj}E})
{NorE2No+1C,{MFC(E+)}E+
2No+2C,{MFC(E-)}E-}
 RETURN T
generateTree㷨УPrǹɾȣaccuracyڼжȣaccuracyf:{T}[0,1]MFCf:{E}Cμ1selectжѡһҶڻ֣selectf:{T}TformulaڷʾEѲrformulaf:{E}RL.
㷨4. select
룺жT.
Ҷ㡴NoC{ci}E.
 ѡҶ

 RETURN NoC{ci}E
4ʵ
INDUCE㷨ֱΪʡ̨йҵܹ˾716о̨·Ԥϵͳ鱨ϵͳ7ݣѽãЧϺ.Ľ̨Ԥ.
̨һҪĿǰҪרҾֹ̨Ԥȷʽϵͣͨ75%.INDUCĘ·Ԥϵͳڳѵ֮ȷʿɴﵽ80%.
̨Ԥı֪ʶ1ʾ.
1̨Ԥⱳ֪ʶ

/ԡȡֵ
̨(class)غǿѹ(c0)ڸ(c1)
۷չ(c2)޲(c3)
̨ϵĸԱĸ(A0)ٷ(v00)(v01)
588㾭(A1)116E(v10)116E120E(v11)
120E127E (v12)127EԶ(v13)
޲۵쳬35N(A2)û(v20)104E120E֮(v21)104E120E֮(v22)
½ӽ̨һѹֵ(gpm) (A3)ٴ5920(v30)Сڵ5920(v31)
̨䶫15588ϵγ֮(B0)(013)
̨븱γֵ֮24Сʱ(B1)(040)
߼̨γȲֵ(B2)(015)
γ(B3)(050)
ľ(B4)(90179)
̨(B5)(113.5123)
̨γ(B6)(21.533)
588߱(B7)(2234.1)


ѡýʡ̨ṩĽʡ1980199251̨ʵΪѵغǿѹ621۷չ8޲16.INDUCE㷨ѧϰжͼ1ʾ.


ͼ1̨Ԥж
5
ͼ1ʾжй㣬ʹӦгѧϰ㷨FTART89.Aһ¹ӣA=v1ˡ(A1=v11) or (A1<>v11 and A1<>v10).ýʡ̨ṩ10̨ʵͼ1ʾж˲ԣΪ80%.
INDUCE㷨н׳ԺáЧʸߡȷʸߵŵ㣬Եʽشʾ桰ĿǰΪֹѡĸӶֲ˳ж㷨ⷽĲ.INDUCE㷨ӿںԴԣͨйԹɣʹøռЧʵõ.ѾʹINDUCE㷨Ԥ͹Ӧϵͳõûλĺ.
õȻѧ(Ŀ 69875006)뽭ʡȻѧ(Ŀ BK97029).
߼飺У196712ְʿоʦҪ»ѧϰݿ⼼ȷо.־У197311ʿоҪоΪѧϰ.ǬŮ19402ڣҪоΪѧϰרϵͳ.У193810ڣʿʦҪ֪ʶ̡ѧϰͼȷо.
ߵλϾѧ¼صʵҡϾ210093
ο
1Hunt E B, Marin J, Stone P. Experiments in Induction. New York: Academic Press, 1966
2Quinlan J R. Induction of decision trees. Machine Learning, 1986,62(1):81106
3Ǭ, ־. ʽIHMCAP㷨оӦ.ѧ,1998,21(8):759764
(Chen Zhaoqian, Zhou Zhihua et al. Research and application of the incremental algorithm IHMCAP. Chinese Journal of Computers(in Chinese), 1998,21(8):759764)
4Michalski R S. A theory and methodology of inductive learning. In:Michalski R S, Carbonell J G, Mitchell T M Eds.Machine Learning: An Artificial Intelligence Approach. New York: Springer-Verlag,1984.83134
5Ǭ,־.ѧϰģHLMеѧϰ㷨.ѧ,1997,8(11):875880
(Chen Zhaoqian, Zhou Zhihua et al. The incremental learning algorithm in hybrid learning model HLM. Journal of Software(in Chinese), 1997,8(11):875880)
6־, Ǭ. IHMCAP㷨ݵĴ. 廪ѧѧ(Ȼѧ), 1998,38(S2):118122
(Zhou Zhihua, Chen Zhaoqian et al. The noisy data disposal by IHMCAP algorithm. Journal of Tsinghua University(natural science version)(in Chinese), 1998,38(S2):118122)
7μ, ־. IHMCAP㷨һģ. 1998йԶѧļ. ϺйԶѧԶרҵίԱ, 1998.969974
(He Jiazhou, Zhou Zhihua et al. A fault diagnosis model based IHMCAP algorithm. In: Proc of the CIAC'98(in Chinese). Shanghai: Intelligent Automation Committee of Chinese Academy of Automation, 1998.969974)
8Ǭ, ֵ. һµӦг㷨FTART. ѧ, 1996,7(8):458465
(Chen Zhaoqian, Zhou Rong et al. A new adaptive resonance theory algorithm. Journal of Software(in Chinese), 1996,7(8):458465)
9Ǭ, . FTART㷨оĽ. ѧ, 1997,8(4):259265
(Chen Zhaoqian, Li Hongbing et al. Analysis and improvement of FTART algorithm. Journal of Software(in Chinese), 1997,8(4):259265)
ԭյڣ1998-08-13
޸ĸյڣ1998-11-23
