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

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

中圖分類號(hào):TN919-34文獻(xiàn)標(biāo)識(shí)碼:A

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

剖分關(guān)聯(lián)規(guī)則指描述剖分面片之間或者面片內(nèi)空間對(duì)象之間的相鄰、相連、共生、包含等空間關(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中至少有一個(gè)空間謂詞，則含單個(gè)謂詞稱為1-謂，含k個(gè)謂詞稱為k-謂詞。c%是此規(guī)則的可信度，表示滿足規(guī)則前件的對(duì)象有c%的對(duì)象，同時(shí)滿足規(guī)則后件。根據(jù)定義，從一個(gè)大型的空間數(shù)據(jù)庫(kù)中可提取若干剖分關(guān)聯(lián)規(guī)則，但人們只對(duì)其中部分感興趣，規(guī)則的支持度和可信度是對(duì)兩個(gè)規(guī)則的興趣度量，它們分別反映規(guī)則的有用性和確定性。

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

(3) X在集合S中的支持度S定義為滿足X的對(duì)象數(shù)量與S中對(duì)象數(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ī)則的分類

為了便于進(jìn)一步研究剖分關(guān)聯(lián)規(guī)則，這里從空間謂詞涉及的空間范圍、數(shù)據(jù)抽象層次、屬性變量類型和數(shù)據(jù)維度四個(gè)角度對(duì)其進(jìn)行如下的分類[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ū)域或某一空間實(shí)體對(duì)象，稱之為局部剖分關(guān)聯(lián)規(guī)則。鄰域關(guān)聯(lián)規(guī)則的數(shù)據(jù)維屬性來(lái)源于兩個(gè)及以上相鄰或相離的空間實(shí)體對(duì)象。復(fù)合剖分關(guān)聯(lián)規(guī)則，涉及的維屬性來(lái)源于內(nèi)部和外部空間實(shí)體對(duì)象。

(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ù)的不同抽象層次?？鐚涌臻g關(guān)聯(lián)規(guī)則不但考慮同一層次上的關(guān)聯(lián)規(guī)則，同時(shí)還要考慮不同層次上的關(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ò)分段定性化與多維關(guān)聯(lián)規(guī)則相結(jié)合來(lái)進(jìn)行剖分關(guān)聯(lián)規(guī)則的挖掘。復(fù)合型剖分關(guān)聯(lián)規(guī)則涉及的屬性既有定性的布爾值數(shù)據(jù)又有定量的連續(xù)數(shù)值數(shù)據(jù)。

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

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

(1) 歸納方法

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

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

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

(3) 空間分析方法

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

(4) 聚類方法

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

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

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

(6) 可視化

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

(7) 遺傳算法

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

[2]趙文武，傅伯杰，呂一河，等.多尺度土地利用與土壤侵蝕[J].地理科學(xué)進(jìn)展，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ī)則與時(shí)空推理的漁業(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)用與擴(kuò)展[C].北京:中國(guó)GIS協(xié)會(huì)第二屆年會(huì)，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.