摘自《武漢科技大學學報(自然科學版)》第25卷第2期－2002 年6 月

基于空間數據庫的數據挖掘技術
蔣　旻
(武漢科技大學計算機學院，湖北武漢，430081)

　　摘　要：探討擴展傳統(tǒng)數據挖掘方法如分類、關聯(lián)規(guī)則、聚類等到空間數據庫的方法，著重對空間數據庫系統(tǒng)實現技術及空間數據挖掘系統(tǒng)等進行比較分析，提出了一種空間數據挖掘系統(tǒng)的實現模式。
　　關鍵詞：空間數據庫；空間數據挖掘；空間分析
　　中圖分類號：TP392　　文獻標識碼：A　　文章編號：1001-4985(2002)02-0183-04

Spatial Data Mining Based on Spatial Databases

　　Abstract : This paper discusses the methods of extending the classic data mining such as classification, association rules and clustering to spatial databases1With the analysis and comparison of the realization techniques of spatial database system and spatial data mining systems ，it proposes a development model of spatial data mining system.
　　Keywords : spatial database; spatial data mining; spatial analysis

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

1　空間數據庫知識發(fā)現面臨的困難
　　從空間數據庫發(fā)現知識的傳統(tǒng)途徑是通過專家系統(tǒng)、數據挖掘、空間分析等技術來實現的。但是在空間數據庫隱含知識的發(fā)現方面，只單獨依靠某一種技術，往往存在著這樣或那樣的缺陷。對于專家系統(tǒng)來講，專家系統(tǒng)不具備自動學習的能力，GIS中的專家系統(tǒng)也達不到真正的智能系統(tǒng)的要求，僅能利用已有的知識進行推導。對于數據挖掘來講，空間數據庫與普通數據庫的在數據存儲機制的不同和空間數據的相互依賴性等特點決定了在空間數據庫無法直接采用傳統(tǒng)的數據挖掘方法。對于空間分析來講，雖然空間分析中常用的統(tǒng)計方法可以很好地處理數字型數據，但是它存在的問題很多，如統(tǒng)計方法通常假設空間分布的數據間是統(tǒng)計上獨立的，而現實中空間對象間一般是相互關聯(lián)的；其次，統(tǒng)計模型一般只有具有相當豐富領域知識和統(tǒng)計方面經驗的統(tǒng)計專家才能用；另外，統(tǒng)計方法對大規(guī)模數據庫的計算代價非常高，所以在處理海量數據方面能力較低。
　　從上面的分析可以看出，由于空間數據具有諸多特點，因此在空間數據庫進行知識發(fā)現，需要克服使用單一技術的缺陷，即需要融合多種不同技術。所以研究人員提出了空間數據挖掘技術來解決從空間數據庫知識發(fā)現隱含知識的難題。
　　空間數據挖掘是多學科和多種技術交叉綜合的新領域，它綜合了機器學習、空間數據庫系統(tǒng)、專家系統(tǒng)、可移動計算、統(tǒng)計、遙感、基于知識的系統(tǒng)、可視化等領域的有關技術。
　　空間數據挖掘利用空間數據結構、空間推理、計算幾何學等技術，把傳統(tǒng)的數據挖掘技術擴充到空間數據庫并提出很多新的有效的空間數據挖掘方法。與傳統(tǒng)空間分析方法相比，它在實現效率、與數據庫系統(tǒng)的結合、與用戶的交互、發(fā)現新類型的知識等方面的能力大大增強。空間數據挖掘能與GIS的結合，使GIS系統(tǒng)具有自動學習的功能，能自動獲取知識，從而成為真正的智能空間信息系統(tǒng)。

2　擴展傳統(tǒng)數據挖掘方法到空間數據庫
　　空間數據挖掘技術按功能劃分可分為三類：描述、解釋、預測。描述性的模型將空間現象的分布特征化，如空間聚類。解釋性的模型用于處理空間關系，如處理一個空間對象和影響其空間分布的因素之間的關系。預測型的模型用來根據給定的一些屬性預測某些屬性。預測型的模型包括分類、回歸等。以下介紹將幾個典型的數據挖掘技術聚類、分類、關聯(lián)規(guī)則擴展到空間數據庫的方法。
　　聚類分析方法按一定的距離或相似性測度將數據分成一系列相互區(qū)分的組，而空間數據聚類是按照某種距離度量準則，在某個大型、多維數據集中標識出聚類或稠密分布的區(qū)域，從而發(fā)現數據集的整個空間分布模式。經典統(tǒng)計學中的聚類分析方法對海量數據效率很低，而數據挖掘中的聚類方法可以大大提高聚類效率。文獻[1]中提出兩個基于CLARANS聚類算法空間數據挖掘算法SD和ND，可以分別用來發(fā)現空間聚類中的非空間特征和具有相同非空間特征的空間聚類。SD算法首先用CLARANS算法進行空間聚類，然后用面向屬性歸納法尋找每個聚類中對象的高層非空間描述；ND算法則反之。文獻[4]中提出一種將傳統(tǒng)分類算法ID3決策樹算法擴展到空間數據庫的方法，該算法給出了計算鄰近對象非空間屬性的聚合值的方法，并且通過對空間謂詞進行相關性分析和采用一種逐漸求精的策略使得計算時間復雜度大大降低。Koperski等[4]將大型事務數據庫的關聯(lián)規(guī)則概念擴展到空間數據庫，用以找出空間對象的關聯(lián)規(guī)則。此方法采用一種逐漸求精的方法計算空間謂詞，首先在一個較大的數據集上用MBR最小邊界矩形結構技術對粗略的空間謂詞進行近似空間運算，然后在裁剪過的數據集上用代價較高的算法進一步改進挖掘的質量。

3　空間數據庫實現技術
　　空間數據挖掘系統(tǒng)中，空間數據庫負責空間數據和屬性數據的管理，它的實現效率對整個挖掘系統(tǒng)有著舉足輕重的影響。所以下面詳細介紹空間數據庫的實現技術。
　　根據空間數據庫中空間數據和屬性數據的管理方式，空間數據庫有兩種實現模式：集成模式和混合模式。后者將非空間數據存儲在關系數據庫中，將空間數據存放在文件系統(tǒng)中。這種采用混合模式的空間數據庫中，空間數據無法獲得數據庫系統(tǒng)的有效管理，并且空間數據采用各個廠商定義的專用格式，通用性差。而集成模式是將空間數據和屬性數據全部存儲在數據庫中，因此現在的GIS軟件都在朝集成結構的空間數據庫方向發(fā)展。下面對集成結構的空間數據庫技術中的兩個主流技術基于空間數據引擎技術的空間數據庫和以Oracle Spatial為代表的通用空間數據庫進行比較分析。
　　空間數據引擎是一種處于應用程序和數據庫管理系統(tǒng)之間的中間件技術。使用不同GIS廠商的客戶可以通過空間數據引擎將自身的數據交給大型關系型DBMS統(tǒng)一管理；同樣，客戶也可以通過空間數據引擎從關系型DBMS中獲取其他類型GIS的數據，并轉化成客戶可使用的方式。它們大多是在Oracle8i Spatial(較成熟的空間數據庫版本8.1.7于2000年9月推出)推出之前由GIS軟件開發(fā)商提供的將空間數據存入通用數據庫的解決方案，且該方案價格昂貴。
　　Oracle Spatial提供一個在數據庫管理系統(tǒng)中管理空間數據的完全開放體系結構。Oracle Spatial提供的功能與數據庫服務器完全集成。用戶通過SQL定義并操作空間數據，且保留了Oracle的一些特性，如靈活的n-層體系結構，對象定義，健壯的數據管理機制，Java存儲過程。它們確保了數據的完整性、可恢復能力和安全性，而這些特性在混合模式結構中幾乎不可能獲得。在Oracle Spatial中，用戶可將空間數據當作數據庫的特征使用，可支持空間數據庫的復制、分布式空間數據庫以及高速的批量裝載，而空間中間件則不能。除了允許使用所有數據庫特性以外，Spatial Cart ridge還提供用戶使用行列來快速訪問數據。使用簡單的SQL語句，應用者就能直接選取多個記錄。Spatial Cart ridge數據模型也給數據庫管理員提供了極大的靈活性，DBA可使用常見的管理和調整數據庫的技術。

4　空間數據挖掘系統(tǒng)的開發(fā)
　　4.1　通用SDM系統(tǒng)
　　在空間數據挖掘系統(tǒng)的開發(fā)方面，國際上最著名的有代表性的通用SDM系統(tǒng)有：GeoMiner，Descartes和ArcView GIS的S-PLUS接口。GeoMiner是加拿大Simon Fraser大學開發(fā)的著名的數據挖掘軟件DBMiner的空間數據挖掘的擴展模塊。空間數據挖掘原型系統(tǒng)GeoMiner包含有三大模塊：空間數據立方體構建模塊、空間聯(lián)機分析處理(OLAP)模塊和空間數據采掘模塊，能夠進行交互式地采掘并顯示采掘結果。空間數據采掘模塊能采掘3種類型的規(guī)則：特征規(guī)則、判別規(guī)則和關聯(lián)規(guī)則。GeoMiner采用SAND體系結構，采用的空間數據采掘語言是GMQL。其空間數據庫服務器包括MapInfo，ESRI/OracleSDE，Informix-Illustra以及其它空間數據庫引擎。
　　Descartes可支持可視化的分析空間數據，它與開發(fā)此軟件的公司所開發(fā)的數據挖掘工具Kepler結合使用，Kepler完成數據挖掘任務且擁有自己的表現數據挖掘結果的非圖形界面。Kepler和Descarte動態(tài)鏈接，把傳統(tǒng)DM與自動作圖可視化和圖形表現操作結合起來，實現C4.5決策樹算法、聚類、關聯(lián)規(guī)則的挖掘。
　　ArcView GIS的S-PLUS接口是著名的ESRI公司開發(fā)的，它提供工具分析空間數據中指定類。
　　除了以上空間數據挖掘系統(tǒng)外，還有GwiM等系統(tǒng)。
　　從以上SDM系統(tǒng)可以看出，它們的共同優(yōu)點是把傳統(tǒng)DM與地圖可視化結合起來，提供聚類、分類等多種挖掘模式，但它們在空間數據的操作上實現方式不盡相同。Descartes是專門的空間數據可視化工具，它只有與DM工具Kepler結合在一起，才能完成SDM任務。而GeoMiner是在MapInfo平臺上二次開發(fā)而成，系統(tǒng)龐大，造成較大的資源浪費。S-PLUS的局限在于，它采用一種解釋性語言(Script)，其功能的實現比用C和C++直接實現要慢得多，所以只適合于非常小的數據庫應用。基于現存空間數據挖掘系統(tǒng)的結構所存在的缺陷，我們提出空間數據挖掘系統(tǒng)一種新的實現方案。
　　4.2　空間數據挖掘系統(tǒng)一種新的實現方案
　　以上幾種系統(tǒng)都是用自己開發(fā)的或GIS軟件開發(fā)商提供的GIS平臺、組件或中間件來實現SDM系統(tǒng)中空間數據管理和分析。本文中提出了空間數據挖掘系統(tǒng)一種新的實現方案，即以現在通用空間數據庫(Oracle Spatial)為核心，利用其空間數據管理和空間分析的能力，完成空間數據挖掘中大量的空間信息抽取任務，GIS組件只承擔對挖掘結果的地圖化顯示任務。采用這種模式，不僅可實現GIS系統(tǒng)與空間數據挖掘系統(tǒng)完全集成，并且由于大部分空間信息抽取過程直接在低層數據庫上進行，從而可大大提高計算效率。
　　新的空間數據挖掘系統(tǒng)結構如圖1所示。該系統(tǒng)的基本結構與一般數據挖掘系統(tǒng)相同，僅在數據挖掘和數據管理中增加了有關空間信息的抽取、空間數據管理和空間分析的功能，并建立了一個人機接口處理用戶的指令和顯示挖掘結果。
　　　　圖1　新的空間數據挖掘系統(tǒng)結構
　　這種開發(fā)模式與現存開發(fā)模式的最大區(qū)別是用通用空間數據庫代替專門的GIS商用軟件實現空間數據管理和空間分析功能。它的優(yōu)點如下：
　　(1)GIS商用軟件一般是為開發(fā)GIS系統(tǒng)而設計的。GIS作為一個獨立軟件系統(tǒng)時，需要具有完整的功能結構，而在為數據挖掘服務時，其主要目的在于為決策者提供決策對象及顯示作為挖掘結果的地圖，因此只要按需選取GIS的部分功能，而不必面面俱到。GIS的一些功能，如空間數據的管理和空間分析等，在通用空間數據庫系統(tǒng)中存在相似模塊，因此可由通用空間數據庫管理系統(tǒng)中已有功能得到。空間數據和屬性數據的查詢和空間操作可利用數據庫管理功能，數據挖掘分析模塊則可作為一個或多個模塊，由數據挖掘子系統(tǒng)統(tǒng)一管理，而空間數據的存儲管理與分析均交給通用空間數據庫完成。這樣不僅可減少系統(tǒng)的功能冗余，提高系統(tǒng)的一致性，還可更好地利用商用數據管理系統(tǒng)的各種優(yōu)化技術來提高系統(tǒng)空間數據管理與分析的速度。
　　(2)從異構數據庫的集成和空間數據與屬性數據的統(tǒng)一管理來看，目前不同GIS廠商的遵循的空間數據格式標準不同，GIS通用平臺或組件一般只能直接處理本系統(tǒng)的空間數據文件，因此異種數據庫的集成是一個難題。而通用空間數據庫提供了數據轉換接口，可以將各種不同格式的空間數據轉換為統(tǒng)一的格式存入擴展的對象——關系數據庫，從而很好地解決了異種數據庫的集成的問題。另外，它還克服了GIS系統(tǒng)空間數據與屬性數據分離的缺點。
　　(3)從數據挖掘與空間數據庫技術結合來看，空間數據庫系統(tǒng)與數據挖掘系統(tǒng)完全分開的系統(tǒng)盡管簡單，但有不少缺點。首先，空間數據庫系統(tǒng)在存儲、組織、訪問和處理數據立方體方面提供了很大的靈活性和有效性。在空間數據庫(SDB)/空間數據倉庫(SDW)系統(tǒng)中，數據多半被很好地組織、索引、清理、集成或合并，使得找出任務相關的、高質量的數據成為一件容易的任務。不使用SDB/SDW系統(tǒng)，數據挖掘系統(tǒng)可能要花大量的時間查找、收集、清理和轉換數據。其次，在SDB或SDW系統(tǒng)中，有許多被測試的、可伸縮的算法和數據結構，因此，使用這種系統(tǒng)開發(fā)有效的、可伸縮的實現，是切實可行的。此外，大部分數據已經或將要存放在SDB/SDW系統(tǒng)中，不與這些系統(tǒng)耦合，數據挖掘系統(tǒng)就需要使用其它工具提取數據，使得很難將這種系統(tǒng)集成到信息處理環(huán)境。
　　(4)Oracle Spatial是專門為開發(fā)與執(zhí)行大型企業(yè)空間數據倉庫而研制的產品，它在海量空間數據的存儲和組織上性能卓越，在開發(fā)基于空間數據倉庫的空間數據挖掘應用方面具有顯著的優(yōu)勢。
　　(5)Oracle Spatial分擔了SDM算法中部分空間數據抽取的任務，減輕了數據挖掘子系統(tǒng)的負擔；另外，由于Oracle對分布式應用的良好支持，從而為實現分布式空間數據挖掘及并行空間數據挖掘提供了最佳方案。
　　基于以上方案，筆者實現了一個基于Oracle Spatial的分布式空間數據挖掘原型系統(tǒng)。系統(tǒng)由五部分組成：①圖形用戶界面：用于進行交互式的挖掘并顯示挖掘結果；②數據準備模塊：進行數據的選擇、預處理和轉換；③挖掘模塊：聚類、分類、關聯(lián)規(guī)則等空間數據挖掘功能及挖掘結果的評價；④空間數據管理模塊：執(zhí)行數據準備模塊及挖掘模塊指定的空間操作；⑤數據庫服務器：管理作為挖掘目標的空間數據和非空間數據及概念層次庫、挖掘結果庫。挖掘目標的空間和非空間數據及概念層次的存儲和空間數據的管理由Oracle8.1.7 Spatial實現。數據準備算法和聚類、分類、關聯(lián)規(guī)則等挖掘算法在服務器端實現，并提供接口給客戶端，在客戶端用GIS組件MapX4.0實現挖掘結果的專題圖顯示。其編程工具為VC++6.0。

參考文獻
[1] R T Ng, J Han. Efficient and Effective Clustering Methods for Spatial Data Mining[A]. Proc. of Twentieth International Conference on Very Large Data Bases[C]. Santiago, Chile, 1994.144-155.
[2] K Koperski, J Han. Discovery of Spatial Association Rules in Geographic Information Databases[A]. Proc
of Fourth International Symposium on Large Spatial Databases[C]. Maine, 1995.47-66.
[3] J Han, K Koperski, N Stefanovic. GeoMiner : A System Prototype for Spatial Data Mining[A]. Proc. of
ACM SIGMOD Conference on the Management of Data[C]. Tucson, Arizona, USA, 1997.553-556.
[4] K Koperski, J Adhikary, J Han. Knowledge Discovery in Spatial Databases : Progress and Challenges[A].
Proc. of ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery[C]. Montreal, Canada , 1996.55-70.