ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



Ŀ 
ܺ
ժҪԹʽ㷨IUA(incremental updating algorithm)˷,ָڵ,һĽ㷨NEWIUA(new IUA).NEWIUA㷨Ѵڵĺͱθʱ²ƵĿԳֵ,,ڱ֤㷨ЧͬʱЧ.3ֹ򿪲ɵĲ㷨,Ը㷨˷.
ؼʡݿ,,ʽ,ƵĿ,㷨.
ͼšTP311
Data Mining and Incremental Updating on Association Rules
ZHOU Hai-yan
(Taiyuan Teachers' College Taiyuan 030001)
AbstractIn this paper, the author analyzes the incremental updating algorithm (IUA) on association rules, points out its existing problems, and presents an improved algorithm, NEWIUA (new IUA), which takes full use of already existing and the current updated new frequent itemsets, therefore the efficiency is increased besides guaranteeing the validity of the algorithm. Three parallel algorithms for data mining on association rules are presented, the analysis and discussion on each algorithm are also presented.
Key wordsData mining, association rules, incremental updating, frequent itemsets, parallel algorithm.
ݿ(data mining)ݿе֪ʶKDD(knowledge discovery in databases)ĺĲ,һִӴģݿݲֿȡصԤϢ·.˷ʶݵֵ,ǱڵĿϢ֪ʶ.ݿĿǰڹݿ⡢ݲֿϢǰصķ֮һ,˹ѧ͹ҵĹ㷺ע.оʵҶչ˸ָо.оҪĿǷչйصķۡ۹,ִ֧Ӵȡõĺ˸Ȥ֪ʶģʽ͹.
ݿɵо,ڹ򿪲ɵоչñȽϻ.ڹ򿪲ɵһҪӦ򼰹ʵеĺ[1~3]оϸ,ڴ˲.ĵ1ڸϸ.2ָIUA(incremental updating algorithm)㷨ڵ,IUA㷨Чʽ˷,һָĽ㷨.33ֹ򿪲ɵĲ㷨,Ӧķ.4ܽ.
1
Ϊʹķ,򿪲ʽ[1,2].
I={i1,i2,...,im}mͬĿļ,һݿD,ÿһTIһЩĿļ,T I.ÿһTһΨһıʶTID.IеһӼX,X T,Ǿ˵һTX.һ(association rule)һX Y̺ʽ,X,YI,XY=.Xǰ,Yǽ.
һһЩĿļϳĿ.һĿĿĸΪĿĳ,XΪĿ,XĳȩX=XĿĸ.XI,DаXĽĿΪs,sΪXֶ֧.Support(X)ʾXֶ֧,Support(X)=s.X Yֶ֧ȶΪSupport(X Y)=Support(XY),һҲ׼,ΪŶȡ(confidence),ΪConfidence(XY)=Support(XY)/Support(X).ĿDɸѡоûָСֶ֧ȺСŶȵĹ,Щֶ֧ȺͿŶȷֱССֶ֧ȺСŶ.
ĿԷֽΪ:
 ɸѡݿDоûָСֶ֧ȵĿ(itemset,IķǿӼ).Сֶ֧ȵĿΪƵĿ,֮ͳΪƵĿ.
 ƵĿеĹ.ÿһƵĿA,ҳAзǿӼa,Support(A)/support(a)>minconf,ɹa(A-a).minconfΪûָСŶ.
˵Ϊ,Ŀǰоص㼯ڵڢٸ.
2ڹʽ㷨
ڹ򿪲ɵĹ,Ϊ˷δ֪Ĺ,ûȻҪͨСֶ֧ȺСŶֵĲϵ𲽾۽ЩȤĹȥ,⽫һ̬Ľ.,ҪЧĸ㷨ûԽϿӦʱ.
ͳĹĸ⿼ǵ,ݿݲֿݷ仯ʱ,θЧؽй¶ͷ,ļ[1]ǵݿDݱֲ,ûֵ(Ҫֶָ֧)ıʱĸ.
ƪ,ڴ˶Թʽ㷨IUAϸ,[1],÷ż京ر˵,[1]ͬ.
2.1 IUA㷨ڵ
IUA㷨Apriori㷨([3])Ҫiua_gen,iua_genĵ2޼,ὫCk3L1еk- 1ĿL1 еһĿɵk-ĿL1еһĿL12 еk- 1Ŀɵk-Ŀȫ޼.¹ڸʱʹһЩƵĿԼһЩЧ򿪲ɲ.
:ݿD4νΪT1={A,B,C},T2={A,B,D},T3={A,D,E},T4={A,B,C,D}.ɵСֶ֧s=3,֮ӦƵk-Ŀ(ΪkƵĿ)ɵļϼΪLk(k=1,2,...,m1),m1ΪƵĿе󳤶,L1={{A},{B},{D}},L2={{AB},{AD}},ʱm1=2.
µСֶ֧s =2.IUA㷨йµ:
L1={{A},{B},{D}}, L1 ={{C}}, L11=L1, L12=L1, L13= , L1 =L1L1 , C21=apriori_gen(Lk-11)-Lk=apriori_gen(L11)- L2={{BD}}(˴k=2),C22=apriori_gen(L12)=.
ִiua_genC23,ִiua_genĵ1ƴӵC23={{AC},{BC},{DC}},ִiua_genĵ2޼,ȡ{AC}C23,Ϊ{A}{AC}k-1=1ԪصӼ,{A}L13=,{AC}C23бɾ,ͬ,{BC},{CD}ͨiua_gen޼C23бɾ,C23= .ǵL20={{BD}},ӶL21=L20L2={{AB},{AD},{BD}},ΪC22= ,C23= ,L22=,L23= ,ӶL2=L21L22L23={{AB},{AD}, {BD}},C31=apriori_gen(L21)- L3={{ABD}}(L3=),C32=apriori_gen(L22)= (ΪL22= ).
ִiua_gen1ƴӵC33={{ABC},{ADC},{BCD}},iua_gen޼C33= (ΪL23= ,ȡcC33,cһĿӼc cL23ӦC33нcɾ),ǵL30={{ABD}}.ӶL31=L30L3={{ABD}},L32= (ΪC32= ),L33= (C33= ),L3 =L31L32L33=L31= {{ABD}}.
,IUA㷨õݿDСֶ֧s=2µƵĿΪ{{A},{B},{C},{D},{AB}, {AD},{BD},{ABD}},ʵݿDСֶ֧s=2µƵĿΪ{{A},{B},{C},{D},{AB}, {AC},{AD},{BC},{BD},{ABD},{ABC}},IUA㷨ûаƵĿ{AC},{BC}{ABC}ɳ.
֪,IUA㷨ܽƵĿԼЧ򿪲ɳ.ʴ㷨ǹʽµЧ㷨.
2.2 IUA㷨Чʷ
1. һƵĿһǿӼضҲƵĿ.
 IUA㷨Apriori㷨һҪ1.һʿ֪,һĿi,iһj(j<k)ĿԪ,iһk-ĿԪ,IUA㷨ĵڢޡಽ([1])ѭ,ÿһiua_gen,ͨúƴӽʹһЩԲƵk-Ŀk-ĿΪѡk-ĿCk3еԪ,Ӷiua_genе޼,㷨ʱ临.
 IUA㷨ڹʱ,k-ĿĿ,ֻע⵽ѴڵƵk-ĿļLk,ûעڻ1ڱθʱ,²Ƶ(k- 1)-ĿļLk- 1 .IUA㷨жCk3ĲԼCk3ȷLk3ȫܹһ.һ,϶IUA㷨ķiua_genڵ,PIUA㷨Ҳʧȥ.
IUA㷨ķ,IUA㷨ĸĽ㷨.
2.3 ʽ㷨NEWIUA 
ݿD,һĿֶ֧ȿΪаĿĽ׵Ŀ.ɵСֶ֧Ϊs,LkΪݿDСֶ֧s¶ӦĳΪkƵĿɵļ,k=1,2,...,m1,˴m1ΪƵĿ󳤶.µСֶ֧s ,LkΪӦƵk-Ŀļ,k=1,2,...,m2,ͬ,m2ΪоСֶ֧s'ƵĿ󳤶.ÿһĿһcountֶ֧ȼ.
Сֶ֧ȷ仯ʱ,ֻ: s >s, s <s.,[1]ѵõĴ,NEWIUA㷨ֻ.
NEWIUA㷨ĻIUA㷨Apriori㷨һ,k=1,2,...,m2,ĳֲɺѡk-ĿļCk,ȻɨݿȷCkЩk-ĿƵĿ.
NEWIUA㷨봫ͳʽ㷨֮ͬҪ.
 Ϊs<s,,ԭھɵСֶ֧sµƵk-ĿµСֶ֧s Ƶk-Ŀ,ÿһɨݿDѡk-Ŀֶ֧ȼʱ,ûбҪLkеĿټһ.NEWIUA㷨ɺѡk-ĿļCkʱLkеĿ,NEWIUA㷨Ļеĵ(1)(8)͵(8)ܹһ.
 NEWIUA㷨ɺѡk-ĿļCkʱ,ѴڵƵk-ĿļLk,ע⵽,ڻ1Աθʱ²Ƶ(k- 1)-ĿļLk- 1 Գ.һNEWIUA㷨еĵ(9)(12).
IUA㷨ĸĽ㷨NEWIUA㷨Ļ.
Lk=Lk - Lk,CkΪкѡk-Ŀɵļ.
NEWIUA㷨(s <s).
(1) C1={all 1-itemsets c of I}- L1
(2) for all transactions tD do begin
(3) Ct=subset(C1,t); /* C1аڽtĺѡ1-ĿCt */
(4) for all candidates cCt do
c.count++; /* Ctкѡ1-Ŀֶ֧ȼ1 */
(5) end 
(6) L10={cC1c.count3 s }; L1 =L10L1
(7) for (k=2; Lk- 1 ٦ ; k++) do begin
(8) Ck=apriori_gen(Lk- 1 )- Lk
(9) for all itemsets cCk do /* Ck޼ */
(10) for all (k- 1)-subset s of c do 
(11) if (sLk- 1) then
(12) delete c from Ck;
(13) for all transactions tD do begin
(14) Ct=subset(Ck,t) /* Ckаڽtĺѡk-ĿCt */
(15) for all candidates cCt do
(16) c.count++; /* Ctкѡk-Ŀֶ֧ȼ1 */
(17) end
(18) Lk2 ={cCkc.conut3 s };Lk =Lk2 Lk;
(19) end
(20) Answer=kLk 
ҲԽ㷨ĵ(8)Ϊʽ:
(8)Ck =c(cLk- 1 );Ck={all k-subset c of Ck }- Lk.
NEWIUA㷨ѡ(8)(8) ҪݿDصȷ.
㷨,(1)ɺѡ1-ĿC1;(2)(5)кѡ1-Ŀֶ֧ȼ;(6)µƵ1-Ŀ;(8)кѡk-ĿļCk;(9)(12)Ck޼;(13)(17)кѡk-Ŀֶ֧ȼ;(18)µƵk-Ŀ;(20)ǽ.
3򿪲ɵĲ㷨
ݿҪս޴,㷨Чǹؼ.ΪݿɵЧ,;:һǲЧʵ㷨,һǼϵͳṹĸĽ.Ŀǰ,߸.ǲöദмģйĿ.õĶദмģ:иԵڴ,ݿDһܹĴⲿ洢.ڼ߶ȷ,ܹվͨɹվȺϵͳĽ,ϲмģǺ.
ĸ򿪲ɲ㷨Ļ˼NEWIUA㷨һ.k=1,2,...,Ȳĳֲɺѡk-ĿļCkһЩɶCk޼,ȻɨݿȷƵk-ĿļLk,kLk.
3.1 ɨݿĲ㷨
ԶСݿĿʱ,µĲ㷨й򿪲.̨P1,P2.Сֶ֧Ϊs,򿪲ɵĻ.
㷨1. 
P1ִ²:
(1) C1={ all 1-itemsets s of I }
(2) for all transactions tD do begin
(3) Ct1=subset(C1,t) /* C1аڽtĺѡ1-ĿCt1 */
(4) for all candidates cCt1 do
(5) c.count++; /* Ct1кѡ1-Ŀֶ֧ȼ1 */
(6) end
(7) L1={cC1c.counts}
(8) for (k=3;Lk- 2٦ ;k=k+2) do begin
(9) C1=c (cLk- 2)
(10) Ck={all k-itemsets s of C1 }
(11) for all itemsets cCk do /* Ck޼ */
(12) for all (k- 2)-subsets s of C
(13) if (sLk- 2) then
(14) delete c from Ck;
(15) for all transactions tD do begin
(16) Ct1=subset(Ck,t) /* Ckаڽtĺѡk-ĿCt1 */
(17) for all candidates cCt do
(18) c.count++;/* Ct1кѡk-Ŀֶ֧ȼ1 */
(19) end
(20) Lk={cCkc.count3 s}
(21) end
P2ִ²:
(1) C2={all 2-itemsets s of I}
(2) for all transactions tD do begin
(3) Ct2=subset(C2,t) /* C2аڽtĺѡ2-ĿCt2 */
(4) for all candidates cCt2 do
(5) c.count++; /* Ct2кѡ2-Ŀֶ֧ȼ1 */
(6) end
(7) L2={cC2c.count3 s}
(8) for (m=4; Lm2٦ ;m=m+2) do begin
(9) C2=c(cLm- 2)
(10) Cm={all m-itemsets s of C2}
(11) for all itemsets cCm do
(12) for all (m- 2)-subsets s of C
(13) if (sLm- 2) then
(14)delete c from Cm;
(15) for all transactions tc do begin
(16) Ct2=subset(Cm,t) /* Cmаڽtĺѡm-ĿCt2 */
(17) for all candidates cCt2 do
(18) c.count++; /* Ct2кѡm-Ŀֶ֧ȼ1 */
(19) end
(20)Lm={cCmc.count3 s}
(21) end
P1,P2Զɼ,һ̨Answer=kLk,㷨ȫ.
㷨1õķǴP1,P2ִ.P1гƵĿ,P2гżƵĿ,Ȼһ̨.
ݿDСֶ֧sƵĿĳΪm1,Apriori㷨ɨݿm1λm1+1.,ڲ㷨1,ֱ̨еɨݿ[m1/2]+1,ʲ㷨1Apriori㷨,ִЧ߽1.㷨1ҲӴ,ݿɵٶ.ڲ㷨1,ǴԽԽ,Ϊʱ,ὫܶƵĿĿӵӦĺѡĿ,Ǿνļ.,ڲò㷨1й򿪲ʱ,ӦʵѡôĿ.
3.2ֲɨݿĲ㷨
n̨P1,P2,...,Pn,ǿԲв㷨йĿ.
㷨2.
(1) ݿDȵطΪnD1,D2,...,Dn;
(2) P1I1-Ŀɺѡ1-ĿļC1;
(3) Pj(j=1,2,...,n)ɨݿDĶӦDj,ѡ1-Ŀֶ֧ȼ
;
(4) ݸļ,P1кѡ1-Ŀֶ֧ȼ,
L1;
(5) ѭ(k=2;Lk- 1٦;k++) do begin
(6) ɴP1ɺѡk-ĿļCk,Ck=apriori_gen(Lk-1);
(7) Pj(j=1,2,...,n)еɨݿDĶӦDj ,ѡk-Ŀ֧
ȼ;
(8) ݸļ,P1кѡk-Ŀֶ֧ȼ,
Lk;
(9) ѭ;
(10) P1Answer.
ע:ڲִʱɴP1ͬ.
㷨2ɨݿApriori㷨ͬ,ÿһɨݿʱ,ڸֱеɨݿһ,ʴϽ,㷨2ɨݿЧApriori㷨n.㷨2Apriori㷨Ч˽n.
Ĳ㷨2,ڵǰģмԼ߶ȷչһַǳʵúЧ㷨.ڷֲʽݿнйĿ,㷨2ҲһЧ㷨.ڲ㷨2,ɨݿԼĿֶ֧ȼִЧǷǳߵ,㷨ٵڲмģеϢյٶ.һϢոЧϵͳ,ò㷨2ݿ(ֲʽݿ)йĿǷǳЧ.
3.3 ɨݿĲ㷨
m̨,ֱΪP1,P2,P3,...,Pm.ݿDĿʱ,һ˵㷨:Pj(j=1,2,3,...,m)еִ²:
(1) Cj={all j-subsets s of I}, /* Ij-ĿɵļΪѡj-Ŀ*/
(2) ɨݿD,ѡĿֶ֧ȼ,
(3) Lj={cCjc.count s}.
дɼ,һ̨Answer=kLk,㷨.
㷨Ȼеɨһݿ⼴ɹĿ,Ǵ㷨ļǷǳ,ҪI2m- 1ǿӼֶ֧.֪IĳһĿɵļϲƵ1-Ŀ,ֻI2m- 1- 1ǿӼֶ֧,½1.ʵʵĹ򿪲ʱ,һص: mĿɵĿI,Ŀɵ1-ĿȫƵ1-Ŀ. IĿɵm-ĿƵĿ.ص,Ϊ˼ټ,²㷨.
㷨3.
(1) Pjеɨݿ,1-Ŀ{ij}ֶ֧,ݸļһ̨ȷL1,C=c(cL1)(1)һ̨L1,C=c(cL1).L1Ƶ1-ĿĿΪmp,mpm;
(2) Pj(j=1,2,...,mp- 1)ִ²:
 Cj+1={all (j+1)-subsets s of C}; /* ѡ(j+1)-Ŀ */
 ɨݿD,ѡֶ֧;
 Lj+1={cCj+1c.counts}; /* ȷƵ(j+1)-Ŀ */
(3) һAnswer=kLk.
һ,㷨3ĵ(1),ִ㷨ĵ(2),ִĺѡĿĿܺҪ2m- 1ٵö.,ڸֱеɨݿDԼѡĿֶ֧ȼʱ,½,֮㷨3ڹ򿪲ʱݿɨ,Ӷ˹򿪲ɵЧ.
ڴǳĲмģ,ݿпʱ,Ĳ㷨3һָ㷨.㷨ĳЩִõļ(ЩԲƵĿֶ֧)Ϊȡٶȵ.Իȡݿɵٶ,ڼӲȽ۵Ľ,Ҳһֺķ.
Ĳ㷨3ָĽ.(1) ʱ,ڲ㷨3,ݿ2ɨʱ,ЩѴڿ״̬,ʱЩеĴȥֵЩ㸺ɽϴĴļ.Ҫ㷨вö̬䴦ķ.(2) Ŀɱʱ,ǿԽ㷨2Ͳ㷨3,ݿΪɲ,ÿһò㷨3Ŀֶ֧ȼ.
ڱĹ򿪲ɲ㷨,ԸݱĹ㷨NEWIUAṩķ,޸ĳЧʽϸߵĹµĲ㷨.
4
ݵĲռϢը,ҪзмֵϢ֪ʶ,ﵽΪ߷Ŀ,Ϊǳ޵.ݿɷΪĿĶ.
ݿԵǴݿݲֿ,ǴӺھмֵϢ֪ʶ.,ݿٵսǼЧ,һ;ǲЧݿ㷨벢д,֮Ľϸ.Ҳ˵,ִϢļ,ҪЧĲݿ㷨Ĳ.
עͣоõȻѧ̫ԭʦרѧУл
߼飺ܺң1957,ʦ,ҪоΪݿɣϢ洢㷨ݿ
ߵλ:̫ԭʦרѧУ ̫ԭ 030001
ο
1,뽣.ʽ㷨.ѧ,1998,9(4):301306
(Feng Yu-cai, Feng Jian-lin. Incremental updating algorithms for mining 
association rules. Journal of Software, 1998,9(4):301306)
2٩,.ڴݲֿݲɾ:о.ѧ,1998,9(1):5363
(Hu Kan, Xia Shao-wei. Large data warehouse-based data mining: a survey. Journal 
of Software, 1998,9(1):5363)
3Agrawal R, Srikant R. Fast algorithms for mining association rules. In: 
Proceedings of the 20th International Conference on Very Large Databases. 
Santiago, Chile, 1994. 487499
ո:1998-08-10޸;1998-10-14
