о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ɾĸЧ㷨
¡桡
ժҪɾݲɾһҪ.жԲɾ˼򵥵Ļعˣһ˳ɾЧʵķввɾ㷨ȱ㣻һЧʽϸߵĲвɾ㷨PMARӦ㷨˱Ƚ.ʵ֤㷨PMARЧ.
ؼʡݲɾ  㷨
ͼšTP311
AN EFFICIENT PARALLEL ALGORITHM FOR MINING ASSOCIATION RULES
TIE Zhi-Xin, CHEN Qi, and YU Rui-Zhao 
(Artificial Intelligence Research Institute of Zhejiang University, Hangzhou 310027)
AbstractMining association rules is an important data mining problem. The problem of mining association rules is simply reviewed in the paper here. A method to improve efficiency of sequential mining association rules is given. The advantage and disadvantage of the existing parallel mining algorithms are analyzed. A more efficient parallel algorithm for mining association rulesPMAR is presented. Comparison with other parallel algorithms is carried out. The experiments show that PMAR is efficient.
Key wordsdata mining, association rules, parallel algorithm
1
ҵͿѧݿļʹ洢豸ĲǴ˴.ݲɾdata miningΪЧʶݿеЧġӱġǱЧõտģʽṩ˿ɿĿѧΪ˹ܺݿŵо13.
ݿзֹR. Agrawalģ4, ĿǰѳΪݲɾеһǳҪо418.һӾǡ90%ĿͻڹͬʱҲṺţֱ̡Ϊ˿ڹĳЩƷʱжṺһЩƷ.ӦҪ˿͹Ŀ¼ơƷʼķ׷ִۡ滮Ϸ.
ȶ˳ɾ㷨˼򵥵ĻعˣָǵĹ֮ͬͬʱΪڶݿкһɨʱûгǰһɨĽһķ.ȻĿǰļֲвɾ㷨ȱ㣬ݴһڶ޹share nothingϵṹĸЧɾĲ㷨PMARparallel mining association rules.
2˳ɾ
˳Ĳɾʽ£4,5ݣmͬĿɵļ.һݿDеÿһTIһĿļϣTһΨһıʶTID.TX.һ̺ʽ.ǣֶ֧sݿDs%XYŶcݿDаXcͬʱҲY.
˳ĲɾݿDҳûСֶ֧minsupСŶminconfĹ.
˳ɾԷֽΪ4,5ݣ
(1) ҳݿед.Xֶ֧support(X)СûСֶ֧minsupXΪlarge itemset.
(2) ôɹ.ÿAй.
AgrawalѾ˱ȽϺõĽڶİ취5ݣĿǰоҪڵһ.AgrawalAIS4,AprioriAprioriTid5,CumulateStratify6ݣHoutsmaSETM7,ParkDHP8,Savasere˵PARTITION9ԼHanĲɾĵȵ.ЧӰ㷨ΪApriori,DHPPARTITION.Щ㷨áڸݿDУӼǴĳһԭݿжɨ裬k(k>1)ɨǰõk-1ɨĽ(k-1Lk-1)ͨĳ㷨(ApriroriúAprirorigen5)ѡkCkȻɨȷCkÿһԪص֧ÿһɨʱkLk.
ΪЩ㷨ݿеk(k>1)ɨʱûгõk-1ݿɨĽʹúѡkCkеԪظkɨʼձΪһŶݿɨС.ʵϣΪCkLk-1ͨں㷨ɣCkеĳһԪص֧ᳬLk-1еԪ֧СһԪص֧pCkеĳһԪX(K-1)е֧Сһp(K-1)ɨ֧Ϊp.countڶݿĵk(k>1)ɨУĿǰɨΪֹ֧pΪp.ocount֧XΪX.countǿԶCk֦ X.count=p.countXǴԽCkɾLkУ Ϊݿ)X϶ǴԽCkɾ.ͿԶ̬СѡCkӶ㷨Ч.Apriori㷨ϲϼ֦ʵʹ㷨AprioriЧ20%40%11.
ڲɾУһЩȽҪŵо⣬緢ʵ(interestingness)Ĺ6,12ݣĸ£13,14ݣֵֶ15ݣвɾ16,17ݣڷֲʽݿвɾ18ݵȵ.
3вɾ
3.1ع
вɾʽ£
P1P2PnΪn̨޹ϵṹļ֮ͨ紫Ϣ⣬ԴӲ̡ڴȣȫǶ.Ǵ洢ڼPiӲϵķݿ⣬еDiܵݿΪܵΪ.вɾͨn̨ͬʱֻԼ˽ݣ̨ͨ紫޵ϢݿDBвɾ.
вɾҲ˳ɾһֽΪ⣬ֻ۵һ.
ĿǰѾĲвɾ㷨AgrawalCD(count distribution)CaD(candidate distribution)DD(data distribution)16, ParkPDM17.㷨DMA18ȻǻڷֲʽݿĲɾ㷨Ҳڲвɾ.
㷨CDٶȽϿ졢ʵ֡Ҫͬٵŵ㣬ͨͺѡȱ.㷨CaDDDPDMִЧCD16.㷨DMA˷㷨CDһЩ㣬Ҫͬ϶.
3.2ɾĲ㷨PMRA
ڽ㷨PMRA֮ǰ֮йϵļ붨.
1. Xݿе֧support countDBiаXΪXľֲ֧X.supiʾ.
2. XݿDBе֧ΪXȫ֧X.supʾ.
3. XXPiľֲ.XеԪΪkXΪֲk.
4. XX.supmin supDXȫִƴ.XеԪΪkXΪk.
5. XǾֲǴX.supimin supDiX.supmin supDXǳܵģHLʾ.HLikʾPikܼԪΪkȫ.
1. XǴkشһʹYPiǳܵ.
2. k>1kLkмľֲѡkĲӼ.ף5.1붨2֤ף18.
3. 裬.
֤. 躯ĵ(1)õĽֱΪݶ4붨5Уɺĵ(1)ùǿɵXALk.ĵ(2)ALkɾеĲԪأʹǷֱΪɾشXԪΪk-1ӼYУYزһXAHLkҲرĵ(2)ɾ..
֤.
㷨PMRAҪÿ䱾ݿDBi򱾵غѡݿCBiжɨ.ڵɨУɺѡ֧㡢֧ɳܼȲ裬£㷨1.
1 ɺѡk.ݼk-1ѭɵĳܼѭkõĺѡkݶ2,pΪX(K-1)ܼе֧Сһ.
2 ֧.ɨ豾ݿDBiѡkеÿԪXľֲ֧X..ǿԶ¼֦ɨ赽DBiĳһ¼ʱX֧ΪX.countX.count=X.ocountX֧ӣݿԺɨвؿеǷX.XǾֲk.
3 ֧.㲥ѡkȻռɼģXȫ֧X.supX.supmin supD.
4 ɳܼ.ԼУXǵԪ.
㷨1. PMAR
룺 洢ڼӲеġ Сֶ֧minsup
L=Lk
ڼִ²
for (k=1 ; ; k++)
if (k=1) then ɨݿDBiȷѡ1

endif
for all transactions tD do
for all items c do
if c.countc.ocount and  then c.count++
for all item c do
if c.countmin supDi then c.LL=1
Broadcast Ԫص֧
Receive ӼPjԪص֧ 
for all items c do
for (j=1;jn,ij;j++)
c.count += cе֧
if c.countmin supD then {c.GL=1 Lk += c}
for (j=1;jn;j++)
if c.GL=1cеLLΪ1 then  += c
if  then exit
L += Lk
endfor
вɾ㷨ЧĹؼɽСĺѡЧؼ֦ѡ.ݶ2붨3ǿ֪㷨PMARĺѡҪС㷨CDĺѡ.㷨PMARڵڣ2ļ֦㷨Ч.
4㷨Ƚ
㷨PMAR㷨CDDMAȽϣǿԵó½ۣ
1 ɶ2붨3֪㷨PMAR㷨CDСĺѡ㷨DMAĺѡͬ.
2 㷨PMARͨ㷨CDС㷨DMA࣬Ϊ㷨DMAȻѭվ18ݣpolling siteҪ㲥ճܼ.
3 㷨PMARҪͬ㷨DMA٣㷨CDͬ.


ͼ1㷨PMAR㷨CDıȽ(minsup=0.75%)


ͼ2㷨PMAR㷨CDıȽ(|D|=100K)
Ϊ֤㷨PMARܣWindows 95ϵͳ3̨166˲.3̨⣬ȫ.ݿйزף4ݡ18ͬ.ǵĲУN1000|L|2000ֱ3̨ɲݿ⣬Խͼ1ͼ2ʾ.ɲԵĽ֪㷨PMARЧģִЧʱ㷨CD10%35%.
5
ĶԲɾ˼򵥵ػعˣһ˳ɾ㷨Чʷ.ڷֲʽݿвɾоһЧʽϸߵĲ㷨PMAR.ʵ֤㷨PMARЧ.㷨PMRAҲԶƲеزɾһ6ݡģʽ19ݼʽ£13,14ݵṩ.
߼飺У19723ʿоҪоΪ˹ܡݿ⡢ݲɾ. 棬У19659ڣҪоΪ˹ܡMPR . ȣУ19379ڣʿʦҪоΪ˹ܡ֧ϵͳ.
ߵλ¡桡ȡ㽭ѧ˹оݡ310027
ο
1Chen M S et al. Data mining: An overview from database perspective. IEEE Trans on Knowledge and Data Engineering, 1996, 8(6): 866883
2Agrawal R et al. Database mining: A performance perspective. IEEE Trans on Knowledge and Data Engineering, 1993, 5(6): 914925
3Usama M Fayyad et al. Advances in knowledge discovery and Data Mining. CA: AAAI Press/The MIT Press, 1996
4Agrawal R et al. Mining association rules between sets of items in lager databases. In: Proc ACM SIGMOD Int'l Conf Management of Data, Washington, DC, 1993. 207216
5Agrawal R, Srikant R. Fast algorithms for mining association rules. In: Proc 20th Int'l Conf Very Large Databases, Santiago, Chile, 1994. 487499
6Srikant R, Agrawal R. Mining generalized association rules. In: Proc 21st International Conference on Very Large Databases, Zurich, Switzerland, 1995. 407419
7Houtsma M, Swami A. Set-oriented mining for association rules in relational databases. In: Yu P, Chen A eds. Proceedings of the International Conference on Data Engineering. Los Alamitos, CA: IEEE Computer Society Press, 1995. 2533
8Park J S, et al. Using a hash-based method with transaction trimming for mining association rules. IEEE Trans on Knowledge and Data Engineering, 1997, 9(5): 813825
9Savasere A, Omiecinski E, Navathe S. An efficient algorithm for mining association rules. In: Proc Int'l Conf Very Large Databases, Zurich, 1995. 432444
10Han J, Fu Y. Discovery of multiple-level association rules from large databases. In: Proc 21st International Conference on Very Large Databases, Zurich, Switzerland, 1995. 420431
11. ݲɾ. 㽭ѧʿ۰౨棬1998
(Tie Zhixin. The data mining technology. Report of Doctoral Discussing Class of Zhejiang University (in Chinese), 1998)
12Shapiro G P. Discovery, analysis, and presentation of strong rules. In: Shapiro Piatetsky G, Frawley W J eds. Knowledge Discovery in Database. CA: AAAI/MIT Press, 1991. 229238
13Cheung D W et al. Maintenance of discovered association rules in large databases: An incremental updating technique. In: Proceedings of the 12th International Conference on Data Engineering, New Orleans Louisiana, 1995. 106114
14, 뽣. ʽ㷨. ѧ, 1998, 9(4): 301306
(Feng Yucai, Feng Jianlin. Incremental updating algorithms for mining association rules. Journal of Software (in Chinese), 1998, 9(4): 301306)
15Srikant R, Agrawal R. Mining quantitative association rules in large relational tables. In: Proc 1996 ACM SIGMOD Int'l Conf Management Data, Montreal, Canada, 1996. 112
16Agrawal R et al. Parallel mining of association rules. IEEE Trans on Knowledge and Data Engineering, 1996, 8(6): 962969
17Park J S et al. Efficient parallel data mining for association rules. In: Proc 4th Int'l Conf Information and Knowledge Management, Baltimore, 1995
18Cheung D W et al. Efficient mining of association rules in distributed databases. IEEE Trans on Knowledge and Data Engineering, 1996, 8(6): 910921
19Agrawal R, Srikant R. Mining sequential patterns. In: Proc 11st International Conference on Data Engineering, Taipei, 1995. 314
յڣ1998-10-06
޸ڣ1999-04-21
