剖分關聯規則綜述

摘 要:剖分關聯規則是描述剖分面片之間或者面片內空間對象之間的相鄰、相連、共生、包含等空間關聯的規則。從基本概念、分類、目前研究成果等方面對其進行綜述，重點闡述了剖分關聯規則的概念、挖掘方法等。通過對現有剖分關聯規則研究成果和存在問題的深入剖析，指出了其未來主要的發展方向。

關鍵詞:空間關聯規則; 剖分關聯規則; 數據挖掘; 地理信息系統

中圖分類號:TN919-34文獻標識碼:A

文章編號:1004-373X(2010)17-0014-03

Survey of Subdivision Association Rule

LI Tie-gen1， NIE Hong-shan2， SUN Zhao-lin2， ZENG Sheng-qiang1， ZHANG Yu-mei2， XU Xin2

(1. College of Continue Eduction， National University of Defense Technology， Changsha 410073， China;

2. College of Electronics Science and Engineering， National University of Defense Technology， Changsha 410073， China)

Abstract: The subdivision association rule is used to describe the subdivision surfaces or the space association of proximity， connectivity， symbiosis and inclusion between spatial objects in the surfaces. An annotated review of basic concepts， classification， current research achievements and so on is made. The concept and mining method of the subdivision association rule are elaborated emphatically. The future main development direction of subdivision association rule mining is pointed out while deeply analyzing the research achievements and existing problems.

Keywords: spatial association rule; subdivision association rule; data mining; geographic information system

隨著GIS技術的發展和進步，空間數據量日益增大，完全超出人們的分析和處理能力。傳統的空間數據分析方法只能進行簡單的數據分析，不能進行深層次的挖掘，無法滿足人們獲取知識的需要?，F有數據庫系統雖然可高效地實現數據錄入、修改、查詢、統計等功能，卻無法發現隱藏在數據背后的關系、規則和發展趨勢等知識。數據挖掘和知識發現(SDMKD)興起于20世紀90年代，本質是從數據庫中提取不明確和隱含的知識、空間關系等，目的是發現、解釋或預測空間現象或事件，其中空間關聯規則是空間數據挖掘的重要知識內容?？臻g關聯規則(Spatial Association Rules)指的是空間實體間相鄰、相連、共生和包含等空間關聯規則，發現的知識采用邏輯規則表達[1]。剖分關聯規則以空間數據剖分為基礎，更深層次的對空間目標關聯關系進行挖掘。

1 剖分關聯規則及其分類

1.1 剖分關聯規則

Agrawal等在1993年提出了關聯規則的定義、概念，給出相應挖掘的算法，并將其成功地應用于商業領域[2-3]。Koprski K將傳統關聯規則引入空間數據挖掘領域，給出空間關聯規則的相關概念、挖掘過程和挖掘算法[4]。此后，學者們從概念、測度和挖掘算法等方面對空間關聯挖掘進行了深入的研究。

剖分關聯規則指描述剖分面片之間或者面片內空間對象之間的相鄰、相連、共生、包含等空間關聯的規則。它表示空間謂詞與非空間謂詞的關系。這里將其定義概述如下[5]:

(1) 剖分關聯規則，如X1∧…∧Xm→Y1∧…∧Yn (c%)，令X=X1∧…∧Xm為規則前件，Y= Y1∧…∧Yn為規則后件。X1…Xm，Y1…Yn中至少有一個空間謂詞，則含單個謂詞稱為1-謂，含k個謂詞稱為k-謂詞。c%是此規則的可信度，表示滿足規則前件的對象有c%的對象，同時滿足規則后件。根據定義，從一個大型的空間數據庫中可提取若干剖分關聯規則，但人們只對其中部分感興趣，規則的支持度和可信度是對兩個規則的興趣度量，它們分別反映規則的有用性和確定性。

(2) 如果謂詞“X∧Y”，在集合S上是頻繁的且規則“X→Y/S”的可信度較高，則稱“X→Y/S”為強規則。

(3) X在集合S中的支持度S定義為滿足X的對象數量與S中對象數量之比，記為φ(X/S)。規則X→Y在集合S中的可信度定義為φ(X∧Y /S))與φ(X/S)之比，記為σ(X→Y/S)。

(4) 如果X的支持度不低于概念層次第k層的最小支持度閾值φ′k，則謂詞X在集合S的第k層是頻繁的，且X的所有祖先在相應的概念層次上也較頻繁。如果可信度不低于相應層的可信度閾值σ′k，則規則“X→Y/S”在集合S的第k層較高。

1.2 剖分關聯規則的分類

為了便于進一步研究剖分關聯規則，這里從空間謂詞涉及的空間范圍、數據抽象層次、屬性變量類型和數據維度四個角度對其進行如下的分類[6-7]:

(1) 根據空間謂詞涉及的空間范圍，可以將剖分關聯規則分成局部關聯規則、鄰域(包括鄰接和相離)關聯規則和復合關聯規則。若關聯規則的謂詞只涉及到某一區域或某一空間實體對象，稱之為局部剖分關聯規則。鄰域關聯規則的數據維屬性來源于兩個及以上相鄰或相離的空間實體對象。復合剖分關聯規則，涉及的維屬性來源于內部和外部空間實體對象。

(2) 基于空間關系和屬性的抽象層次，可以分成單層關聯規則、多層關聯規則和跨層關聯規則。單層關聯規則不考慮空間數據的抽象層次，多層關聯規則考慮空間和屬性數據的不同抽象層次?？鐚涌臻g關聯規則不但考慮同一層次上的關聯規則，同時還要考慮不同層次上的關聯規則。

(3) 根據剖分關聯規則處理的變量類型，可以分成布爾型關聯規則、數值型關聯規則和復合型關聯規則。布爾型關聯規則處理的變量都是定性化、種類化和離散化的，規則顯示了這些定性屬性之間的關系。數值型空間關聯規則處理的屬性是連續的，可以通過分段定性化與多維關聯規則相結合來進行剖分關聯規則的挖掘。復合型剖分關聯規則涉及的屬性既有定性的布爾值數據又有定量的連續數值數據。

2 剖分關聯規則挖掘方法

剖分數據挖掘是多學科和多技術綜合交叉的新領域，包括人工智能、數據庫、模式識別等領域的相關技術，因此它的方法不僅包括一般數據挖掘的方法，同時也有很多針對剖分數據庫的方法。下面簡要介紹剖分數據挖掘的方法[8-9]。

(1) 歸納方法

歸納學習是從大量的己知數據中歸納抽取出一般的判斷規則和模式，一般需要相應的背景知識。歸納學習在數據挖掘中的使用非常廣泛，己經有了成熟的理論算法。如著名的C4.5算法(由ID3算法發展而來)[10]，具有分類快和適用于大型數據庫的特點;AOI[11](面向屬性的歸納方法)，能歸納出高層次的模式或特征。

(2) 統計方法

統計方法具有較強的理論性和成熟的算法，多用于處理數字型數據。統計分析方法中的回歸分析、方差分析、主成分分析、因子分析等方法經常用于規律和模式的提取。但在空間數據挖掘中，由于空間對象屬性的相關性很強，在一定程度上限制了統計分析方法在剖分數據挖掘中的使用。

(3) 空間分析方法

空間分析能力是GIS的關鍵技術，是GIS系統區分于一般制圖系統的主要標志之一?？臻g分析方法常作為數據預處理和特征提取方法與其他數據挖掘方法結合使用。

(4) 聚類方法

聚類分析方法按一定的距離或相似性測度將數據分成一系列相互區分的組，不需要背景知識。經典方法有K-mean，K-medoid，ISODATA等，但對于大數據庫存在速度慢、效率低的問題。

(5) 關聯規則挖掘方法

關聯規則反映一個事物與其他事物之間的相互依賴性或相互關聯性。如果兩個或多個事物之間存在關聯，那么，其中一個事物就能從其他己知事物中預測得到。所謂關聯規則是指數據集中支持度和信任度分別滿足給定閾值的規則。經典的算法如R. Agrawal等人提出的Apriori算法[4]，以及對其的改進算法:AprioriTid， AprioriHybrid等。

(6) 可視化

可視化是一種將數據(特別是多維數據)以圖形方式顯示的計算機技術，其最新的發展為虛擬現實(VR)。由于人類對于圖形的模式識別能力非常強，遠遠超過現有的任何模式識別和異常檢測的計算機技術。因此，在數據挖掘中充分利用和發揮人的智慧是行之有效的方法。充分利用最新的可視化技術，不僅可以大大增強GIS系統的功能，同時也會給剖分數據挖掘帶來極大的便利。

(7) 遺傳算法

遺傳算法最先由John Holland于1975年提出，是一種有效的解決最優化問題的方法。它仿效生物的進化與遺傳，根據“生存竟爭”和“優勝劣汰”的原則，借助復制、交換、突變等操作，使要解決的問題從初始解逐漸逼近最優解。在數據挖掘中的分類、聚類、預測等問題，可以表達或轉換成最優化問題，進而用遺傳算法來求解。

3 剖分關聯規則的發展趨勢

剖分關聯規則挖掘是一個多學科交叉的綜合問題，需要充分理解GIS的有關知識。謂詞邏輯是剖分關聯規則挖掘過程中首先碰到的主要問題，適用于表達空間關系和地學背景知識，但不同專題圖層、不同空間對象之間的空間謂詞的計算與表達仍然是剖分關聯規則挖掘面臨的難點。雖然，目前有幾種對原有算法的改進，但它們仍然只是對原有算法的優化，以減少其時間復雜性和空間復雜性，提高空間謂詞的精確性。

通過研究近幾年的剖分關聯規則的產生、發展并結合GIS自身的特點，剖分關聯規則研究的未來發展趨勢是:

(1) 將面向對象的空時數據庫、空間連接索引、空間分析、空間數據倉庫等技術與GIS技術有效集成，在多層、跨層上自動挖掘剖分關聯規則。

(2) 基于空間關系、空間計算和空間分析的復雜性，對空間分析技術的進一步優化以減少數據丟失，誤差將是下一步的研究的主要內容。

(3) 由于GIS數據的多維特性，其地理實體不僅具有三維幾何特性，而且有些還具有時空性。因此，在多維GIS數據庫中，挖掘剖分關聯規則以獲取用戶感興趣的知識也將是未來的發展趨勢。

(4) 在RS，GPS，GIS與專家系統集成中，其前提是空間數據信息的獲取，將獲取知識的關鍵技術——剖分數據挖掘技術，尤其是將剖分關聯規則挖掘與其相結合，這將是未來新的發展趨勢。

4 結 語

介紹了剖分關聯規則的概念、分類，指出了剖分關聯規則是描述剖分面片之間或面片內的空間實體之間的關聯關系。闡述了剖分關聯規則挖掘的常用方法。結合GIS自身的發展，提出了剖分關聯規則研究的一些發展趨勢。

參考文獻

[1]李德仁，王樹良，史文中，等.論空間數據挖掘和知識發現[J].武漢大學學報:信息科學版，2001(6):54-57.

[2]趙文武，傅伯杰，呂一河，等.多尺度土地利用與土壤侵蝕[J].地理科學進展，2006，25(1):24-33.

[3]AGRAWAL R， IMIELINSKIN T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc. ACM SIGMOD. [S.l.]: ACM， 1993: 207-216.

[4]AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules in large databases[C]//Proc. 1994 Int. Conf. VLDB. California:VLDB， 1994: 487-499.

[5]KOPERSKI K， HAN J. Discovery of spatial association rules in geographic information databases[J]. Lecture Notes in Computer Science， 1995， 951:47-66.

[6] BEMBENIK Robert， RYBINSKI Henryk. Mining spatial association rules with no distance parameter[C]//Proc. Intelligent Information Processing and Web Mining. Heidelberg: Springer， 2006， 35: 499-508.

[7]蘇奮振，杜云艷，楊曉梅，等.地學關聯規則與時空推理的漁業分析應用[J].地球信息科學，2004，6(4):68-69.

[8]HAN J， Data mining techniques[C]//ACM-SIGMOD′96 Conf. Tutorial. Montreal， Canada: ACM， 1996(6): 78-82.

[9]邸凱昌，李德仁.KDD技術及其在GIS中的應用與擴展[C].北京:中國GIS協會第二屆年會，1996.

[10]QUINLAN J R. C4.5: programs for machine learning[M]. San Mateo，CA: Morgan Kaufmann， 1993: 81-90.

[11]HAN J， CAI Y， CERCONE N. Knowledge discovery in databases: an attxibute databases[J]. IEEE Trans. Know-ledge and Data Engineering， 1992(5): 29-40.