ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



ؼСһջ
Ҷ硡
ժҪһֹ-µĹСһջ,ΪؼСһջ.һܹЧؼջ̶,ӶʹջϺõصԽ.ΪЧؼ㼫Сһջ,оʾϵջʽ뼫СһջĹϵ,һֻڸĹѧϰ㷨(clustering-based multiple minimum general generalization,CMGG).㷨ܹЧزؼСһջ,׼ȷطӳѧϰʾϵ.
ؼʡѧϰ,߼,ؼСһջ,Сһջ.
ͼšTP181
Multiple Minimum General Generalization
YE Feng XU Xiao-fei
(Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
AbstractIn this paper, the authors present a kind of generalized least general generalization, called MGG (multiple minimum general generalization), under generalized -subsumption. MGG does effectively reduce the generalization of inductive hypotheses to extent, such that the problem of over-generalization is satisfactorily overcome. For computing MGG efficiently, the relation between normal generalization and MGG is studied and an algorithm CMGG (clustering-based multiple minimum general generalization) based on concept clustering is proposed, which can effectively figure out MGG and reflect accurately the internal relation of the set of learning examples.
Key wordsInductive learning, inductive logic programming, multiple minimum general generalization, least general generalization.
ڹ߼ƣinductive logic programming,ILPһѧϰȵо,ջǽйѧϰҪ[1],Сһջ(least general generalization,LGG)һֳõջʽ,ڰ(-subsumption)µӾСһ㻯[2].ѧϰ㷨LGGʾջ,Ϊɽ.LGGһЧĹɷ.ھ֪ʶֵ,LGGҪӦ[1,3].
LGGڵҪǹɽ۵Ĺջ(over generalization),Ĺɽ۸ǹδ֪ʵ.ɽ۵ĸͨӦһΧڣ֪ʵ,ǹѧϰձڵСҪminimality criteria[4].ɵСҪʹɽӽʾ̺߼Ϣ,ʹɹ̲¹ƫ,ѧϰǱ.Ȼ߼̺,ջǷǳѵ,LGGһǲȫ.֤,ʹڦ-,ƹɽ۵ռ,ܲջ걸ջ[5].,ջⲻڳ׽.ջһ½,,ܲɡԾľСջʵĹӵ.ʵеĽǻȡܹЧؽջ̶ȵĹ.ArimuraĵλӾϵK-Сջ[6],ضķΧ,Զ൥λӾʽЧزʾϵľнϵջ̶ȵĹɽ.
-,һӾ伯ϵĶؼСһջ(multiple and minimum general generalization,MGG)뷽,Чػ˹ջ.ĵĽǶ[6]ĽĽһƹ.ΪʵMGG,һȷӾس̶ȵ,ݴ˸һֻڸ㷨(clustering-based multiple minimum general generalization,CMGG),ʹMGGЧʵ.ʵ,MGGǽLGGջЧ.
1 ظ
1.1 Ӿ
ǹԭӵĻɷ.ĽṹʵоMGGĻ.AΪ,AʾAĻʾż,ΪԪҲУXΪ릲ı.
1. tΪ,
(1) tʦ,tΪԪtX
(2) t1,...,tnΪ,f(n)ʦ,f(t1,...,tn)Ϊ.
Ϊ,Ԫ.Tʾ,GTʾ.ϵĶԪϵܶΪt,tT,tt䵱ҽ滻ʹt=t.tΪtһ,tΪtջ,ttΪһ.sɵĹԼΪLt(s),Lt(s)={أءGT,ءs}.LtĶ֪,ss䵱ҽLt(s)Lt(s).V,VLt(v),vVջ.Vջv䶼vv,vVСһջLGG,ΪLGG(V).
Ӿ估Ķ.PΪνʷż,A(t1,...,tn)Ϊԭӹʽ,t1,...,tnΪ,APΪnԪν.ԭӹʽ.ӾΪֵ,ӾҲʾֵȡ,бԪΪȫԼ.Ӿ伯ϵĶԪϵݦ(-).
2. C,DΪӾ,C-D,ΪCݦD,ҽ滻ʹCD.
CΪDջ,Ӧ,DΪCػ,ΪCһ.CΪDջ,ΪC>D,CݦDDC.ӾEɵԼΪLc(E),Lc(E)={FEݦF}.Ӿ伯SɵԼΪLc(S),Lc(S)=Lc(E).UӾ伯,ULc(u),uUջUջu,uݦu,uΪUСһջ,ΪLGG(U).ڿֵĳ,Ӿʹù.Ƶ,CݦDҽLGG({C})ݦLGG({D}),γΪCD.
1.2 Сһջļ
-ϵӾСһջLGGILPõջ,㷨Plotkin[2],㰴ݹ鷽ʽ.
LGG㣺
(1) LGG({s,t})=X,s=f(s1,...,sn),t=g(t1,...,tm),fg,Xмδֵ±,ں,{s,t}LGGX֮
(2) LGG({s,t})=f(LGG({s1,t1}),...,LGG({sn,tn})),s=f(s1,...,sn),t=f(t1,...,tn).
ּLGG㣺
(3) LGG({p(s1,...,sn),p(t1,...,tn)})=p(LGG{s1,t1}),...,LGG({sn,tn})),pΪnԪνʣ
(4) LGG({p(s1,...,sn),q(t1,...,tm)})=޶,p,qΪͬ.
ӾLGG㣺
(5) LGG({C})=C
(6) LGG({C1,C2})={ll1(C1,l2C2,l=LGG({l1,l2},LGG({l1,l2}ж)}
(7) LGG({C1,...,Cn})=LGG({C1,LGG(C2,...,Cn)}).
1:C1={p(a)q(a),q(f(a))},C2={p(b)q(f(b))}.
LGG({C1,C2})={p(X)q(Y),q(f(X))}C1C2һLGGC={p(X)q(f(X))},ڦ-ϵ,CCȼ,ΪCݦCCݦ C.
2ջ
Сһջڦ-ϵ¶,߼̺¶,Ϊڼ,߼̺µСһջźܴ,-µСһջ߼̺Ҫ׵ö.,LGGԴŹջ.
2:ӵ߼ǵ͵ILPѧϰ.ʾE={{app([],[],[])}, {app([b],[a],[b,a])},{app([a],[],[a])},{app([],[a],[a])}, {app([a,b],[c,d],[a,b,c,d])}}.LGG㷨,õLGG(S)={app(X,Y,Z)}.Ȼ,{app(X,Y,Z)}Ϊɽ,򼸺,Ϊapp(X,Y,Z)һ,Ըǹappһ.
Sʵ,ٽLGGջ,õ
LGG({{app([],[],[])},{app([],[a],[a])}})={app([],X,X)};
LGG({{app([b],[a],[b,a])},{app([a],[],[a])},{app([a,b],[c,d],[a,b,c,d])}})={app([AX],Y,[AX])}.
ջۺɸS,һɽѽӽȷıӱ,ǱĵĶؼСһջ.
жջıҪ.֮ջ(LGG),ջؽջ̶,ڵõĹɽ.йضջʽ,Ƚ-ƹ㵽Ӿ伯.S,SΪӾ伯.
3. S G-S,ΪSGS,ҽDS,CS滻,ʹCD,SS䶼Ӿ伯.
1. S,SΪӼ,SGS䵱ҽSݦS.
2. SGS,SS.
,SΪSջ.ĽSΪkӾ伯,SkӾ乹ɵļ.
4. kӾ伯SΪSkؼСһջ(k-minimum general generalization,k-MGG),Ϊk-MGG(S),ҽ
(1) SGS;
(2) kӾ伯T,TGSSGT,TGS.
3. SΪkӾ伯,k-MGG(S)=S.
,ڶջֻҪջӾĻ,ջ̶ڡGȹϵ¾Ϳɽ,.ջԽڴ.Ȼ,k-MGG(S)=SĽƽ.ʵ,ѧϰĹɽۼҪʵ,ҪһϢѹ.kҪȡһΧ֮.
4. kؼСһջΨһ.
3: S={{p(a,a)},{p(a,b)},{p(b,b)}},SĶؼСһջ3
(1) S1={p(X,X),p(a,b)};
(2) S2={p(a,a),p(Y,b)};
(3) S3={p(a,Z),p(b,b)}.
,Ӿ伯ͨûжСһջ.
CSʾӾȫ,ȼ۹ϵԶΪCD,ҽCGDDGC.CS/ΪɹϵԹɵ̼,[C]CS/ΪӾCĵȼ,GCSϵƫϵ.ILPеĹɲΪȷӾGȹϵĴ.
1. GΪCS/ϵƫϵ.
֤:(1) [C]CS/,ȡ滻={},CC,[C]G[C]
(2) [C],[D]CS/,[C]G[D][D]G[C],ɡԵĶ,[C][D]
(3) [C],[D],[E]CS/,[C]G[D][D]G[E],eE,dD,ʹde,ҶdD,cCȡ,ʹcȡd.ȡd=d,(cȡ)e.,[C]G[E].,(CS/,G)ƫ.
ƫG,S,k-MGG(S)LGG(S)ϵ.
2. LGG(S)Gk-MGG(S)GS.
֤:ֻ֤ǰ벿,벿k-MGGĶֱӵõ.Ȼ,ӾCk-MGG(S),ʹö滻,LGG(S)C.k-MGG(S)C滻(k-MGG(S)-{C}){C},C=CLGG(S),滻γkӾ伯T.ע⵽CGCCGC,CΪCջ.,LGG(S)Gk-MGG(S)>GT.,Ck-MGG(S)滻,ʹCe,Ӧ,CT,C=CC= CLGG(S),ǰCe,ֻעLGGĶ,滻ȡʹLGG(S)ȡe,,CȦȡe.,TΪSջ,TGS.k-MGG(S)ļСì.
,ϵGȱȡݦȸǿ,ؼСһջܱСһջõؽͽ۵һԳ̶,ջĺҲڴ˵.
5. LGG(S)=1-MGG(S).
k-MGGҲΪСһջ.
3 ջʽؼСһջ
оӾ伯ϵһҪʡ,һνջʽĻ,ջʽؼСһջйϵ.ֹϵɽڶؼСһջѧϰ㷨.
5. CSڼϰн,ҽLc(D)(g),gGʹLc(D)Lc(g).DCS,GCS.
CSϵĽǼk-MGGĻ.
6. tĲݹ鶨£
(1) tΪ1,tΪ
(2) tΪn+1,t=f(t1,...,tn),n=Max({t1Ĳ,...,tnĲ}).
1. >k>0,CSڼϰн.ЦǹCSĺż.
֤: Lc(D)(g).=m,={f1,...,fm},DӾ,G={g1,...,gk}CS.ʩDĲ.ɻʼDΪ1,DΪ.
(1) DΪ,Lc(D)={D}(g).Ȼ,gG,ʹDLc(g)
(2) ,DһΪ,ֻһΪX,Lc(D)=Lc({{D{X/f1}},...,{D{X/fm}}),{X/fi}Ϊ滻.иһʽ.ڸfiͬ,ɽfiɳ.(1),ԸD{X/fi}һgiG滻i,ʹgiiD{X/fi}.Ϊm>k,ɳԭ,һgGD,ֱΪD{X/fi}D{X/fj},D{X/fi}Lc(g),D{X/fj}Lc(g).fifj,gжӦܸfifjΪ.,ͨĸֿ滻,gܸD,D{X/fi}Lc(g).Lc(D)={D{X/f1}),...,(D{X/fm})Lc(g).
ɼ裺DĲΪnʱ,۳.֤DĲΪn+1ʱ,Գ.DֻһΪn+1,ʾtɲΪnt乹,ǽtλΪiı֮f(t1,...,tn),fʦ,t1,...,tnΪ.
(3) t1,...,tnΪ,f=f(t1,...,tn)Ϊһµĳ릲УıLc(D)ȵݣ,ͬʱtΪ.,DΪnң=m+1>k,ɹɼ,۳
(4) t1,...,tn֮һΪ,t1ΪΨһ.t1ֱ滻fi,ki1,γӦDi,kffi,t2,...,tn)Ϊµĳ릲.,DiΪnң=m+k>k.Lc(D)=Lc({D1},...,{Dm})=Lc{D1}...Lc {Dm}.i,1im,Lc{Di}(g),ɹɼ,gG,ʹLc{Di}Lc(g).Ӧóԭ(2)ķ,õ.
Ǿٶ>k,ΪһٶILPѧϰʵ.
7. Ӿ伯S,T.SΪTջʽ,ҽCS,C=LGG(T-Lc(S-{C})).
ջʽһ˵ջ۵ļС,һָջеĸӾԸʾĶ.
3. S,TӾ伯,S=k,TLc(S),STkؼСһջҽSTջʽ.
֤:Ҫ.STջʽ.Ȼ,CS,ʹCLGG(T-Lc(S-{C})).C0=LGG(T-Lc(S-{C})),C0С,Lc(C0)TLc(C)TLc(C)TLc(C0)T.,ǰߵTLc(S),TLc(S)ìܣߵTLc(S),SļСì.
.STkؼСһջ.Ȼ,kӾ伯S,ʹTLc(S),SGS,SGS,S>S.,TLc(S)Lc (S).
(1) S<S,1,,CS,ʹLc(C)Lc (C).ȡӾ伯S={CCS,CSʹLc(C)Lc(C)},S=S.ɴ,T(S),S帲TΪSӼ.ȡC(S-S),T-Lc(S-{C})=.,LGG(T-Lc(S-{C}))C,STջʽ
(2) S=S,1,,CS,ʹLc(C)Lc(C).ɼS>S֪,شCS,CS,ʹLc(C)Lc (C).Ȼ,Lc(S-{C})Lc(S-{C}).,T-Lc(S-{C})T-Lc(S-{C}),,ΪTLc(S),T-Lc(S-{C})Lc(C).ͬ,T-Lc(S-{C})Lc(C).,T-Lc(S-{C})T-Lc(S-{C})Lc(C)Lc(C).ɴ,CLGG(T-Lc(S-{C})),SΪջʽì.
ָ,ҪkؼСһջ,ֻ轫ʾTʵk໮,γkӼ,ٶÿӼLGG,kLGGγɸTջʽ,ҲTkؼСһջ.,kؼСһջתΪʾĺk໮.
4 ؼСһջ㷨
ɵ3ۿ֪,kؼСһջĹؼǽкk໮.Ȼ,͹ѧϰ,ǽ֪ѧϰʾ,Ŀ֪ʶ֪,ڵõֵı׼.,ɽ۵ʵ.ɽ۵һԱ䷴ӳʾľ,ÿһʾĿһӸ,ӦʾеһӼ.ɴ,ǿļٶɽ۾оµ.ݴ,ĻڶؼСһջѧϰ㷨Ļ˼·ǣȶʾEʵľࣨkࣩ,γEһk໮,ȻEеĸӼLGG,γkӾ伯ΪkؼСһջĽ.
Ϊи,붨һԲ,ֲӦ׼ȷӳʾԻ.Ϊ,һLGGĶ,ѷ,LGG(E)ʵʲ׽ʾĹṹ,ӳʾĹ.,ɽLGGΪԪؼԵĻ׼.ԵĶǲ.ڸӾCD,ǵĲҪ¼棺ּͬӦλĲ졢ӾĲ졢ͬĲԼӾбƵĲ(ڴ,ָһӾг.ӾP(X)Q(X),XƵ,XӾP(X)Q(Y)ǲƵ.бڱȫԼ).4ֲ,ӾĺDif.
ȶӾ䣨ȵĸ,ȵĲͬһӾӰ첻ͬ.һ,λԽС,ӰԽ.
8. XΪһ,tcΪӾ.Xtcеd(X,tc)ݹ鶨Ϊ
(1) d(X,tc)=0,tcXͬı
(2) d(X,tc)=,tcXͬı
(3) d(X,tc)=1+min{d(X,ti)tc=f(t1,...,tn),1in}
(4) d(X,tc)=1+min{d(X,ti)tc=()P(t1,...,tn),1in,tcΪ}
(5) d(X,{})=ޣ
(6) d(X,tc)=1+min{d(X,li)tc={l1,...,ln},1in,tcΪӾ}.
,XC={Even(s(X))Odd(X)}еΪ1,XC={Even(s(s(X)))Odd(s(X))}Ϊ2.Ե,ڦ-,XCҪXC.
9. C,DΪӾ,CDĲDifΪ

+k(C-LGG({C,D})1+D-LGG({C,D})2).
Ц12Ϊ滻,ʹLGG({C,D})1CLGG({C,D})2D,X/tʾ滻еһ,EʾӾEָ,kkɵ,ȷȨ.
Dif,1CD빫ṹLGG({C,D})Ĳ,ҲƱԪĲ,ֲҪ滻12ĸϣ2(C-LGG({C,D})1+D-LGG({C,D})2)CD빫ṹLGG({C,D})Ĳ벻ͬĲ.
6. (1) Dif(C,C)=0(2) Dif(C,D)=,LGG({C,D})={}.
DifڸĶؼСһջ㷨CMGG.
(1) Ӿ伯T={C1,...,Cn},k
(2) ѭֱTk do
(3) ȡC,DT,CD,ʹDif(C,D)=min{Dif(A,B)AT,BT,AB};
(4) AT,LGG({C,D})ݦA,T=T-{A};
(5) T=TLGG({C,D});
(6)  T.kؼСһջ.
7. 㷨CMGGӾ伯ϵĶؼСһջ.
㷨CMGGڽо.˵㷨ִй,ȡk=k=1.
4:T={{app([],[],[])},{app([b],[a],[b,a])},{app([a],[],[a])}, {app([],[a],[a])}, {app([a,b],[c,d],[a,b,c,d])}}.EĶؼСһջ.
(1) ״ѭ,{app([],[],[])}{app([],[a],[a])}Ϊ,Dif(app([],[],[]),app([],[a],[a]))=2,γT={{app([b],[a],[b,a])},{app([a],[],[a])},{app([a,b],[c,d],[a,b,c,d])},{app([],X,X)}};
(2) ѭ,{app([b],[a],[b,a])}{app([a,b],[c,d],[a,b,c,d])}Ϊ,Dif(app([b],[a],[b,a]),app([a,b],[c,d],[a,b,c,d]))=5,γT={{app([AB],C,[AD])},{app([],X,X)}}.
㷨ЧصõTĶؼСһջ{{app([AB],C,[AD])},{app([],X,X)}}.ע⵽״ѭ,{app([],[],[])}{app([a],[],[a])}Ҳһ,ǵLGG{app(X,[],X)},γһֶؼСһջ.
㷨CMGGڽоʱ,ʱҲɹջĽ.㷨ĵ(3)ٿLGGʾĸ,һܵõϺõĴ.㷨ĵ(3)ΪȡC,DT,CD,ʹDif(C,D)+Cov(LGG({C,D}))=min,Cov(LGG({C,D}))={eeT,eLc(LGG({C,D}))},ۺϿӾLGG۵ջ̶.
4õĹɽ{app([AB],C,[AD]),app([],X,X)}Ѿǳӽȷıӱ.ע⵽㷨CMGGõÿһֹɽʵʶһʾĽṹ,app([],X,X)ʾapp1ԪΪ[],2Ԫ3Ԫͬʾ,app([AB],C,[AD])ʾapp1Ԫ3ԪͷԪͬʾ.ЩṹܹЧز൱һЩȷɽ,رǵλӾ.4Ľṹܹ׵عһձ{app([],X,X),app([AB],C,[AD])app(B,C,D)}.
5:Ȼ˷ʾE={{mul(0,1,0)},{mul(0,2,0)},{mul(1,1,1)},{mul(1,2,2)},{mul(1,4,4)},{mul(2,2,4)dec(2,1),mul(1,2,),plus(2,2,4)},{mul(3,1,3)dec(3,2),mul(2,1,2),plus(2,1,3)}}.ȡk=3.
(1) 㷨γ{{mul(0,1,0)},{mul(0,2,0)}}ľmul(0,A,0)
(2) 㷨γ{{mul(1,1,1)},{mul(1,2,2)},{mul(1,4,4)}}ľmul(1,B,B).
LGG(C,D)۵ջ̶,һνmul(0,A,0)mul(0,B,B)о,mul(X,Y,Z),LGGʽһ.ڿLGG(C,D)۵ջ̶غ,
(3) 㷨{{mul(2,2,4)dec(2,1),mul(1,2),plus(2,2,4)},{mul(3,1,3)dec(3,2),mul(2,1,2),plus(2,1,3)}}о,γmul(C,D,E)dec(D,F),mul(F,D,G),plus(G,D,E).
EȡȻ˷߼{mul(0,A,0).mul(0,B,B).mul(C,D,E)dec(D,F),mul(F,D,G),plus(G,D,E).}ĻӼ.Ŀǿ㷨CMGGջ.Eȡʾһ֡[7],ʾ˽йʾ,ڡϽжؼСһջȡ.㷨һʾ˶ջѧϰ,Ȼplus(+),lesseg(),.
5  
Ӿ伯ϵĶؼСһջǶСһջɵֱƹ.֤˶ջܹЧ͹ɽ۵һԳ̶,ӶʹؼСһջΪһʺϵĹɷ.Ȼ,֤Ӿ伯ϵkؼСһջȼڸüϵkջʽ.ɴ,ͨӾDif,һֻڸ෽ĶؼСһջ㷨CMGG.ʵ,㷨׼ȷγĶؼСһջɽ.
оõ863߿ƼĿ.Ҷ,1960,ʿ,ҪоΪѧϰ,˹߼,רϵͳ.,1962,ʿ,,ʿʦ,ҪоΪ,ֲʽݿ.
ͨѶϵ:Ҷ,150001,ҵѧѧ빤ϵרϵͳо
ߵλҵѧѧ빤ϵ150001
E-mail: yf@mlg.hit.edu.cn
ο
1Muggleton S, Raedt L D. Inductive logic programming: theory and method. Journal of Logic Programming, 1994,19(20):629679
2Plotkin G G. A note on inductive generalization.In: Meltzer B, Michie D eds. Machine Intelligence. Edinburgh University Press, 1970,(5):153163
3Dzeroski S. Inductive logic programming and knowledge discovery in databases. In: Fayyad U M, Shapiro G, Smyth P et al eds. Advances in Knowledge Discovery and Data Mining. Cambridge, CA: AAAI Press, 1996.117152
4Wrobel S. First order theory refinement. In: DeReadt L ed. Advances in Inductive Logic Programming. Amsterdam: IOS Press, 1996.1433
5Patrick R J, Nienhuys-Cheng S. Existence and nonexistence of complete refinement operators. In: Bergadano F, Raedt L D eds. Proceedings of the 7th European Conference on Machine Learning. Lecture Notes in Artificial Intelligence. Berlin: Springer Verlag, 1994.307322
6Arimura H, Shinohara T, Otsuki S et al. A generalization of the least general generalization. In: Furukwa K, Michie D, Muggleton S eds. Machine Intelligence. Oxford: Clarendon Press, 1994,(13):5985
7Ling C X. Logic program synthesis from good examples. In: Muggleton S ed. Inductive Logic Programming. London: Academic Press, 1992.113127
1998-05-29յԭ 
1998-08-25յ޸ĸ
