Ϣ
Information and Control
1999ꡡ284ڡVol.28No.41999



KDDData Mining ǵĲֹͿ
ˡԬ

ժҪĽʲôKDDData MiningĿǰData MiningоһҪݵĸſԼKDDData MiningеĲֹͿ
ؼʣKDD, Data Mining, ּ, Ԫ, Ŵ㷨
ͼţTP274ױʶ룺A
A PART OF OUR RESEARCH WORK AND VIEWS IN THE
KDD AND DATA MINING
QIN Zhenxing1 YUAN Zengren2
(1. Dept of Mathmatics and Computer Science, Guangxi Teachers Tra ining University, Guangxi;
2. Depr. of Mathmatics and Computer Science and Technology, Tsinghua Univer sity100084Beijing)
Abstract: The paper presents the definition of KDD and Data M ining. It also presents briefly a surver of a part of important contrnt s in the intemational data mining research work as as a part research work and v iews in the KDD and data mining in recent yeats.
Key words: KDD, data mining, rough sets, artifivial Neural netwo rk, genetic algiruthm

 һϢըʱݹȫϢÿ18·һ ĿǰϢԶչٶȻ죮ŽInternet Ѹٷչݺһӿǵǰ˵ǲȱϢǸϢûˣǷ֪βܴѸҵҪ֪ʶ
һԣͨøָݿϢڻЩݿ÷ǳӴĿǰǧ¼ݿѱȱȽǣЩһֱԴһ̲طḻľ޴󳡣ҵǣǴзȴǳޣʱǲòȡᣬܿеһСֶѣ
Ŀǰݿϵͳһߣܲһļܻͳ̸Ͻ͸ԴͳϢ̶ܴһֹҵͨͳƷ ݿĴݼ򻯵ܴķΧȻרҸݾ֮з⣬ӦĽۣźݿݲֿĴ֣ഫͳķʽдԵ÷ǳʱԺܴˣǰҪõķʽ͹ͷЩӴݿ⣮һµоݿе֪ʶ֣Knowledge Discovery in DatabasesKDD) ҲӦ˶ڽѸٷչʵܼݿϣΪṩ֪ʶͲԣΪͶߴЧ.
1ʲôKDD
KDDKnowledge discovery in databases)һ1989AAAIKDDרֻϣFayyad[1]һ꾡Ķ壮ΪKDDŸ裺
(1)ȷоû;(2)Ŀݼѡһݼ߼ڱ Ӽϣʹܷ֮ӳֵĶ;(3)ݵľԤų ;(4)ݵļٺӳ䣺ѰõԱʾȷҵĿݣý 任Լٱҵݵĺ㶨ıʾ;(5)ѡȡʵݲɾ: KD DĿǷǷࡢع顢;(6)ѡݲɾ㷨ѡѰģ ʽķ;(7)ݲɾ򣬷ģʽ;(8)ֵģʽʽ;(9) ѷֵ֪ʶ֪ʶȻӦã
ǱȽ壬ΪData MiningĶΪ䣬58ʱڹ϶ɿData Miningķ룮ǲ14ΪData Mini ngǰ(8)(9)KDDɿһЧĵκ֮ܰ·ѭ̣KDDһûĴջ; Data Miningеһڻ. ںļӦУֲһ»򲻺ɻͷǰ沽޸ģֱõĽһǾData MiningΪһȽȷݿϣضݲɾ򷽷ȡġδ֪ġǱӦüֵϢḶ́
2ⲿо
1989AAAI֯һKDDרֻᣬļ1991[2]־KDDʽ֮£ԽԽоͶУΪ˴ݲֿInte rnetϺ̺ϢݣIBMNASAGMMICROSOFTȴ˾ͶʽƶKDD оʵû˽γһKDDоȳ1995꿪ʼÿһKDD ʻ飬AAAIIJCAI AIϵлKDDר⣬йKDDר־ 
  棬ǾData MiningǰоҪȵǱȽϸȤһЩļֱ䵱ǰо״Ƚϸ˽KDD  Data Mining  Ķ߿Բμ[1,2,3,15]
2.1 Խģ
ͨѡݱзҵһģϵйķǽоñȽ϶һҪ[410]ҪΪ ʵʵĴݿ⣨̳򳬼гݿ⣩УӦЧǰ ǳã
ѧģ[4]覣{i1i2,im}һ֣(ϵһӼÿһΨһʶTidͬ һ𹹳һݿ⣬ΪDDǷԴһΪ XYʽXʦXY=գXѧģ[4]覣{i1i2,im}һ ֣(ϵһӼÿһΨһʶTidͬһ𹹳һݿ⣬ΪDDǷԴһΪ XYŶcʾDcX YXѧģ[4]覣{i1i2,im}һ ֣(ϵһӼÿһΨһʶTidͬһ𹹳һݿ⣬ΪDDǷԴһΪXYֶ֧sʾDsXY˿ԸҪֵͬs䣬ΪСֶ֧ȣֶֻ֧ssʱԿǣ
磺ĳ̳зֹƷABĿͻ6%ƷCDĿͻ4%ҹABĿͻ90%ṺCDһϢùRABCD (c=90%s=10% )ʾ̳Ĳ֣Ʒڷżгȶǳã
[4]Էֽ
(1) ҳСֶ֧ȵ
(2) ȡСŶȵĹ
е(1)ĺģݿDǳҲܶʱܿ ׼ȷҳЩǷǳؼģȽϾ㷨IBM˾Quest ϵͳеApriori[5][8]DHP㷨ģ8벢㷨Чʣ
㷨ݿ⣬ֻȡ0,1(Ͳ)ֵֶͨκӰƹ͵ݿõԵع[6,11,12,13]
һƹ뱳֪ʶ Եĸ[5,10]һ֣ʹùչ༶Σ
2.2 ۺϺ͸
ݸǰһݼӽϵ͸γ󵽸߸εḶ́ ֪ݿеݳǱȽϾϸµģϵͣûʱ ҪڸߵĳϽзҪһĳ󻯣
ĿǰҪ෽ (1) [1619]Ҳάݿ⡱ݿӻOLAPOn-Line Analytical Processing (2)  ԵĹԼ(attribute-oriented, ¼AO)[20,21]ҪAO 
AOҪصһı֪ʶ,λ[20,21], ݿеԭʼݰ֪ʶתΪ߼ĸ,ԴСݹģ
2.3 ݷ
ݷ༴ݷģͣݿӰ򻮷ֵԤȶõеĳһ ݷڸͳƣѧϰרϵͳооһҪData Miningר⣮
ھķ[22.23]ԴڻѧϰһôලѧϰͬʱҪǷ׼ȷԺĴС森
ȲѧϰõһȻм飬ЩЩĶѧϰֱõһ׼ȷľ߼սһÿһƬҶӶһ࣬ڽһԣȡֵ֦УбȽϼ򵥵ıʾʽȽƵ
ϾľѧϰϵͳID3[22]C4.5[23] C4.5ǰID-3ӷչֻܶԽз࣬[21]ID3㷨ԵĹԼ Ƹ߳󼶵ķ[28]еDBMinerһɵĶ༶ϵͳʹü ںּߴݿķ׼ȷԣͬʱӦԵĹԼͷ෽ 
ǣ ѧϰֵķ㷨Ҫѵݷڴ棬ֻڽСģݣڴݿܲ[24] [25]һֿٷӣSLIQ(Supervised Learning in Quest)ҲһֻھӣѵݶڴٵһСıͬʱֵԣĽ㷨SPRINT[26]ʹѵݲڴƣ
оǰľԵΪ֧ݣʱҪöۺ[27]Ϊɷֳ׶ΣȡҳһõķԣȻ Щۺз࣬ԵõõķЧ
ڸʵķ[29,30,31]Roughsetsķ[32]ȣ [33]Ӧڴݿķ෽3ɾʱ [34,42]кȡһֽµķ [43]Ҳһmeta-learningķۺϼֻķӣһȽϺõĳԣ
2.4 ݾ (ҲзǼලѧϰ)
ݾ༴ǰѸɳĶ󻮷ֳ޸ ͳѧ[29,35]ͻѧϰ[36,37]ооЩڴʱ̫󣬱һķм򻯣
[40]CLARANSȳپķۺPAMCLARA㷨ŵ㣮Ҫڴ棬Ҽľ뿪Ҳܴ[39]R*-tree [38]۽ĴԴʡռͼټ㸴ӶȣR*-treeһڣBIRCH㷨[41]ԸڴСе
3ǵĲо
ЩоΪKDDǻѧϰͳѧȷһ˵˵KDDData Mining˵ҪȫǰķҪϣһЩµܼչʹ֮Ӧ±仯
ʵҺע⵽KDDһо,һֱעӹ½չ,Ŀǰڹڹ־ͻ鷢йʮƪ¼һЩоּҪ£
3.1 ߼ѧϲ뱳֪ʶ[4447]
ʿȫ߱仯򷽷[44]ͻڹԹɷ(rule-based attribute-oriented ΪRBAO)޻ݷ[45]Ӧ֪ʶ֣Ҫ˼ǰѲȫ߱AOϣһAO  ֲڼĽܵ˵,ǰĸKDD, ǴݿⱾϢ,ھ ģʽ,ûľ顢ʶ޷,ԭ֮һȱЧıʾʹֶ AORBAO߳˵һ,ֻܱʾ÷ѧ֪ʶ,漰 ʶݿеԣǣʱݿ֮ĳЩʿݿй,֮ ȻĳЩֻԲֶ壮Ϊݿһı֪ʶ ,Ϊ֪ʶ(knowledge-based)KDD[46,47]÷òѭһԪν֪ʶʾ֪ʶ,ѷǵѧϰһͳһ,˱֪ʶı
3.2 ӦԪ磨BP㷨ʵData Mining
3.2.1 Ԫȡ[4853]
ڹȥļANNȡ(crispģ)ɷѾˣѵõĶȡcrisp(Ǭ)ļBRINNE[48]KT㷨[49]ԼYoon Byungjaoͨdestructive learning(ٻѧϰ)ȡ[50]Ishikawa,M.ṹѧϰӦڹȡ[51]
ߵһԤ͹ȡ׶ɵķ[53]Ԥ׶аж̬ɾ֦֣̬Զɻɳʼ򼯹ȫӻ߷ȫĳ˽ṹɾֱɾصҪ߶ڵӣӶԵõ͹ģС˽ṹΪȡĻߵ˻˹ȡ㷨ɾغõȡַ߽ӦADͼݣȡ򼯣ݼĲԱȷĺЧģһּ򵥺Ϳеķ
3.2.2 Ԫɾ
òɾ㷨ѵɾ֦ȡͺĸģɣѵģҪǲóͷѧϰ֪ʶеٵԪϣʼѡñȱҪṹ ȻȥҪĲ֣൱Ҷʼ̫еȥѧϰ֪ʶ ͬʱϵͳĸԣڸĽģϴ󽫻ɾڵѣԳͷӦüӵ԰֪ʶ㼯Ԫϣ[54]вChaulinĳͷɾģҪ쳣ıȥѡڷ صԪ㷨ǻѲõģ صĳ̶Ȼģģڲ쳣ĳ̶ȣΪ쳣 ıΪԪһȣһµԪ㷨ȥ ڽӵԪȥʹ֮СԪĸȥ쳣֮ ʱζڷʹʱδ֪ݵʶʣ նϣƪϵٽܣ[54]ַӦIris,Cancer,Spli ce,PlomotesAgrawalļֺϣʵȡ׼ȷʡ ȽϺã
3.2.3 Ϸ[55]
[55]вŴ㷨ɾѾѵõԪ˽ṹȻɾõ תΪMMԪĿͨÿȡ ÿĹ򼯣ַӦIris,Breast Caneer DatasetsHandnitten Numeral Datasetȡ˺1995Setiono˵õNNDT൱ֳַ ͬʱľȣ⣬ַ˵߹̣
лʿųͲʿԶԲʿṩǵԼεۣ
߼飺ˣУ25꣬˶ʿоΪ˹ܺKDDData Mining
ԬΣУ64꣬.оΪܿƺͼ(˹磬ģ߼ 㷨)Ӧ.
ߵλ :ʦѧѧѧϵ, 廪ѧϵܼϵͳصʵҿ
Ԭ: 廪ѧϵ100084
ο
1 U M Fayyad, G Piatetsky-Shapiro, P Smyth. From Data Mining to Knowledge Discove ry : An Overview. In U.M.Fayyad, G. Piatetsky-Shapiro, P. Smyth, R U Uthurusamy , editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996 :83115
2 G Piatesky-Shapiro, W J Frawley. Knowkledge Discovery in Databases, AAAI/MI T Press, 1991
3 U M Fayyad, G Piatetsky-Shapiro, P Smyth, R U Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996:83115.
4 R Agrawal, T Imielinski, A Swami. Mining Association Rules Between Sets of Items in Large Databases. Proceedings of ACM SIGMOD, May 1993:207216
5 R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules in Large Databases. Proceedings of the 20th International Conference on Very Lage Data Bases, September 1994:478499
6 J Han, Y Fu. Discovery of Multiple-Level Association Rules from Large Databases. Proceedings of the 20th International Conference on Very lage Data B ases, September 1994:478499
7 H Mannila, H Toivonen, A Inkeri Verkamo. Efficient Algorithms for Disco vering Association Rules. Proceedings of AAAI Workshop on Knowledge Discovery in Databases, July, 1994:181192
8 J-S Park, M-S. Chen, P S Yu. An Effective Hash Bashed Algorithm for Minin g Association Rules. Proceedings of ACM SIGMOD, May 1993:175186
9 A Savasere, E Omiecinski, S Navathe. An Efficient Algorithm for Mining Assoc iation Rules in Large Databases. Proceedings of the 21th International Conferenc e on Very lage Data Bases, September 1995:432444
10 R Srikant, R Agrawal. Mining Generalized Association Rules. Proceedings of t he 21th International Conference on Very lage Data Bases, September 1995:40741 9
11 Srikant R, Agrawal R. 1996a. Mining Quantitative Association Rules in Large Relational Tables. In Proc. of the ACM SIGMOD Conference on Management of Data 
12 Randy Kerber. Chimege: Discretization of Numeric Attributes. In Proceedings of the AAAI-92 workshop on KDD. 123128
13 H Tsukimoto. The Discovery of Logical Propositions in Numerical Data, AAAI'9 4 Workshop on Knowledge Discovery in Databases, 1994:205216
14 R Agrawal, JC Shafer. Parallel Mining of Association Rules IEEE Transation on Knowledge and Data Engineering, Dec 1996:962969
15 M Chen, J Han, P S Yu. Data Mining: An Overview from Database Perspective. I EEE Trans. Kjnowledge and Data Engineering, 1996,8:833866
16 A Fupta, V Harinarayan, D Quass. Aggregate-query Processing in Data Warehou sing Environment. In Proc. 21st Int. Conf. Very Large Data Bases, Pages, Zurich , Switzerland, Sept. 1995:358369
17 V Harinarayan, J D Ullman, A Rajaraman. Implementing Data Cubes Efficientl y. In Proc. of the ACM SIGMOD Conference on Management of Data
18 J Widom. Reserch Problems in Data Warehousin. In Proc. 4th Int. Conf. on Information and Knowledge Management, Baltimore, Maryland, Nov. 1995:2530
19 W P Yan, P Larson. Eager Aggregation and Lazy Aggregation. In Proc 21st Int Conf Very Large Data Bases, Zurich, Switzerland, Sept. 1995:345357
20 J Han, Y Cai, N Cercone. Data-driven Discovery of Quantitative Rules in Re lational Databases. IEEE Trans. Knowledge and Data Engineering, 1993, 5:2940
21 J Han, Y Fu. Exploration of the Power of Attribute-oriented Induction in Da ta Mining. In U M Fayyad, G Piatetsky-Shapiro P Smyth, R U Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996:83115
22 J R Quinlan. Induction of Decision Trees. Machine Learning, 1986, 1:81106
23 J R Quinlan. C4.5: Programs for Machine Learning, Morgan Kaufmann, 1986
24 R Agrawal, M Mehta, J Shafer, R Srikant, A Arning, T Bollinger. The Quest Data Mining System. In Proc. 1996 Int'l Conf. on Data Mining and Kno wledge Discovery (KDD'96), Portland, Oregon, August 1996
25 M Mehta, R Agrawal, J Rissanen. SLIQ: A Fast Scalable Classifier for Data Mi ning. In Proc. 1996 Int. Conference on Extending Database Technology (EDBT'96), Avignon, France, March 1996
26 J Shafer, R Agrawal, M Mehta. Fast Serial and Parallel Classification of V ery Large Data bases. In VLDB 96
27 M S Chen, P S Yu. Using Multi-Attribute Predicates for Mining Classificati on Rules. IBM Research Report, 1995
28 J Han, Y Fu, W Wang,etc. DBMiner: A System for Mining Knowledge in La rge Relational Databases. In KDD'96, Portland, Oregon, Augest 1996
29 P Cheeseman, J Stutz. Bayesian Classificaton (AutoClass): Theory and Result s. In U M Fayyad, G Piatetsky-shapiro, P Smyth, R U Uthurusamy, Editors, Advanc es in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996:153180
30 J Elder IV, D Pregibon. A Statistical Perspective on Knowledge Discovery in Databases. In U M Fayyad, G Piatetsky-shapiro, P Smyth, R U Uthurusamy, Editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996 :83115
31 G Piatetsky-shapiro. Discovery, Analysis, and Presentation of Strong Rules. In G Piatetsky-shapiro, W J Frawley, Editors, Knowledge Discovery and Databases, AAAI/MIT Press, 1991:229238
32 W Ziarko. Rough Sets, Fuzzy Sets and Knowledge Discovery. Springer-verlag , 1994
33 R Agrawal, S Ghosh, T Imielinski, B Iyer, A Swami. An Interval Classifier for Database Mining Applications. Proceedings of the 18th International Confere nce on Very lage Data Bases, August 1992:560573
34 H Lu, R Setiono, H Liu. Neurorule: A Connectionist Approach to Data Mining . Proceedings of the 21th International Conference on Very Lage Data Bases, September 1995:407419
35 A K J, R C Dubes. Algorithms for Clustering Data. Printice Hall, 1988
36 D Fisher. Improving Inference Through Conceptual Clustering. In Proc. 1987 A AAI Cconf., Seattle, Washington, July 1987:461465
37 D Fisher. Optimization and Simplification of Hierarchical Clusterings. In Pr oc. 1st Int. Conf. on Knowledge Discovery and Data Minging (KDD'95), Montreal, C anada, Aug. 1995:118123
38 N Beckmann, H P Kriegel, R Schneider, B Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In Proc. 1990 ACM-SIGMOD Int . Conf. Management of Data, Atlantic City, NJ, June 1990:322331
39 M Ester, H P Kriegel, X Xu. Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification. In Proc. 4th Int. Symp. on Large Spatial Databases (SSD'95), Portland, Maine, August 1995:6782
40 R Ng, J Han. Efficient and Effective Clustering Method for Spatial Data Mini ng. In Proc. 1994 Int. Conf. Very Large Data Bases, Santiago,Chile,September 19 94:144155
41 W P Yan, P Larson. Eager Aggregation and Lazy Lazy Aggregation. In Proc. 21 th Int. Conf. Very Large Data Bases, Zurich, Switzerland, Sept. 1995:345357
42 HJ Lu, R Setiono, H Liu. Effective Data Mining using Neural Networks. IEEE Transactions on Knowledge and Data Engi
50 Yoon Byungjoo, Lacher R C. Extraction Rules neering 8: 6 (DEC 1996) Page 957961
43 P K Chan, S J Stolfo. Learning Arbiter and Combiner Trees from Partitioned Data for Scaling Machine Learning. In KDD'95, August 1995:3944
44 . ȫ߱仯. ѧ ) 
45 . RBAO޻㷨. ѧ )
46 . ֪ʶKDD. йѧE
47 . ֪ʶKDD. 廪ѧʿվ, : 1997,4
48 Binaghi E. (1192), Empirical Learning for Fuzzy Knowledge Acquisition, Proc . 2nd Int. Conf. Fuzzy Logic & Neural Networks, IIZUKA'92, 1992
49 Fu LiMin. Rule Generation from Neural Networks, IEEE Transactions on Systems , Man and Cybernetics, 1994, 24(8):11141124by Destructive Learning, IEEE, 1994:17661771
51 Ishikawa M. Structural Learning and its Applications to Rule Extraction, IEEE,1994:354359
52 ԬΣ¬. ȡһַͼеӦ. 1996 йԶѧļ(ϲᣩ180186
53 ԬΣ¬. ȡһַ. Ϣ, 1997,26(1):6166
54 Zhou yuanlui, Lu Yuchang. Shi Chunyi Using Neual Nework to Discover Knowled ge from Database (to be published)
55 Zhaohui Zhang, Yuanhui Zhou, Yuchang Lu, Bo Zhang. Extracting Rules from a GA-Pruned Neual Network
ոڣ1998-02-09
