剖分關(guān)聯(lián)規(guī)則綜述

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

關(guān)鍵詞:空間關(guān)聯(lián)規(guī)則; 剖分關(guān)聯(lián)規(guī)則; 數(shù)據(jù)挖掘; 地理信息系統(tǒng)

中圖分類號:TN919-34文獻標(biāo)識碼: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技術(shù)的發(fā)展和進步，空間數(shù)據(jù)量日益增大，完全超出人們的分析和處理能力。傳統(tǒng)的空間數(shù)據(jù)分析方法只能進行簡單的數(shù)據(jù)分析，不能進行深層次的挖掘，無法滿足人們獲取知識的需要。現(xiàn)有數(shù)據(jù)庫系統(tǒng)雖然可高效地實現(xiàn)數(shù)據(jù)錄入、修改、查詢、統(tǒng)計等功能，卻無法發(fā)現(xiàn)隱藏在數(shù)據(jù)背后的關(guān)系、規(guī)則和發(fā)展趨勢等知識。數(shù)據(jù)挖掘和知識發(fā)現(xiàn)(SDMKD)興起于20世紀90年代，本質(zhì)是從數(shù)據(jù)庫中提取不明確和隱含的知識、空間關(guān)系等，目的是發(fā)現(xiàn)、解釋或預(yù)測空間現(xiàn)象或事件，其中空間關(guān)聯(lián)規(guī)則是空間數(shù)據(jù)挖掘的重要知識內(nèi)容。空間關(guān)聯(lián)規(guī)則(Spatial Association Rules)指的是空間實體間相鄰、相連、共生和包含等空間關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)的知識采用邏輯規(guī)則表達[1]。剖分關(guān)聯(lián)規(guī)則以空間數(shù)據(jù)剖分為基礎(chǔ)，更深層次的對空間目標(biāo)關(guān)聯(lián)關(guān)系進行挖掘。

1 剖分關(guān)聯(lián)規(guī)則及其分類

1.1 剖分關(guān)聯(lián)規(guī)則

Agrawal等在1993年提出了關(guān)聯(lián)規(guī)則的定義、概念，給出相應(yīng)挖掘的算法，并將其成功地應(yīng)用于商業(yè)領(lǐng)域[2-3]。Koprski K將傳統(tǒng)關(guān)聯(lián)規(guī)則引入空間數(shù)據(jù)挖掘領(lǐng)域，給出空間關(guān)聯(lián)規(guī)則的相關(guān)概念、挖掘過程和挖掘算法[4]。此后，學(xué)者們從概念、測度和挖掘算法等方面對空間關(guān)聯(lián)挖掘進行了深入的研究。

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

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

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

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

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

1.2 剖分關(guān)聯(lián)規(guī)則的分類

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

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

(2) 基于空間關(guān)系和屬性的抽象層次，可以分成單層關(guān)聯(lián)規(guī)則、多層關(guān)聯(lián)規(guī)則和跨層關(guān)聯(lián)規(guī)則。單層關(guān)聯(lián)規(guī)則不考慮空間數(shù)據(jù)的抽象層次，多層關(guān)聯(lián)規(guī)則考慮空間和屬性數(shù)據(jù)的不同抽象層次。跨層空間關(guān)聯(lián)規(guī)則不但考慮同一層次上的關(guān)聯(lián)規(guī)則，同時還要考慮不同層次上的關(guān)聯(lián)規(guī)則。

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

2 剖分關(guān)聯(lián)規(guī)則挖掘方法

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

(1) 歸納方法

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

(2) 統(tǒng)計方法

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

(3) 空間分析方法

空間分析能力是GIS的關(guān)鍵技術(shù)，是GIS系統(tǒng)區(qū)分于一般制圖系統(tǒng)的主要標(biāo)志之一。空間分析方法常作為數(shù)據(jù)預(yù)處理和特征提取方法與其他數(shù)據(jù)挖掘方法結(jié)合使用。

(4) 聚類方法

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

(5) 關(guān)聯(lián)規(guī)則挖掘方法

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

(6) 可視化

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

(7) 遺傳算法

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

3 剖分關(guān)聯(lián)規(guī)則的發(fā)展趨勢

剖分關(guān)聯(lián)規(guī)則挖掘是一個多學(xué)科交叉的綜合問題，需要充分理解GIS的有關(guān)知識。謂詞邏輯是剖分關(guān)聯(lián)規(guī)則挖掘過程中首先碰到的主要問題，適用于表達空間關(guān)系和地學(xué)背景知識，但不同專題圖層、不同空間對象之間的空間謂詞的計算與表達仍然是剖分關(guān)聯(lián)規(guī)則挖掘面臨的難點。雖然，目前有幾種對原有算法的改進，但它們?nèi)匀恢皇菍υ兴惴ǖ膬?yōu)化，以減少其時間復(fù)雜性和空間復(fù)雜性，提高空間謂詞的精確性。

通過研究近幾年的剖分關(guān)聯(lián)規(guī)則的產(chǎn)生、發(fā)展并結(jié)合GIS自身的特點，剖分關(guān)聯(lián)規(guī)則研究的未來發(fā)展趨勢是:

(1) 將面向?qū)ο蟮目諘r數(shù)據(jù)庫、空間連接索引、空間分析、空間數(shù)據(jù)倉庫等技術(shù)與GIS技術(shù)有效集成，在多層、跨層上自動挖掘剖分關(guān)聯(lián)規(guī)則。

(2) 基于空間關(guān)系、空間計算和空間分析的復(fù)雜性，對空間分析技術(shù)的進一步優(yōu)化以減少數(shù)據(jù)丟失，誤差將是下一步的研究的主要內(nèi)容。

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

(4) 在RS，GPS，GIS與專家系統(tǒng)集成中，其前提是空間數(shù)據(jù)信息的獲取，將獲取知識的關(guān)鍵技術(shù)——剖分數(shù)據(jù)挖掘技術(shù)，尤其是將剖分關(guān)聯(lián)規(guī)則挖掘與其相結(jié)合，這將是未來新的發(fā)展趨勢。

4 結(jié) 語

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

參考文獻

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

[2]趙文武，傅伯杰，呂一河，等.多尺度土地利用與土壤侵蝕[J].地理科學(xué)進展，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]蘇奮振，杜云艷，楊曉梅，等.地學(xué)關(guān)聯(lián)規(guī)則與時空推理的漁業(yè)分析應(yīng)用[J].地球信息科學(xué)，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技術(shù)及其在GIS中的應(yīng)用與擴展[C].北京:中國GIS協(xié)會第二屆年會，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.