ѧ
JOURNAL OF SOFTWARE
1999 4 10 Vol.10 No.4 1999



ʱ䴰ڵʽ¼*
ŷΪ񡡲
ժҪ˻ʱ䴰ڵʽ¼.÷ǰֹѾõĽ,ʱ䴰,ݼн֪ʶ.
ؼʡ֪ʶ,,ʽ,ʱ䴰.
ͼšTP311
A Time-Window Based Incremental Technique for 
Updating Association Rules
OU-YANG Wei-min1 CAI Qing-sheng2
1(Computer Center Anhui University Hefei 230039)
2(Department of Computer ScienceUniversity of Science and Technology of China Hefei 230027)
Abstract A time-window based incremental technique for updating association rules is presented in this paper, which can not only re-use the results acquired in the previous discovery process, but also focus the discovery on the recent data set using time window.
Key wordsKnowledge discovery, association rule, incremental update, time-window.
ݿз֪ʶ(knowledge discovery in databases,KDD),ݷ(data mining),ǵ˹ܺݿоһҪȵ1.KDDо,ǽ϶ز֪ʶּ빤ߵо,ѷֵ֪ʶĸ¡άע2.
Rakesh AgrawalһҪKDDо3.ʵݿпԷָָʱ̬,,еĽ׼¼ʱǡԱĲݼ¼־ļȵ.ʱ̬ݵĳʹбҪ֪ʶֹпʱ.Ϊ,ڽݿı,оʱ̬ά.Ĺؼʱı仯仯,ǰѷֵĳЩܲЧ,ܴڵµЧдһȥ.ҵеĽһϽеĹ,Ϊģʽܿʱֳĳַչƻ.ַչƻԶгƻǺмֵ.ļʱ̬ĸ洢.һַǽе,ͬȥľһ,ͨĹ㷨.÷ȱҪ´Ѿ,ЧѾõĽ.һַݵĲʽظ¹,ֻܵ.Ȼ,߸ȡ,ҲǱȡķ.
Ŀǰ,ʽ¹һЩ2,4,5,δʱ,δȷʱݵ̭.,ͲӦʱ̬ĸάҪ.Ϊ,ʱ䴰ڵʽ¼.㷨ǰֹѾõĽ,ʱ䴰,ݼн֪ʶ.
1ʱ䴰ڵʽ¼
νʱ䴰ָһʱ,ڸ֮ĽݾΪǹʱ,ڵǰķֹ.,㷨ɼ,˷ֽʱЧ.㷨й򱣴һ,Щݿ⣻ʱԼĹڵǰʱ䴰ЧĹ.
ǰʱ䴰ΪCurWindow,ֹʱֱΪTstartTend,DBΪڵǰʱ䴰CurWindowеĽɵĽݿ,DΪеĽ,LΪݿDBƵĿм,sΪ֧,cΪ.ע,scΪٷ.ٶÿĿXL,֧X.support(DBаXĽ)ǿõ.
ʱTendʼTnow,ԽݿĳЩ,µĽɵļΪdb,dΪdbеĽ.ʱ䴰ΪNewWindow,ֹʱֱΪTnow(TendTstart)Tnow.,ʱTnowTstartTend֮ǰĽݲʱ䴰NewWindow,Ӧ̭.ʱTnowTstartTend֮ǰĽɵļΪretire,佻Ϊr.ǼǶԽݿºʱ䴰NewWindowеĽɵĽݿΪNewDB,ôNewDB=DBdb/retire.֧ͬs,ĳĿXʱ䴰еֲ֧s,X.supports(Ddr),ô,XNewDBоƵ.
 ʱ䴰ڵĹµĹؼڷָºʱ䴰еݿNewDBеƵĿмNewL.ע,ԭƵмLеƵXڸºݿNewDBпܲƵ,XL,XNewLȴǿܵģLеƵXڸºݿNewDBҲпܱΪƵ,XL,XNewLȴǿܵ.
²ֲ¼Ǻ.ݿDBгΪkƵĿ(ΪƵk-Ŀ)ļϼΪLk,ºݿNewDBеµƵk-ĿмΪNewLk,CkΪ㷨IWUPkѭгΪkĺѡ.,X.supportD,X.supportrX.supportdԼX.supportNֱΪĿXDB,retire,dbNewDBе֧.,TWUP㷨ĵ1ѭ,ۺ̵ĸѭ.ƪ,ȥ㷨.
1.1Ƶ1-Ŀмĸ
ƵºݿNewDBеƵ1-Ŀʱ,Ƿǳõ.
1. ĳԭƵ1-ĿXL1ڸºݿNewDBǷƵ,ҽX.supportN<s(Ddr).
ֺ֤֧Ƶ1-ĿеĶֱ֪.
2. ĳԭƵ1-ĿXL1,ĿXڸºݿNewDBƵ1-ĿеıҪX.supportds(dkr),skΪX̭ݿretireе֧.
֤ȻXL1,ôX.supportDsD.ٶX.supportds(dkr),ôX.supportN=X.supportDX.supportdsk<sDs(dkr)sk<s(Ddr).,XڸºݿNewDBоǷƵ.,2֤.
,NewDBзƵ1-ĿмNewL1ɰ²У
(1) ̭ݿretire,ĿXL1retireе֧,ΪX.supportr
(2) ݿdb,ĿXL1dbе֧,ΪX.supportd,ӶõL1ĿXڸºݿNewDBе֧,X.supportN=X.supportDX.supportdX.supportr.X.supportNĴС,X.supportNs(Ddr),1,XڸºݿNewDBоǷƵ,̭.һ˺,L1ʣµڸºݿNewDBоƵ1-Ŀ.
(3) ڶdbretireͬʱ,dbеÿһt첻L1еĺѡ1-ĿмC1,ֱѡdbretireе֧.2,C1еһĿX,X.supportds(dkr),ôXڸºݿNewDBоͱǷƵ.,ɽXC1ɾ.,ǱɶC1޼,ɾЩdbеֵ֧s(dkr)ĺѡ.
(4) ԭݿDB/retireб,C1иѡXDB/retireе֧,ӶõXڸºݿNewDBе֧X.supportN.ͨX.supportNǷ񲻵s(Ddr),ǿԴC1зµƵ1-Ŀ.ºݿNewDBеƵ1-ĿмNewL1ԭL1NewDBƵĿкC1зֵƵĿйͬ.
Apriori㷨ĵ1ѭ,TWUP㷨ȴԭƵ1-ĿL1ųڸºݿNewDBвƵĿ.˹˺,L1ʣµڸºݿNewDBоȫƵ1-Ŀ.ﵽһĿ,ݿdb̭ݿretire1α.㷨2,ԸdbĺѡC1޼,ųЩܳΪƵĿеԪ.ڶݿdb̭ݿretire1α.Ȼ,㷨ԭݿDB/retire1α,ԴC1зµƵĿ.γɶ,Apriori㷨ĿɳΪ1ĺѡ,ºݿNewDBб,ԷƵ1-ĿмNewL1.Ȼ,TWUP㷨漰ĺѡԶԶApriori㷨漰ĺѡ.
1.2Ƶk-Ŀмĸ
ƵºݿNewDBƵ2-ĿмNewL2ʱ,ʽõ.
3. ĳĿ{X1,X1,...,Xk-1}Lk-1ڵk-1ѭз,ڸºݿNewDBвƵ,{X1,X1,...,Xk-1}NewLk-1,ô,ĿеκԭƵk-ĿYLk(k2)ڸºݿNewDBоܳΪƵĿ,YNewLk.
֤ƵĿеκĿоƵ(ף3)һʿ֪.
4. ԭƵk-ĿмLkеκk-Ŀ{X1,X1,...,Xk}ڸºݿNewDBǷƵ,ҽ{X1,X1,...,Xk}.supportN<s(Ddr).
ֺ֤֧Ƶk-ĿеĶֱ֪.
5. ĳԭƵk-Ŀ{X1,X1,...,Xk}Lk,ĿXڸºݿNewDBƵk-ĿеıҪ{X1,X1,...,Xk}.supportds(dkr),skΪ{X1,X1,...,Xk}̭ݿretireе֧.
֤2.
,NewDBзƵ2-ĿмNewL2ɰ²У
(1) 3,L2ɾNewDBвƵĿ.1ѭʶĲƵĿеļΪL1-NewL1.κĿXL2,ĳĿYL1NewL1,ô,XڸºݿNewDBоͲƵ,ɽXL2ɾ.,ǱL2޼.
(2) ֱݿdb̭ݿretire1α,޼L2ÿĿXdbretireе֧X.supportdX.supportr,ӶXڸºݿNewDBе֧,X.supportN=X.supportDX.supportd-X.supportr.4,NewDB̭зƵĿ.,L2ʣµNewDBоȫƵ2-Ŀ.
(3) ǷµƵ2-Ŀ.,úѡ㷨Apriorigen3ݸNewL1ɺѡC2,ע,L2еĿѾ,ӦC2ɾL2Ŀ.Ȼ,ֱdbretire1α,ÿѡXdbretireе֧X.supportdX.supportr.ŶC2һ޼,κXC2,X.supportds(dkr),ô,5,XNewDBоͱǷƵ,˿ɽXC2ɾ.
(4) ԭݿDB/retireб,C2иѡXDB/retireе֧,ӶõXNewDBе֧X.supportN.ÿѡXC2,X.supportNs(Ddr),ôXµƵ2-Ŀ.NewDBеƵ2-ĿмNewL2ԭL2NewDBƵĿкC2зֵƵĿйͬ.
Եk(k3)ѭ,Ӧ㷨,ֱûµĺѡʱΪֹ.TWUP㷨ĵkѭ,ݿ1.ԭƵk-Ŀ,㷨ֻݿdb̭ݿretire1α,ͿɷڸºݿNewDBƵk-ĿУµƵk-Ŀ,ѡCkϴѭõNewDBеƵ(k-1)-ĿмNewLk-1,Ȼ35Ck޼.޼ĺѡCk,ҪԶԶСApriori㷨ɵĺѡ.,ڹ·,TWUP㷨ҪApriori㷨.
2С
һֻʱ䴰ڵʽά㷨.ʱ䴰ڼ,ǵ߹뵱ǰݵ,ͬʱѾõĽ,͹򼯸µĴ.TWUP㷨PC 586/166(32Mڴ)Visual FoxPro1.0ʵ,úϳݽ˲.ʵ,㷨˼ȷ,õĿ.
*оõȻѧ͹ҽίʿ.
ͨѶϵ:ŷΪ,Ϸ230039,մѧ
߼顡ŷΪ,1964,ʿ,,ҪоΪKDD,ѧϰ,˹ܼӦ.
,1938,,ʿʦ,ҪоΪѧϰ,֪ʶ,˹.
ߵλŷΪ(մѧġϷʡ230039)
ŷΪ񡡲(йѧѧϵϷʡ230027) 
ο
1ŷΪ,.ݿжԪģʽƵ.ѧ,1997,8(12):920927
(Ou-Yang Wei-min, Cai Qing-sheng. Meta-pattern guided discovery of multiple-level association rule in large databases. Journal of Software, 1997,8(12):920927)
2Cheung D W, Han J, Ng V et al. Maintenance of discovered association rules in large databases: an incremental updating technique. In: Proceedings of 1996 International Conference on Data Engineering. 1996. http: //www.cs.hku.hk/dcheung
3Agrwal R, Srikant R. Fast algorithm for mining association rules. In: Proceedings of the 20th Very Large DataBases Conference. 1994. 487499. http: //www.almaden.ibm.com/cs/quest
4Cheung D W, Lee S D, Kao B. A general incremental technique for updating discovered association rules. In: Proceedings of the 1997 International Conference on Databases Systems for Advanced Applications. 1997. http: //www.cs.hku.hk/dcheung
5Feldman R, Aumann Y, Amir A et al. Efficient algorithms for discovering frequent sets in incremental databases. In: Proceedings of 1997 SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery. 1997. 5966. http: //www.cs.biu.ac.il/feldman
1998-02-12յԭ,1998-04-16յ޸ĸ
