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



ݿз־ʱ̬ԼĹ
< 
ŷΪ񡡲
ժҪ Ŀǰ,ϵĹоδʱ.Ȼ,ʱʵĹ,ʵ ݿⶼʱ̬.ĿΪЧʱʱ̬Լ,ʱ չ鲢Լµʱ̬㷨,Ӷһƹ˹Ӧ.
ؼʡ֪ʶ,,ʱ̬Լ.
ͼšTP311
Discovery of Association Rules with Temporal Constraint in Datab ases
OU-YANG Wei-min1,2CAI Qing-sheng2
1Computing CenterAnhui UniversityHefei230039 
2Department of Computer ScienceUniversity of Science and Technolo gy of ChinaHefei230027
AbstractTime has not been taken into account in the current international researches of association rules. However, time is an inherent property in the real world. Ther e exists temporal semantics in many real world databases. The temporal constrain t problem called valid time is considered in this paper. Both the methods for ex tending and merging time intervals and the new discovery algorithm for temporal association rules are proposed. Thus, the application of association rules h as been further generalized.
ݿз֪ʶ(knowledge discovery in databases,KDD),Ϊݷ( data mining),ǵ˹ܺݿо.ĿΪ ûĿ,Զԭʼ,ʶҪģʽ,Ϊ֪ʶ Ա1,2.ǿӦǱԼ㷺õĴڸݿеĴ ,,KDDΪһʵҪĺǰ;ȵо1.
IBM Almaden Research CenterRakesh Agrawal1993 KDDоеһҪ2.νһ߼̺ʽ:XY, XYͬԼ.ֱۺǶݿеԪ,Xе ֵΪ,ôYеֵҲΪ.,ϵ30%ѧǰռ,ݿ2% ѧǼϵǰռ.,30%Ϊζ,2%Ϊֶ֧. ҪֵĹӦûֶָ֧ȺζԼ.ڹķ ,ĿǰɸЧ㷨3,4.
ʵ,ʱʵݿⱾе,гᷢʱ̬ .ʱ̬ݵĳʹбҪ֪ʶֹпʱ.ʵݿ Էָָʱ̬,,еĽ׼¼ʱǡԱĲݼ¼ ־ļȵ.￼ʱ̬νʱ̬Լ,ݿеÿ ԪЧʱ,ôݿֵ֪ʶҲȻӦʱ̬Լ,Ա ֵ֪ʶʱЧ.Ŀǰ,ʵ϶ǼٶԶЧ.,ûκζ ʱЧ,ʱֱΪЧ.ͬ,ĿǰЧĹҲû˵ڹȥ ǷЧ.ʵ,ĳʱ̬ԼĹ򽫿Ըõ͹ʵ,Ҳ мֵ.ʵڻϣʱ̬ԼĹ,ǳֹΪʱ̬ .
ĵ1ڸ.2ڼҪ㷨Ҫ˼.3 ʱ̬йؼ,Ӧ㷨.4ʵ.ǽһ .
1
Ϊ۵ķ,ǲùϵģ.,ֻڱķԼ޸ Ӧģ,չĹϵģ͡ģ.R={I1,I2,...,I m}һֵΪ{0,1}Լ(ҲΪĿ).֪ʶصݼr={t1,t2 ,...,tn}Ƕڹϵģʽ{I1,I2,...,Im}ϵһϵ,ԪظΪmĶԪ ļ.
ǳĳԪt֧(support)ĳA,ԪtֱӰA,AԪt ĳֵȱ,ΪtA=1.XRӼ,trǹϵĳһлԪ.ÿ AXtA=1,ôǳt֧X,tX=1.ԼXƥԪ鼯Ϊsupp ort(X)={tr|tX=1}.ϵrеĹXY,XR,YRX. ֵ(minimum confidence threshod)ֵ֧(minimum support threshod) Ϊúͦ,|support(XY)|ݦn|support(XY)|/|support(X)|ݦ,ǳƹ ϵrֵúֵ֧XY.˵,ϵrЦn ԪXYеԾΪ1,ڶԼXΪ1ԪбΪõԪԼY ҲΪ1.ԼX,|support(X)|ݦn,nΪݿеԪ,Ϊ ֵ֧,ôǳXƵ.Ҳ˵ݿбΪҵԪԼXΪ1.
ʱʵĹ,Ϣϵͳʱ̬.ǵʱ̬ νЧʱ(valid time),ĳʱ,ĳԪЧĻϷ., ھЧʱԪ鼯зֵĹҲȻͬӦЧʱ, ʱЧ.Ϊ,ڶĻЧʱԼһ,ڹ ϵģʽһЧʱvalidtime,涨ÿԪ븽Чʱvalid time.,жĳԪǷ֧ĳAʱ,AǸЧʱԼ, ,ǱжϸԪЧʱǷAЧʱƥ.ֻߵЧʱ ƥ,ſԽһǷֵ֧.Ҳ˵,ǽжĳԪǷ֧ĳA Ϊ⣺(1) ԪЧʱAЧʱǷƥ䣻(2) δЧ ʱͨԪǷ֧A.ڵ2,ǿԲκһֹ㷨 ,R.AgrawalApriori㷨еķ.1ǱҪ.
2㷨Apriori
ķֿɷΪ3ݣ
(1) Ѱֶ֧Ȳûֵָ֧.ǳΪƵ м
(2) ƵмĹ.,˵ABCDƵ ,support(ABCD)/support(AB)ûָζȦ,ôABCD .ע,ABCDƵ,ضûָ֧.
,ǼҪR.AgrawalѰƵмApriori㷨. Ը㷨Ϊ־ʱ̬ԼĹĻ.K-ΪKԵļ,Fr eKΪƵK-еļ,CKΪѡK-(ܵƵ) .Apriori㷨ݿα,ÿα׶ι.1,ϴ( K-1)õƵ(K-1)-мFreK-1ɺѡK-мCK. ѡ㷨Apriorigen3ݱ֤CKƵK-мĳ .2,ݿһα,еÿԪȷ֧CKеЩѡ,Ӧ ѡcountۼ֧.,ѡCK,ȷЩѡƵ, ƵK-мFreK.㷨,ֱFreKΪʱΪֹ.
֪Ƶ(K-1)-мFreK-1,ѡ㷨ApriorigenƵK -мĳ.úѡɵ㷨˼ǻһ۲죺Ƶеκһ ӼƵ.úѡ㷨ҲΪ
(1) (join),FreL,K-1ԼCL,K.
Insert into CL,K
Select p.item1,p.item2,...,p.itemk-1,q.itemk-1
From pFreL,K-1,qFreL,K-1
Where p.item1=q.item1,p.item2=q.item2,...,p.itemk-2=q. itemk-2,p.itemk-1<q.itemk-1,
(2) ޼(prune),ɾCL,Kеκһѡc,cдһK-1Ӽ FreK-1,Ƶ.
ѡ㷨ȷף2.
3ʱ̬ԼĹ㷨
еĹ㷨AprioriĻϽչ,Դݵʱ̬Լ ,Ӷʱ̬ķ㷨.ڱĵչݿ,ͨݿ, ԪһֵΪʱЧʱ,ʱ̬Լ.Apriori㷨, ǵ㷨õĺѡɷApriorigenͬ,֮ͬ,ݿ кѡʱ,ĿҪƥ,ߵЧʱҲɹ鲢.ǵķ һ(ûضӦȷñ)չʱ,Ȼٰղͬ ʱй鲢,ۼ֧.ע,ʱѡݽṹгĿitemsetͼ support,ҪһЧʱvalidtime,ԱʾЧʱ.
3.1ʱչ
ʱչָ˵,ʹʱܹ򽻵,Ȼ ٹ鲢Ϊͬһʱ.չʱ.һַǽʱ ˵̶ĳ,һַǰһչʱ.ǰһʱ, ޷ʱ䱾ĳ,ÿʱһ˹̶ĳ.,е չ20%,еȴչ100%.,ԭϴʱ,ԭС ʱϸϢʧϴ.ⲻ.,ǲú߰һչʱ ķ,ʹϸϢʧԲͬСʱǾ.ʱչ,ϸ Ϣʧǲɱ,øιϵƹʱϸϢҲʧһµ. 
ʱ˵ĳ̶ɱʾʱչ̶ȵƹfȷ.ƹ fֵȿ㷨Զ,Ҳڵñ㷨ʱָ.Ȼ,,ƹfֵӦ ضӦƾѡȡ.fֵԽ,ʱչԽ,ϸϢ ʧԽ֮ࣻ,fԽС,ʱչԽ,ϸϢʧԽ, ˶ҪĶչ,㷨Чʾͽ.ʱʱϵķֲϡ ,ôڹ鲢ʱ֮ǰҪϴչ.ʱʱϵķֲǳܵ ,ôʹʱչ,ҲܿϸϢѸʧ.Щȷ ƹfֵʱӦԿ.ʵ,Ȳ֪ƹfֵٲǺʵ ,,һȡ̽Եİ취.,ƹfֵ趨òҲ.Ϊ ûȤģʽ,ȻҪϵصƹfֵ.
3.2ʱĹ鲢
һĿм,üеĿеĿͬ,ԵЧʱ δͬ,ǵĿǽԹ鲢ʱֱϲ,ۼƹ鲢ͬһʱ ڱ˴ƥĿеĸ.ʱĹ鲢ɰ4ֱֻУ
(1) abͬ,ȻؿɲΪһa,˵㲻䣻
(2) a(i,j)b(m,n),j=m,һc(i,n)滻
(3) a(i,j)b(m,n),im,jmj<n,һc(i, n)滻
(4) a(i,j)b(m,n),imjn,Ϊһc(i,j).
ѡĿмĹؼʶصʱ䲻֮ͬ,Ŀ ˴ƥĿ,һʶʱ֮Ļϵ,Թ鲢, ໥ƥĿеĸ.
3.3ʱ̬ԼĹ㷨
ȸһʱ̬ԼĹķַ,ȻٸӦ 㷨.
1ʾݿ,TIDΪʶ,ItemsetΪӦĿ Ӽ,ValidtimeΪӦЧʱ,ٶƹf=1.5.ǵĿǴз־ йʱ̬Ĺ.ַRakesh AgrawalApriori㷨нʱ չ鲢.ԺѡĿм,ҪʶĿǷƥ,һҪʶӦ ʱǷԹ鲢,ɴͳƺѡĿе֧.巽£
1ݿ

TIDItemsetValidtime
100A,C,D40,70
200B,C,E60,90
300A,B,C,E90,120
400B,E30,50
500A,B,C400,500

(1) Ƶ1-Ŀмķ
ƹf=1.5ƹݿDиЧʱ,еĵĿɺѡ C1={{A},{B},{C},{D},{E}},ݿ,õѡĿ-ʱԵļϣ 
Set(A)={(A,20,105),(A,45,180),(A,200,750)}
Set(B)={(B,30,135),(B,45,180),(B,15,75),(B,200,750)}
Set(C)={(C,20,105),(C,30,135),(C,45,180),(C,200,750)
Set(D)={(D,20,105)}
Set(E)={(E,30,135),(E,45,180),(E,15,75)}
ͳƸʱɱ˴˹鲢ԪضԸ,ֵΪӦԪضԵ֧.Set(A) ԪضԿɹ鲢Ϊ(A,20,180),(A,200,750)ɹ鲢.,(A,20,180) ֧Ϊ2.Set(A)δܹ鲢ԪضԵļΪRest(A)={(A,200,750)},Ǳ Ƿɹ鲢,Rest(A)н1Ԫض,ԸԪصֻ֧1,֧,Ӧ ɾ.ͬķSet(B),Set(C),Set(D)Set(E)ɵ(B,15,180)֧Ϊ3 (C,30,180),֧Ϊ3(D,20,105),֧Ϊ1(E,30,180),֧Ϊ3.ȡֲ֧ ֧2ԪضԹƵ1-ĿмL1={(A,20,180),(B,15,180),(C ,30,180),(E,30,180)}.
(2) Ƶ2-Ŀмķ
Apriorigenѡ㷨,ɴ˿ɵѡ2-ĿмC2={AB,A C,AE,BC,BE,CE}.ݿ,õѡĿ-ʱԵļϣ
Set(AB)={(AB,45,180),(AB,200,750)}
Set(AC)={(AC,20,105),(AC,45,180),(AC,200,750)}
Set(AE)={(AE,45,180)}
Set(BC)={(BC,30,135),(BC,45,180),(BC,200,750)}
Set(BE)={(BE,30,135),(BE,45,180),(BE,15,75)}
Set(CE)={(CE,30,135),(CE,45,180)}
(1)еķͬ,ͳƸʱɱ˴˹鲢ԪضԸ,ֵΪ ӦԪضԵ֧,ȡֲ֧֧2ԪضԹƵ2-ĿмL2={(AC,20, 180),(BC,30,180),(BE,15,180),(CE,30,180)}.
(3) Ƶ3-Ŀмķ
Apriorigenѡ㷨,ɴ˿ɵѡ2-ĿмC2={BCE} ,ע,ĿABCBCƵ,޼.ݿ,õúѡĿ -ʱԵļϣSet(BCE)={(BCE,30,135),(BCE,45,180)}.֪,L3={(BCE ,30,180)}.
L3ֻ1Ԫ,ɸĺѡ,㷨̽.
,Ǹ㷨
Algorithm TCAR:ʱ̬ԼĹ㷨
Input: (1) DBΪR={I1,I2,...,Im,validtime}֮ ĳϵݿ,IiֵΪ{0,1},validtimeΪԪĺϷʱ 䣻
(2) minsup,minconffֱΪֶ֧ȡζȺƹӣ
Output: ֶ֧Ⱥζȵʱ̬.
Begin
(1)L0={1}; /* initialized the L0 */
(2)for (k=1;Lk-1٫;k++) {
(3)if (k==1) then C1=getallitem(D); /* take all items as C1 */
(4)else Ck=getcandidateset(Lk-1 ); /* as same as A priorigen */
(5)for each t transaction t in D do {
(6)if (k==1) then generalize the t.validtime with f;
(7)for each candidate cCk do 
(8)if (t.itemset matchs c) then Set(c)=Set(c){(c,t.valid time)}
(9) }
(10) for each candidate cCk do
(11) while |Set(c)|1 do {
(12) x=firstelement(Set(c));Set(c)=Set(c)-{x};
(13) while |Set(c)|1 do {
(14) y=nextelement(Set(c));Set(c)=Set(c)-{y};
(15) if y can be merged with x /* by the methods described i n 3.2 */
(16) then {x.validtime=merge(x.validtime,y.validtime );
(17) x.support++;}
(18) else Rest(c)=Rest(c){y};
(19) }
(20) if x.supportminsup then Lk=Lk{x};
(21) Set(c)=Set(c);
(22) } 
(23) }
(24) DiscoveredRuleset=K getrules(Lk,minconf);
End.
4ܲ
Ϊ˲Ͻ㷨,PC 586/166(32Mڴ)Visual FoxPro1.0ʵ˸ 㷨.ϳݵɷIBM AlmadenоRakesh Agrawal쵼KDDоС õķ(μhttp:www.almaden.ibm.com/cs/quest/syndata.html#AssocSynDa ta),ֻһЧʱ.ϳݿɲ£(1) DΪ 200(2) ĿƽСTΪ5(3) ƵĿеƽСIΪ 3(4) ݿĿĸNΪ20(5) ֧minsupΪ10%.Ϊ ,ε,500,ÿε500,6,3500,Ӧ ͼ1ʾ.ʵ,㷨ȷ,õĿ.
5һĹ
ʱʵĹ,ʵݿⶼʱ̬.Ŀǵʱ̬ νЧʱ(valid time),ĳԪĳʱЧ.,ھЧ ʱݼзֵĹҲȻͬӦЧʱ,Ҳʱ Ч.Ϊ,Rakesh AgrawalApriori㷨Ļ,ʱ չ鲢,õµܹʱ̬ԼĹ㷨.
ǵʱ̬嵥һ,ʱʱ̬Լ,һо (Ա仯)ʱ̬Լ.
лĹõ˹KDDо֪ѧ߼ôSimon Fraster ѧHan JiaweiںIBM Almaden Research CenterRakesh Agrawalڵ֧ ,Ϊṩйصо,ش˱ʾл.

оõȻѧͰʡίл.
ŷΪ ,1964,ʿ,,ҪоΪKDD,ѧϰ,˹ܼӦ.
,1938,,ʿʦ,ҪоΪѧϰ,֪ʶ,˹ .
ͨѶϵˣŷΪ,Ϸ 230039,մѧ
ߵλŷΪ񣨰մѧġϷʡ230039
ŷΪ񡡲йѧѧѧϵϷʡ230027
E-mail: oywm@mars.ahu.edu.cn
ο
[1]Piatetsky-Shapiro G. Discovery, analysis, and presentation of strong rules. In: Piatetsky-Shapiro G, Frawlay W J eds. Knowledge Discovery in Databa ses. Cambridge, MA: AAAI/MIT Press, 1991. 229238
[2]Agrawal R, Imielinski T, Swami A. Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACMSIGMOD Internationa l Conference on Management of Data. Washington, DC, 1993. 207216
[3]Agrawal R, Srikant R. Fast algorithm for mining association rules. In: Proc eedings of the 1994 International Conference on Very Large Data Bases. Santiago, Chile, 1994. 487499
[4]Mannila H, Toivonen H, Verkamo A Inkeri. Efficient algorithms for discoveri ng association rules. In: Proceedings of AAAI Work Shop Knowledge Discovery in D atabases. 1994. 181192
1997-11-20յԭ,1998-05-28յ޸ĸ
