關聯規則在空間數據挖掘中的研究
Research On Association Rules of Spatial Data Mining
曾玲　熊才權　胡恬
(湖北工業大學信息工程學院武漢430068)

摘　要
　　在智能化、集成化的空間數據應用領域中，空間數據挖掘是一門很重要的技術，而關聯規則分析是空間數據挖掘的主要方法之一。文章基于數據挖掘中的關聯規則分析方法，提出不同于一般數據挖掘的算法，設定興趣度量，并通過將項的概念泛化為空間謂詞，事務的概念泛化為鄰域，關聯規則的概念泛化為同位規則，發現多種形式的有效規則，并用邏輯語言或類SQL語言方式描述規則，以使空間數據挖掘趨于規范化和工程化。最后進行了實評。
　　關鍵詞：關聯規則　空間數據庫　數據挖掘
　　中圖分類號：TP3l1.13

1　引言
　　隨著雷達、紅外、光電、衛星、電視攝像、電子顯微成像、CT成像等各種宏觀與微觀傳感器的普遍使用，空間數據的數量、大小和復雜性都在飛快地增長，已經遠遠超出了人的解譯能力。終端用戶不可能詳細地分析所有的這些數據，并提取感興趣的空間知識，致使“空間數據爆炸但知識貧乏”。因此，利用空間數據挖掘和知識發現[1](SDMKD，Spatial Data Mining and knowledge discovery)從空間數據庫中自動或半自動地挖掘事先未知卻潛在有用的空間模式變得十分必要。
　　SDMKD所能發現的知識主要包括空間的關聯、特征、分類和聚類等規則。一般表現為一組概念、規則、法則、規律、模式、方程和約束等形式的集合，是對數據庫中數據屬性、模式、頻度和對象簇集等的描述。常用的空間數據挖掘技術包括：空間關聯規則分析、分類分析、聚類分析、時間序列分析、粗集方法等。
　　由于空間關聯規則分析可快速地、較好地發現隱含的空間地理位置的相關性，文章基于數據挖掘中的關聯規則分析方法，提出算法，通過設定興趣度量、將項的概念泛化為空間謂詞、將事務的概念泛化為鄰域、關聯規則的概念泛化為同位規則，并以邏輯語言或類SQL語言方式描述規則，根據位置圖尋找頻繁的空間事件類型的同位子集，發現多種形式的有效規則。

2　空間數據挖掘及其特殊性
　　數據挖掘是發現新穎的、有效和完全的能夠被人們理解的數據模式的一種方法。它結合統計和計算技術，從大量的數據集中獲取有用的模式，進而產生指導性的規則集合，這些規則是對數據庫中數據屬性、對象集的有效描述，提供給決策支持系統。
　　空間數據庫是在數據倉庫的基礎上，引入空間維數據，增加對空間數據的存貯、管理和分析能力，根據主題從不同的空間數據應用系統(如GIS)中截取從瞬態到區段直到全體地球系統的不同規模時空尺度上的信息，從而為當今的地學研究以及有關環境資源政策的制定提供最好的信息服務。空間數據庫中的空間數據除了其顯式信息外，還具有豐富的隱含信息，如數字高程模型[DEM或TIN]，除了載荷高程信息外，還隱含了地質巖性與構造方面的信息；植物的種類是顯式信息，但其中還隱含了氣候的水平地帶性和垂直地帶性的信息，等等。這些隱含的信息只有通過數據挖掘才能顯示出來。
　　空間數據挖掘和知識發現(SDMKD)是計算機技術、數據庫應用技術和管理決策支持技術等發展到一定階段、多學科交叉的新興邊緣學科，匯集了來自機器學習、模式識別、數據挖掘與空間數據庫技術、統計學、人工智能以及管理信息系統等各學科的成果[2]。
　　SDMKD與傳統的地學數據分析方法的本質區別在于SDM 是在沒有明確假設的前提下去挖掘信息、發現知識，挖掘出的知識應具有事先未知、有效和可實用三個特征。
　　SDMKD也不同于普通的數據挖掘和知識發現，它的對象主要是空間數據庫或空間數據倉庫，有別于常規的事務型數據庫，空間數據庫中不僅存儲了空間事物或對象的幾何數據、屬性數據，而且存儲了空間事物或對象之間的圖形空間關系等，因此，SDM比一般數據挖掘的發現狀態空間理論[3]增加了尺度維(scale)SDM的處理方法有別于一般的數據挖掘方法。
　　SDMKD具有廣泛的應用前景和潛在的綜合效益，隨著空間數據量的增加及軟硬件技術的發展，其應用正日益滲透到人們認識和改造空間世界的各個學科，如地理信息系統、信息融合、遙感、圖像數據庫、醫療圖像處理、導航、機器人等使用空間數據的領域。SDMKD發現的知識將會促進這些學科的自動化和智能化。因此，SDMKD當前相當于數據庫技術在70年代所處的地位，迫切需要類似于關系模式、DBMS系統和SQL查詢語言等模型和工具，才能使SDMKD的應用得以普遍推廣。

3　空間關聯規則及算法描述
　　關聯規則分析主要用于發現不同事件之間的關聯性，即一事物發生時，另一事物也經常發生。關聯規則分析的重點在于快速發現那些有實用價值的關聯發生的事件。一個關聯規則可以特征化為兩個參數：支持度(support)和置信度(confidence)[4]。其主要依據是：事件發生的概率和條件概率應該符合一定的統計意義。
　　此外，由于SDM過程可能產生大量模式，通常，這些模式中只有一小部分是特定用戶感興趣的，為此，需要進一步限制挖掘過程產生的不感興趣的模式數量。這可以通過設定興趣度量來實現。興趣度評估模式的簡潔性、確定性和新穎性。
　　生成空間關聯規則可采用兩種方法：第一種方法的焦點是空間謂詞而不是項，第二種方法將事務概念泛化以包括鄰域，將關聯規則的概念泛化為同位規則。從而發現多種形式的規則，并用邏輯語言或類SQL語言方式描述規則，使SDMKD趨于規范化和工程化。
　　3.1 空間關聯規則
　　空間謂詞的形式通常有：表示拓撲結構的謂詞、表示空間方向的謂詞和表示距離的謂詞等，例如，距離信息(如Close_to(臨近)、Far_away(遠離))、拓撲關系(Intersect(交)、Overlap(重疊)、Disjoin(分離))和空間方位(如Right_of(右邊)、West_of(西邊))等[5]。各種各樣的空間謂詞可以構成空間關聯規則。
　　一條空間關聯規則可表示為X=>Y(C%，S%，I%)，其中，X和Y是空間或非空間謂詞的集合，C%、S%和I%分別是規則的可信度、支持度和興趣度。
　　例如，規則
　　is_a(x，largetown)∧close_to(x，highway)=>close_to(x，water)[S%，c%，I%]
　　(即靠近高速公路的大城鎮通常與水相鄰)是一個支持度為S、置信度為C和興趣度為I的關聯規則)
　　與傳統的Apriori算法不同，空間關聯規則分析的優化算法可描述如下：
　　(1) 根據查詢要求查找相關的空間數據；
　　(2) 運用臨近等原則描述空間屬性和特定屬性；
　　(3) 過濾重要的數據，剔除不滿足最小支持度的空間謂詞；
　　(4) 運用興趣度量等其它手段對數據進一步提純(如OVERLAY)；
　　(5) 生成空間關聯規則。
　　表1-1給出一個根據給定的空間數據發現關聯規則的例子。

　　　　　　表1　根據實際空間數據發現關聯規則的例子
　　空間關聯規則　　　　　　　　　　　　　　　　　　　　　　支持度　置信度
　　close_to(x, golf course)  ->  Is_a(x,park)　　　　　　　　　　0.05　　0.86
　　water_depth(x,shallow)&Far_away(x,water)
　　　　　　　　->  Stem_height(x,high)　　　　　　　　　　　 0.05    0.95
　　Far_away(x,edge)&Stem_heitght(x,high)
　　　　　　　　->  Vegetation_durability(x,close)　　　　　　　0.1     0.94

　　由于關聯規則用于分類屬性，因此對于數據集為數值型的應用來說就很受限制。這是因為從數值到分類數據的變換涉及到一個離散化過程，在大多實例中這會有某些隨意性。
　　3.2 同位規則
　　同位規則試圖將關聯規則泛化為空間索引的點的集合數據集。在空間與非空間關聯之間有幾個關鍵區別，包括：
　　(1) 在空間數據的環境中，沒有事務的概念，因為數據嵌入到連續空間中。把空間分區成事務會導致高估或低估所感興趣的度量(如支持度或置信度)。
　　(2) 空間數據庫中項集的規模比較小，即在空間情況下項集中的項數遠小于非空間情況下的項數。例如，在零售業中，處理動輒有上萬個項數的不同項的情況非常普遍，而對空間數據集來說，這種情況就很少出現，空間項一般不超過幾十個。這意味著候選集生成的代價不再是Aprior算法的支配因素，而鄰域的枚舉(例如，頻繁項集的實例)在整體的計算代價中占主導地位。
　　(3) 在多數情況下，空間項是連續變量的離散化版本。例如，可以把那些年齡不大于14歲的人稱為未成年人。
　　在這種空間關聯規則發現方法中，采用區別于一般的數據挖掘方法，事務的概念被鄰域所取代，根據位置圖尋找頻繁的空間事件類型的同位子集，從而發現同位模式。例如，對動植物生活習性的分析可以得出捕獵肉食動物的物種、共生物種和具有燃燒源的火災事件之間的同位性。

4 結束語
　　本文提出了空間數據挖掘中關聯規則分析的基本思路和算法，通過設定興趣度，將一般關聯規則挖掘中項的概念泛化為空間謂詞，事務的概念泛化為鄰域，關聯規則的概念泛化為同位規則，以發現隱含的地理位置同位性等多種形式的有效空間關聯規則，并以邏輯語言或類SQL語言方式描述規則，從而使SDMKD趨于規范化和工程化。給出實驗結果，驗證了算法可行性。

參考文獻
[1] 李德仁等. 論空間數據挖掘和知識發現[J]. 武漢大學學報·信息科學版. 2001.26(6):491~492
[2] 鄔倫等. 地理信息系統一原理、方法和應用[M]. 科學出版社，2001
[3] Jia Wei Han，Micheline Kamber. 數據挖掘概念與技術[M]. 北京：機械工業出版社，2001,8
[4] 李德仁等. 論空間數據挖掘和知識發現的理論與方法[J]. 武漢大學學報·信息科學版，27(3)
[5] 邸凱昌. 空間數據挖掘和知識發現的理論與方法[D]. 武漢：武漢測繪科技大學，1999
[6] 王珊、羅立，從數據庫到數據倉庫. 計算機世界, 1996.28
[7] Shashi Shekhar, Sanjau Chawla. 空間數據庫[M]. 北京：機械工業出版社. 2004,1
[8] 楊靖、朱揚勇. 1997，數據挖掘中的關聯規則(Assoiation Rules)和序列模式，復旦大學計算機系博士學位論文