о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



ռݲɾо뷢չ
ʯơ񷽡󡡴
ժҪݲɾоѴӹϵͺݿչռݿռݲɾһзչǰڴռн֪ʶֵļ.ܽ˿ռݲɾеоɹռݲɾϵṹ ѯԼط̽Ŀǰڵͷչ.
ؼʣݿ֪ʶ֣ռݲɾ򣬿ռݿ
ͼţTP311.13
THE RESEARCH AND DEVELOPMENT OF SPATIAL
DATA MINING
SHI Yun, SUN Yu-Fang, and ZUO Chun
(Institute of Software, Chinese Academy of Sciences, Beijing 100080)
AbstractRecent studies have extended the scope of data mining from relational and transactional databases to spatial databases. Spatial data mining, that is knowledge discovery from huge amounts of spatial data, is a prom ising research filed. In this paper, current techniques used in spatial datamining, including the architecture, query language, and related methods, are summarized, and future research directions are discussed.
Key wordsKDD, spatial data mining, spatial database
1
ҵҵлţڹȥʱﶼ˺ݣĿǰ ЩȻҵͷ.˴ͳϢ֪ʶȡ޴ս.ݲɾݿ֪ʶ֣KDDΪһµоµļδڴӴ_ݿзȤġġǰ֪֪ʶ1.
ݲɾоѴӹϵͺݿչռݿ.ռ{ɾǴӴռз֪ʶһзչǰ. ΪռݴңСϢϵͳ(GIS)ýϵͳҽѧͼȶӦռռԶԶԷ.ռݿⱣпռЩռÿռͺͶĿռϵʾ.ռ಻ͬڹϵݿ.˺/ϢͨԸӵĶάռṹ֯ͨռݴȡȡҪռμͿռ֪ʶʾ.ЩʹôӿռвɾϢкܶսԵ2.ռݲɾָǴӿռݿгȡ֪ʶռϵʽش洢ڿռݿеģʽ3ݣռݡֿռͷǿռݼĹϵռ֪ʶ⡢ѯŻռݿ顢Լ򵥾ȷķʽͨȵ.
ܽ˿ռݲɾеоɹռݲɾϵṹѯԼ ط̽Ŀǰڵͷչ.
2ռݲɾϵṹ
ݲɾиָϵṹHanͨݲɾԭDBLEARN/DBMINER4ݡHolsheimer˵Ĳϵṹ5ݡMatheus˵Ķ ϵṹ6.Щϵṹɽչڿռݲɾ.֮£Matheus ϵṹҪͨһЩѾһЩоǲɣϵṹͼ1ʾ.


ͼ1ռݲɾϵṹ
ڶϵṹУûԿƲɾеÿ裨ͼ1֪ʶд洢 ֪ʶռͷǿռ㣬йݿϢ.ɾҪ4ɣDBӿڡ۽ģʽȡ.DBӿڴԴȡݣýӿвѯŻÿռṹRȷиЧ۽жԳȡЩݶģʽʶõģģʽȡֹģʽʹͳѧѧϰݲɾϼ㼸ѧ㷨ֹ͹ϵֵģʽȤ̶ȺҪԣȥԺ֪ʶ. 4ͨнɾĽմû.
3ռݲɾ򷽷
ռݲɾͬһݲɾ.ϵݲɾ㷨ٶǶģڿռ ݿһܻڽɸӰ죬֮Ҳ໥.ˣչͳݲɾռɾԱõطӵĿռͿռ.ռݲɾռݽṹռ㼸ѧеļܶµЧĿռݲɾ򷽷.ԴͳռչصʵЧʡݿϵͳĽϡûϺõؽԼ͵֪ʶϣ7.
ռıŽܻڷࡢࡢռԼۺ ڽĿռݲɾ򷽷Ҫ˿ռݲɾһͼݿĲɾ. 
3.1
3.1.1ռݽṹռͲѯ
ռݲɾ㷨аռӡͼǡڽӲѯȿռ.ڴ ĸЧĿռȡSAMݽṹǿռݲɾһĽ8 .
(1) ռݽṹ
ռݽṹ㡢ߡε.Щݵöά.άĲ k-dRR*.۵RR*.洢RеĶС߽ΣMBR.Rеÿڵ洢һμ.Ҷڵдεı߽ͶεMBRsָ.ڲڵÿһָŮָŮеоεMBRs.
(2) ռ
ռʱ临ӶĿռ֮һ.BrinkhoffһЧĶδ 9ݣR*ͿռڽĿռ.ʹMBRsڽҵཻܵйˣȻִϸļ㣬ཻԱϸ.
KoudasSevcik10S3JSize Separation Spatial JoinռӼݿռвԷֽ⣬ڵռݼвڿռʱռݼϵĿռ.
Theodoridisˣ11ռݿӲѯĳɱģͣÿռݽṹֶ֧άݵӲѯڿռѯŻ.
һҪĿռǵͼǣڵϢϵͳΪҪ.
(3) ռѯ
ArefSamet12ռѯŻԣΪռݿһΪSANDռͷǿռݣϵṹһʹÿռչĹϵݿģͣ13.ϵṹṩռݿĿռҲṩǿռԲѯ.
3.1.2ͳѧռ
ͳƷǷռݵõķ.ͳƷнǿۻӵд㷨 Ż.ܹЧֵݣͨᵼռʵģ.Ȼ÷ͳƲؼ裬ʵڿռݿռͨصģռڽӰ죬ּ裬ͻ.öпռ䱣Krigingعģĳ̶ֳϼ.ǣʹģ̹ڸӣֻɾ൱֪ʶͳѧרɣնûԲøüռ.⣬ͳƷԷԹܺܺýģַݵϲԴȫȷݣĴ۽ϸ.ף1һЩԿ˷ ͳѧռȱ.
3.2ڷķ
ݿеݺͶԭʼĸΰϸϢҪݵļϽ иԽϸߵĸչʾ.ڷ֪ʶּٶ֪ʶԸεʽ.οרṩݷԶ.ռݿпԶ͵ĸΣǿռͿռ.Han and Fu4һЧݷԵĹ.ִһݲɾѯɼݿݵļϣȻͨΣڽϸ߸ϸռͷǿռݼķϵԽݷ.Ľ÷ϵʽִнһOLAPҲӳΪͼпӻʾܴгȡб.Luˣ2ݽԵĹչռݿ⣬㷨ռ֧䷺ͷǿռ ֧䷺.
(1) ռ֧䷺㷨
㷨ø߽νռ.ȣݿռκϲռ򣬵õ һŵͼ.Ȼ󣬲ԵĹɼÿķǿռ.ѯĽÿxνʵȡ.
(2) ǿռ֧䷺㷨
㷨ȶԷǿռԵɣ䷺ߵĸ.Ȼ󣬽ͬ ķֵϲһ𣬿ڽԾвͬǿռС.ѯĽɰĵͼЩͬһεķǿռ.
3.3ھķ
ռݾһĶάݼвþԱʶ࣬ɴݼ ֲģʽ.
(1) ľ෽CLARANS
CLARANSClustering Large Applications based upon RANdomized Search㷨NgH an14̿ԱʾΪһͼͼеÿڵ㶼ǱڵĽ.滻һĵõľΪǰھ.ԵھӵĿɲmaxneighbor.ҵһõھӣĵھӽڵ㣬¿ʼ̣ڵǰľһֲ.ҵһֲźѡһµĽڵѰµľֲ.ֲŵĿnumlocal.ԿCLARANSеռ䣬ҲκξĲ.CLARANSÿεļ㸴ӶԹϵ.CLARANSҲɼ뿪Ĳ֣粻κξĵ.CLARANSĿռݾ㷨Ҳ֣ռ֧㷨ͷǿռ֧㷨.
CLARANSȱҪҪĶԤȶڴԷǳĿռݿ ǲ.
(2) CLARANS۽
߾㷨Чʣĳᵼ²ľ.Esterˣ15ÿռݽṹ߳㷨.㷨R*ҶڵĶ. ΪҶڵн洢ڽĵ㣬ʧľСʵԼΪ1.5%3.2%ٶȴԼ50.һּR*ṹڶִм㣬߾Ч.
۽ͨRڴݣȱRĹ׶Ҫķ൱ļ.
(3) ƽ෨BIRCH
Zhangˣ16ƽ෨BIRCHBalanced Iterative Reducing and ClusteringԽ۽ѵ.һֽΪʽ෽ܸڴôСԶڴҪ.clustering feature;CF-tree.
CFһԪ飬ܽһظйϢӶʹһصıʾܽΪӦһûҪþһʾ.һN㡢άΪdһظ{Xi}ظľɱʾΪУNǵĸNԺͣ=صģSSNƽͣصֱСSSԽСص۵Խ.
һƽ.ֱǣ֦Ӻʹֱ.֦ ӹ涨ÿڵŮֱ˶һصֱСƣSS̫󣬷ܾΪһ.Ҷӽڵϴ洢Ůľĺͣ˸ýڵܽŮϢ.
Զ̬죬˲Ҫһζڴ棬Դ.µǲ뵽ݾҶ.ʹøҶӵֱС˴ֱҪѸҶӻҶӷѣֱҶܹ뵽жͬʱֱ.µϢͿԴҶһֱݵ¼Ҷӵĸȵľֵ.
ͨıֱƴС޸ľĴС.ֱֵԽСҪ ƶȴ󣩣Խ󣻷֮ԽС.ˣ洢ڴ治ʱ԰ѴֱֵΪϴֵȻ¹عʱֱӴԭҶӼ㣬Ҫ¶.
BIRCH㷨õ㷨ԡ˳ԼϺõľЧ.÷ һͨüڸ־㷨.
(4) ԴӦõĻܶȵĿռ㷨DBSCAN
DBSCANDensity Based Spatial Clustering of Applications with Noise17ݻھܶȵĸִĿռݿ״ľ.㷨Чʽϸߣ㷨ִǰֵ.
(5) Ϳռݿھֲľ㷨DBCLASD
Xuˣ18Ϳռݿھֲľ㷨Distribution Based Clustering of Large Spatial DatabasesCLARANS㷨ȣԷָ״ľࣻDBSCANȣҪκ.DBCLASDЧʽCLARANS㷨DBSCAN㷨֮䣬ӽDBSCAN㷨.
(6) Ŵ㷨пռ
һľ㷨νġɽѰֲţVladimirŴ㷨 ʽѰҾĵ㣬õľ֤ͨҪ.
3.4ڷķ
Ŀǰռ{од𲽽׶.Esterһֿռ෽19ݣ÷ID3㷨ʹͼĸ׼ڷķǿռԼڽλضռϵԡνʺͺ.÷ȱûзڽǿռԵľۺֵʵһڽĳԵľۺֵһڽɸڶӦԵľۺֵͬôԾӦΪ.⣬㷨ҲûнԷܻɵľ.ң㷨ûпǷǿռͿռֵпܴڵĸ.
NgYuһַԳȡרͼϾǿġġбԵ20ݣֵĶ.๫ĹУ㷨ѡЩֵֵƵ⣻бĹУ㷨ѡõб.㷨ڷרͼֵ.
KoperskiHanEster˵㷨19Ӧ˸Ľ21ݣʹüʱ临ӶȽ.ǻھķ㷨ʺϴвϢ.ռݷ׼ ݼĿռϵĳѵݼռԼпȱʧ.ݳ˲һ¡㷨ܻޏ֣ͻӰ㷨Ԥ׼ȷ.þռ㷨ܺܺõֵռϵڷӰ.Կռݷķһо.
3.5ڿռķ
ռǽһռռ.Agrawalĸ Ϊ˲ɾ͵ݿ.Koperski˽չռݿ3.ռʽXY(c%)XYǿռǿռνʵļϣc%ǹĿŶ.ռν3ʽʾ˹ϵνʣཻǵȣʾռ䷽νʣ綫ҵȣʾνʣӽԶ.
ڴݿУܴڴĶĹд󲿷ֻ󣬻߹ ĿŶȽϵ.ռʹֵСֶ֧ȺСŶȣԹ˳Ĺ;еͿŶȵĹ.ڶǿռĲֵͬͬΪʹֵͬڵ͵ĸϿҲȤĹԭǴʱͬνʵĶĿ൱.
3.6ۺڽ
ۺڽǸݾ߽Ͷ߽֮ľ룬ԾеļڽĽӽ ȵĶ.KnorrNg22CRHCΪԲRǾΣH͹㷨ܿٲҾڽ.㷨вöڽ𽥼ٺѡ.ȻΧԲȻʹþȥнϴۺϾĶ󣬽żеĵ˳ÿ͹߽ľۺڽ.㷨ѾۺڽĶʾе㼯С롢ƽ롢Լֵָ뷶Χڵĵı.ʵ֤㷨CRHЧʺܸ.
3.7ɾͼݿķ
ͼݿһĿռݿ⣬ݼȫͼͼƬ.ͼݿңСҽѧͼӦãͨդʽʾդһ׷Χͼܶ. ͼݿĲɾԿǿռݲɾһ֣Ҫͼ.гⷽһЩо.
(1) POSS-II Second Palomar Observatory Sky Survey
FayyadʹþԴԼ3TBͼеϵз23.ͼȾͲͼϵͳFOCASԤѡͼҪءܶȡȵĻ.ѧѵݼеĶз.ַ࣬㷨ѵ.ѧϰ㷨õľҵһΪǿСĹ򼯺.÷רѧӦ.
(2) Magellanо
Magellanо24ݷǱԼ30,000߾ȵ״ͼĿΪʶɽһֹԼ10.ϵͳ3ɣݾ۽ȡͷѧϰ.ͬݾ۽һݾ۽ͨصܶƵصܶȵƽֵȽϣʶͼпܰɽĲ֣ϵͳЧ.ȡгȡȤ.ʹԵ任һģʽʶ𷽷ΪЩȻеĿɱԺϲ.ҾȷɽԷǳѣ˽ɽͼľֽΪֵΪɽ.ѧϰþɽͿɽĶ.
(3) ݵʱղѯCONQUEST
Shekˣ25һֲʽвѯͷCONQUESTCONtent-based QUE rying in Space and Timeڲɾѧդݿ.CONQUESTդݿ 򹤾ߵݼеʱвкͷֲʽ.ϵͳ Ӵݼгȡӵʱն.CONQUESTһϵеĲڵѧѯ жͳȡ.
4ռݲɾѯ
ĿǰΪֹûжԿռݲɾѯSDMQLSpatial Data Mining Query LanguagĶ. Hanˣ26Ϊ˲ɾռݿһֵݲɾѯGMQLGeo-Mining Query LanguageǶԿռSQLչɹӦڿռݲɾϵͳԭGeoMiner.GMQLΪƶSDMQLĻԽһ綨SDMQLԵĻԭ.
SDMQLָԭӦΪ
(1) ڿռݲɾӦ˵ڲɾݼ
(2) ڿռݲɾӦ˵Ҫɾ֪ʶࣻ
(3) ɾӦÿصı֪ʶ
(?) ɾӦýϸĻθ
(5) Ӧܹ˵ֵָʹÿع˵ЩǺ˸Ȥ֪ʶ
(6) ӦSQL﷨Ӧڸ߼ԵˮƽϽݲɾϵѯSQL Ȼں.
5ռݲɾϵͳԭGeoMiner
ôSimonѧһռݲɾϵͳԭGeoMiner26.ϵͳڿռݿ⽨ģʹSAND13ϵṹģ飺ռ幹ģ顢ռOLAPģͿռݲɾģ飬õĿռݲɾGMQL.Ŀǰܲɾ3͵Ĺб͹. GeoMinerϵṹͼ2ʾ4֣ͼû棬ڽнʽزɾʾɾڷģ鼯ϣ3ʵֵ֪ʶģԼ4ƻʵֵģ(ֱʵ߿߿ʾ)ۿռݿMapInfoESRI/Oracle SDEInformix-IllustraԼռݿ棻ܴ洢ǿռݡռݺ͸εݿ֪ʶ.


ͼ2GeoMiner ϵṹ
6ռݲɾδ
ռݲɾһǳǰкܶоҪ֣̽ҲǸ δ.
(1) Object-OrientedOOĿռݿнݲɾ
ĿǰʵӦõĿռݲɾ򷽷ٶռݿвõչĹϵģͣ ϵݿⲢܺܺõشռ.оָOOģͱȴͳĹϵģͻչϵģ͸ʺϴռݣΡκ͸ӵĿռOOݿкȻؽģ.ˣԿǽĿռݿԽݲɾ.ҪʹOOƿռݿ⣬Լݿвɾ֪ʶ.ĿǰOOݿ⼼죬ڿռݲɾпOOһмǱ.ף27ݡ28ݶԴ˳̽.
(2) вȷԲɾ
֤ͼݿĲɾԼȷԽģݿķ.Bell ˣ29֤֤۱ȴͳĸģͣ籴Ҷ˹ȷвȷԽģЧҪ.⣬ɿͨͳѧģ߼ʹֲڼԴȷԺͲϢдչ.
(3) ξ༼
ĿǰռĽоڶԵľ࣬δǴز Ķľ࣬ξ.
(4) άӻ
ֹЧķʽǽͼοӲ.άݿӻӦо30ݣάӻһ򣬿ɿǲüͼѧеһЩӻ.
(5) ڷĿռݲɾҪһĿأԴרͼͶεĽ ʽɾ򣬲ռռȡݲֿ⼼Ч.
(6) ռݷҵЧĿռ෽ԴвϢ. 
(7) ģʽԵĲɾԼԪָĿռݲɾ̽.
(8) ռݲɾѯSDMQLϸƺͱ׼.
(9) ңͼҪݲɾ򷽷ԼƵͼƬԼ ֲͬĹϵ. 
7
ͨĶԿռݲɾۣԿռݲɾһ˶ֳսԵ ǰؼΪռϢϵͳ֪ʶֵƽܻռϢϵͳķչ.
*õҡ 306(Ŀ863306-ZD-07-4).
߼飺ʯƣŮ 197211ʿоҪоΪݿ֪ʶ֡ռݲɾ.
񷽣У1947оԱʿʦҪzΪݿӦϵͳ ϵͳϢ.
󴺣У1959оԱҪоΪ ݿӦϵͳݿ֪ʶ.
ߵλйѧԺо100080
ο
1Fayyad U, Piatetsky-Shapiro et al. From data mining to knowledge discovery: An overview. In: Advances in Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI/MIT Press, 1996
2Lu W, Han J et al. Discovery of general knowledge in large spatial databases. In: ProcFar East Workshop on Geographic Information Systems. Singapore, 1993. 275289
3Koperski K, Han J. Discovery of spatial association rules in geographic information databases. In: Proc 4th Int'l Symp on Large Spatial Databases(SSD '95), Portland, Maine, 1995. 4766
4Han J, Fu Y. Exploration of the power of attribute-oriented induction in data mining. In: Advances in Knowledge Discovery and Data Mining. Menlo Park , CA: AAAI/MIT Press, 1996
5Holsheimer M, Kersten M. Architectural support for data mining. CWI Tech Rep: CS-R9429, 1994
6Matheus C J, Chan P K et al. Systems for knowledge discovery in databases. IEEE Trans on Knowledge and Data Engineering, 1993, 5(5): 903913
7Koperski K, Han J, Adhikary J. Mining knowledge in geographical data,Communications of ACM, 1999
8Guting R H. An introduction to spatial database systems. VLDB Journal, 1994, 3(4): 357400
9Brinkhoff T, Kriegel H P et al. Efficient processing of spatial joins using R-trees. In: Proc AC?-SIGMOD Conf Management of Data, Washington, 1993. 237246
10Koudas N, Sevcik K C. Size separation spatial join. In: Proc ACM-SIGMO D Conf Management of Data, 1997. 324335
11Theodoridis Y, Stefanakis E et al. Cost models for join queries in spatial databases. In: Proc of ICDE'98, Florida, USA, 1998. 476483
12Aref W G, Samet H. Optimization strategies for spatial query processing. In: Proc 17th Int'l Conf VLDB, Barcelona, Spain, 1991. 8190
13Aref W G, Samet H. Extending DBMS with spatial operations. In: Proc 2nd Symp SSD'91, Zurich, Switzerland, 1991. 299318
14Ng R, Han J. Efficient and effective clustering method for spatial datamining. In: Proc of Int'l Conf VLDB, San Francisco, CA: Morgan Kaufmann, 1994. 144155
15Ester M, Kriegel H P et al. Knowledge discovery in large spatial d atabases: Focusing techniques for efficient class identification. In: Advances i n Spatial Databases, Proc of 4th Symp SSD'95, Berlin: Springer-Verlag, 1995. 67 82
16Zhang T et al. BIRCH: An efficient data clustering method for very large databases. In: Proc of ACM-SIGMOD Int'l Conf on Man?gement of Data. ACM, New York, 1996. 103114
17Ester M, Kriegel H P et al. A density-based algorithm for discover ing clusters in large spatial databases with noise. In: Proc 2nd Int'l Conf on K nowledge Discovery and Data Mining. Oregon: AAAI Press, 1996
18Xu X et al. A distribution-based clustering algorithm for mining in large spatial databases. In: Proc of ICDE'98, Florida, USA, 1998. 476483
19Ester M, Kriegel H P et al. Spatial data mining: A database approac h. In: Proc Int'l Symp on Large Spatial Databases (SSD'97), Berlin, Germany, 199 7. 4766
20Ng R T, Yu Y. Discovering strong, common and discriminating characteris tics of clusters from thematic maps. In: Proc of the 11th Annual Symp on Geograp hic Information Systems. 1997. 392394
21Koperski K, Han J et al. An efficient two-step method for classifi cation of spatial data, In: Proc Int'l Symp on Spatial Data Handling SDH'98, Van couver, BC, Canada, 1998
22Knorr E M, Ng R T. Finding aggregate proximity relationships and common alities in spatial data mining. IEEE Trans Knowledge and Data Eng, 8(6): 884897 
23Fayyad U M, Djorgovski S G et al. Automating the analysis and catal oging of sky surveys. Advances in Knowledge Discovery and Data Mining. Menlo Par k, CA: AAAI/ MIT Press, 1996
24Fayyad U M, Smyth P. Image database exploration: Progress and challenge s. In: Proc of Knowledge Discovery in Databases Workshop. Menlo Park, CA: AAAI P ress, 1993. 1427
25Shek E C et al. Scalable exploratory data mining of distributed geo scientific data. In: Proc of the Second Int'l Conf on Knowledge Discovery and D ata Mining. Menlo Park, CA: AAAI Press, 1996. 3237
26Han J et al. A system prototype for spatial data mining. In: Proc A CM-SIGMOD Conf Management of Data, AZ, USA, 1997. 324335
27Mohan L, Koshyap R L. An object-oriented knowledge representation for spatial information. IEEE Trans on Software Engineering, 1988, 14(5): 675681
28Han J, Nishio S, Kawano H. Knowledge discovery in object-oriented and active databases. In: Fuchi F, Yokoi T eds. Knowledge Building and Knowledge Sharing, Ohmsha/IOS Press, 1994. 221230
29Bell D A, Anand S S, Shapcott C M. Database mining in spatial databases . International Workshop on Spatio-Temporal Databases, 1994
30Keim D, Kriegel H P, Seidl T. Supporting data mining of large databases by visual feedback queries. In: Proc 10th of Int'l Conf on Data Engineering, Ho uston, TX, 1994. 302313 
ԭյڣ1999-02-12޸ĸյڣ1999-08-20.
