關(guān)聯(lián)規(guī)則在空間數(shù)據(jù)挖掘中的研究
Research On Association Rules of Spatial Data Mining
曾玲　熊才權(quán)　胡恬
(湖北工業(yè)大學信息工程學院武漢430068)

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

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

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

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

　　　　　　表1　根據(jù)實際空間數(shù)據(jù)發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的例子
　　空間關(guān)聯(lián)規(guī)則　　　　　　　　　　　　　　　　　　　　　　支持度　置信度
　　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

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

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

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