Ϣ
Information and Control
1999ꡡ285ڡVol.28No.51999



ݲɾ֪ʶ֣ع˺չ
֣֮ Ź㷲 ۻݺ

ժҪ δӴģݿзε֪ʶϢЩӴͳ ѯõƽݣⷽоܵԽԽĹעΪһŶӦ о⣬ѳΪڶоȵݣѾ൱Ӧñȡ˷˶ ɹԾݲɾ֪ʶֵĸݣɾ̡㷨Ӧõȣ һĻعˣҲһδĹս 
ؼʣݲɾ֪ʶ֣ѧϰ򣬷࣬
ͼţTP274ױʶ룺A

DATA MINING AND KNOWLEDGE DISCOVERY:
AN OVERVIEW AND PROSPECT
ZHENG Zhi-kai ZHANG Guang-fan SHAO Hui-he
(Dept. Automation, Shanghai Jiao Tong University, 200030)
AbstractDiscovery knowledge and useful information form lar ge scale databases has been recognized by more and more researchers as a key res earch topic in many different fields. This paper is to provide a survey of data mining and knowledge discovery on several issues, such as the process, methods, algorithms and applications. Future research work and challenges are also discus sed.
Key wordsdata mining, knowledge discovery in database, associa tion rules, classification, data clustering, machine learning

 żͨѶϢĸٷչϢģѸٲҵ ֲҵڼϾͱΪģĴģݲĲҵְݲɼ䡢ۺϵȵȻڣ
Щó׵ӻҵӻѸռ˴ģԴ ͬʱĿѧʹģĹҵҲṩ˺ݣݿϵͳݿϵͳΪЩݵĴ洢͹ṩ˼֤һ棬缼ĳ͹ģıըΪݵĴԶ̽ṩ˼ֶΣرǹʻǽȫϢԴһͬݿϵͳ֮УЩɡɼʹݵ˾޴ΪϢʱ춨˻
ЩѸߵͬʱǿݲеһҪڣϢȡش ȴԵشˣʣЩӴݿ⼰еĺǼḻϢԴǽͳݼƺͳƷѾԶԶҪ[1]ˣһ˵ĵԶϢȡݲɾ֪ʶ֣Ӧ˶õѸٷչĳΪԶܵذѺתõϢ֪ʶṩֶ[2, 3]
ݲɾ֪ʶΪһ˵о漰ѧϰģʽʶͳ ѧݿ˹ܵȵڶѧƣرأɿݿۺͻѧϰĽѧ ΪһֶӦõļһܵ㷺ĹעĿǰⷽоչܿ ֪ʶֺݲɾѧڿӣڿҲΪ򿪱רڶѧ ҲƵƵУͬʱһʵû֪ʶֹҲͶгõ㷺Ӧ [47]
Ծݲɾ֪ʶֵĸȫĻع˺ͽܣԹؼĹɾϸۣµ̽һսͷչ
1
1.1 
[8]У֪ʶģ֪ʶʶݿЧġ ӱġǱڼֵտģʽķƽ̣ݲɾָݿ нʾġǰδ֪ĲǱڼֵϢķƽ[9,10] ɼںͬϸڡ֪ʶ96ʻ顱 ϣFayyad, Piatetsky-ShapiroSmythָ[8]֪ʶǴݿз ֪ʶọ̈̄ݲɾǴȫ̵һضġؼ裮ڱУ ۼݲɾϣԶʹݲɾʵϣֽ еĴϣȻֵʹ[9]
1.2 ݲɾص
ݲɾѧϰǴȡ֪ʶҪڣѧϰҪضģʽݽѧϰݲɾǴʵʵĺԴгȡ֪ʶЩԴͨһЩݿ⣮ݲɾʹõֱݿ⣬ݵ֯ʽݹģݿص㣬رģݲɾǳ޴ݵԡһԺȷԶԱ֤ԣݲɾ㷨ЧʡЧԺͿԶԵҪȻִݿ⼼Ҳݲɾ㷨ЧʵЧ;
봫ͳݿѯϵͳȽϣݲɾҲĲͬ
ȣͳݿѯһ㶼ϸĲѯʽSQLݲɾһϸҪ󣬳ֳʱص㣮ѯҪҲȷɾҲ޷SQLԾʵϣݲɾ򳣳һSQL
ߣͳݿѯһϸĽݲɾܲϸĽɾͳƹɣĹ򲢲ҪеǳֻҪﵽһȸֵͿˣ
 ͨ£ݿѯֻݿԭʼֶνУݲɾݿĲͬϷ֪ʶ
1.3 ݲɾķ
ݲɾ֪ʶּչڣ༼֧оЩ ڲͬݿϵͳӦòͬĲɾӶɾ֪ͬʶݲɾ ෽ֱ
1) ݵݿ
ͬݿݵ֯ʹ洢ʽкܴͬһԷΪϵݿ ݿ⡢ݿ⡢ݿȵȣˣݲɾ԰ݿĲͬ ֳɲ࣮ͬӹϵݿɾ֪ʶĹϵݲɾʹΪ㷺Ҳ Ϊһݲɾ
2) ɾ֪ʶ
ɾ֪ʶжʽ[3,11,12,13,14] [15 ,16][1719][2022]ʱ[23,24] ȵȣͬʱЩ֪ʶҲڲͬĲϱ磺֪ʶԭʼ֪ʶ֪ʶ ȵȣԣݲɾϵͳҲɲɾ֪ʶ࣮ȻʹͬһݿУ ֪ʶҲǶֶģԣһӦȫزɾڲͬ ڵĲ֪ͬʶ
3) Ӧõļ
ڹ;[10,25]ķֽݲɾǻ෽ģ ùֺ;༼ģʽ͹ĺĳֹ㷨ͨ ݿеݽвɾ򣬲;Ȼ󣬶ݽзԤ⣮
Ԫķ[26]ԪжԷݵĿ õ㷺ӦãݲɾĹУԪݾߣ ݿķͽģӦù㷺
ģ[27]ʹּ[28]Ӧģʹּ۽ݲѯ ҲݲɾҪķ
ͳƷͳڷǳƵѧۣݷӦ÷㷺Ӧãʵϣ෽ҪݣǴзģʽ͹ԣݲɾҪΪĻڣ
ݿӻ[6]һศݿӻչݵıݲɾǷǳҪģݿӻܵ㷺ӣ
2Ĳɾ
ݿй򷢾о϶[12,13,14,29]ڣĲɾѾӵһιķַչεĹķ֣оص㷽㷨Чʺ͹ģϣ
2.1 
ѧģͼ[29]I={i1, i2,,im}ĸΪDȫļϣTIһӼTIÿΨһı־TIDʶXITXҽXTʽXYXIYIXYգXΪY ΪĽABԼDŶȶΪDc%XҰYDй XYֶ֧ȶΪDs%XYŶȱʾǿȣֶ֧ȱʾ ƵȣŶȺֶ֧ȾڸֵĹΪǿ򣬶ݲɾҪȤǶǿ Ĳɾ
㷨УĿɱֽΪ[11,13,29]
(1) ҳһֶ֧ȴڸֵĴ
(2) 򣮶ԸLǿӼAL

ʽΪAL-AĹ
Уһ㷨ĹؼһҵĵǺȻ 
2.2 Ĳɾ㷨
͵Ĺɾ㷨Apriori[11]DHP[13,30]ȣ Ƕݿ㷨
Apriori㷨Ļ˼ǣͨɨݿ⣬һĺѡ ÿѡĴȻԤȸСֶ֧һάL 1ȻL1ݿеݣάL2ͬķֱN άLNѲٿСֶ֧ȵN+1άβ {L1L2LN}òв
Ǵ[11]м򻯶ģݿDͼ1ʾڵһɨݿ Уͨ򵥵ɨÿĴõѡC1 Сֶ֧Ϊ2ɵõһάL1ΪL2ע⵽ κӼҲСֶ֧ȣApriori㷨L1*L1L2  * Ϊ
L1*L2={XY|X,YLk,|XY|=k-1}
ԣõѡC2Сֶ֧ȵõL2L2C3ʱͬ {BC}{BE}ȷٿ{BC}{BE}βɵ{C E}ǷСֶ֧ȣǳģ{BCE}жάӼǴ{ BCE}ΪѡͬʱL2ҲòάѡC3ȷˣͬ L3ΪֹҲòάˣԣȷ ˣòв


ͼ1 ѡ

DHP[13,30]㷨Apriori㷨ƣDHP㷨ɢб Żk-1άkάḶ́㷨Чʣ
2.3 Ķβɾ
ںܶӦУݿвͬĳϣ磺ڷ ݿУݿеԭʼֶΣţ̵ȵȽйɾ򣬿 Է˸ȤĹһЩεĸҲǽȥţ̸ ĸʳƷпܷµĹоݿвͬĳϷ [3,12]Ԫ[31]ݲɾҪоݣ
2.4 㷨Ч
ȻڲɾУҪݿ¼ҿܶݿжɨ ԣ㷨ЧǷǳҪģ
[32]һּݿɨʾּЧʵľ޴ߣ[3]Уò˾ȿɵĲɾһЩЧʸΪ ҪӦǷǳЧģģݿ⾭ֲڵϣòݲɾ ȻЧʣ˲ݲɾһҪĵо[33,34]  ˼ֲ㷨[7]ϸ˲㷨ʵָݣ
3Լȡ
ݿеԭʼֶ˹ľϢΪݱգǳҪ Щĸһ㻯һϸߵĳΣͨݲɾ̣ ݷԼǲͼͿӻȼõӼĽ ȡǴһȡЩݵʽЩʽݼһ Щ̶Ѱݵһ㻯Ĺ[9]
ĿĵķɷΪࣺ
1) (Data Cube)[2022]
Ҳ֮Ϊάݿ⣬һֳõļ[21]Ҫ˼ǰЩ۰ĳ磺CountSumAverageMaxMinȻܺԤȼݲͬԷ洢һάݿУʱ԰աڡ¡ֱܲݿΪ֧֡ݲɾӦ÷
2) ԹɷAttribute-Oriented Induction Approach[5,35,3 6]
ԹɲĳԴӾֵĸο֪ʶṩ[37]ضδһ㵽ĸڵʾһĸҶڵĸԵľֵ[38]Ϊɷṩ Ϣ֯ɲͬΣӶڽϸ߸ü򵥡ȷеĹʽ Ա[sophos1]෽һߵġݷķһSQL ݲɾѯѯҪ󣮲һݷ[5]磺ɾ ݻܷһַĹϵݣٰЩת֪ʶ ʽ[39]
4ݷ
ݷǰһݶݶѧֵḶ́ݲɾҪо ֮һͬʱҲ˹ܡģʽʶ˹ԪѧƵҪоݣзḻĽ͹㷺Ӧã
ȿԣӶȷķ߷ȻѷӦõѵɷ̣߹õķģͣ
Ҫķ㷨лھķ෽[25] ͳƷ[40,41] 緽[42,43]ʹּ[28]ȣ
ڻѧϰУо˻ھķ෽[10]һִӲйļලѧϰ̣ƷʺڷľȺĴСȣ㷨ѡһѵӼܶеĶ࣬ѡ ֱȷľҵ
ڷӦݲɾУЩ㷨ҪսѵĹģ[15,16] ھķ෽ڴģݿµӦã[44]ڽϸ ĳη㷨MehtaԴݿһֿٷ㷨ΪQ UESTеĳѧϰ㷨(SLIQ)[44][45]УԶάԷ Ҫ˫෽
5ݾ
ʶһݶڹ򣬴Ӷ飬ƶ࣬Եݵ ֲɣҪڷǰѼеķӦõݶȥ ͼȥһӵݶķķ Ƿǳģ
㷨ͳƷѧϰԪͬõ㷺о
ͳľҪȻ෽ļǰǲͬԵĸ ֲ໥ȻʵӦõݲɾϵͳУҲ˵һĴݼ£ ܿǲģݿУ֮ܰصϣ⣬ ʵǷƽݽṹ롢ʱͿռ۶ߣȻ ҲʹþĴȡ͸¶ǳѵģ
NgHan[19]չڴģӦõĻ㷨CLARANS 㷨Իڶĸ[18]ڴ㷨[5,46] ʱݿľ㷨SDNSDEster[18]CLARANS 㷨ȱ㣬˸ĽͨΪЧĿռݿȡ㷨R-  CLARANS㷨ܣT. Zhang[47]һ־㷨BIR CHһֺܺõľ㷨кܺõľƷʺͶԽĲԣӦñϾԵĹģԣԼ㸴ӶȶO(N)׵ģ
6չٵļս
1) 㷨ЧʺͿ
ݲɾ봫ͳĻѧϰڣݲɾֱݿϵͳģ ݿͨϰٸԺ¼ݱ֮ӵĹϵͱȻ ݲɾάռļͬʱҲ˳ֲȷ[48] Ͳ̬ģʽĿԣˣ㷨ЧԼйģʵӦ Եľ޴ս
2) ͬ͵ݺԴ
ֽݿģʹǹϵݿģͣԣݿģִݲɾ ǷǳҪģңݿӦ÷ΧݿĹģ͹ҵ ƣˣµݿģͲϳ֣ݿУŴӵͣԣ ݲɾϵͳЩݿĲҪģ
һż缼ķչҵţҵ͹ʻϵ ڶԴӳһ͵ķֲ칹ݿ[49]Щͬĸ ʽͷǸʽп֪ʶǶݲɾشս[50]ݲɾɽ ʾ칹ݿдڵͨѯֵܷ֪ʶݿľ޴ģطֲ ݲɾ򷽷ļ㸴Ҫзֲݲɾ㷨
3) ˽ԺͰȫ
ݲɾܴӲͬĽǶȡͬĳϿݣǱڽӰ쵽ݵ˽ԺͰȫ[51]оݲɾܵµķǷ֣ͬʵӦùؽ ⣮
4) ʻϵݲɾ
ģıըʹΪһȫģϢԴпԷִ֪ʶˣʻݲɾ˵ǰԽԽоԱȤ[49 ,32,52]
5) ݲɾϵͳ
ݲɾһӵḶ́ݲɾвߵʵǱزٵģϵͳĽϵͳҪģһ棬ûļѯҪݲɾԣΪûṩֶҪͲⷽĹؼһ棬ְɵĽݸûɵĽǶֶģˣ׼ȷֱ۵ɾĽѺöЧûһֱⷽоҪ[53,54] 
߼飺֣֮29꣬ʿоΪܿơݲɾ
Ź㷲24꣬ʿоΪԤơܿơʵʱרϵͳ
ۻݺף63꣬ڣʿʦĿǰоȤǹģͻŻơܿоӦã
ߵλϺͨѧԶϵ 200030
ο
1 Shortland R, Scarfe R. Digging for Gold (Data Management), IEE Review , 1995, 41(5): 213217
2 A Silberschatz, M Stonebraker, J D Ullman. Database Research: Ach ievements and Opportunities into the 21st Century Report NSF Workshop Future of Database Systems Research, 1995
3 R Srikant, R Agrawal. Mining Generalized Association Rules. Proc. 21 st Int'l Conf. Very Large DataBases, 1995: 407419
4 R Agrawal, M Mehta, J Shafer, eds. The QUEST Data Mining System. Pro c. Int'l Conf. Data Mining and Knowledge Discovery(KDD'96), 1996: 244249
5 J Han, Y Cai, N Cercone. Data-Driven Discovery of Quantitative R ules in Relational Databases, IEEE Trans. Knowledge and Data Eng., 1993, 5 :2940
6 H-Y Lee, H-L Ong. Visualization Support for Data Mining, IEEE Exper t, 1996:6975
7 R Agrawal, J Shafer. Parallet Mining of Association Rules: Design, Implementation, and Experience, IBM Research Report, 1996
8 Fayyad U, eds. Knowledge Discovery and Data Mining Towards a Unifying Framework. KDD'96 Proc. 2nd Intl. Conf. on Knowledge Discovery & Data Mining, A AAI Press, 1996
9 M-S Chen, J Han, P S Yu. Data Mining: An Overview from a Datab ase Perspective, IEEE Trans. on Knowledge and Data Eng. 1996, 8(6):8 66883
10 G Piatetsky-Shapiro, W J Frawley. Knowledge Discovery in Database s. AAAI/MIT Press, 1991
11 R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules in Large Databases, Proc. 20th Int'l Conf. Very Large DataBases, 1994: 478499
12 J Han, Y Fu. Discovery of Multiple-Level Association Rules form L arge Databases, Proc. 21st Int'l Conf. Very Large DataBases, 1995: 420431
13 J-S Park, eds. An Effective Hash based Algorithm for Mining Associa tion Rules Proc. ACM SIGMOD, 1995:175186
14 A Savasere, E Omiecinski, S Navathe. An Efficient Algorithm for Mi ning Association Rules in Large Databases, Proc. 21st Int'l Conf. Very Large Dat a Bases, 1995:432444
15 R Agrawal, S Ghosh, T Imielinski, B Iyer, A Swami An Interval Classifier for Database Mining Applications, Proc. 18th Int'l Conf. Very Large D atabases, 1992: 560573
16 T M Anwar, H W Beck, S B Navathe. Knowledge Mining by Imprecise Queryin g: A Classification-Based Approach, Proc. 8th Int'l Conf. Data Eng., 1992: 622630
17 D Fisher, Optimization and Simplification of Hierarchical Clusterings, Proc. 1st Int'l Conf. Knowledge Discovery and Data Mining(KDD'95), Montreal, Ca nada, 1995: 118123
18 M Ester, H-P Kriegel, X Xu. Knowledge Discovery in Large Spati al Databases: Focusing Techniques for Efficient Class Indentification, Proc, 4th Int'l Symp. Large Spatial Databases (SSD'95), Portland, Maine, 1995: 6782
19 R Ng, J Han. Efficient and Effective Clustering Method for Spatial Data Mining, Proc. Int'l Conf. Very Large Database, Santiago, Chile, 1994: 144 155
20 A Gupta, V Harinarayan, D Quass. Aggregate-Query Processing in Data Ware-housing Envirment, Proc. 21st Int'l Conf. Very Large DataBases, 1995: 358369
21 J Widom. Research Problems in Data Warehousing, Proc. 4th Int'l Conf. Information and Knowledge Management, Baltimore, 1995: 2530
22 W P Yan, P Larson. Eager Aggregation and Lazy Aggregation, Proc. st Int'l Conf. Very Large Data Bases, Zurich, 1995: 345357
23 R Agrawal, eds. Fast Similarity Search in the Presence of Noise, Scal ing, and Translation in Time Series Databases, Proc. 21st Int'l Conf. Very Large Data Bases, 1995: 490501
24 C-S Li, P S Yu, V Castelli. Hierarchy Scan: A Hierarchical Sim ilarity Search Algorithm for Databases of Long Sequences, Proc. 21st Int'l Conf . Data Eng., 1996
25 C Apte, S Weiss. Data Mining with Decision Trees and Decision Rules, Future Generation Computer Systems, 1997, 13(2): 197210
26 H Lu, R Setiono, H Liu, Effective Data Mining Using Neural Netwo rks, IEEE Trans. on Knowledge and Data Eng., 1996, 8(6)
27 H Nakajima. Fuzzy Logic and Data Mining, Proc. '96 Asian Fuzzy Systems Symposium, Taiwan, 1996: 133138
28 Wojciech Ziarko, Introduction to the Special Issue on Rough Sets and Kn owledge Discovery, Computational Intelligence, 1995, 11(2): 223226[ ZK)]
29 R Agrawal, T Imielinski, A Swami. Mining Assocation Rules betwee n Sets of Items in Large Databases, Proc, ACM SIGMOD, 1993: 207216
30 J S Park, M-S Chen, P S Yu. Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Trans. on Knowledge and Data Eng. 1997, 9(5)
31 Y Fu, J Han. Meta-Rule-Guided Mining of Association Rules in Rel ational Databases, KDOOD'95, Singapore, 1995: 3946
32 M-S Chen, J-S Park, P S Yu. Data Mining for Path Travers al Patterns in a Web Environment, Proc. 16th Int'l Conf. Distributed Computing S ystems, 1996: 385392
33 J-S Park, eds. Efficient Parallel Data Mining for Association Rules , Proc. 4th Int'l Conf. Information and Knowledge Management, 1995: 3136
34 R Agrawal, John C Shafer. Parallel Mining of Association Rules, IEEE Trans. on Knowledge and Data Eng. 1996, 8(6)
35 F J Venter, G D Oosthuizen, J D Roos. Knowledge Discovery in Databases using Lattices, Expert Systems with Applications, 1997, 13(4): 259264
36 J Han, Y Fu. Exploration of the Power of Attribute-Oriented Induc tion in Data Mining, Advances in Knowledge Discovery and Data Mining, AAAI/MIT P ress. 1996: 399421
37 V Dhar, A Tuzhilin. Abstract-Driven Pattern Discovery in Databas es, IEEE Trans. Knowledge and Data Eng., 1993: 926938
38 J Han, Y Fu. Dynamic Generation and Refinement of Concept Hierarch ies for Knowledge Discovery in Databases, Proc. KDD'94, 1994: 157168
39 J Han. Mining Knowledge at Multiple Concept Levels, Proc. 4th Int'l Co nf. Information and Knowledge Management, 1995: 1924
40 J Elder IV, D Pregibon. A Statistical Perspective on Knowledge Dis covery in Databases, Advances in Knowledge Discovery and Data Mining, AAAI/MIT P ress. 1996: 83115
41 P Cheeseman, J Stutz. Bayesian Classification (AutoClass):Theory a nd Results, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press., 19 96: 153180
42 H Lu, R Setiono, H Liu. NeuroRule: A Connectionist Approach to Data Min ing, Proc. 21st Int'l Conf. Very Large Databases, 1995: 478489
43 A. Eide, eds., Data Mining and Neural Networks for Knowledge Discovery. Proc. AIHENP'96, 1996: 251254
44 M Mehta, R Agrawal, J Rissanen. SLIQ: A Fast Scalable Classifier for Data Mining, Proc. Int'l Conf. Extending Database Technology(EDBT'96), Avig non, France, 1996
45 M S Chen, P S Yu. Using Multi-Attribute Predicates for Mining Cla ssification Rules, IBM Research Report, 1995
46 W Lu, J Han, B C Ooi. Knowledge Discovery in Large Spatial DataB ases, Proc. Far East Workshop Geographic Information Systems, Singapore, 1993: 2 75289
47 T Zhang, R Ramakrishnan, M Livny. BIRCH: An Efficient Data Cluste ring Method for Very Large Databases, Proc, 1996 ACM SIGMOD Int'l Conf. Manageme nt Data, Montreal, Canada, 1996
48 F McErlean, D A Bell. Experiment in Knowledge Discovery using Data D ependencies Kybernetes: An International Journal of Cybernetics and General Syst ems, 1997, 26(8)
49 Oxman Rivka. Interactive Visual Exploration for Knowledge Discovery on the Web, Proc. '97 Int'l Conf. on Information Visualization, London, 1997
50 F Ronen, H Haym. Exploiting Background Information in Knowledge Disco very From Text, Journal of Intelligent Information Systems, 1997, 9( 1): 8397
51 C Zhengxin. Knowledge Discovery and System-user Adversary, Kybernete s: An International Journal of Cybernetics and General Systems, 1997, 26(4): 425441
52 C Shahabi. Knowledge Discovery from users Web-page Navigation. Proc. '97 Int'l Workshop on Research Issues in Data Eng., 1997: 2029
53 A Basden. User Interface for Knowledge Discovery, Proc. '96 IEE Colloq uium on Knowledge Discovery and Data Mining, London, 1996
54 Xu Wu, Nick Cercone, Graphical User-Interface for Knowledge Discovery in Databases. Engineering Applications of Artificial Intelligence, 1996, 9 (6): 691700

ոڣ1998-10-29
