Ӧо
APPLICATION RESERCH OF COMPUTERS
2000  Vol.17No.1P.1-5




ɾ
桡
ժҪ˹ɾоһЩͲɾ㷨˷ָۣ˹׼Ĳ㣬չ˹ɾδо
ؼʡݲɾ֪ʶ
1
ݲɾо˹˹ܺݿרѧߵĹ㷺ע[1 3]ݿвɾݲɾеһǳҪо⡣R .Agrawal[4]һӾǡ90%ĿͻڹͬʱҲṺţֱ̡Ϊ˿ڹĳЩƷʱжһЩƷӦҪ˿͹Ŀ¼ơƷʼķ׷ִۡ 滮Ϸȡ
Ĳɾʽ[4,5]
I={i1i2...im}mͬĿɵļϡһݿD ÿһTIһĿļϣTITһΨһıʶTIDXIXT TXһX(Y̺ʽXIYIXY=ա XYǣֶ֧sݿDs%XY ŶcݿDаXc%ͬʱҲY
ĲɾݿDҳûСֶ֧minsupС ŶminconfĹ
ɾԷֽΪ[4,5]
ҳݿедXֶ֧support(X)Сû Сֶ֧minsupXΪ(largeitemset)
ôɹ򡣶ÿABAB٦գSupport(A)/Support(B)m inconfйB(A-B)
ڢڸȽף㷨ɲμ[5]Ŀǰоڵһ ϡǶ㷨ĽҲڵһϡ
2о״
2.1ɾһ㲽
R.Agrawal[4]˹ĲɾⲢԭʼ AIS֮󣬸õ˹˹ܺݿѧߵйע˶ֵ еĲɾ㷨ǲʲôݽṹ临ӳ̶ȡЧΣǶԷΪ ¼衣
ԤɾйصݡݾҪݿӦĲӶ 񻯵ݿD
DСֶ֧ȵһٵ ⶼȽϴԴ˲㷨ĺġ
СŶȵĹγɹR
ܽͲR
2.2Ҫо͵㷨
R.Agrawal˹ĲɾԺ󣬸оõ˳طչĿǰ ΪֹҪоУ
(1)ѭʽĲɾ㷨
㷨AgrawalAIS[4]AprioriAprioriTidAprioriHybrid[5]Park DHP[6]Savasere˵PARTITION[7]ԼToivonenĳ㷨Sampling [8]ȵȡЧӰ㷨ΪAprioriDHPPARTITION
㷨AISУѡɨݿĹвġ˵ڶݿеk ɨʱѡ(ÿһԪصԪظһkԴk)ɵk-1ɨı߽缯(Frontierset)ͨӵǰеõͬʱѡеԪصֱ֧ĳһɨı߽缯Ϊʱֹͣ㡣Ӧעǣkɨı߽缯ҪڱɨɵĴ㷨ȱɵĺѡ̫
㷨AprioriAprioriTidáڸݿDУӼǴ ĳһԭݿжɨ裬һɨó1L1k(k>1)ɨǰõk-1ɨĽ(k-1Lk-1)ͺApriori_g en[5]ѡkCkȻɨȷCkÿһԪص֧ÿһɨ ʱkLk㷨ڵѡkCkΪʱڳõԭ 㷨ĺѡҪ㷨AISСö࣬Ӷ㷨Чʡ㷨Aprio riTidһص㣬ڵһɨʱݿDѡ֧ ɨһɨɵĺѡݿD'ѡ֧ ɨУD'ĴСҪԶԶСDСI/Oʱ䣬㷨Чʡ㷨Aprio riHybrid㷨Apriori㷨AprioriTidĽϣѡݿD'ȫ ʱ㷨AprioriڴܹȫɺѡݿD'ʱ㷨AprioriTid
㷨DHPùϣ(Hashing)ЧظĽ˺ѡɹ̣˱ǰ㷨 Сĺѡ(Դ2ѡΪ)ͬʱҲݿĴССI/O ʱ䣬Чʱ㷨Aprioriߡ
㷨PARTIONΪ֡ڵһУ㷨ȽҪзֹ DΪnཻݿD1D2...DnDi(i=1,2,...,n)ĴСҪ ܹڴ֮УȻÿһݿDi(i=1,2,...,n)ڴ沢 еĴLiڵһֽʱзݿĴϲΪһ ݿDеǱڴ㷨ڶּǱڴPLݿDе֧óL㷨ֻݿDɨΣI/OӶ㷨Чʡ
㷨Sampling˼ΪݿDõݿD'С ûСֶ֧ȵֶ֧ȷִD'дL'ʣµݿD-D'м L'иԪص֧ûСֶ֧ȼLڴ󲿷£ ô˷ȷĴʱܻ©һЩʱԶDеڶ ɨԵó©Ĵ㷨ڴ󲿷¿ֻDһɨ͵ó Dɨ裬㷨Чʽϸߡ
(2)ʽ㷨
ʽҪڸСֶ֧ȺСŶ£һ ݼdbӵɵݿDBʱdb(DBеĹ򣻢ڸ ݿDBСֶ֧ȺСŶȷ仯ʱݿDBеĹ[9]˹µĵһ⣬һ㷨Apriori[5]һµ㷨FUP[10]ԹµĵڶоƳӦ㷨IUAPIUA
㷨FUPĻ˼Ϊһk(k1)DBdbжǴһ DBdbжһDB(db)Ǵ ֧Ӧdb(DB)е֧ȷǷΪ㷨FUPDBзֵ (nΪLԪصԪظ)ѱҪDBdbжɨ裬ڵ 1ɨУ㷨ɨdbL1еԪΪdb(DBеĴԪؼL'1ɺ ѡ1C1C1еԪΪdbеĴ1ҲL1УȻɨDBԾC1еԪ ǷΪdb(DBеĴdb(DBеĴԪؼL'1Сڵk(k>1)ɨǰ ȶL'k-1Apriori_Gen()ɺѡkCkȥLkеԪأCk=Ck-Lk Lkм֦XLkYLk-1-L'k-1X϶dbDBеĴkӦLkɾȻɨdbLkеԪΪdbDBеĴԪؼL'k¼ѡkCkеԪdbе֧ɨDB¼CkеԪDBе֧ɨʱCkdbDBд ԪؼL'kС㷨LkCkΪʱ˶DBвɾĽ㷨Чʱһ㷨AprioriDHPdbDBвɾЧҪߵöࡣ
㷨IUAһصĺѡ㷨iua_genÿһζݿDBɨ֮ǰ СĺѡӶ㷨ЧʡҲҪһζݿDBвɾʱֵ (nΪLԪصԪظ)ڱβɾʱǿɵõġΪڷֹʱҪϵصСֶ֧ȺСŶۼЩȤ 㷨кҪ塣
(3)з㷨
ĿǰѾĲвɾ㷨УAgrawalCD(Count Distribution) CaD(Candidate Distribution)DD(Data Distribution)[11]ParkPDM[12]Chueng㷨DMA[13]FDM[14]ȻǻڷֲʽݿĲɾ㷨Ҳ ڲвɾ
㷨CDٶȽϿ졢ʵ֡Ҫͬٵŵ㣬ͨ ѡȱ㡣㷨CaDDDPDMִЧCD[13]㷨DMA˷㷨C DһЩ㣬Ҫͬ϶ࡣ㷨FDM㷨DMAһ£F DMȫּ֦
Щ㷨ǻ޹ϵṹмn̨֮ ȫġÿ̨Pi(i=1,2,...,n)϶ԼķݿDBiܵݿ⡣
㷨CD㷨AprioriڲлµӦãҪPi(i=1,2,...,n)DBiжɨ衣ڵkɨ裬k>1ʱPi(i=1,2,...,n)õk-1ɨ ĴLk-1Apriori_Gen()ɺѡCkk=1ʱPiɨDBió еĴ1õĴ1нкϲӶɺѡ1 C1ȻɨDBiCkеԪDBiе֧Pi㲥CkԪص֧ մCkԪص֧Щ֧ۼӣóCk Ԫصȫ֧kLkLkԪظΪ1㷨
㷨DMAǻڡXDBǴĳһDBiҲǴԭơ㷨вþֲ֦(Local pruning)ʹɵĺѡ㷨CDҪС㷨վ֧ʱѯվ㼼(polling site)ʹÿһXͨѶ 㷨CDo(n2)Ϊo(n)nΪվɷΪ¼ɺѡkCHiKݼPi(i=12...n)k-1ѭɵĳܼHLiK-1ѭkõĺѡkCHiK֧㡣ɨDBiѡkеÿԪXľֲ֧X.supi۽֧ѯվ㼼ѡkе Ԫص֧ȫ֧ɴLkͳܼеԪؾʣDBiDBжǴ
(4)ɾһ
оɾĹУѧ߷һЩʵӦУݱȽ٣Ҫ ԭʼĸϷǿ(Strong)Ȥ(Interesting)ǱȽѵģΪ öû㹻֧ڸҪɾݿоǴڵģ һΣţţ̣ţʳƷȣǳƸ߲ε Ͳĸףָιϵͨһѭͼ(DAG)ʾǾͿ ڽϸߵĸϷֹ򡣻Ҫɾݿеĸκͷֵһ еĹ㷨ѧЧһ㷨ҪУ Han˵ML_T2L1ML_T1LAML_TML1ML_T2LA[15]R.Srikant˵Cumulate StratifyEstimateEstMerge[16]ȡ
㷨ML_T2L1Ļ˼ȸҪֵԭݿһݸ Ϣбݿ⣬иϢɵݿ⣬Զ ڲͬηӦĹʵ㷨Aprioriڶλеչ ݶڷָ߲õݽṹɵмʽĲͬ 㷨ML_T2L1֣ML_T1LAML_TML1ML_T2LA
㷨CumulateĻ˼Aprioriȫһֻɨ赽ݿĳһʱ ȼ뵽УŻٶԼ뵽еȽй ԤȼϵTеÿһȣõȵĶձT*۶ԼȰ XְXȵм֦
㷨StratifyڡXĸײǴX϶Ǵʵơ˼ΪڸѭͼУûи׵Xdepth(X)=0 Ϊ㷨Ҫݿжɨ裬kk(0)ɨΪkk(0)Ck֧óΪkk(0)ĴLkڵkk(1)ɨ֮ǰCkм֦ɾCkЩȰCk-1-Lk-1еԪءΧĳЩȽϴǷǴ⣬[16]ó Stratifyչγ㷨EstimateEstMerge
(5)ɾֵԹ
ɷΪ͹ͶֵԹ򡣶ֵֿɷΪԺ ԡֵԹɾ[17]ĿǰĲɾֵԹ 㷨ǽֵԹɾתΪ͹ɾ⣬ֵ ֵΪ䣬ÿһԣԵÿһһԡ
[17]зֵĶֵԹʽΪx=qxy=qyǰͺӦĶǵһ ֵһ䣬㷨Ƚϼ򵥣Ҫ֮Ĺ ʱǽϵıը⡣
[18]áƫԶpartial completenessmeasureԭԻΪȵļΣĳһε֧СûС֧ʱǾͽڽ кϲΪʹֵĹȤԣвˡֵgreater-than- expected-value׼
[19]Ϊ[18]еԻַܺܺõرʾݵķֲֲֵ ʱһ㷨ݿݵķֲֵλ ɽصνкϲڴ˻ϷֵĶֵЧԺͿԡ
(6)ԼĹɾ
ԼĹɾҪĿǷָȤġʵõĺ͸رĹⷽ оҪ[2027]
[20]оṩʽԼµĹ⡣ֲʽԼ ûָȤĹļϣԼݿԤӹ ҿ԰ڲɾ㷨ڲӶ㷨ִЧʣиּɷʽĲ ֲͬͬ㷨MultipleJoinsReorderDirect
[21]ûԼԷ㷨ļ֦ǳҪԣ (anti-monotonicity)ͼ(succinctness)һЧĻԼĹ ɾ㷨CAP
һ͵ĻԼĹɾ򷽷ԪģʽƵĹɾ㷨[2527] ͵ķ㷨ûҪֵĹԪģʽģ壬ȻЩģ ݿзģӦʵʴڵĹ[26]ǻģʽ Ӧ㷨ν㷨(largepredicate-growing)ֱp-νʲ㷨(Direct p-predicatetesting)
(7)
оٵıȽϳо⣬һЩо磺ֹ [28,29]ɾģʽܼݼ[24,30]ɾԺϵ[31,32]ֱ [33](cyclic)(calendric)[34,35]ɾά[25] ȵȡ
2.3׼Ĳ
Ŀǰɹı׼Ҫֶ֧ȺŶȡ׼ ȻǲģΪûСֶ֧ȺСŶɹ ִᷢġٵĺͷǲɾ߹ĵĹ
һ[1]һӡĳѧУ5,000ѧ糿 60%ѧ75%ѧƬ࣬40%ѧȴֳƬࡣǽСֶ֧ȺСŶȷֱΪ40%60%ǿԷֹ򣺴Ƭֶ֧࣬ȺŶȷֱΪ40%66.6%ùʵһٵĹΪ ƬѧΪ75%ȸСֶ֧60%ָڹֶ֧66.6%ù Ϣûκμֵ
ֲѾ˲ѧߵע⣬һЩɾȤʵõĹ㷨[16, 31]ûγһͳһı׼ΪбҪȤ׼뵽 ֮УŷݲɾּͼٹɾäĿԡ
3һоķ
ĿǰݿɾѾȡĿĳɼоҲǾ սԵĹ
ЧĲɾ㷨
ݿĳߴĲ󣬲˲ɾ㷨ռ䣬ҲäĿֵ ԡǱ֪ʶȥȡǷйصݣɾݣ ЧؽάƳЧĲɾ㷨ⷽ棬ԼĹɾ йǰ;
ӻɾ
һû棬ûɾϵͳнɾĽкܺ ĿӻʾʹרҲܹвɾ
ڲͬýĲɾ
Ŀǰɾ㷨ǻڹϵݿݿ㷨Ӧ ݿ(ݿ⡢άݿ⡢ݲֿ)ɾ㷨Ҳʮ Ĺ
ƶΪĹ۱׼
ǰĿǰĹĺ׼ܻʹǷһЩġٵĺͷǲɾ߹ ĵĹбҪƶһЩµĺ׼Щ׼ƶҪ 
ϵͳļ
ļɰɾ򷽷ļɺϵͳ(רϵͳ֧ϵͳ)ļ 
4
ĶԽɾҪо˻عˣһЩ㷨˷ ָۡ˹׼Ĳ㣬չ˹ɾδо
㽭ѧ˹о310027
棨㽭ѧ˹о310027
ȣ㽭ѧ˹о310027
ο
1M. -S. Chen, et al. Data mining: an overview from database perspective. IEEE Transactions on knowledge and data engineering, 1996, 8(6), 866883
2R. Agrawal, et al. Database Mining: A Performance Perspective. IEEE Transactions on knowledge and data engineering, 1993, 5(6), 914925
3Usama M. Fayyad, et al. Advances in knowledge discovery and data mining. California: AAAI Press/The MIT Press. 1996
4R. Agrawal, et al. Mining association rules between sets of items in large databases. Proc. ACM SIGMOD int'l conf. management of data, Washington, DC, May 1993, 207216
5R. Agrawal, R. Srikant. Fast algorithms for mining association rules. Proc. 20th int'l conf. very large databases, Santiago, Chile, Sept. 1994, 487499
6J. S. Park, et al. Using a hash-based method with transaction trimming for mining association rules. IEEE Transactions on knowledge and data engineering, 1997, 9(5), 813825
7A. Savasere, E. Omiecinski and S. Navathe. An efficient algorithm for mining association rules. Proceedings of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 432444
8Hannu Toivonen. Sampling large databases for association rules. Proceedings of the 22nd international conference on very large databases, Bombay, India, 1996, 134145
9D. W. Cheung, 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
10, 뽣. ʽ㷨. ѧ, 1998, 9(4),301306
11R. Agrawal, et al. Parallel mining of association rules. IEEE Transactions on knowledge and data engineering, 1996, 8(6), 962969
12J. S. Park, et al. Efficient parallel data mining for association rules. Proc. Fourth int'l conf. information and Knowledge management, Baltimore, Nov. 1995
13D. W. Cheung, et al. efficient mining of association rules in distributed databases. IEEE Transactions on knowledge and data engineering, 1996, 8(6), 910921
14D. W. Cheung, et al. A fast distributed algorithm for mining association rules. Proc. of 1996 Int'l Conf. on Parallel and Distributed Information Systems (PDIS'96), Miami Beach, Florida, USA, Dec. 1996
15J. Han, Y. Fu. Discovery of multiple-level association rules from large databases. Proc. of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 420431
16R. Srikant, R. Agrawal. Mining generalized association rules. In: Proceedings of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 407419
17G. Piatetsky-Shapiro. Discovery, Analysis, and Presentation of strong rules. In: G. Piatetsky Shapiro and W. J. Frawley eds. Knowledge discovery in database. AAAI/MIT Press. 1991, 229248
18R. Srikant, R. Agrawal. Mining quantitative association rules in large relational tables. In: Proc. 1996 ACM SIGMOD int'l Conf. Management Data, Montreal, Canada, 1996, 112
19ų, ½,  . ֵԵĹ. ѧ, 1998, 9(11), 801805
20R. Srikant, R. Agrawal. Mining association rules with item constrains. Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, August 1997, 6773
21R. Ng, L. V. S. Lakshmanan, J. Han and A. Pang, Exploratory Mining and Pruning Optimizations of Constrained Associations Rules, Proc. of 1998 ACM-SIGMOD Conf. on Management of Data, Seattle, Washington, June 1998, 1324
22L. V. S. Lakshmanan, R. Ng, J. Han and A. Pang, Optimization of Constrained Frequent Set Queries with 2-Variable Constraints, Proc. 1999 ACM-SIGMOD Conf. on Management of Data, Philadelphia, PA, June 1999
23R. Ng, L. V. S. Lakshmanan, J. Han and T. Mah, Exploratory Mining via Constrained Frequent Set Queries, Proc. 1999 ACM-SIGMOD Conf. on Management of Data, Philadelphia, PA, June 1999
24R. J. Bayardo Jr., R. Agrawal, and D. Gunopulos. Constraint-Based Rule Mining in Large, Dense Databases. In Proc. of the 15th Int'l Conf. on Data Engineering, 1999, 188197
25Micheline Kamber, Jiawei Han, Jenny Y. Chiang, Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes, Proceeding of the 3rd International Conference on Knowledge Discovery and Data Mining, Newport Beach, California, Aug. 1997, 207210
26Y. Fu and J.Han, Meta-Rule-Guided Mining of Association Rules in Relational Databases, Proc. 1995 Int'l Workshop. on Knowledge Discovery and Deductive and Object-Oriented Databases(KDOOD'95), Singapore, December 1995, pp.3946
27Wei-Min Shen, et al. Metaqueries for data mining. In: U. M. Fayyad, G. Piatetsky-Shapiro, et al eds. Advances in knowledge discovery and data mining. AAAI/MIT Press. 1996, 375398
28R. Meo, G. Psaila, and S. Ceri. A new SQL-like operator for mining association rules. Proc. of the 22nd int. Conf. on very large databases, Bombay, India, 1996, 122133
29J. Han, Y. Fu, K. Koperski, W. Wang, and O. Zaiane, DMQL: A Data Mining Query Language for Relational Databases, 1996 SIGMOD'96 Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'96), Montreal, Canada, June 1996
30R. J. Bayardo Jr., Efficiently Mining Long Patterns from Databases, Proc. of the ACM SIGMOD Conference on Management of Data, Seattle, Washington, June 1998, 8593
31S. Brin, R.Motwani, and C. Silverstein. Beyond market basket: generalizing association rules to correlation. Proc. 1997 ACM-SIGMOD int. conf. management of data, Tucson, Arizona, May 1997, 265276
32C. Silverstein, S. Brin, R. Motwani, and J. Ullman. Scalable techniques for mining causal structures. Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 594605
33F. Korn, et al. Ratio rules: A new paradigm for fast, quantifiable data mining. Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 582593
34B. Ozden, et al. Cylic association rules. Proc 1998 int. conf. Data Engineering, Orlando, FL, Feb. 1998, 412421
35S. Ramaswamy, et al. On the discovery of interesting patterns in association rules, Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 368379
ոڣ1999623
