通用關(guān)聯(lián)規(guī)則挖掘框架的設(shè)計與實現(xiàn)

董 林，舒 紅

（1.武漢大學(xué) 測繪遙感信息工程國家重點實驗室，湖北 武漢 430079）

通用關(guān)聯(lián)規(guī)則挖掘框架的設(shè)計與實現(xiàn)

董 林1，舒 紅1

（1.武漢大學(xué) 測繪遙感信息工程國家重點實驗室，湖北 武漢 430079）

對適用于多種數(shù)據(jù)類型的關(guān)聯(lián)規(guī)則挖掘框架進行了研究。從概率論出發(fā)討論了支持度計算問題，提出利用有限測度計算項集支持度的方法，分析了Apriori性質(zhì)的本質(zhì)，提出通用關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計思路。在此基礎(chǔ)上，設(shè)計并實現(xiàn)了通用關(guān)聯(lián)規(guī)則挖掘框架，使用該框架進行了事務(wù)、空間和時空數(shù)據(jù)的挖掘?qū)嶒灒炞C了其可行性、通用性及正確性。

關(guān)聯(lián)規(guī)則；空間關(guān)聯(lián)規(guī)則；時空關(guān)聯(lián)規(guī)則；支持度；測度；通用框架

關(guān)聯(lián)規(guī)則挖掘是一種用于分析事物和現(xiàn)象之間內(nèi)在聯(lián)系的數(shù)據(jù)挖掘方法，挖掘的對象可以是數(shù)據(jù)庫或數(shù)據(jù)倉庫中的事務(wù)數(shù)據(jù)[1]，也可以是空間、時態(tài)或時空數(shù)據(jù)[2-4]，隨著研究與應(yīng)用的發(fā)展，更多種類的數(shù)據(jù)將成為關(guān)聯(lián)規(guī)則挖掘的對象。多樣化的數(shù)據(jù)帶來了對多樣化挖掘算法的需求，研究適用于多種數(shù)據(jù)類型的算法框架對加速新算法的設(shè)計與實現(xiàn)有重要意義。為此，提出一種通用關(guān)聯(lián)規(guī)則挖掘框架GARMF（general association rule mining framework）。

1 理論基礎(chǔ)

要設(shè)計適用于多種數(shù)據(jù)類型的通用挖掘框架，必須解決2個問題：①將針對不同數(shù)據(jù)類型的項集支持度計算方法納入統(tǒng)一框架；②找出通用的關(guān)聯(lián)規(guī)則挖掘算法。關(guān)聯(lián)規(guī)則挖掘是從數(shù)據(jù)中提取頻繁模式（頻繁項集和關(guān)聯(lián)規(guī)則）的過程，模式頻繁與否是根據(jù)其支持度（即對應(yīng)事件發(fā)生的概率）進行判斷的，因此支持度計算是關(guān)聯(lián)規(guī)則挖掘中最重要的操作。同時，關(guān)聯(lián)規(guī)則挖掘是一種復(fù)雜度較高的計算。為了確保挖掘效率，必須選用合理的挖掘算法。以概率論為基礎(chǔ)，GARMF利用有限測度之比以及經(jīng)典Apriori算法的框架來解決這2個問題，下面對其原理進行介紹。

1.1 基本概念

定義1 σ域。由非空集合X的一些子集組成的集合稱為X上的集合系。滿足以下3個條件的集合系F稱為σ域（也稱作σ代數(shù)）：

定義2 測度。設(shè)E是X上的集合系且?∈E，如果E 上的非負集函數(shù)μ有可列可加性且有μ（?）=0，則稱之為E 上的（σ可加）測度（measure）。

稱（X，F(xiàn) ，μ）為測度空間，其中X是一個給定的非空集合，F(xiàn) 是X上的σ域，μ是F 上的測度。

定義3 概率。對于測度空間（X，F(xiàn) ，P），如果P（X）=1，則可以稱之為概率空間，稱P為概率測度，稱集合A∈F 為事件A，稱P（A）為事件A發(fā)生的概率。

定義4 項集。對于有限集I={i1，i2，…，in}，稱其中每個元素為一個項，稱2I中的元素為項集，稱包含n個項的項集為n-項集。

稱一個非空點集Ω為基本事件空間。給定一個映射f：I ?2Ω，對于任意項A∈I，稱f （i）為i的對應(yīng)事件。例如，對于事務(wù)數(shù)據(jù)來說，基本事件空間Ω是用所有事務(wù)記錄的集合，一個項的對應(yīng)事件即其對應(yīng)字段取真值的事務(wù)記錄的集合。

對任意項集A={a1，a2，…，am}（A? I），稱為其對應(yīng)事件，稱P（Ae）為其支持度。

定義5 關(guān)聯(lián)規(guī)則。用 A，B? I（A ( B=?）組成的蘊含式A?B來表述條件概率P（Be|Ae），稱這個蘊含式為關(guān)聯(lián)規(guī)則，稱這個條件概率為該規(guī)則的置信度。稱A ' B為規(guī)則對應(yīng)的項集，那么Be(Ae就是規(guī)則對應(yīng)的事件，P（Be(Ae）就是規(guī)則的支持度。

1.2 支持度是有限測度之比

基于事務(wù)表的關(guān)聯(lián)規(guī)則挖掘算法大多是利用古典概型的概率公式計算支持度的。對于一個由m條事務(wù)記錄組成的事務(wù)表，如果滿足某項集的事務(wù)有m條，則該項集的支持度為m/n[2]。這是目前占主導(dǎo)地位的支持度計算方法。一些文獻采取了基于幾何概型的計算方法[6-9]，例如Estivill-Castro[7]利用面積之比來計算支持度：假設(shè)滿足某項集的區(qū)域面積為a，研究區(qū)域總面積為A，則該項集的支持度為a/A。雖然兩種方法有區(qū)別，但本質(zhì)上又是相同的：計算的都是項集對應(yīng)事件的概率，并且這個概率都是用一個除式得到的。基于古典概型的計算方法使用的是總事務(wù)數(shù)n和滿足項集的事務(wù)數(shù)m，它們的本質(zhì)是計數(shù)測度，這是一個有限測度；在基于幾何概型的計算方法中，研究區(qū)域總面積A和滿足某項集的區(qū)域的面積a，本質(zhì)上是面積測度，同樣是有限測度。顯然，這兩種方法實際上是用有限測度的比值來計算項集的支持度。對于基本事件空間Ω，假設(shè)存在定義于2Ω上的有限測度m，則任意項集A的支持度（即其對應(yīng)事件Ae∈2Ω的概率，）可以用如下公式計算：

m（Ω）/m（Ω）=1，由此可知：

1）m/m（Ω）是一個定義在2Ω上的概率測度；

2）m（Ae）/m（Ω）可稱作事件Ae的概率；

3）m（Ae）/m（Ω）作為A的支持度是合理的。式中，m（Ω）為數(shù)據(jù)總量； m（Ae）為項集A的支持度計數(shù)；項集的支持度等于其支持度計數(shù)與數(shù)據(jù)總量之比。對于任意一類描述事件域內(nèi)一組事件的數(shù)據(jù)，只要能找到可計算的有限測度m，就可對其進行關(guān)聯(lián)規(guī)則挖掘。

1.3 Apriori性質(zhì)的本質(zhì)

絕大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法會利用Apriori性質(zhì)來提高挖掘效率。所謂Apriori性質(zhì)，即任意頻繁項集的子集必然是頻繁的，或者說，任意項集的支持度不低于其超集的支持度。從概率論的角度來看，對于任意項集A、B（A，B? I），如果A? B則Be? Ae，那么對于任意概率測度P都有P（Be） ≤ P（Ae）。顯然，Apriori性質(zhì)的本質(zhì)是概率測度的非負性和可列可加性，是支持度固有的數(shù)學(xué)性質(zhì)，而不是由事務(wù)數(shù)據(jù)的邏輯或存儲結(jié)構(gòu)帶來的。因此，基于Apriori性質(zhì)的經(jīng)典Apriori算法[10]雖然是針對事務(wù)數(shù)據(jù)設(shè)計的，但將具體的支持度計算操作（即遍歷事務(wù)表）抽象為一般的支持度計算操作，就可以得到一個通用于各種數(shù)據(jù)類型的關(guān)聯(lián)規(guī)則挖掘算法。

2 框架的設(shè)計與實現(xiàn)

2.1 GARMF的架構(gòu)

關(guān)聯(lián)規(guī)則挖掘主要涉及數(shù)據(jù)、算法和挖掘結(jié)果這3類要素，GARMF將它們抽象為數(shù)據(jù)類、通用挖掘算法類和挖掘結(jié)果類，如圖1所示。

圖1 GARMF架構(gòu)圖

1）數(shù)據(jù)類。數(shù)據(jù)類是對可以用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)的抽象。不論挖掘?qū)ο鬄楹畏N類型的數(shù)據(jù)，不論采用何種挖掘算法，用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)總是描述項的對應(yīng)事件的數(shù)據(jù)，項集的支持度也總是利用有限測度m來計算。

2）通用挖掘算法類。現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法大都是針對某些具體的數(shù)據(jù)類型設(shè)計的，集成了訪問數(shù)據(jù)計算支持度的操作。在GARMF框架中，這一操作則由數(shù)據(jù)類負責(zé)，這使得挖掘算法與具體的數(shù)據(jù)類型相對獨立，具有較強的通用性。

3）挖掘結(jié)果類。挖掘結(jié)果類的功能是存儲頻繁項集和關(guān)聯(lián)規(guī)則。之所以還要保存頻繁項集是因為一些應(yīng)用所需的是頻繁項集，并且很多評價方法和增量挖掘算法要用到頻繁項集（及其支持度）。

2.2 GARMF的實現(xiàn)

本文將GARMF框架實現(xiàn)了一個Java類庫（稱作GARMF類庫），該類庫核心的3個類如圖2所示。

圖2 GARMF類庫的核心類

1）數(shù)據(jù)類（Data）。使用抽象類Data來表述可用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)（如圖3所示）。Data類最重要的3個屬性是miner、recordCount和items，分別為關(guān)聯(lián)規(guī)則挖掘算法、數(shù)據(jù)總量以及項集到對應(yīng)數(shù)據(jù)的映射；最重要的2個方法是mine和getSupportCount，即進行關(guān)聯(lián)規(guī)則挖掘和獲取指定項集的支持度計數(shù)。需要指出的是，雖然數(shù)據(jù)總量和支持度計數(shù)實際上是用同一個有限測度求出的，但對于一組數(shù)據(jù)其總量是恒定的，只需要求一次，而要計算支持度計數(shù)的項集則有很多個，因此數(shù)據(jù)總量recordCount被作為屬性來處理，getSupportCount則是作為方法。

2）挖掘結(jié)果（AssociationRules）。使用AssociationRules類來存儲挖掘結(jié)果，包括挖掘所使用的最小支持度和置信度閾值、挖掘得到的頻繁項集和關(guān)聯(lián)規(guī)則。挖掘閾值對挖掘結(jié)果的影響很大，并且是進行增量式挖掘的必要信息。

3）通用挖掘算法（DefaultApriori）。將Apriori算法[10]的核心抽取出來，得到了通用關(guān)聯(lián)規(guī)則挖掘算法DefaultApriori。該算法的輸入為Data對象，輸出為AssociationRules對象，與具體的數(shù)據(jù)類型無關(guān)。需要指出，該算法輸入的Data對象負責(zé)數(shù)據(jù)總量及支持度的計算。Data類是一個抽象類，應(yīng)當(dāng)根據(jù)具體的數(shù)據(jù)類型創(chuàng)建其實例，主要工作就是實現(xiàn)用于計算數(shù)據(jù)總量和支持度計數(shù)的有限測度。

為了便于使用，還實現(xiàn)了一些用于挖掘結(jié)果查看和持久化的類，并針對一些常用數(shù)據(jù)類型設(shè)計了Data的子類（部分見圖3），包括基于文件的/基于數(shù)據(jù)庫的/加權(quán)/模糊事務(wù)數(shù)據(jù)、空間數(shù)據(jù)（矢量/柵格）以及時空數(shù)據(jù)（快照序列）。這些雖然不是核心類，但對GARMF類庫的實用性有重要意義。

圖3 GARMF類庫中的數(shù)據(jù)類

3 實驗驗證

用GARMF對事務(wù)數(shù)據(jù)、柵格數(shù)據(jù)、矢量數(shù)據(jù)以及快照序列數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘?qū)嶒炓詸z驗其可行性與正確性。為了便于對比分析，本文使用與文獻[11]相同的實驗數(shù)據(jù)。該類庫以及實驗數(shù)據(jù)均可在作者網(wǎng)站http://www.c2001.net/GARMF.html下載（含API文檔，完成軟件著作權(quán)登記后將開放全部開源代碼）。

3.1 數(shù)據(jù)準備

本文實驗所使用的是美國地質(zhì)調(diào)查局（USGS）覆被變化趨勢項目網(wǎng)站（http://landcovertrends.usgs.gov）上提供的威拉米特河谷生態(tài)區(qū)（Willamette Valley Ecoregion）第3號樣本區(qū)（圖4）的覆被序列數(shù)據(jù)，由5幅大小為167×167像素、分辨率為60 m的柵格格式的覆被分類圖組成，分別對應(yīng)于該樣本區(qū)1972、1979、1985、1992和2000年的覆被狀態(tài)。數(shù)據(jù)涉及的覆被類型及它們在各個時期的狀況見表1。

圖4 威拉米特谷生態(tài)區(qū)第3號樣本區(qū)的地理位置[11]

表1 數(shù)據(jù)涉及的覆被類型及出現(xiàn)情況

要進行關(guān)聯(lián)規(guī)則挖掘，必須先選定項的集合。本文以時間與覆被類型的組合作為項，例如“1972年農(nóng)業(yè)用地”（簡記為1972AG）。如表1所示，實驗數(shù)據(jù)中實際存在的組合共38種（用對號標出），因此共有38 個項。接下來，分別將這組數(shù)據(jù)轉(zhuǎn)換為事務(wù)數(shù)據(jù)、矢量數(shù)據(jù)、柵格數(shù)據(jù)以及快照序列數(shù)據(jù)以進行挖掘?qū)嶒灐?/p>

1）事務(wù)表。以一個像素位置作為一個事務(wù)單元，研究區(qū)域可劃分為27 889個事務(wù)單元，因此實驗數(shù)據(jù)可以轉(zhuǎn)換為一個具有38個布爾型字段（對應(yīng)于38個項）、27 889條記錄的事務(wù)表，表中每條記錄存儲一個像素位置各年份的覆被狀態(tài)。例如，如果一個像素位置在1972、1979、1985、1992和2000年的覆被類型分別為AG、AG、AG、DU、DU，則相應(yīng)的事務(wù)記錄為{ 1972AG, 1979AG, 1985AG, 1992DU, 2000DU}（即這些字段取值為真，其余字段取值為假）。

2）柵格數(shù)據(jù)。依照像素值對覆被序列數(shù)據(jù)進行分割，得到一組由38個柵格圖層組成的柵格數(shù)據(jù)，每個圖層對應(yīng)一項，表示一種覆被在某一年份的空間分布情況。例如在1972AG對應(yīng)圖層中，如果一個像素取值為1，則表示該位置在1972年覆被類型為農(nóng)業(yè)用地。

3）矢量數(shù)據(jù)。對上一步驟所得到的柵格數(shù)據(jù)中每一個圖層進行矢量化，所得到的矢量圖層的集合就是一組可用于關(guān)聯(lián)規(guī)則挖掘的矢量數(shù)據(jù)（共含38個多邊形圖層）。

4）快照序列數(shù)據(jù)。將樣本區(qū)5種主要覆被類型（AG、DU、FW、WL和WT）保存為5個柵格快照序列，并生成了表述與它們在空間上鄰近/遠離（例如Near_AG和Far_AG）、由它們轉(zhuǎn)入/轉(zhuǎn)出（例如Trans_From_AG和Trans_To_AG）的時空區(qū)域的柵格快照序列，并將1972、1979、1985、1992和2000這5個年份用柵格快照序列來表述，得到一組由31個快照序列組成的快照序列數(shù)據(jù)。

3.2 實驗與分析

在實驗中用于挖掘的事務(wù)數(shù)據(jù)、柵格數(shù)據(jù)和矢量數(shù)據(jù)源于同一組覆被數(shù)據(jù)，二者表述的項相同，選取相同的支持度閾值，利用GARMF對其進行關(guān)聯(lián)規(guī)則挖掘所得結(jié)果應(yīng)當(dāng)完全一致。因此，可以將挖掘結(jié)果的一致性作為其正確性的判據(jù)。這些數(shù)據(jù)與文獻[11]中挖掘算法的輸入數(shù)據(jù)相同，因此還可以與該文獻中實驗結(jié)果（使用的不是GARMF）進行對比。

挖掘事務(wù)數(shù)據(jù)、柵格數(shù)據(jù)和矢量數(shù)據(jù)所使用的最小支持度閾值參照文獻[11]，設(shè)為10-7，得到3組頻繁項集，它們的數(shù)量、內(nèi)容和支持度完全一致（因此根據(jù)頻繁項集生成的關(guān)聯(lián)規(guī)則也相同），并且與文獻 [11]中的挖掘結(jié)果相符。挖掘得到的頻繁項集共有510個，包括38個1-項集、140個2-項集、189個3-項集、116個4-項集和27個5-項集。表2列出了支持度最高的5個頻繁5-項集，這些項集中都只包含對應(yīng)于同種覆被類型的項，且其支持度之和為93.858%，由此可知該樣本區(qū)從1972年到2000年覆被類型基本維持不變。

表2 支持度最高的頻繁5-項集

取10-7為最小支持度閾值、0.75為最小置信度閾值，對快照序列數(shù)據(jù)進行挖掘，共得到24 505個頻繁項集和54 045條關(guān)聯(lián)規(guī)則。其中，2到9-項集共24 474個，9-項集共有44個。9-項集中支持度大于0.1%的只有{AG, Near_DU, Far_WT, Far_WL, Far_FW, Trans_From_AG, Trans_To_DU, change, 1985}（0.11%）。由該項集可以得知，有一些1985年鄰近建筑用地的農(nóng)田到1992年會變?yōu)榻ㄖ玫亍Ｓ捎谠擁椉瑫r間項1985，可以直接用GIS對各項對應(yīng)于1985年的快照圖層進行求交得到該項集對應(yīng)的柵格快照序列中唯一一個非空圖層。該圖層共包含147個取值為1的像素，而研究區(qū)域總共有167×167×5=139 445個像素，其比例為0.11%，與挖掘結(jié)果一致。

顯然，GARMF類庫能夠?qū)κ聞?wù)數(shù)據(jù)、柵格數(shù)據(jù)、矢量數(shù)據(jù)和時空數(shù)據(jù)（快照序列）進行關(guān)聯(lián)規(guī)則挖掘并得到可靠的結(jié)果，這表明GARMF框架不僅是正確的理論框架，還是切實可行的。

4 結(jié) 語

本文設(shè)計并實現(xiàn)了GARMF框架，旨在降低挖掘新的數(shù)據(jù)類型的難度。對于任意一類可用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)，只需要找出數(shù)據(jù)總量和支持度計算方法（即有限測度m），就可以利用該框架對其進行挖掘。但GARMF主要關(guān)注關(guān)聯(lián)規(guī)則挖掘問題，挖掘結(jié)果（即頻繁項集和關(guān)聯(lián)規(guī)則）的評價、篩選及可視化方法還有待進一步研究與實現(xiàn)。

[1] Agrawal R, Imielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases[C].1993 ACM International Conference on Management of Data (SIGMOD93),1993

[2] Han J, Kamber M, Pel J. Data Mining:Concepts and Techniques[M]. Morgan Kaufmann, 2011

[3] Koperskik, Han J. Discovery of Spatial Association Rules in Geographic Information Databases[C].London: Springer Berlin Heidelberg, 1995

[4] 李光強, 鄧敏, 張維玲，等. 利用事件影響域挖掘時空關(guān)聯(lián)規(guī)則[J]. 遙感學(xué)報, 2010, 14(3): 468-481

[5] 程士宏. 測度論與概率論基礎(chǔ)[M]. 北京: 北京大學(xué)出版社, 2004

[6] 董林, 舒紅, 牛宵. 利用疊置分析和面積計算實現(xiàn)空間關(guān)聯(lián)規(guī)則挖掘[J]. 武漢大學(xué)學(xué)報:信息科學(xué)版, 2013, 38(1): 95-99

[7] Estivill-Castro V, Lee I. Data Mining Techniques for Autonomous Exploration of Large Volumes of Georeferenced Crime Data[C]. 6th International Conference on Geocomputation,2001

[8] Sha Z, Li X. Mining Local Association Patterns from Spatial Dataset[C].Fuzzy Systems and Knowledge Discovery (FSKD), 2010

[9] 李中元. 基于空間緩沖矩陣的空間關(guān)聯(lián)知識提取與表達[D].武漢：武漢大學(xué), 2012

[10] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules[C].20th International Conference on Very Large Databases(VLDB94),1994

[11] 董林, 舒紅, 李莎. 直接從空間數(shù)據(jù)中挖掘頻繁模式[J]. 計算機應(yīng)用研究, 2013, 30(8): 2 330-2 333

P208

B

1672-4623（2015）04-0068-04

10.3969/j.issn.1672-4623.2015.04.025

董林，博士，研究方向為空間數(shù)據(jù)挖掘。

2014-07-23。

項目來源：國家自然科學(xué)基金資助項目（41171313）;蘇州市科技計劃2013年應(yīng)用基礎(chǔ)研究計劃資助項目（SYG201319）。