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



ڴֱݷֲĹЧ㷨
ŷΪ񡡲
ժҪ·KDDоеĹ㷨ƵĿԷ,һµĻڴֱݷֲĹ㷨.㷨踴ӵHashݽṹ,ݿα,Ӷȷʵ,Ч.
ؼʡ,ƵĿ,ȼ.
ͼšTP311
An Efficient Algorithm for Discovering Association 
Rules Based on Vertical Data Layout
OU-YANG Wei-min1CAI Qing-sheng2
1(Computing Center Anhui University Hefei 230039)
2(Department of Computer Science University of Science and Technology of China Hefei 230027)
AbstractIn this paper, the authors analyze the methods to generate and test frequent itemsets in existing algorithms in KDD research, and put forward a new efficient algorithm for discovering association rules based on vertical data layout. This algorithm has no need of Hash data structure and makes only two databases scans. As a result, the algorithm not only facilitates the implementation, but also improves the efficiency.
Key wordsAssociation rule, frequent itemsets, equivalence class.
R.Agrawal[1,2]KDDоһҪ.ʽ壺I={i1,i2,...,im}ΪĿ,DΪݿ,ÿTһĿӼ(TI),һΨһĹ˿ͱʶTID.˵TĿX,XT.XY߼̺ʽ,XT,XY=.ݿs%XY,ô,˵XY֧ΪsݿаXc%ͬʱҲY,ô,˵XYΪc.
[27]ֱ˶ֹ㷨,R.AgrawalApriori㷨[2].㷨ҪȱҪݿα,Ӷ½ϴI/O.,Щ㷨ʹHashݽṹ,άҪӶĸ.Partition㷨[7]Ȼֻݿα,Żֿ,ֲƵҲӦ.DIC(dynamic itemset counting)㷨[6]һαжԳȲͬĿм,ӶÿαЧ.ʵ,ȻҪHashݽṹ.ǵĿǣ㷨ҪЧʵҪ.Ϊ,˵ȼ,ݿݷֲͨˮƽʽΪֱʽ,ӶڴֱݷֲĹ㷨.
ĵ1Ŀ༼ȼ.2ݵķֲʽ.3ڴֱݷֲĹЧ㷨.4ʵ.ܽȫ.
1 Ŀ
켯{A,B,C,D,E},ӼɵӼռͼ1ʾ.ע,Ӧпռ.Ƶʵ߿ʾ,Ƶ(ĳƵ,κƵӼ)Դʵ߿ʾ,Ƶ߿ʾ.ĳƵӼƵ,еƵγһ߽,ͼ1еĴʾ,߽֮Ƶ,߽֮ǷƵ.Ȼ,ѵĹ㷨ӦɲƵ,κηƵɲ.˵,㷨ӦЧȷƵ߽Ľṹ.˵,ƵӼռ߽ṹһ.ЩӿռҲͼ1ʾ.

ͼ1Ŀ
һ,޷Ԥ֪Ƶ,,ǿ跨õСġƵĳ.Ϊ,ȼĿо.Apriori㷨еĺѡɷ.kαĺѡCkͨƵ(k-1)-ĿLk-1õ.,Ck={x=p[1]p[2]...p[k-1]q[k-1]},p,qLk-1,p[1:k-2]=q[1:k-2].Ϊ,һҪĿиĿ֮䱣ĳƫϵ,ǲͨĸ.,p[k-1]<q[k-1].x[i]ʾĿxĵiĿ,x[i:j]ʾĿxеĴӵijĿ.ͼ1֪,L2={AB,AC,AD,BC,BD,CD,CE,DE},ôC3={ABC,ABD,ACD,BCD,CDE}.ǰǰk-2Ŀ(Ϊ(k-2)-ǰ׺)ǷͬLk-1еȼ໮,ͬ(k-2)-ǰ׺Ŀͬһȼ,
Pa=[a]={x[k-1]L1|a[1:k-2]=x[1:k-2]}.
,ѡk-ĿͨͬһȼееԪض,ȻʶΪӽǰ׺ַ.еL2,ǵõµȼࣺPA=[A]={B,C,D},PB=[B]={C,D},PC=[C]={D,E},PD=[D]={E}.ɵȼ[A][B][C]ɵļϷֱΪ{ABC,ABD,ACD},{BCD},{CDE}.3ϱ˴˶.ڽ1Ԫصĵȼ಻ܲµĺѡ,ԲٽһԿ.
ע,ʵʵʱ,ȼɿںѡɵͬʱй.䷽£
Input: Ck={x1,x2,...,xn},иĿֵ,Ck[i]ʾѡCkеĵiĿ,|Ck|ʾѡCkĿĸ
Output: Lk+1ĵȼࣻ
Begin
(1)for i=1 to |Ck| do {
(2)[Ck[i]]=; /* ȼ[Ck[i]]ʼΪռ */
(3)for j=i+1 to |Ck| do {
(4)C=Ck[i][1]Ck[i][2]...Ck[i][k]Ck[j][k]; /* ѡ,2 */
(5)if C.supportminsup then[Ck[i]]=[Ck[i]]{C};
(6)}
(7)}
End
㷨еĺѡɷApriori㷨еĺѡɷŵ.,ǰ߲ҪκαȽ,ֱӽƴӼɣȴҪжpqǰk-1ĿǷͬ.Ȼ,ǰ߸Ϊ㡢.,ǰںѡɺû޼,е.һ,Ƿǰߵĺѡںߵĺѡ,ҪԸĺѡּ֧,ӶЧ½أشǷ񶨵.ʵ,ߵĺѡȵ,ֻ߾޼ѡ.Ҫ,һĻڴֱݷֲԵĺѡӷ,ĳѡһ,֧֪,ֱжǷƵ.,ûбҪںѡɺٽ޼.3ŵ,ȼ,ǿԶڸȼзֱƵĿķ,㷨Ĳл.
㷨κм䲽,ȷƵLk(k2)Ժ,ǾͿԴLkǱڵƵ.ע,ڪk=1,ĿΪǱƵ.Ȼ,k2,ǱԵõϾȷĹĿ֮ϵ֪ʶ.kֵԽ,Խȷ.ÿȼһǱڵƵ.,ӵȼ[A][C],տԷֱõƵABCDCDE.
2ݷֲ
KDDϵͳĴɲ.һͨԼ۽ݳ뷢صĿݼ.Ϊ˱ݹԼӳ,ݿĽһ㻹ҪĳЩݱ任ҪϢɾȱ(missing data)Ĳ.,ûȷݷѡʵ㷨.ȻǶѷֵģʽ֪ʶۡ͵.Ԥ׶εһҪݼݵıֲʽ.,ǼҪݷֲֲַʽˮƽֲ봹ֱֲ.
2.1 ˮƽݷֲ
ˮƽݷֲһֳķʽ.,ݼһϵ񹹳.ÿһʶTIDԼӦĿ(Ŀ).ʹָʽ,㸺Ҫּ֧.ƽLĿ,ڵkѭڼ,ǱɲԸk-ԪӼ,ǷںѡCk.Ϊ˿ٵؽӼ,һ㶼øӵHashݽṹ洢ѡ.Hashݽṹά,Ӷ˶ļ㸺.,ݵˮƽֲʹÿѭݿÿֲ.
2.2ֱֲ
ݵĴֱֲָ,ݼһϵĿ,ÿһĿӦTID,Ŀıʶ,Ұֵ.ֱֲˮƽֲ,ԭҪǣ
(1) ΪTID洢,Ժѡk-Ŀֿ֧ͨ򵥵(k-1)-Ӽõ,ҪӵHashݽṹ,ݿб.ǲĳһk-Ӽ,ҲҪHashݽṹά.

ͼ2ݷֲ
(2) TIDаеĹĳĿϢ,ֱֲ˾пɱػŵ.ƵĿļÿһж.,ͼ2,ͼԱˮƽֲ봹ֱֲ.Ϊ򵥼,ͼжԿֵԪҲ˱ʾ.ACTIDзֱΪA.tids={1,3},C.tids={1,2,3,5,6}.,Tidеӽͬʱһα,ɵõACTIDAC.tids={1,3}.ֻҪTIDм򵥵ԪظͿȷӦĿ֧.ʵ,ɹоͿԽּ֧,º,ӶʡȥAC.tidsһα.֧,㽫ƵĿL2֮.
,TIDе㷨
Algorithm join of two candidates;
Input: two candidate L-itemsets X and Y, and their ctid-list X.tids and Y.tids;
Output: new candidate (L+1)-itemset C and its tid-list;
Begin
(1)C=X[1]X[2]...X[L]Y[L];
(2) C.support=0;
(3) i=1;j=1;k=0;
(4) while i|X| and j|Y| do {
(5) if X.tids[i]==Y.tids[j]then {
(6) k++; C.support++;
 (7) C.tids[k]=X.tids[i];
(8) }
(9) else if X.tids[i]<Y.tids[j]then i++;
(10)else j++;
(11)}
End
֧ͨ,ԸִTID֮.,Ǽٶ֧Ϊ100,ӵĿABAC,ֱַ֧Ϊ119200.һABг20ʧ,ǾͿֹ,ΪABC֧󲻿ܳ119,20ʧ,,ֿ֧϶100.Żʽ,ǿԸЧؽ.
Ȼ,ˮƽֲڲһ,ֱֲҲȱ.СĿļ,ֱֲĴҪˮƽֲĴ,ΪСĿTIDûжĿĹϵṩõϢ,ر1-Ŀ,TIDо͸ûϢ.Ϊ,Ƶ1-ĿƵ2-ĿļʱԲˮƽݷֲʽ,Ƶ2-ĿļʱÿƵ2-ĿTID,Ȼ,Ƶk-Ŀ(k3)ļйĿTIDн,תôֱݷֲʽ.,ǽݿ.
3 ڴֱݷֲĹ㷨
ȸһ˵ڵĸ뷽ƵĹ,ȻӦ㷨.
:ͼ2ʾݿƵAnswer-Set.
ٶû֧Ϊ2,Answer-SetΪ.,ǻˮƽݷֲʽƵ1-ĿF1Ƶ2-ĿF2.Ŀɺѡ1-ĿC1,C1={A,B,C,D,E,F}.ݿһ,ѡ֧,ȡֲ֧2кѡƵ1-ĿF1={A,B,C,E,F}.ŰϽͬʱȼĺѡɷ,F1ɺѡ2-ĿмC2.,[A]={B,C,E,F},[B]={C,E,F},[C]={E,F},[E]={F},C2={AB,AC,AE,AF}{BC,BE,BF}{CE,CF}{EF}.
ٴαݿ,ѡ֧,ѡTID.ȼɾֵ֧2Ԫ,õ[A]={C},[B]={C,E,F},[C]={E,F},[E]={F},ӶƵ2-ĿF2={AC,BC,BE,BF,CE,CF}.
Ȼ,ôֱݷֲʽ,йĿTIDƵk-Ŀ(k3)ļ.θݸȼ,ֱƵk-Ŀ(k3)ķ.
(1) Ϊȼ[A]={C}һԪ,޷õƵĿ,ؽһ.,Answer-Set=Answer-Set{AC}.
(2) ȼ[B]={C,E,F}.еԪض,õѡ2-ĿеĸȼиѡTID:[BC]={E,F},BCE.tids={2,3,5,6},BCF.tids={5,6};[BE]={F},BEF.tids={5,6}.
(2.1) ȼ[BC]={E,F}.ѡ֧־2,ʼԪض,õһѡ3-Ŀеĵȼ[BCE]={F},BCEF.tids={5,6}.ڸõȼֻ1Ԫ,вõƵĿ,ٶһԿ.,BCEFΪһƵĿ,Answer-Set=Answer-Set{BCEF}.
(2.2) ڵȼ[BE]={F}ֻһԪ,ԲƵĿ,ٶһ.,BEFBCEF,ԲΪƵĿ.
(3) ȼ[C]={E,F}.ԪضԵõһѡ2-Ŀеĵȼ༰TIDУ[CE]={F},CEF.tids={5,6}.ڸõȼֻһԪ,Բٶһ.BCEBCEF,ԲΪƵĿ.
(4) ͬ,ȼ[E]={F},ҲûвµƵĿ.
,еȼ࿼,ƵĿķֹ̱.,ǸƵĿ㷨FID
Algorithm: ƵĿ㷨FID
Input:(1) DBΪR={I1,I2,...,Im}֮ϵĳϵݿ,IiֵΪ{0,1}
(2) minsupΪֶ֧ȣ
Output: ֶ֧ȵƵĿAnswer-Set;
Begin
(1)C1=all items in DB, which are lexicographically sorted;
(2)for each tuple t in DB do
(3)Ct=get-subset(C1,t); /* all candidates contained in t */
(4)for each candidate cCt do c.support++;
(5)}
(6)for i=1 to |C1| do {
(7)C2=;
(8)for j=i+1 to |C1| do {
(9)C=C1[i][1]C1[i][2]...C1[i][k]C1[j][k];
 (10)C2=C2{C};
 (11)}
 (12)}
 (13)for each tuple t in R do
 (14)Ct=get-subset(C2,t); /* all candidates contained in t */
 (15)for each candidate cCt do {c.support++;c.tid-list=c.tid-listt.tid}
 (16)}
 (17)L2={c|cC2,c.supportminsup};
 (18)S=Get-equivalence-classes(L2);/* յȼĸ */
 (19)for each equivalce class E in S do
 (20)Result-Set=Result-SetBottom-Up(E);
 (21)Answer-Set=Maximum itemsets in Result-Set;
 (22)Return Answer-Set;
End.
Get-equivalence-classes(L2)
{
S=;E=L2[1];
x=L2[1][1];/* get the first element of the first frequent itemset in L2 */
for i=2 to |L2| do
if x==L2[i][1]then E=E{L2[i]};
else {S=S{E};E=L2[i];x=L2[i][1];}
Return S;}
Bottom-Up(Fk) /* Fk={I1,I2,...,Im} */
{if |Fk|=1 then {
Result-Set=Result-Setget-element-of(Fk);
Return Result-Set;
}
for i=1 to m do{
Fk+1=;
for j=i+1 to m do{
C=Join(Ii,Ij); /* μ2.1ڵJoin㷨*/
if C.supportminsup then Fk+1=Fk+1{C};
}
if Fk+1 then Result-Set=Result-SetBottom-Up(Fk+1);
Return Result-Set;
}
4ʵ
Visual FoxproڴΪ16M586΢ʵApriori㷨FID㷨,úϳݽ㷨Ƚϲ.ݿ⺬5,ÿ100ԭʼֵ.Ȳ㷨.ǽݿԪ1 000ʼ,ε10 000.֧Ϊ2%.㷨ͼ3ʾ.ɼ㷨ܾϺ,FID㷨Խ,ִʱһЩ.
,ǱȽ㷨ڲ֧ͬµܱ仯.ʱ,ݿ̶Ϊ5000Ԫ,5α仯֧,S1(2%),S2(1.5%),S3(1%),S4(0.75%)S5(0.5%).Խͼ4ʾ.Կ,֧½ʱ,ִʱ,ԭǹ.,ǻԿ,FID㷨ִʱApriori㷨Ҫ.

ͼ3ͼ4
۷ʵ֪,FID㷨ЧҪApriori㷨.
5һ
ǶеĹ㷨о,˵ȼ,ΪӶݿݷֲͨˮƽʽΪֱʽ,Ӷ˷ƵĸЧ㷨FID(frequent itemset discovery).㷨ʵַ,踴ӵHashݽṹ,ݿ.ʵFID㷨ЧҪApriori㷨.
оĽǵεĹ.ν᷽Ӧڶ(multiple level association rules)Ͷ͹(quantitative association rules)ķֵýһо.
оõȻѧ͹ҽʿ.ŷΪ,1964,ʿ,,ҪоΪKDD,ѧϰ,˹ܼӦ.,1938,,ʿʦ,ҪоΪѧϰ,֪ʶ,˹.
ͨѶϵ:ŷΪ,Ϸ230039,մѧ
ߵλŷΪ(մѧġϷʡ230039)(йѧѧϵϷʡ230027)
ο
1Agrawal R, Imielinski T, Swami A. Mining association rules between sets of items in large databases. In: Proceedings of 1993 ACM SIGMOD International Conference on Management of Data. Washington, DC, 1993. 207216
2Agrawal R, Srikant R. Fast algorithm for mining association rules. In: Proceedings of 1994 International Conference on Very Large Databases. Santiago, Chile,1994. 487499
3Agrawal R, Mannila H, Srikant R et al. Fast discovery of association rules. In: Fayyad U et al eds. Advances in Knowledge Discovery and Data Mining. New York: MIT Press, 1996. 307328
4Klemettinen M, Mannila H, Ronkainen P et al. Finding interesting rules from large sets of discovered association rules. In: Proceedings of the 3rd International Conference on Information and Knowledge Management. 1994. 401407
5Park J S, Chen M, Yu P S. An effective Hash based algorithm for mining association rules. In: Proceedings of 1995 ACM SIGMOD International Conference on Management of Data. 1995. 175186
6Brin S, Motwani R, Ullman J et al. Dynamic itemset counting and implication rules for market basket data.In: Proceedings of ACM SIGMOD Conference on Management of Data. 1997
7Savasere A, Omiecinski E, Navathe S. An efficient algorithm for mining association rules in large databases. In: Proceedings of 1995 International Conference on Very Large Databases. Zrich, Swizerland, 1995. 432444
1997-12-23յԭ 
1998-08-11յ޸ĸ
