時空關聯(lián)規(guī)則挖掘綜述

楊漢雨

摘 要：當前智慧城市的建設還停留在數(shù)字城市階段，但隨著“互聯(lián)網(wǎng)+”和“地理時空大數(shù)據(jù)”等外部因素的推動，智慧城市的建設迎來了良好的發(fā)展機遇，迫切需要“大數(shù)據(jù)思維”去推動數(shù)字城市向智慧城市發(fā)展，挖掘隱藏在數(shù)字城市中的知識。本文針對空間對象存在普遍的關聯(lián)性出發(fā)，研究了關聯(lián)規(guī)則挖掘的相關知識。分析了空間關聯(lián)規(guī)則挖掘和時空關聯(lián)規(guī)則挖掘的現(xiàn)狀；文章最后指出了時空關聯(lián)規(guī)則挖掘現(xiàn)狀存在的問題，并給出了初步的研究方案。

關鍵詞：智慧城市；時空數(shù)據(jù)挖掘；關聯(lián)規(guī)則；空間自相關

1.引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，信息爆炸已經(jīng)積累到了引發(fā)科學研究范式變革的程度，大數(shù)據(jù)時代已經(jīng)來臨。以3S技術、云計算、互聯(lián)網(wǎng)、物聯(lián)網(wǎng)等技術為基礎，使得地球空間與自然、人文對象的數(shù)據(jù)能夠更容易的被量測、存儲、管理、分析、顯示，進而反映自然與人文現(xiàn)象的空間分布規(guī)律，提供地理信息智能服務，構建智慧環(huán)境，如智慧城市、智慧戰(zhàn)場、智慧中國、智慧地球等。以智慧城市建設為例，當前智慧城市的建設還停留在數(shù)字城市的階段，但隨著“互聯(lián)網(wǎng)+”和“地理時空大數(shù)據(jù)”等外部因素的推動，迫切需要“大數(shù)據(jù)思維”去發(fā)掘“地理時空大數(shù)據(jù)”的潛在價值，進而加速智慧城市的建設。

空間數(shù)據(jù)挖掘（SDM）是地理時空大數(shù)據(jù)挖掘的基礎，是從一個空間數(shù)據(jù)中提取出有效的、新穎的、潛在有用的、并能最終被人理解的模式的非凡過程，揭示出蘊含在數(shù)據(jù)背后的客觀世界的本質(zhì)規(guī)律、內(nèi)在聯(lián)系和發(fā)展趨勢，實現(xiàn)知識的自動獲取，從而提供技術決策與經(jīng)營決策的依據(jù)，也是當前“智慧城市”建設的核心內(nèi)容?？臻g數(shù)據(jù)挖掘包含的內(nèi)容很多，包括空間聚類挖掘、關聯(lián)規(guī)則挖掘等等內(nèi)容。其中空間關聯(lián)規(guī)則挖掘是空間數(shù)據(jù)挖掘的重要內(nèi)容，其目的是發(fā)現(xiàn)現(xiàn)實世界中空間對象之間有趣的關聯(lián)模式或相互關系。

2.關聯(lián)規(guī)則的定義

關聯(lián)規(guī)則首先由Agrawa，并應用于零售行業(yè)，實現(xiàn)從顧客的購買記錄中發(fā)現(xiàn)顧客的購買模式，如“90%的男性顧客在購買了尿布的同時購買了啤酒”。這種購買模式即可以用X=>Y[s%，c%]形式的關聯(lián)規(guī)則表示。根據(jù)這條關聯(lián)規(guī)則，商場的決策者可以將擺放尿布的貨架和擺放啤酒的貨架放在一起，從而實現(xiàn)銷量的增長。關聯(lián)規(guī)則挖掘的實質(zhì)就是從數(shù)據(jù)中找出頻繁出現(xiàn)的模式，并以關聯(lián)規(guī)則的形式表示出來。

3.時空關聯(lián)規(guī)則挖掘的現(xiàn)狀

3.1 空間關聯(lián)規(guī)則挖掘現(xiàn)狀

關聯(lián)規(guī)則的研究主要集中在以下兩個方面：一是基于事務數(shù)據(jù)庫的關聯(lián)規(guī)則挖掘，首先將空間數(shù)據(jù)離散化轉(zhuǎn)換成事務數(shù)據(jù)庫，然后再使用基于事務數(shù)據(jù)的關聯(lián)規(guī)則算法對得到的事務數(shù)據(jù)庫進行規(guī)則挖掘，從而得到感興趣的空間關聯(lián)規(guī)則，其中空間數(shù)據(jù)離散化和對關聯(lián)規(guī)則算法進行改進來提高算法效率是該方法的兩個研究重點；二是基于空間事務的關聯(lián)規(guī)則挖掘，利用疊置分析、距離和面積計算等空間分析操作直接從空間圖層中提取關聯(lián)規(guī)則。

（1）基于事務數(shù)據(jù)庫的方法

Koperski和Han首先將關聯(lián)規(guī)則應用于空間數(shù)據(jù)挖掘，提出了一種空間關聯(lián)規(guī)則挖掘方法，該方法采用自上而下的策略，由用戶指定的領域作為空間關聯(lián)規(guī)則挖掘的事務，先對粒度較大的空間謂詞進行計算，發(fā)現(xiàn)較高概念層次的關聯(lián)規(guī)則，然后再對空間謂詞逐級細分發(fā)現(xiàn)較低層次的關聯(lián)規(guī)則。這兩個過程交替進行，直到無法發(fā)現(xiàn)新的規(guī)則為止。

（2）基于空間事務的方法

Lee和Hong等提出一種9DLT關聯(lián)規(guī)則挖掘算法，使用空間關系九交模型表示圖像之間關系，分別用數(shù)字0-8表示，并制作空間關系連接表，用來由k頻繁項集連接得到（k+1）項候選集，同時給出針對這種空間關系表達的關聯(lián)規(guī)則算法和剪枝策略。EstivillCastro和Lee提出了基于聚類的覆蓋圖方法，將屬性相同的實體作為一個圖層，對每一層的實體進行聚類分析，再對聚類產(chǎn)生的實體集間通過面積計算得到置信度和支持度從而進行關聯(lián)規(guī)則挖掘。陳江平等提出了一種基于空間分析的空間關聯(lián)規(guī)則挖掘方法，利用空間查詢和拓撲計算等空間分析技術對空間謂詞進行剪枝，構建拓撲關系概念層次樹并進行關聯(lián)規(guī)則挖掘。董林等提出利用疊置分析來進行關聯(lián)規(guī)則挖掘的算法，通過計算多邊形圖層重疊面積比來得到支持度，該算法不依賴實物數(shù)據(jù)庫，直接從矢量多邊形圖層中提取關聯(lián)規(guī)則，可從多種類型空間數(shù)據(jù)中提取出多謂詞關聯(lián)規(guī)則，并給出了對應的可視化方法。

3.2時空關聯(lián)規(guī)則挖掘現(xiàn)狀

時空關聯(lián)規(guī)則挖掘主要研究空間對象隨時間發(fā)生變化的規(guī)律，即在空間關聯(lián)分析的基礎上增加時間約束，以發(fā)現(xiàn)時空數(shù)據(jù)中處于一定時間間隔和空間位置的關聯(lián)規(guī)則。時空關聯(lián)規(guī)則挖掘的研究主要集中在時空關聯(lián)規(guī)則挖掘算法研究方面，目前時空關聯(lián)規(guī)則挖掘方法主要有：

（1）基于時空事務的挖掘方法：

這類算法通常由時空數(shù)據(jù)事務化算法和事務表挖掘算法組合而成，前者的作用是根據(jù)挖掘目標構建一個時空事務表，后者的作用是對這個事務表進行挖掘，從中提取頻繁項集和關聯(lián)規(guī)則，如Mennis J等、沙宗堯、Shu H.等在對研究區(qū)域進行空間劃分后，生成時空事務表，再進行關聯(lián)規(guī)則挖掘。Calargun S.U.等、和Laube P.等研究了模糊空間事務表的挖掘算法。

（2）不依賴事務的挖掘方法：

Li D.等對時空關聯(lián)規(guī)則挖掘中的插值問題進行了研究，認為地理學第一定律對于項的取值也成立，以此為依據(jù)提出一種基于空間統(tǒng)計的規(guī)則提取算法，利用已知點的關聯(lián)規(guī)則對無樣本站點的關聯(lián)規(guī)則進行估計。Estivill-castro V.等提出一種不依賴于事務數(shù)據(jù)表的空間關聯(lián)規(guī)則提取算法，依靠空間分析來實現(xiàn)支持度計算，對該算法進行拓展可以實現(xiàn)時空關聯(lián)規(guī)則挖掘。

（3）結合領域知識的關聯(lián)規(guī)則挖掘方法：

利用領域知識來指導關聯(lián)規(guī)則挖掘有利于提高挖掘結果的質(zhì)量。Fang G.等討論了基于約束條件的拓撲關聯(lián)規(guī)則挖掘方法。董林等[30]在進行空間關聯(lián)規(guī)則挖掘時添加了基于背景知識的約束條件，減少了候選集的數(shù)量；郭文月等[31]改進了現(xiàn)有挖掘算法需要指定挖掘時間區(qū)間的問題，提出一種非指定時間約束的時空關聯(lián)規(guī)則挖掘方法。

4.總結

關聯(lián)規(guī)則挖掘的研究熱點主要集中在算法改進、挖掘數(shù)據(jù)的組織上，在傳統(tǒng)關聯(lián)規(guī)則的基礎上，對時空數(shù)據(jù)進行一定的處理，如時空數(shù)據(jù)離散化、構造帶有時空知識標簽數(shù)據(jù)等，進行關聯(lián)規(guī)則挖掘，在這種處理過程中，目前采取的方法主要依靠人的先驗知識，以人工處理為主，使得處理后的數(shù)據(jù)會丟失一些信息，從而在關聯(lián)規(guī)則挖掘中失去一些有用的規(guī)則，如不同的空間方位劃分、時間劃分會導致挖掘的結果丟失一些重要的結果。若結合空間自相關分析等方法，對要挖掘的空間數(shù)據(jù)進行空間、時間上分布的檢測，得到一定先驗知識從而指導關聯(lián)規(guī)則挖掘，可以減少人的先驗知識帶來的影響。

參考文獻

[1]王家耀.深耕測繪一甲子：王家耀院士文集[M].科學出版社，2016.

[2]李德仁，王樹良，李德毅，等.論空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的理論與方法[J].武漢大學學報（信息科學版），2002（03）：221-233.

[3]李德仁，王樹良，李德毅.空間數(shù)據(jù)挖掘理論與應用[M].北京：科學出版社，2006.