全面解析基于空間數(shù)據(jù)庫的數(shù)據(jù)挖掘技術(shù)

隨著GIS技術(shù)在各個行業(yè)的應(yīng)用以及數(shù)據(jù)挖掘、空間數(shù)據(jù)采集技術(shù)、數(shù)據(jù)庫技術(shù)的迅速發(fā)展，對從空間數(shù)據(jù)庫發(fā)現(xiàn)隱含知識的需求日益增長，從而出現(xiàn)了用于在空間數(shù)據(jù)庫中進行知識發(fā)現(xiàn)的技術(shù)――空間數(shù)據(jù)挖掘(Spatial Data Mining，本文簡稱為SDM)。空間數(shù)據(jù)挖掘是從空間數(shù)據(jù)庫中提取隱含的、用戶感興趣的空間和非空間模式和普遍特征的過程。 本文分析了空間數(shù)據(jù)庫知識發(fā)現(xiàn)面臨的困難，研究了擴展傳統(tǒng)數(shù)據(jù)挖掘方法如分類、關(guān)聯(lián)規(guī)則、聚類等到空間數(shù)據(jù)庫的方法，并對空間數(shù)據(jù)庫系統(tǒng)實現(xiàn)技術(shù)及空間數(shù)據(jù)挖掘系統(tǒng)開發(fā)模式等進行了比較分析。

 1　空間數(shù)據(jù)庫知識發(fā)現(xiàn)面臨的困難 

從空間數(shù)據(jù)庫發(fā)現(xiàn)知識的傳統(tǒng)途徑是通過專家系統(tǒng)、數(shù)據(jù)挖掘、空間分析等技術(shù)來實現(xiàn)的。但是在空間數(shù)據(jù)庫隱含知識的發(fā)現(xiàn)方面，只單獨依*某一種技術(shù)，往往存在著這樣或那樣的缺陷。對于專家系統(tǒng)來講，專家系統(tǒng)不具備自動學(xué)習(xí)的能力，GIS中的專家系統(tǒng)也達不到真正的智能系統(tǒng)的要求，僅能利用已有的知識進行推導(dǎo)。對于數(shù)據(jù)挖掘來講，空間數(shù)據(jù)庫與普通數(shù)據(jù)庫的在數(shù)據(jù)存儲機制的不同和空間數(shù)據(jù)的相互依賴性等特點決定了在空間數(shù)據(jù)庫無法直接采用傳統(tǒng)的數(shù)據(jù)挖掘方法。

對于空間分析來講，雖然空間分析中常用的統(tǒng)計方法可以很好地處理數(shù)字型數(shù)據(jù)，但是它存在的問題很多，如統(tǒng)計方法通常假設(shè)空間分布的數(shù)據(jù)間是統(tǒng)計上獨立的，而現(xiàn)實中空間對象間一般是相互關(guān)聯(lián)的；其次，統(tǒng)計模型一般只有具有相當豐富領(lǐng)域知識和統(tǒng)計方面經(jīng)驗的統(tǒng)計專家才能用；另外，統(tǒng)計方法對大規(guī)模數(shù)據(jù)庫的計算代價非常高，所以在處理海量數(shù)據(jù)方面能力較低。 從上面的分析可以看出，由于空間數(shù)據(jù)具有諸多特點，因此在空間數(shù)據(jù)庫進行知識發(fā)現(xiàn)，需要克服使用單一技術(shù)的缺陷，即需要融合多種不同技術(shù)。所以研究人員提出了空間數(shù)據(jù)挖掘技術(shù)來解決從空間數(shù)據(jù)庫知識發(fā)現(xiàn)隱含知識的難題。 

空間數(shù)據(jù)挖掘是多學(xué)科和多種技術(shù)交*綜合的新領(lǐng)域，它綜合了機器學(xué)習(xí)、空間數(shù)據(jù)庫系統(tǒng)、專家系統(tǒng)、可移動計算、統(tǒng)計、遙感、基于知識的系統(tǒng)、可視化等領(lǐng)域的有關(guān)技術(shù)。 空間數(shù)據(jù)挖掘利用空間數(shù)據(jù)結(jié)構(gòu)、空間推理、計算幾何學(xué)等技術(shù)，把傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)擴充到空間數(shù)據(jù)庫并提出很多新的有效的空間數(shù)據(jù)挖掘方法。與傳統(tǒng)空間分析方法相比，它在實現(xiàn)效率、與數(shù)據(jù)庫系統(tǒng)的結(jié)合、與用戶的交互、發(fā)現(xiàn)新類型的知識等方面的能力大大增強?？臻g數(shù)據(jù)挖掘能與GIS的結(jié)合，使GIS系統(tǒng)具有自動學(xué)習(xí)的功能，能自動獲取知識，從而成為真正的智能空間信息系統(tǒng)。

 2　擴展傳統(tǒng)數(shù)據(jù)挖掘方法到空間數(shù)據(jù)庫 

空間數(shù)據(jù)挖掘技術(shù)按功能劃分可分為三類：描述、解釋、預(yù)測。描述性的模型將空間現(xiàn)象的分布特征化，如空間聚類。解釋性的模型用于處理空間關(guān)系，如處理一個空間對象和影響其空間分布的因素之間的關(guān)系。預(yù)測型的模型用來根據(jù)給定的一些屬性預(yù)測某些屬性。預(yù)測型的模型包括分類、回歸等。以下介紹將幾個典型的數(shù)據(jù)挖掘技術(shù)聚類、分類、關(guān)聯(lián)規(guī)則擴展到空間數(shù)據(jù)庫的方法。

 聚類分析方法按一定的距離或相似性測度將數(shù)據(jù)分成一系列相互區(qū)分的組，而空間數(shù)據(jù)聚類是按照某種距離度量準則，在某個大型、多維數(shù)據(jù)集中標識出聚類或稠密分布的區(qū)域，從而發(fā)現(xiàn)數(shù)據(jù)集的整個空間分布模式。經(jīng)典統(tǒng)計學(xué)中的聚類分析方法對海量數(shù)據(jù)效率很低，而數(shù)據(jù)挖掘中的聚類方法可以大大提高聚類效率。文獻[1]中提出兩個基于CLARANS聚類算法空間數(shù)據(jù)挖掘算法SD和ND，可以分別用來發(fā)現(xiàn)空間聚類中的非空間特征和具有相同非空間特征的空間聚類。

SD算法首先用CLARANS算法進行空間聚類，然后用面向?qū)傩詺w納法尋找每個聚類中對象的高層非空間描述；ND算法則反之。文獻[4]中提出一種將傳統(tǒng)分類算法ID3決策樹算法擴展到空間數(shù)據(jù)庫的方法，該算法給出了計算鄰近對象非空間屬性的聚合值的方法，并且通過對空間謂詞進行相關(guān)性分析和采用一種逐漸求精的策略使得計算時間復(fù)雜度大大降低。Koperski等[4]將大型事務(wù)數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則概念擴展到空間數(shù)據(jù)庫，用以找出空間對象的關(guān)聯(lián)規(guī)則。此方法采用一種逐漸求精的方法計算空間謂詞，首先在一個較大的數(shù)據(jù)集上用MBR最小邊界矩形結(jié)構(gòu)技術(shù)對粗略的空間謂詞進行近似空間運算，然后在裁剪過的數(shù)據(jù)集上用代價較高的算法進一步改進挖掘的質(zhì)量。

 3　空間數(shù)據(jù)庫實現(xiàn)技術(shù)

 空間數(shù)據(jù)挖掘系統(tǒng)中，空間數(shù)據(jù)庫負責空間數(shù)據(jù)和屬性數(shù)據(jù)的管理，它的實現(xiàn)效率對整個挖掘系統(tǒng)有著舉足輕重的影響。所以下面詳細介紹空間數(shù)據(jù)庫的實現(xiàn)技術(shù)。 根據(jù)空間數(shù)據(jù)庫中空間數(shù)據(jù)和屬性數(shù)據(jù)的管理方式，空間數(shù)據(jù)庫有兩種實現(xiàn)模式：集成模式和混合模式。后者將非空間數(shù)據(jù)存儲在關(guān)系數(shù)據(jù)庫中，將空間數(shù)據(jù)存放在文件系統(tǒng)中。這種采用混合模式的空間數(shù)據(jù)庫中，空間數(shù)據(jù)無法獲得數(shù)據(jù)庫系統(tǒng)的有效管理，并且空間數(shù)據(jù)采用各個廠商定義的專用格式，通用性差。而集成模式是將空間數(shù)據(jù)和屬性數(shù)據(jù)全部存儲在數(shù)據(jù)庫中，因此現(xiàn)在的GIS軟件都在朝集成結(jié)構(gòu)的空間數(shù)據(jù)庫方向發(fā)展。下面對集成結(jié)構(gòu)的空間數(shù)據(jù)庫技術(shù)中的兩個主流技術(shù)基于空間數(shù)據(jù)引擎技術(shù)的空間數(shù)據(jù)庫和以O(shè)racle Spatial為代表的通用空間數(shù)據(jù)庫進行比較分析。 

空間數(shù)據(jù)引擎是一種處于應(yīng)用程序和數(shù)據(jù)庫管理系統(tǒng)之間的中間件技術(shù)。使用不同GIS廠商的客戶可以通過空間數(shù)據(jù)引擎將自身的數(shù)據(jù)交給大型關(guān)系型DBMS統(tǒng)一管理；同樣，客戶也可以通過空間數(shù)據(jù)引擎從關(guān)系型DBMS中獲取其他類型GIS的數(shù)據(jù)，并轉(zhuǎn)化成客戶可使用的方式。它們大多是在Oracle8i Spatial(較成熟的空間數(shù)據(jù)庫版本8.1.7于2000年9月推出)推出之前由GIS軟件開發(fā)商提供的將空間數(shù)據(jù)存入通用數(shù)據(jù)庫的解決方案，且該方案價格昂貴。 Oracle Spatial提供一個在數(shù)據(jù)庫管理系統(tǒng)中管理空間數(shù)據(jù)的完全開放體系結(jié)構(gòu)。Oracle Spatial提供的功能與數(shù)據(jù)庫服務(wù)器完全集成。用戶通過SQL定義并操作空間數(shù)據(jù)，且保留了Oracle的一些特性，如靈活的n-層體系結(jié)構(gòu)，對象定義，健壯的數(shù)據(jù)管理機制，Java存儲過程。它們確保了數(shù)據(jù)的完整性、可恢復(fù)能力和安全性，而這些特性在混合模式結(jié)構(gòu)中幾乎不可能獲得。在Oracle Spatial中，用戶可將空間數(shù)據(jù)當作數(shù)據(jù)庫的特征使用，可支持空間數(shù)據(jù)庫的復(fù)制、分布式空間數(shù)據(jù)庫以及高速的批量裝載，而空間中間件則不能。除了允許使用所有數(shù)據(jù)庫特性以外，Spatial Cart ridge還提供用戶使用行列來快速訪問數(shù)據(jù)。使用簡單的SQL語句，應(yīng)用者就能直接選取多個記錄。Spatial Cart ridge數(shù)據(jù)模型也給數(shù)據(jù)庫管理員提供了極大的靈活性，DBA可使用常見的管理和調(diào)整數(shù)據(jù)庫的技術(shù)。

 4　空間數(shù)據(jù)挖掘系統(tǒng)的開發(fā) 

4.1　通用SDM系統(tǒng) 

在空間數(shù)據(jù)挖掘系統(tǒng)的開發(fā)方面，國際上最著名的有代表性的通用SDM系統(tǒng)有：GeoMiner，Descartes和ArcView GIS的S-PLUS接口。GeoMiner是加拿大Simon Fraser大學(xué)開發(fā)的著名的數(shù)據(jù)挖掘軟件DBMiner的空間數(shù)據(jù)挖掘的擴展模塊?？臻g數(shù)據(jù)挖掘原型系統(tǒng)GeoMiner包含有三大模塊：空間數(shù)據(jù)立方體構(gòu)建模塊、空間聯(lián)機分析處理(OLAP)模塊和空間數(shù)據(jù)采掘模塊，能夠進行交互式地采掘并顯示采掘結(jié)果?？臻g數(shù)據(jù)采掘模塊能采掘3種類型的規(guī)則：特征規(guī)則、判別規(guī)則和關(guān)聯(lián)規(guī)則。GeoMiner采用SAND體系結(jié)構(gòu)，采用的空間數(shù)據(jù)采掘語言是GMQL。其空間數(shù)據(jù)庫服務(wù)器包括MapInfo，ESRI/OracleSDE，Informix-Illustra以及其它空間數(shù)據(jù)庫引擎。 Descartes可支持可視化的分析空間數(shù)據(jù)，它與開發(fā)此軟件的公司所開發(fā)的數(shù)據(jù)挖掘工具Kepler結(jié)合使用，Kepler完成數(shù)據(jù)挖掘任務(wù)且擁有自己的表現(xiàn)數(shù)據(jù)挖掘結(jié)果的非圖形界面。Kepler和Descarte動態(tài)鏈接，把傳統(tǒng)DM與自動作圖可視化和圖形表現(xiàn)操作結(jié)合起來，實現(xiàn)C4.5決策樹算法、聚類、關(guān)聯(lián)規(guī)則的挖掘。 ArcView GIS的S-PLUS接口是著名的ESRI公司開發(fā)的，它提供工具分析空間數(shù)據(jù)中指定類。

 除了以上空間數(shù)據(jù)挖掘系統(tǒng)外，還有GwiM等系統(tǒng)。 從以上SDM系統(tǒng)可以看出，它們的共同優(yōu)點是把傳統(tǒng)DM與地圖可視化結(jié)合起來，提供聚類、分類等多種挖掘模式，但它們在空間數(shù)據(jù)的操作上實現(xiàn)方式不盡相同。Descartes是專門的空間數(shù)據(jù)可視化工具，它只有與DM工具Kepler結(jié)合在一起，才能完成SDM任務(wù)。而GeoMiner是在MapInfo平臺上二次開發(fā)而成，系統(tǒng)龐大，造成較大的資源浪費。S-PLUS的局限在于，它采用一種解釋性語言(Script)，其功能的實現(xiàn)比用C和C++直接實現(xiàn)要慢得多，所以只適合于非常小的數(shù)據(jù)庫應(yīng)用。基于現(xiàn)存空間數(shù)據(jù)挖掘系統(tǒng)的結(jié)構(gòu)所存在的缺陷，我們提出空間數(shù)據(jù)挖掘系統(tǒng)一種新的實現(xiàn)方案。 

4.2　空間數(shù)據(jù)挖掘系統(tǒng)一種新的實現(xiàn)方案 

以上幾種系統(tǒng)都是用自己開發(fā)的或GIS軟件開發(fā)商提供的GIS平臺、組件或中間件來實現(xiàn)SDM系統(tǒng)中空間數(shù)據(jù)管理和分析。本文中提出了空間數(shù)據(jù)挖掘系統(tǒng)一種新的實現(xiàn)方案，即以現(xiàn)在通用空間數(shù)據(jù)庫(Oracle Spatial)為核心，利用其空間數(shù)據(jù)管理和空間分析的能力，完成空間數(shù)據(jù)挖掘中大量的空間信息抽取任務(wù)，GIS組件只承擔對挖掘結(jié)果的地圖化顯示任務(wù)。采用這種模式，不僅可實現(xiàn)GIS系統(tǒng)與空間數(shù)據(jù)挖掘系統(tǒng)完全集成，并且由于大部分空間信息抽取過程直接在低層數(shù)據(jù)庫上進行，從而可大大提高計算效率。 

新的空間數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)如圖1所示。該系統(tǒng)的基本結(jié)構(gòu)與一般數(shù)據(jù)挖掘系統(tǒng)相同，僅在數(shù)據(jù)挖掘和數(shù)據(jù)管理中增加了有關(guān)空間信息的抽取、空間數(shù)據(jù)管理和空間分析的功能，并建立了一個人機接口處理用戶的指令和顯示挖掘結(jié)果。 這種開發(fā)模式與現(xiàn)存開發(fā)模式的最大區(qū)別是用通用空間數(shù)據(jù)庫代替專門的GIS商用軟件實現(xiàn)空間數(shù)據(jù)管理和空間分析功能。

它的優(yōu)點如下：  (1)GIS商用軟件一般是為開發(fā)GIS系統(tǒng)而設(shè)計的。GIS作為一個獨立軟件系統(tǒng)時，需要具有完整的功能結(jié)構(gòu)，而在為數(shù)據(jù)挖掘服務(wù)時，其主要目的在于為決策者提供決策對象及顯示作為挖掘結(jié)果的地圖，因此只要按需選取GIS的部分功能，而不必面面俱到。GIS的一些功能，如空間數(shù)據(jù)的管理和空間分析等，在通用空間數(shù)據(jù)庫系統(tǒng)中存在相似模塊，因此可由通用空間數(shù)據(jù)庫管理系統(tǒng)中已有功能得到。空間數(shù)據(jù)和屬性數(shù)據(jù)的查詢和空間操作可利用數(shù)據(jù)庫管理功能，數(shù)據(jù)挖掘分析模塊則可作為一個或多個模塊，由數(shù)據(jù)挖掘子系統(tǒng)統(tǒng)一管理，而空間數(shù)據(jù)的存儲管理與分析均交給通用空間數(shù)據(jù)庫完成。這樣不僅可減少系統(tǒng)的功能冗余，提高系統(tǒng)的一致性，還可更好地利用商用數(shù)據(jù)管理系統(tǒng)的各種優(yōu)化技術(shù)來提高系統(tǒng)空間數(shù)據(jù)管理與分析的速度。

 (2)從異構(gòu)數(shù)據(jù)庫的集成和空間數(shù)據(jù)與屬性數(shù)據(jù)的統(tǒng)一管理來看，目前不同GIS廠商的遵循的空間數(shù)據(jù)格式標準不同，GIS通用平臺或組件一般只能直接處理本系統(tǒng)的空間數(shù)據(jù)文件，因此異種數(shù)據(jù)庫的集成是一個難題。而通用空間數(shù)據(jù)庫提供了數(shù)據(jù)轉(zhuǎn)換接口，可以將各種不同格式的空間數(shù)據(jù)轉(zhuǎn)換為統(tǒng)一的格式存入擴展的對象――關(guān)系數(shù)據(jù)庫，從而很好地解決了異種數(shù)據(jù)庫的集成的問題。另外，它還克服了GIS系統(tǒng)空間數(shù)據(jù)與屬性數(shù)據(jù)分離的缺點。

 (3)從數(shù)據(jù)挖掘與空間數(shù)據(jù)庫技術(shù)結(jié)合來看，空間數(shù)據(jù)庫系統(tǒng)與數(shù)據(jù)挖掘系統(tǒng)完全分開的系統(tǒng)盡管簡單，但有不少缺點。首先，空間數(shù)據(jù)庫系統(tǒng)在存儲、組織、訪問和處理數(shù)據(jù)立方體方面提供了很大的靈活性和有效性。

在空間數(shù)據(jù)庫(SDB)/空間數(shù)據(jù)倉庫(SDW)系統(tǒng)中，數(shù)據(jù)多半被很好地組織、索引、清理、集成或合并，使得找出任務(wù)相關(guān)的、高質(zhì)量的數(shù)據(jù)成為一件容易的任務(wù)。不使用SDB/SDW系統(tǒng)，數(shù)據(jù)挖掘系統(tǒng)可能要花大量的時間查找、收集、清理和轉(zhuǎn)換數(shù)據(jù)。其次，在SDB或SDW系統(tǒng)中，有許多被測試的、可伸縮的算法和數(shù)據(jù)結(jié)構(gòu)，因此，使用這種系統(tǒng)開發(fā)有效的、可伸縮的實現(xiàn)，是切實可行的。

此外，大部分數(shù)據(jù)已經(jīng)或?qū)⒁娣旁赟DB/SDW系統(tǒng)中，不與這些系統(tǒng)耦合，數(shù)據(jù)挖掘系統(tǒng)就需要使用其它工具提取數(shù)據(jù)，使得很難將這種系統(tǒng)集成到信息處理環(huán)境。 (4)Oracle Spatial是專門為開發(fā)與執(zhí)行大型企業(yè)空間數(shù)據(jù)倉庫而研制的產(chǎn)品，它在海量空間數(shù)據(jù)的存儲和組織上性能卓越，在開發(fā)基于空間數(shù)據(jù)倉庫的空間數(shù)據(jù)挖掘應(yīng)用方面具有顯著的優(yōu)勢。 (5)Oracle Spatial分擔了SDM算法中部分空間數(shù)據(jù)抽取的任務(wù)，減輕了數(shù)據(jù)挖掘子系統(tǒng)的負擔；另外，由于Oracle對分布式應(yīng)用的良好支持，從而為實現(xiàn)分布式空間數(shù)據(jù)挖掘及并行空間數(shù)據(jù)挖掘提供了最佳方案。 基于以上方案，筆者實現(xiàn)了一個基于Oracle Spatial的分布式空間數(shù)據(jù)挖掘原型系統(tǒng)。

系統(tǒng)由五部分組成：①圖形用戶界面：用于進行交互式的挖掘并顯示挖掘結(jié)果；②數(shù)據(jù)準備模塊：進行數(shù)據(jù)的選擇、預(yù)處理和轉(zhuǎn)換；③挖掘模塊：聚類、分類、關(guān)聯(lián)規(guī)則等空間數(shù)據(jù)挖掘功能及挖掘結(jié)果的評價；④空間數(shù)據(jù)管理模塊：執(zhí)行數(shù)據(jù)準備模塊及挖掘模塊指定的空間操作；⑤數(shù)據(jù)庫服務(wù)器：管理作為挖掘目標的空間數(shù)據(jù)和非空間數(shù)據(jù)及概念層次庫、挖掘結(jié)果庫。挖掘目標的空間和非空間數(shù)據(jù)及概念層次的存儲和空間數(shù)據(jù)的管理由Oracle8.1.7 Spatial實現(xiàn)。數(shù)據(jù)準備算法和聚類、分類、關(guān)聯(lián)規(guī)則等挖掘算法在服務(wù)器端實現(xiàn)，并提供接口給客戶端，在客戶端用GIS組件MapX4.0實現(xiàn)挖掘結(jié)果的專題圖顯示。其編程工具為VC++6.0。