（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）基于空間數(shù)據(jù)庫的數(shù)據(jù)挖掘方法研究.pdf

山東師范大學(xué)碩士學(xué)位論文 摘要 隨著空間數(shù)據(jù)獲取技術(shù)的快速發(fā)展，空間數(shù)據(jù)量急劇增加。為了充分地利用空間數(shù) 據(jù)庫中的資源，在大量的數(shù)據(jù)中獲取有價值的信息，提出了空間數(shù)據(jù)挖掘技術(shù)?？臻g數(shù) 據(jù)挖掘技術(shù)可以幫助人們理解空間數(shù)據(jù)，獲取空間數(shù)據(jù)之間的內(nèi)在關(guān)系。文中對空間數(shù) 據(jù)庫以及空間數(shù)據(jù)挖掘方面的基礎(chǔ)知識咆括空間數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)模型、索 引技術(shù)，以及空間數(shù)據(jù)挖掘的基本步驟、方法等進(jìn)行了詳細(xì)的介紹，作為進(jìn)行空間聚類 研究的理論基礎(chǔ)。 聚類分析是空間數(shù)據(jù)挖掘的一個重要的研究方向，它通過度量空間數(shù)據(jù)之間的相似 性將空間數(shù)據(jù)庫劃分為不同的簇或類，使得同簇中的對象盡可能相似，而不同簇之間的 對象盡可能不同。聚類分析在現(xiàn)實生活中用途廣泛，可以用在選址、客戶群分類等方面， 幫助投資者進(jìn)行決策，并帶來盡可能大的效益。因此，聚類具有重大的研究意義。 目前，已經(jīng)有許多比較成熟的聚類算法，如d b s c a n 算法、c u r e 算法、c l a r a n s 算法等。這些算法是空間聚類的經(jīng)典算法，但仍在某些方面存在一定的問題。本文的研 究重點就是在已有算法的基礎(chǔ)上，對算法進(jìn)行改進(jìn)，以提高算法效率。本文針對普通聚 類和帶障礙約束的聚類，分別提出了一種改進(jìn)算法。 算法1 ：對d b s c a n 算法的改進(jìn)。d b s c a n 算法需要判斷每個對象是否是核心點， 這種判斷會占據(jù)大量的i o 開銷，是限制算法效率的瓶頸。、本文的算法不需要對每個點 進(jìn)行核心點判斷，算法在尋找連通區(qū)域的過程中，每次循環(huán)選取一個沒有聚類標(biāo)識的點： 如果這個點是核心點，并且其核心區(qū)域內(nèi)的點已經(jīng)有其他的聚類標(biāo)識，則將該點及其核 心區(qū)域的點的聚類標(biāo)識設(shè)置為其中的最小值；若該點不是核心點，則選擇下一個點繼續(xù) 判斷。這種算法不僅大大減少了需要判斷的核心點的數(shù)量，而且在尋找連通區(qū)域的同時 直接將聚類合并，會大大提高算法的時間效率。 算法2 ：基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的空間聚類算法。該算法主要借鑒數(shù)學(xué)形態(tài) 學(xué)聚類一m m c 算法的基本思想，在此基礎(chǔ)上加入了對障礙約束的處理。該算法與 d b c l u c 算法不同，不需要通過每兩個對象的連線是否與障礙物相交來判斷兩對象是否 屬于同一個類，而是借助于結(jié)構(gòu)元素，僅僅對受障礙物影響的對象( 即障礙物附近的點) 進(jìn)行判斷。從數(shù)據(jù)點集中選取一個點作為結(jié)構(gòu)元素的圓心進(jìn)行膨脹運算，若結(jié)構(gòu)元素與 障礙物相交，則將位于圓心的點與該點膨脹運算所包含的點分別連線，對于連線與障礙 物相交的點，將其f l a g 值設(shè)為f a l s e ，說明該點位于障礙物的另一側(cè)，與圓心點不屬于 1 山東師范大學(xué)碩士學(xué)位論文 同一個連通區(qū)域：對于連線不與障礙物相交的點賦予與圓心位置的點同樣的聚類標(biāo)識。 經(jīng)過分析，算法的效率優(yōu)于其他算法。在文章的最后，進(jìn)行了數(shù)據(jù)實驗，進(jìn)一步驗證了 算法的正確性和有效性。 本文對空間數(shù)據(jù)庫、空間數(shù)據(jù)挖掘、空間聚類技術(shù)進(jìn)行了探討，一步一步深入，最 后提出了改進(jìn)的聚類算法。在后續(xù)的研究工作中，作者需要閱讀大量的聚類技術(shù)方面的 書籍及文章，提出更快、更易于理解的算法，并應(yīng)用在實際的生產(chǎn)、生活中，輔助決策 者做出正確的決策，獲得更好的效益。 關(guān)鍵詞：空間數(shù)據(jù)庫；空間數(shù)據(jù)挖掘；空間聚類：基于密度的空間聚類算法；障礙約束 中圖分類號：t p 3 9 3 2 山東師范大學(xué)碩士學(xué)位論文 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fs p a t i a ld a t ao b t a i n e dt e c h n o l o g y , s p a t i a ld a t ai n c r e a s eu p r a p i d l y s p a t a i ld a t am i n i n gt e c h n o l o g yw a sm e n t i o n e di no r d e rt ou s et h er e s o u r c e si nt h e s p a t a i ld a t a b a s e se n o u g h l y s p a t a i ld a t am i n i n gt e c h n o l o g yc o u l dh e l pp e o p l eu n d e r s t a n d i n g s p a t i a ld a t aa n dp i c k i n gu pr e l a t i o n sb e t w e e ns p a t i a ld a t a i nt h sp a p e r , w ei n t r o d u c e t h eb a s i c t h e o r yo fs p a t i a ld a t a b a s ea n ds p a t i a ld a t am i n i n g ，i n c l u d et h es p a t i a ld a t as t r u c t r u e ，s p a t i a l d a t am o d e l ，s p a t i a ld a t ai n d e xt e c h n o l o g ya n dt h es t e p s ，m e t h o d so fs p a t i a ld a t am i n i n g 砧lo f t h e s ea r et h eb a s i ct h e o r yo fc l u s t e ra l g o r i t h m c l u s t e r i n ga n a l y s i si sav e r yi m p o r t a n tf i e l di ns p a t i a ld a t am i n i n ga r e a i td e p e n d so n m e a s u r et h es i m i l a r i t yb e t w e e ns p a t i a ld a t a si n t om e a n i n g f u ls u b c l a s s e ss ot h a tt h em e m b e r s o fac l u s t e ra l ea ss i m i l a ra sp o s s i b l ew h e r e a st h em e m b e r so fd i f f e r e n tc l u s t e r sd i f f e ra s m u c ha sp o s s i b l e s p a t i a lc l u s t e r i n gi sw i d e l yu s e di nd a i l yl i f e i tc a l lb eu s e di nl o c a t i o n s e l e c t i o n ，c u s t o m e rc l a s s i f i c a t i o na n ds oo n i tc a nh e l pi n v e s t o r s d e c i s i o n m a k i n g ，a n db r i n g b e n e f i ta sm u c ha sp o s s i b l e i ns y n t h e s i s ，c l u s t e r i n gh a si m p o r t a n tr e s e a r c hs i g n i f i c a n c e n o w , t h e r ea r em a n ym a t u r ec l u s t e r i n ga l g o r i t h m s ，s u c ha sd b s c a na l g o r i t h m ，c u r e a l g o r i t h m ，c l a r a n sa l g o r i t h ma n ds oo n t h e s ea r ec l a s s i ca l g o r i t h m si nc l u s t e r i n gf i l e d ，b u t t h e r ea r es t i l lm a n yc h a l l e n g e s t h em o s ti m p o r t a n tr e s e r a c hi nt h i sp a p e ri st oi m p r o v et h e e f f i c i e n c yo fc l u s t e r i n ga l g o r i t h m s i nt h i sp a p e r , w ei n t r o d u c et w oi m p r o v e da l g o r i t h m sf o r t h eg e n e r a lc l u s t e r i n ga n df o rt h ec l u s t e r i n gw i t ho b s t a c l ec o n s t r a i n t s a l g o r i t h m1 - i m p o v et h ed b s c a na l g o r i t h m d b s c a na l g o r i t h mr e p e a t e d l yp i c k s e v e r yp o i n t sa n de x a m i n i n gw h e t h e ri ti sac o r ep o i n t ，t h ei os p e n d i n go f t h i ss t e pi sv e r yb i g a n dt h es t e pl i m i t st h ea l g o r i t h me f f i c i e n c y t h ei m p o v e da l g o r i t h mn e e d n tt oj u d g ew h e t h e r e a c ho ft h ep o i n ti st h ec o r ep o i n t i nt h es e a r c hf o rr e g i o n a lc o n n e c t i v i t y , e a c hc y c l es e l e c ta p o i n tw i t h o u tam a r k ：i ft h ep o i n ti sac o r ep o i n t ，a n di t se p s - r e g i o nh a so t h e rp o i n t sw h i c h h a s o t h e rm a r k s ，t h e na l lt h ep o i n t sm a r kt h em i n i m u m ；i fn o t ，s e l e c tt h en e x tp o i n tt oc h a r g e t h e a l g o r i t h mn o to n l yr e d u c et h ea m o u n to f t h ep o i n tw h i c hn e e dt oj u d g e ，b u ta l s oi m p r o v et h e e f f i c i e n c y a l g o r i t h m2 ：c l u s t e r i n ga l g o r i t h mb a s e do nm a t h e m a t i c a lm o r p h o l o g yi nt h ep r e s e n c e o fo b s t a c l e s t h ea l g o r i t h mb a s e do nt h ei d e ao ft h ea l g o t i t h mo fm m c ，a n da d d i n ga c o n s t r a i n tt od e a lw i t ho b s t a c l e s t h ea l g o t i t h r ni sd i f f e r e n tf r o mt h ed b c i u c ，i ti sn e e dn o tt o c o n n e c te a c ht w op o i n t st oj u d g ew h e t h e rt h ep o i n t sa r ei nas a m ec l a s so rs e p a r a t e db y 3 山東師范大學(xué)碩士學(xué)位論文 o b s t a c l e s i tu s e das t r u c t u r a le l e m e n t ，d e a lw i t hp o i n t sw h i c ha r ea f f e c t e db yt h eo b s t a c l e s o n l y i ft h es t r u c t u r a le l e m e n ti sc r o s s e dw i t ho n eo b s t a c l e ，t h e nc o n n e c tt h ec e n t e rp o i n ta n d o t h e rp o i n t si nt h ec i r c l e ，i fo n el i n ei sc r o s s e dw i t ht h eo b s t a c l e ，t h e nt a k ei t sf l a ga sf a l s e ，i t s s a i dt h a tt h ep o 硫i si nt h eo t h e rs i d eo ft h eo b s t a c l e ；i fn o t ，t h ep o 血i si nt h es a m ec l a s sw i t h t h ec e n t e rp o i n t a f t e ra n a l y s i s ，t h ee f f i c i e n c yo fa l g o r i t h mi ss u p e r i o rt oo t h e r a l g o r i t h m s i n t h ee n d ，w et a k ead a t ae x p e r i m e n t ，v e r i f i e dt h ec o r r e c t n e s sa n de f f e c t i v e n e s so f a l g o r i t h m i nt h i s p a p e r , w e d i s c u s ss p a t i a l d a t a b a s e ，s p a t i a ld a t a b a s em i n i n g ，s p a t i a ld a t a b a s e c l u s t e r i n gs t e pb ys t e p ，a n dt h e np u tf o r w a r da ni m p r o v e dc l u s t e r i n ga l g o r i t h m i nt h ef u t u r e r e s e a r c hw o r k ，i n e e dt or e a da l a r g en u m b e r o fc l u s t e r i n gt e c h n o l o g yb o o k sa n da r t i c l e s ，m a d e f a s t e r , e a s i e ru n d e r s t a n d i n ga l g o r i t h m s ，a n du s e di nr e a l p r o d u c t i o n , l i f e ，t os u p p o r t d e c i s i o n m a k e r $ t oo b t a i nb e t t e rr e s u l t s k e y w o r d s ：s p a t i a ld a t a b a s e ；s p a t i a ld a t am i n i n g ；s p a t i a ld a t ac l u s t e r ； s p a t i a lc l u s t e rb a s e do nd e n s i t y ；o b s t a c l e c l a s s i 6 c a t i o n ：t p 3 9 3 4 獨創(chuàng)聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。 據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其它人已經(jīng)發(fā)表或撰寫過 的研究成果，也不包含為獲得( 注：如沒有其它需要特別聲明的，本欄可空) 或其它教育機(jī)構(gòu)的學(xué)位或證書使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn) 均已在論文中作了明確的說明并表示謝意。 學(xué)位論文作者簽名：0 ，厶娟 導(dǎo)師簽字： 孥 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家有關(guān) 部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)學(xué)?？梢詫W(xué)位論 文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、 匯編學(xué)位論文。( 保密的學(xué)位論文在解密后適用本授權(quán)書) = 篡撬日三：2 0 0 磐9 剛?cè)?簽字r 期：2 0 07 年月舊日簽字日期： 。年彳月7 日 山東師范大學(xué)碩士學(xué)位論文 1 。1 引言 第一章緒論 由于雷達(dá)、紅外、光電、衛(wèi)星、電視攝像、電子顯微成像、c t 成像等各種宏觀與 微觀傳感器的使用，空間數(shù)據(jù)的數(shù)量、大小和復(fù)雜性都在飛快地增長，已經(jīng)遠(yuǎn)遠(yuǎn)超出了 人們的解譯能力。終端用戶不可能詳細(xì)地分析所有數(shù)據(jù)，并提取感興趣的空間知識，致 使“空間數(shù)據(jù)爆炸但知識貧乏 現(xiàn)象的出現(xiàn)【l 】。因此，利用空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn) ( s d m k d ，s p m i a ls a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 從空間數(shù)據(jù)庫中自動或半自動 地挖掘事先未知卻潛在有用的空間模式變得十分必要。 1 9 9 4 年，在加拿大渥太華舉行的g i s 國際學(xué)術(shù)會議上，李德仁院士首次提出了空 間數(shù)據(jù)挖掘概念。從此，空間數(shù)據(jù)挖掘研究全面展開。目前，許多研究人員除借鑒數(shù)據(jù) 挖掘已有的理論方法之外，主要針對空間數(shù)據(jù)的數(shù)據(jù)量大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜以及多維性等 特點進(jìn)行研究，試圖提高算法運行的時間效率和空間效率。本文的研究目的就是通過分 析已有的空間聚類算法，對算法進(jìn)行改進(jìn)，提高空間數(shù)據(jù)挖掘的時間效率和空間效率p j 。 1 2 國內(nèi)外研究現(xiàn)狀及研究方向 目前，國內(nèi)外對數(shù)據(jù)挖掘與知識發(fā)現(xiàn)方面的研究，無論是在學(xué)術(shù)上，還是在實踐中 都取得了很大的突破。然而，由于空間數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫的特點不同，傳統(tǒng)的數(shù)據(jù)挖 掘方法并不完全適用于空間數(shù)據(jù)庫，空間數(shù)據(jù)挖掘技術(shù)尚存在很多需要研究、改進(jìn)的方 面，正是這些需求指引著空間數(shù)據(jù)挖掘技術(shù)不斷向前發(fā)展。 1 2 1 研究現(xiàn)狀 空間數(shù)據(jù)挖掘作為數(shù)據(jù)挖掘的一個分支，發(fā)展歷史較短，但近幾年己成為國際研究 的一個熱點，國外開展這方面的研究較早于國內(nèi)。 加拿大的西蒙弗雷( s i m o n f r a s e r ) 大學(xué)、德國的慕尼黑大學(xué)、芬蘭赫爾辛基大學(xué)以及 美國、澳大利亞等國家的許多大學(xué)和研究所，都有較為著名的研究成果報道。這些研究 的重點是提高原有數(shù)據(jù)挖掘算法在空間數(shù)據(jù)庫上的執(zhí)行效率【3 】。 在一些數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的國際會議中，空間數(shù)據(jù)挖掘逐漸成為重要的研究主題 之一。由美國人工智能協(xié)會( a a a i ) 舉辦的國際k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g f k m d k ) 學(xué)術(shù)會議，關(guān)于空間數(shù)據(jù)挖掘的論文數(shù)量不斷增長。目前，各種規(guī)模的學(xué)術(shù)會 議都已經(jīng)把空間數(shù)據(jù)挖掘作為一個重要的研究課題。此外，d a t am i n i n g 、a d v a n c e d s p a t i md a t a b a s e s 、v e r yl a r g ed a t a b a s e s 、i n t e r n a t i o n a ls y m p o s i u mo nd i g i t a l e a r t h 、 a c m 、i f i s 和s i g m o d 等國際學(xué)術(shù)會議，空間數(shù)據(jù)挖掘已經(jīng)成為關(guān)注的熱點。k l u w e r p u b l i c a t i o n 、s p r i n g e r - v e r l a g 、a c a d e m i cp r e s s 、w i tp r e s s 等國際著名的出版公司也開始出 山東師范大學(xué)碩士學(xué)位論文 版發(fā)行空間數(shù)據(jù)挖掘的學(xué)術(shù)期刊、專著或者論文集。 在中國，武漢大學(xué)、中科院地理所資源與環(huán)境信息系統(tǒng)國家重點實驗室、中科院遙 感所、中科院軟件所、中國測繪科學(xué)研究院等，都開展了空間數(shù)據(jù)挖掘的研究。武漢大 學(xué)的李德仁教授提出從空間數(shù)據(jù)庫可以發(fā)現(xiàn)包括幾何信息、空間關(guān)系、幾何性質(zhì)與屬性 之間的關(guān)系、面向?qū)ο笾R等。 空間數(shù)據(jù)挖掘可以應(yīng)用在城市管理、經(jīng)營效益分析、空間決策支持等各個領(lǐng)域，正 在引起越來越多的研究與關(guān)注。 1 2 2 研究方向 空間數(shù)據(jù)挖掘不同于數(shù)據(jù)挖掘，起步較晚，且空間數(shù)據(jù)具有數(shù)據(jù)量巨大、數(shù)據(jù)類型 復(fù)雜、多維性等特點。對它的研究目前主要集中在以下幾個方面【l ，3 4 】： 1 、空間數(shù)據(jù)挖掘與經(jīng)典數(shù)據(jù)挖掘的比較 空間數(shù)據(jù)中的部分空間關(guān)系可否轉(zhuǎn)換為傳統(tǒng)的數(shù)據(jù)列，以便使用經(jīng)典數(shù)據(jù)挖掘技術(shù) 進(jìn)行挖掘? 如果可以，哪些空間關(guān)系可以轉(zhuǎn)化，哪些不可以? 這將是未來空間數(shù)據(jù)挖掘 的一個研究方向。 2 、空間數(shù)據(jù)的預(yù)處理 空間數(shù)據(jù)本身的復(fù)雜性以及數(shù)據(jù)采集過程中設(shè)備、人員操作的誤差，決定了空間數(shù) 據(jù)存在大量的缺陷。為了避免“g a r b a g ei n ，g a r b a g eo u t ，在進(jìn)行數(shù)據(jù)挖掘之前，需要 對原始數(shù)據(jù)進(jìn)行預(yù)處理：首先進(jìn)行屬性篩選，去除對結(jié)果影響較小的屬性數(shù)據(jù)，然后進(jìn) 行數(shù)據(jù)清理，遺漏數(shù)據(jù)修復(fù)等。這些工作是空間數(shù)據(jù)挖掘能夠得到精準(zhǔn)結(jié)果的保障； 3 、算法效率的提高 對任何一個算法來說，提高效率都是研究者追求的一個重要目標(biāo)?？臻g數(shù)據(jù)的復(fù)雜 性和海量性的特點使得空間數(shù)據(jù)挖掘比經(jīng)典數(shù)據(jù)挖掘更加耗時，同時占用的存儲空間也 更大，所以提高空間數(shù)據(jù)挖掘算法的時空效率是重要的研究方向； 4 、空間數(shù)的表達(dá) 如何將據(jù)挖掘結(jié)果數(shù)據(jù)挖掘結(jié)果以用戶易于理解的方式( 如：自然語言、圖形) 精 確的表達(dá)出來，以給用戶提供良好的決策支持，是空間數(shù)據(jù)挖掘研究的一個方向。 1 3 空間數(shù)據(jù)庫概述 空間數(shù)據(jù)庫是空間數(shù)據(jù)及其相關(guān)非空間數(shù)據(jù)的集合，用以描述現(xiàn)實世界的空間位 置、屬性等信息?？臻g數(shù)據(jù)是與地理和空間分布有關(guān)的，反映現(xiàn)實世界各種現(xiàn)象及其變 化的符號記錄【2 1 。其中，空間數(shù)據(jù)是基礎(chǔ)，非空間數(shù)據(jù)是內(nèi)涵，是地理單元的縱深描述。 與一般數(shù)據(jù)庫相比，空間數(shù)據(jù)庫具有空間性、時間性、多維性、海量性、復(fù)雜性等特點。 空間數(shù)據(jù)庫的種類很多，可分為觀測數(shù)據(jù)、地圖數(shù)據(jù)、遙感數(shù)據(jù)以及統(tǒng)計數(shù)據(jù)等【6 】。 6 山東師范大學(xué)碩士學(xué)位論文 1 3 1 空間數(shù)據(jù)結(jié)構(gòu) 空間數(shù)據(jù)結(jié)構(gòu)是指空間數(shù)據(jù)在計算機(jī)內(nèi)的組織和編碼形式，是指適合于計算機(jī)存 儲、管理、處理的地理實體空間數(shù)據(jù)的邏輯結(jié)構(gòu)【刀。它是對數(shù)據(jù)的一種理解和解釋。 對于空間實體，我們首先要確定空間數(shù)據(jù)對空間實體的描述形式。在計算機(jī)內(nèi)，常 用的對空間實體的存儲、描述形式有：矢量數(shù)據(jù)結(jié)構(gòu)( 隱式描述) 、柵格數(shù)據(jù)結(jié)構(gòu)( 顯 式描述) 、失柵一體化的數(shù)據(jù)結(jié)構(gòu)。這三種數(shù)據(jù)結(jié)構(gòu)各有自己的特點及適用范圍，其中， 失柵一體化的數(shù)據(jù)結(jié)構(gòu)是在前兩種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上并結(jié)合它們的優(yōu)點而發(fā)展起來的。 下面分別介紹三種數(shù)據(jù)結(jié)構(gòu)【s j ： 1 、矢量數(shù)據(jù)結(jié)構(gòu) 矢量數(shù)據(jù)結(jié)構(gòu)是通過記錄坐標(biāo)的方式，盡可能地將點、線、面等地理實體表現(xiàn)的精 確無誤。矢量數(shù)據(jù)結(jié)構(gòu)將其坐標(biāo)空間假定為連續(xù)空間，每一個點由( x ，n 坐標(biāo)來表示。 在矢量數(shù)據(jù)結(jié)構(gòu)中，點實體包括由單獨一對( x ，y ) 坐標(biāo)定位的一切地理或制圖實體；線 實體可以定義為直線元素組成的各種線性要素，直線元素由兩對以上的( x ，y ) 坐標(biāo)定 義；面狀實體由首尾相連的線狀實體組成，最終也由點來表示。各種類型空間實體的存 儲方式如圖1 1 所示： y ( a ) 點的表示 x ( b ) 線的表示 圖i - i 空間實體的矢量結(jié)構(gòu) x ( c ) 面的表示 2 、柵格數(shù)據(jù)結(jié)構(gòu) 顧名思義，柵格數(shù)據(jù)結(jié)構(gòu)就是將存儲空間劃分為均勻的網(wǎng)格，每一個網(wǎng)格為一個 柵格，有唯一的行列數(shù)，行列的數(shù)目取決于柵格的分辨率和空間實體的特征。點狀實體 直接表示為一個單一的網(wǎng)格；線狀實體由一系列相鄰的網(wǎng)格連接而成；面狀實體表示為 由邊所圍成的區(qū)域內(nèi)的所有網(wǎng)格點以及各個邊所包含的網(wǎng)格點的集合。為了便于理解， 我們用圖1 2 表示了幾種空間實體的存儲方式： 7 山東師范大學(xué)碩士學(xué)位論文 l i l l i il i _l i ( a ) 點的表示( b ) 線的表示( c ) 面的表示 圖1 - 2 空間實體的柵格結(jié)構(gòu) 比較內(nèi)容矢量結(jié)構(gòu)柵格結(jié)構(gòu) 數(shù)據(jù)共享容易實現(xiàn)不易實現(xiàn) 拓?fù)潢P(guān)系提供有效的拓?fù)渚幋a，容易實難以表達(dá)拓?fù)潢P(guān)系，但容易實 現(xiàn)網(wǎng)絡(luò)分析現(xiàn)疊加操作 數(shù)據(jù)量 小大 圖形精度高低 圖形運算復(fù)雜、高效簡單、低效 輸出顯示抽象、昂貴、比較美觀直觀、便宜、線條宜有鋸齒 表1 - 1 矢量結(jié)構(gòu)與柵格結(jié)構(gòu)的比較1 3 、失柵一體化數(shù)據(jù)結(jié)構(gòu) 為了解決柵格、矢量數(shù)據(jù)直接交互的問題，矢柵一體化的數(shù)據(jù)結(jié)構(gòu)應(yīng)運而生，這種 數(shù)據(jù)結(jié)構(gòu)兼有矢量和柵格兩種結(jié)構(gòu)的特性。 目前研究的矢柵一體化結(jié)構(gòu)主要有三種：柵格索引型、矢量柵格化型、混合型。柵 格索引型數(shù)據(jù)的特點是點線面的矢量數(shù)據(jù)結(jié)構(gòu)中加入柵格索引結(jié)構(gòu)來輔助矢量數(shù)據(jù)的 編輯、處理及空間分析。矢量柵格化型數(shù)據(jù)結(jié)構(gòu)則是在建立空間柵格索引的同時，把傳 統(tǒng)的矢量型點線面數(shù)據(jù)也部分采用元子充填形式表示，郎矢量數(shù)據(jù)柵格化，較具代表性 的是粗細(xì)分格網(wǎng)法?；旌闲徒Y(jié)構(gòu)通過矢柵轉(zhuǎn)換接口把矢量數(shù)據(jù)和柵格數(shù)據(jù)有機(jī)地結(jié)合在 一起。 為了使點狀：線狀、面狀地物的數(shù)據(jù)結(jié)構(gòu)兼具柵格和矢量的特點，龔建雅( 1 9 9 2 ) 年做了如下約定：( 1 ) 地面上的點狀地物是地球表面上的點，它僅有空間位置，沒有形 狀和面積，在計算機(jī)內(nèi)僅有一個位置數(shù)據(jù)；( 2 ) 地面上的線狀地物是地球表面的空間曲 線，它有形狀但沒有面積，在計算機(jī)內(nèi)需要用一組元子填滿整個路徑；( 3 ) 地面上的面 狀地物是地球表面的空間曲面，并具有形狀和面積，在計算機(jī)內(nèi)由一組填滿路徑的元子 表達(dá)的邊界和內(nèi)部區(qū)域構(gòu)成。 山東師范大學(xué)碩士學(xué)位論文 1 3 2 空間數(shù)據(jù)模型 空間數(shù)據(jù)模型是描述空間實體與實體之間關(guān)系的數(shù)據(jù)模型，一般來說既可以利用傳 統(tǒng)的數(shù)據(jù)模型加以擴(kuò)充和修改來實現(xiàn)，也可以用面向?qū)ο蟮臄?shù)據(jù)模型來實現(xiàn)?？臻g數(shù)據(jù) 模型可以分為以下幾種類型： 1 、層次模型 用層次結(jié)構(gòu)表示實體間聯(lián)系的數(shù)據(jù)模型稱為層次數(shù)據(jù)模型( h i e r a r c h i c a l d a t a m o d e l ) 。層次結(jié)構(gòu)是樹狀結(jié)構(gòu)，樹的結(jié)點是記錄類型，根在上，葉在下，它是數(shù)據(jù) 處理中發(fā)展較早、技術(shù)上也比較成熟的一種數(shù)據(jù)模型。 當(dāng)數(shù)據(jù)實體之間存在l ：n 的“父子 關(guān)系，且主從關(guān)系明確時，易于用層次模型 來描述。它具有如下性質(zhì)： ( 1 ) 有且只有一個根節(jié)點； ( 2 ) 除根節(jié)點外，每個節(jié)點都有且只有一個父節(jié)點； ( 3 ) 除葉節(jié)點外，其他節(jié)點都可以有若干個子結(jié)點； ( 4 ) 有多個葉節(jié)點，其下再無其他節(jié)點。 層次模型反映了現(xiàn)實世界中實體間的層次關(guān)系，層次結(jié)構(gòu)是眾多空間對象的自然表 達(dá)形式，并在一定程度上支持?jǐn)?shù)據(jù)的重構(gòu)。層次模型直觀，應(yīng)用范圍廣泛，典型的例子 是描述一個城市的房屋位置。圖1 3 為層次模型的示意圖，包括區(qū)文件、街道文件和房 屋文件三個層次。 圖1 - 3 層次模型 ( 其中q 為區(qū)文件，s 為街道文件，h 為房屋文件) 2 、網(wǎng)絡(luò)模型 在空間網(wǎng)絡(luò)模型中，地理現(xiàn)象被抽象為鏈、結(jié)點以及它們之間的連通關(guān)系。網(wǎng)絡(luò)模 型將數(shù)據(jù)組織成圖的結(jié)構(gòu)，結(jié)點代表數(shù)據(jù)記錄，邊表示結(jié)點之間的連通關(guān)系，任何一個 結(jié)點可以和其他任意多個結(jié)點建立聯(lián)系。圖的形式化定義為： g = v ( g ) ，e ( g ) ，r g 9 山東師范大學(xué)碩士學(xué)位論文 式中，v ( g ) 為圖的結(jié)點的集合，e ( g ) 為邊的集合，r g 為結(jié)點之間關(guān)系的集合。網(wǎng) 絡(luò)模型的結(jié)點間沒有明確的從屬關(guān)系。由于網(wǎng)絡(luò)模型的結(jié)構(gòu)復(fù)雜，且無規(guī)律，用戶對數(shù) 據(jù)的查詢和定位比較困難，因此在空間分析中應(yīng)用較少。網(wǎng)絡(luò)模型的結(jié)構(gòu)如圖1 _ 4 所示： 圖1 4 網(wǎng)絡(luò)模型 3 、關(guān)系模型 關(guān)系模型是使用范圍最廣泛的一種數(shù)據(jù)模型，比較大型的空間數(shù)據(jù)庫均采用關(guān)系模 型。關(guān)系模型將數(shù)據(jù)的邏輯結(jié)構(gòu)轉(zhuǎn)化為滿足一定條件的二維表，二維表中的每一行代表 一個實體，列代表實體的屬性，既能表示實體又能表示聯(lián)系，而且能表達(dá)多種聯(lián)系。關(guān) 系模型能處理多種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)靈活、清晰，便于用戶使用。 例如，一個城市數(shù)字化地圖的關(guān)系型數(shù)據(jù)庫的部分關(guān)系如下： 道路：r o a d s ( f r a m e 、r o i d 、x l 、x 2 、y l 、y 2 ) 道路名：r o n a m e ( f r a m e 、r o i d 、n a m e ) 位置：p o s ( f r a m e 、x s i z e 、y s i z e 、x c e n 、y c e n ) 1 3 3 空間數(shù)據(jù)索引技術(shù) 一般的數(shù)據(jù)挖掘技術(shù)在處理高維數(shù)據(jù)時效率低下，為了提高算法效率，人們尋求各 種解決方法，其中，索引技術(shù)是比較常見的一種方法【4 2 1 。 傳統(tǒng)的索引方法( 如：b 樹索引) 只能針對一維的字符、數(shù)字等簡單數(shù)據(jù)類型，無 法支持空間數(shù)據(jù)的查詢與更新，為此，人們提出了空間索引?？臻g數(shù)據(jù)索引是指依據(jù)空 間實體的位置和形狀或空間實體間的某種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu) 【9 】。作為一種輔助性的空間數(shù)據(jù)結(jié)構(gòu)，空間數(shù)據(jù)索引介于空間操作算法和地理實體之間， 它通過篩選，排除大量與特定空間操作無關(guān)的地理實體，從而提高空間操作的速度和效 率【1 3 】。 根據(jù)自身結(jié)構(gòu)的不同，空間索引分為樹型空間索引和基于h a s h 的網(wǎng)格類索引兩類： l 、樹型索引【1 1 , 1 2 j 樹型索引可以高效支持查詢。要回答一個查詢，若沒有樹型索引，則必須掃描整個 數(shù)據(jù)集，若通過樹型索引，則只需訪問部分字?jǐn)?shù)對應(yīng)的數(shù)據(jù)，因而縮小查詢范圍，提高 查詢效率。樹型空間索引分為基于數(shù)據(jù)劃分和基于空間劃分兩類，前者劃分?jǐn)?shù)據(jù)集，并 建立數(shù)據(jù)子集的包含區(qū)域( b o u n d i n gr e g i o n ) 的層次結(jié)構(gòu)，如r 樹、r 宰樹、s s 樹等； 1 0 山東師范大學(xué)碩士學(xué)位論文 后者將數(shù)據(jù)空間劃分為不相交的子空間，并建立子空間的層次結(jié)構(gòu)，如q u a d t r e e ( 四叉 樹) 、k d 樹等。下面分別介紹這幾類空間索引技術(shù)。 r 樹 r 樹是一種常用的動態(tài)索引技術(shù)，主要用于對多維空間數(shù)據(jù)索引。r 樹類似于b 樹， 是一種高度平衡的樹，它基于最小包含矩形m b r 劃分?jǐn)?shù)據(jù)，使空間上靠近的空間對象 擁有盡可能近的共同祖先。 r 樹中每個節(jié)點由若干個形如( r e c t ，r e 0 的單元組成。對于中間節(jié)點，r e 堤指向子樹 的指針，r e c t 是包含該子樹中所有對象的m b r ；對于葉節(jié)點，r e f , $ 空間對象在數(shù)據(jù)庫中 的記錄指針，r e c t 是它的m b r 。根節(jié)點至少含有兩個孩節(jié)點；除根節(jié)點，所有節(jié)點的單 元數(shù)在m 到m 之i 日- j ，m 是一個頁塊最多容納單元的個數(shù)，且2 m lm 2i 。當(dāng)節(jié)點 中的單元數(shù)超過m 時，就需要分裂。r 樹選擇采用使分裂產(chǎn)生的兩部分m b r 面積之和 最小的分裂方案。 四叉樹 四叉樹是基于空間劃分的空間索引，適用于二維空間，分支數(shù)為4 。四叉樹使用遞 歸分解的原則，不斷將空間等分為東北、東南、西北、西南四個象限，直至每個子空間 中的對象數(shù)目不大于某個閾值。四叉樹易于理解，但不平衡，對于高密度區(qū)域，子樹要 比低密度區(qū)域的子樹深。四叉樹一旦建立，樹的層次就被固定，不能滿足空間數(shù)據(jù)的動 態(tài)更新，四叉樹不適合于大型高維數(shù)據(jù)集。 k d 樹 ， k - d 樹是用于存儲維點數(shù)據(jù)( k e y , ，k e y ：，k e y , ) 的二叉樹。它遞歸地用經(jīng)過某個數(shù)據(jù) 點、且垂直于某一維的k 一1 維分裂超平面來劃分?jǐn)?shù)據(jù)空間，直到所有子空間包含的點 數(shù)都不大于1 。 k d 樹可以支持多種查詢操作，但在高維時性能下降。k d 樹不易保持動態(tài)平衡， 其結(jié)構(gòu)依賴于點數(shù)據(jù)的輸入順序。 2 、網(wǎng)格類索引【1 o 】 格網(wǎng)索引面向地圖對象的空間位置和分布，屬于柵格類索引，它的特點是簡潔、高 效、易于實現(xiàn)。 格網(wǎng)索引將工作區(qū)按一定的規(guī)則劃分成正方形格網(wǎng)，之所以劃分成正方形是為了方 便計算。格網(wǎng)劃分后，以落入每個格網(wǎng)內(nèi)的目標(biāo)建立索引，這樣檢索過程只需考察每個 格網(wǎng)，檢索的區(qū)域大大減小。 根據(jù)空間數(shù)據(jù)的特點，我們可以將空間目標(biāo)數(shù)據(jù)分為點、線、面等類型。為了在索 引結(jié)構(gòu)中定位這些類型的數(shù)據(jù)，為每一個空間數(shù)據(jù)定義其索引值、目標(biāo)分類碼、坐標(biāo)值 等屬性的數(shù)據(jù)結(jié)構(gòu)。線結(jié)構(gòu)的屬性中包含所有點的集合，面結(jié)構(gòu)屬性還應(yīng)包含其在數(shù)組 中的索引號。在數(shù)據(jù)查詢過程中，根據(jù)數(shù)據(jù)對象的坐標(biāo)值等信息計算其所在格網(wǎng)的行號 和列號，從而達(dá)到定位對象的目的。 1 1 山東師范大學(xué)碩士學(xué)位論文 基于格網(wǎng)劃分的空間索引技術(shù)在實際生產(chǎn)操作中應(yīng)用廣泛，因為它簡單、易行，又 能起到很好的效果；在數(shù)據(jù)量不是很大，不需要設(shè)計像r 樹或四叉樹那樣很復(fù)雜的索 引結(jié)構(gòu)時，格網(wǎng)索引不失為一種較好的選擇。 1 4 研究內(nèi)容與章節(jié)安排 在空間數(shù)據(jù)挖掘領(lǐng)域，空間數(shù)據(jù)挖掘任務(wù)所面臨的空間數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)結(jié) 構(gòu)復(fù)雜并且在現(xiàn)實世界中常常具有障礙約束等特點。針對這些問題，本文主要做了如下 工作： 1 研究基于密度的各種空間聚類算法，并分析現(xiàn)有算法的優(yōu)缺點。對d b s c a n 算法進(jìn)行改進(jìn)，改變其尋找核心點的方式，以提高聚類算法的效率； 2 對空間數(shù)據(jù)庫中障礙物的有效處理，是當(dāng)前研究的一個方向，并且也是大多數(shù) 實際應(yīng)用所面臨的問題。針對這種需求，在數(shù)學(xué)形態(tài)學(xué)聚類算法的基礎(chǔ)上，提出了一種 帶障礙約束的空間聚類算法； 3 對帶障礙約束的聚類算法進(jìn)行數(shù)據(jù)實驗，證明算法的有效性。 本文的章節(jié)安排如下： 第一章：緒論，簡要介紹了選題的意義、研究現(xiàn)狀及空間數(shù)據(jù)庫的基礎(chǔ)知識； 第二章：首先提出空間數(shù)據(jù)挖掘的基礎(chǔ)知識，然后分別介紹空間數(shù)據(jù)挖掘的主要方 法、步驟、數(shù)據(jù)挖掘的體系結(jié)構(gòu)以及數(shù)據(jù)挖掘的結(jié)果表示等方面的問題； 第三章：對空間聚類技術(shù)的各方面進(jìn)行了詳細(xì)的介紹，主要包括：聚類分析的概念、 主要的應(yīng)用范圍及示例、幾種常用的空間聚類算法以及聚類算法當(dāng)前需要解決的問題： 第四章：對基于密度的空間聚類算法進(jìn)行深入的研究，將基于密度的空間聚類算法 進(jìn)行改進(jìn)，改變其尋找核心點的思想，以提高算法的效率，并給出算法的實現(xiàn)步驟，進(jìn) 行評價； 第五章：根據(jù)目前空間聚類過程中經(jīng)常存在障礙物的實際情況，結(jié)合數(shù)學(xué)形態(tài)學(xué)聚 類的基本思想，提出了基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的聚類算法，并對算法進(jìn)行分析， 實驗； 第六章：對本次研究工作的總結(jié)，并提出未來研究的努力方向。 1 2 山東師范大學(xué)碩士學(xué)位論文 2 ，1 基礎(chǔ)知識 第二章空間數(shù)據(jù)挖掘技術(shù) 空間數(shù)據(jù)挖掘，簡單地說，就是從空間數(shù)據(jù)中提取隱含其中、事先未知、潛在有用、 最終可理解的空間或非空間的一般知識規(guī)則的過程。具體而言，就是從大量含有噪聲、 不確定性的空間數(shù)據(jù)中，析取人們可信的、新穎的、感興趣的、隱藏的知識，揭示蘊涵 在數(shù)據(jù)背后的客觀世界的本質(zhì)規(guī)律、內(nèi)在聯(lián)系和發(fā)展趨勢，為技術(shù)決策與經(jīng)營決策提供 不同層次的知識依據(jù)p j 。 空間數(shù)據(jù)挖掘是計算機(jī)技術(shù)、數(shù)據(jù)庫應(yīng)用技術(shù)和管理決策技術(shù)等發(fā)展到一定階段、 多學(xué)科交叉的新興邊緣學(xué)科，匯集了來自機(jī)器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計學(xué)、人工 智能以及管理信息系統(tǒng)等各學(xué)科的成果【l6 1 7 】?？臻g數(shù)據(jù)挖掘方法可以用來理解空間數(shù) 據(jù)、發(fā)現(xiàn)空間數(shù)據(jù)和非空間數(shù)據(jù)之間的關(guān)系、創(chuàng)建空間知識庫、優(yōu)化查詢、組織空間數(shù) 據(jù)庫中的數(shù)據(jù)以及以簡明的形式描述空間數(shù)據(jù)的一般特征?？臻g數(shù)據(jù)挖掘產(chǎn)生的空間知 識主要包括空間的關(guān)聯(lián)關(guān)系、特征、分類和聚類。挖掘結(jié)果一般表現(xiàn)為一組概念、規(guī)則 和模式等形式的集合，是對數(shù)據(jù)庫中的數(shù)據(jù)屬性、模式、頻度和對象簇集等的描述。 2 1 1 空間數(shù)據(jù)挖掘的由來 隨著遙感技術(shù)、雷達(dá)、電視成像、c t 成像以及自動數(shù)據(jù)采集工具的廣泛應(yīng)用，人 們在空間數(shù)據(jù)庫中收集了大量的空間和非空間的數(shù)據(jù)，并且空間數(shù)據(jù)的復(fù)雜性顯著提 高，己經(jīng)遠(yuǎn)遠(yuǎn)超出了人類的理解能力。為了從空間數(shù)據(jù)庫中得到知識，需要對空間數(shù)據(jù) 進(jìn)行分析。二十世紀(jì)九十年代中期以前的大部分空間數(shù)據(jù)分析方法都使用統(tǒng)計方法處理 數(shù)值數(shù)據(jù)【1 6 1 ，這種方法具有很大的局限性。首先，空間數(shù)據(jù)的數(shù)據(jù)量正在不斷增長， 數(shù)據(jù)統(tǒng)計方法的效率也越來越低；其次，它忽略了空間對象之間的拓?fù)潢P(guān)系，得到的結(jié) 果是片面的、不真實的，并且這種統(tǒng)計模型只有具有豐富領(lǐng)域知識和統(tǒng)計經(jīng)驗的專家才 能使用?；谝陨蟽牲c，人類急需探求一種新的數(shù)據(jù)分析模式，能夠更高效、更客觀的 分析空間數(shù)據(jù)，以提供在稅收、交通、營業(yè)網(wǎng)點選址、環(huán)境保護(hù)等方面的決策支持。 空間數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫最根本的區(qū)別是空間數(shù)據(jù)庫包括兩部分：空間對象和有關(guān) 這些對象的非空間屬性，并且各空間對象之間還存在著拓?fù)潢P(guān)系。這些特點使得在對空 間數(shù)據(jù)進(jìn)行統(tǒng)計分析時，除借鑒傳統(tǒng)數(shù)據(jù)挖掘方法外，還應(yīng)該考慮空間對象之間的相互 影響，有時要重新設(shè)計算法來適應(yīng)數(shù)據(jù)的空間特性，以達(dá)到令人滿意的結(jié)果【i 引。 空間數(shù)據(jù)挖掘是伴隨著空間數(shù)據(jù)獲取手段以及存儲技術(shù)的提高而出現(xiàn)并不斷發(fā)展 的。同時，人類對生活、生產(chǎn)、環(huán)境的智能化要求也是其出現(xiàn)與發(fā)展的動力。 山東師范大學(xué)碩士學(xué)位論文 2 1 2 空間數(shù)據(jù)挖掘的特點 由于空間數(shù)據(jù)庫存儲了空間實體的位置特征、幾何特征以及屬性特征這三種基礎(chǔ)數(shù) 據(jù)，空間實體之間又具有空間拓?fù)洹⒖臻g距離、空間方位這三種關(guān)系，所以空間數(shù)據(jù)庫 的分析和計算要比關(guān)系數(shù)據(jù)庫復(fù)雜，這意味著空間數(shù)據(jù)挖掘( s d m ) 的方法要比數(shù)據(jù) 挖掘( d m ) 復(fù)雜的多，技術(shù)實現(xiàn)也更加困難。s d m 具有如下特點【1 】： 空間數(shù)據(jù)庫的數(shù)據(jù)量龐大，為了提高數(shù)據(jù)分析效率，需要建立空間索引結(jié)構(gòu)組 織空間數(shù)據(jù)； 空間數(shù)據(jù)挖掘的對象是空間數(shù)據(jù)庫或空間數(shù)據(jù)倉庫，存儲的是空間實體的位置、 屬性信息以及空間實體之間的拓?fù)潢P(guān)系信息； 空間數(shù)據(jù)挖掘粒度為矢量結(jié)構(gòu)的點、線、面、多邊形等空間對象，或柵格結(jié)構(gòu) 的像元； 空間對象之間通常具有一定的拓?fù)潢P(guān)系，空間數(shù)據(jù)相關(guān)度高，在挖掘知識時需 要充分考慮； 空間數(shù)據(jù)挖掘針對空間數(shù)據(jù)的特點，增加了尺度維，形成空間數(shù)據(jù)挖掘的四維 發(fā)現(xiàn)狀態(tài)空間。在尺度維上，表達(dá)了空間數(shù)據(jù)由細(xì)至粗的多比例尺或多分辨率的幾何變 換過程。尺度越大，觀察點越遠(yuǎn)，比例尺越小，對空間目標(biāo)表達(dá)越概括、越宏觀；尺度 越小，相當(dāng)于觀察點越近，比例尺越大，對空間目標(biāo)表達(dá)越精細(xì)、越微觀。 針對空間數(shù)據(jù)的復(fù)雜性、海量性、多維性等特點，目前對s d m 的研究主要集中于： 在充分考慮空間數(shù)據(jù)特點的基礎(chǔ)上，提高算法的時間效率和空間效率。 2 2 空間數(shù)據(jù)挖掘的體系結(jié)構(gòu) 空間數(shù)據(jù)挖掘系統(tǒng)的體系結(jié)構(gòu)可分為三層，數(shù)據(jù)源、數(shù)據(jù)挖掘器、用戶界面i l9 1 。 數(shù)據(jù)源是指直接存儲在空間數(shù)據(jù)庫或空間數(shù)據(jù)倉庫中的數(shù)據(jù)，是空間數(shù)據(jù)挖掘系統(tǒng) 的基礎(chǔ)，對空間數(shù)據(jù)來說，包括位置數(shù)據(jù)、屬性數(shù)據(jù)以及圖形圖像。 數(shù)據(jù)挖掘器是用戶根據(jù)數(shù)據(jù)挖掘的目標(biāo)以及數(shù)據(jù)量的大小選擇的一種或幾種數(shù)據(jù) 挖掘方法，是數(shù)據(jù)挖掘系統(tǒng)的核心。 。用戶界面主要用來進(jìn)行知識表達(dá)，將數(shù)據(jù)挖掘的結(jié)果或獲取的知識類型以便于用戶 理解和觀察的方式展現(xiàn)給用戶，是整個數(shù)據(jù)挖掘系統(tǒng)的出口。 當(dāng)用戶對獲取的知識不滿意，例如由于數(shù)據(jù)的選取不夠準(zhǔn)確導(dǎo)致數(shù)據(jù)挖掘結(jié)果不精 確時，用戶可以返回數(shù)據(jù)選取步驟，重新進(jìn)行數(shù)據(jù)挖掘過程。 數(shù)據(jù)挖掘系統(tǒng)的體系結(jié)構(gòu)如圖2 1 所示。 1 4 山東師范大學(xué)碩士學(xué)位論文 匝虱 區(qū)亙h 區(qū)匾一 圖2 - 1 數(shù)據(jù)挖掘體系結(jié)構(gòu) 2 3 空間數(shù)據(jù)挖掘的基本方法 對結(jié)果不滿意返回 - - | _ t ：# t z = = = = = ：三 空間數(shù)據(jù)挖掘的任務(wù)不同，所選用的方法也不同，主要的空間數(shù)據(jù)挖掘的方法可分 為如下幾類【2 0 , 2 1 ，2 2 】： 1 、統(tǒng)計分析方法 統(tǒng)計分析方法一直是數(shù)字型空間數(shù)據(jù)分析的常用方法，有著較強的理論基礎(chǔ)，擁有 大量的算法，可有效地處理數(shù)字型數(shù)據(jù)。該方法著重于空間物體和現(xiàn)象的非空間特性分 析。但該方法對空間數(shù)據(jù)統(tǒng)計的獨立性假設(shè)往往難以滿足，且難以處理非數(shù)值型數(shù)據(jù)。 當(dāng)數(shù)據(jù)不完全或不充分時，統(tǒng)計分析的結(jié)果會缺乏實際意義。應(yīng)用統(tǒng)計方法需要領(lǐng)域知 識和統(tǒng)計知識，一般由具有統(tǒng)計經(jīng)驗的領(lǐng)域?qū)＜襾硗瓿伞?2 、聚類的方法 聚類分析方法是數(shù)據(jù)挖掘的一種重要的方法，其基本思想是按一定的距離或相似性 測度將數(shù)據(jù)分成一系列相區(qū)分的組，它不需要背景知識而直接發(fā)現(xiàn)一些有意義的結(jié)構(gòu)和 模式，類似于機(jī)器學(xué)習(xí)的非監(jiān)督學(xué)習(xí)。用聚類分析方法處理屬性數(shù)據(jù)庫中的大數(shù)據(jù)量時， 速度慢且效率低，但處理圖形數(shù)據(jù)庫時效率高。聚類是本文的重點研究對象。 3 、歸納的方法 歸納方法是從大量的經(jīng)驗數(shù)據(jù)中進(jìn)行概括和綜合，歸納出高層次的模式或特征。歸 納方法一般需要背景知識，常以概念樹的形式給出。在g i s 中，有屬性概念樹和空間 1 5 山東師范大學(xué)碩士學(xué)位論文 關(guān)系概念樹兩類。背景知識由用戶提供，在有些情況下也可作為知識發(fā)現(xiàn)任務(wù)的一部分 自動獲取。 4 、空間分析方法 空間分析方法可采用拓?fù)浣Y(jié)構(gòu)分析、空間緩沖區(qū)及距離分析、