基于有序樹的時空關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的應(yīng)用

楊井榮，柳 軍

(成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂山 614007)

0 引 言

目前Apriori算法仍是具有影響力的典型數(shù)據(jù)挖掘算法，在文獻(xiàn)[1]中全面化、系統(tǒng)化、深入化地介紹了該算法，Apriori算法中的兩個設(shè)計缺陷被發(fā)現(xiàn)，這兩個缺陷都是與性能效率有關(guān)。在算法執(zhí)行過程中，對于事務(wù)數(shù)據(jù)庫的多次讀取寫入操作，內(nèi)外存之間頻繁進(jìn)行數(shù)據(jù)交互導(dǎo)致執(zhí)行效率大大降低；在算法的中間階段，候選項集的大量產(chǎn)生，算法的中間過程過于龐大，無論時間消耗是空間消耗都是巨大的。

針對Apriori算法存在的性能問題，研究人員紛紛提出了改進(jìn)算法。在眾多改進(jìn)算法中，如文獻(xiàn)[2]介紹的Partition算法，影響算法的執(zhí)行效率的關(guān)鍵是如何設(shè)定劃分后的閾值；文獻(xiàn)[3]介紹的Hash算法，影響算法空間效率在于需要建立Hash表；文獻(xiàn)[4]介紹的FP-tree(頻繁增長模式樹)算法，影響算法效率在于存儲空間的限制，因為頻繁模式增長樹的生成隨著數(shù)據(jù)庫規(guī)模的增大而增大；另外，文獻(xiàn)[5]中還介紹了壓縮數(shù)據(jù)的改進(jìn)算法，算法的依據(jù)是按頻繁項集的先驗性質(zhì)。

1 關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘概念及原理

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

設(shè)I={i1,i2,…,im}是一個屬性(字段)集合，事務(wù)數(shù)據(jù)庫D={t1,t2,…,tn}是一個集合，它的元素全部是集合，即關(guān)鍵字標(biāo)識TID的集合，每個事務(wù)ti(i=1,2,…,n)是I中一組屬性集合，即ti∈I，其所含屬性個數(shù)稱為事務(wù)長度。關(guān)聯(lián)規(guī)則[6]在離散數(shù)學(xué)中，定義為X=>Y的蘊涵式，其中X?I，Y?I，X∩Y=?。關(guān)聯(lián)規(guī)則的蘊涵式X=>Y成立的條件有2個:

第一，它要具有支持度support(X=>Y)=count(X∪Y)/‖D‖，在定義中，‖D‖為集合D的基數(shù)。count(X)代表項集X在D中出現(xiàn)的次數(shù)。最小支持度的定義：由用戶確定的一個百分比，即項集A的基數(shù)與集合D的基數(shù)的百分比，記作Minsupport(最小支持度)。

第二，它要具有置信度C=confidence(X=>Y)=P(Y|X)=P(X∪Y)/P(X)，這個等式的中心意思是在數(shù)據(jù)庫D中包含Y元組的充分條件是包含X元組。根據(jù)上面的等式，引出最小置信度定義:由用戶定義一個百分比，即同時包含蘊含式前后項的個數(shù)與只包含蘊含式前項的個數(shù)的百分比。在兩個條件同時成立的關(guān)聯(lián)規(guī)則中，不小于最小支持度和置信度閾值的規(guī)則記為強關(guān)聯(lián)規(guī)則。

1.2 頻繁項目集概念

進(jìn)行關(guān)聯(lián)規(guī)則挖掘之前，指定I為全局屬性集，D為事務(wù)數(shù)據(jù)庫。若屬性集合L?I，L≠?，L的支持度超過(可以等于)最小支持度，當(dāng)support(L)≥Minsupport時，屬性集合L稱為頻繁項集，記為Lk，表示k-項頻繁集(文中遵照此約定)。

1.3 頻繁項目集的理論推理及相關(guān)性質(zhì)

性質(zhì)1：一個屬性集L是頻繁的充分條件是它的所有超集(包括本集合)是頻繁的屬性集。

推理1：一個屬性集L是非頻繁的是屬性集L的超集也是非頻繁的充分條件。根據(jù)此條件，L不會不是頻繁項集的元素，L的超集也不是頻繁項集的元素。

性質(zhì)2：如果可以刪除Lk，則說明一個事務(wù)長度不大于k,此事務(wù)不會包含k-項頻繁集。

1.4 經(jīng)典Apriori算法設(shè)計思路

在文獻(xiàn)[7]中，Apriori算法的思路如下:

步驟1:第一次掃描數(shù)據(jù)庫，計算出所有支持度大于等于最小支持度的字段，所有這些字段形成的集合即頻繁1-項集，構(gòu)成一個數(shù)據(jù)表，記為L1。

步驟2(連接步):對于第一次掃描的結(jié)果構(gòu)成數(shù)據(jù)表Lk-1時進(jìn)行全自連接生成候選項集Ck(k≥2)。

步驟3(剪枝步):對候選項集數(shù)據(jù)表Ck(k≥2)，按照頻繁項目集的相關(guān)性質(zhì)和相關(guān)推理進(jìn)行處理，刪除掉不滿足條件的項集，合并滿足條件的子集。

步驟4:通過步驟3的處理生成頻繁k-項集Lk。

步驟5:對于步驟2到步驟4進(jìn)行循環(huán)操作，循環(huán)結(jié)束的條件是：不能產(chǎn)生頻繁項集。

步驟6:通過上述1到5步生成的頻繁項集來計算關(guān)聯(lián)規(guī)則，根據(jù)具體的項目含義來判定出有決策力的強關(guān)聯(lián)規(guī)則。

在此算法中，中間的循環(huán)部分，每次生成頻繁集Lk都需要存儲海量的候選項集Ck，空間效率低，并且不斷地重復(fù)掃描數(shù)據(jù)庫D，時間效率也不高，并且形成了巨大的輸入輸出負(fù)載。

2 時空數(shù)據(jù)挖掘主要挖掘任務(wù)

根據(jù)挖掘數(shù)據(jù)的研究現(xiàn)狀，時空數(shù)據(jù)挖掘的挖掘任務(wù)或角度是根據(jù)時空數(shù)據(jù)的種類來分的。目前的挖掘主要集中在頻繁模式挖掘、預(yù)測挖掘、分類挖掘和聚類挖掘。按圖1把挖掘任務(wù)細(xì)分成子任務(wù)。

圖1 時空數(shù)據(jù)的挖掘任務(wù)

文獻(xiàn)[8]介紹了一種關(guān)聯(lián)模式挖掘，挖掘時空關(guān)聯(lián)規(guī)則是基于旋轉(zhuǎn)的方法來進(jìn)行多任務(wù)挖掘。文獻(xiàn)[9]介紹了一種在時空域擴(kuò)展應(yīng)用的經(jīng)典的Apriori算法。文獻(xiàn)[10]介紹了一種關(guān)聯(lián)規(guī)則STAR-Miner算法，針對特定項目隨時間跨區(qū)域移動變換的時空數(shù)據(jù)，能夠快速解決空間區(qū)域中不同區(qū)域大小的問題。在2009年，Leong等構(gòu)造了一種動態(tài)分析的架構(gòu)模式，主要應(yīng)用在兩個方面，一是用來挖掘兩個相異區(qū)域間的相互作用模式，二是用來挖掘空間相同但時間卻相異的頻繁關(guān)聯(lián)規(guī)則模式。夏英等在2011年對Apriori算法進(jìn)行了改進(jìn)，提出了一種STApriori算法，這個算法的長處主要是在分析時空數(shù)據(jù)時，能夠把無關(guān)冗雜的數(shù)據(jù)全部過濾掉，在時空數(shù)據(jù)中應(yīng)用非常有效，并對時空數(shù)據(jù)的空間關(guān)系、時間關(guān)系有效性進(jìn)行了高效地分析。由于時空數(shù)據(jù)的變化性，在2016年李圍成等著眼于挖掘出強的時空關(guān)聯(lián)規(guī)則，在基于FP-tree的數(shù)據(jù)結(jié)構(gòu)中，提出了一種時空關(guān)聯(lián)規(guī)則算法，將時空數(shù)據(jù)運算在FP-tree上。時空關(guān)聯(lián)規(guī)則在氣候科學(xué)、神經(jīng)科學(xué)、環(huán)境科學(xué)、精準(zhǔn)農(nóng)業(yè)、醫(yī)療保健、社交媒體、交通動態(tài)、太陽物理學(xué)等領(lǐng)域都有應(yīng)用。

3 關(guān)聯(lián)規(guī)則挖掘算法(canonical-order tree，CAN-tree)

3.1 算法衍生過程

Leung等人提出了一種基于樹結(jié)構(gòu)來改進(jìn)關(guān)聯(lián)規(guī)則的算法—CAN-tree(canonical-order tree)。該算法不再考慮候選項集，解決了FELINE和AFPIM所存在的弊端。CAN-tree的構(gòu)建只需對數(shù)據(jù)庫進(jìn)行一次掃描，這一點與掃描兩次數(shù)據(jù)庫的FPTree算法完全不同。在CAN-tree中，項是按照一種序列排好序的，序列的設(shè)定，可以由用戶在挖掘過程之前或者挖掘過程中根據(jù)實際情況進(jìn)行設(shè)定。

3.2 CAN-tree的構(gòu)建

首先，要對原始數(shù)據(jù)庫的事務(wù)項構(gòu)建樹結(jié)構(gòu)，構(gòu)建過程描述如下：

(1)用戶指定某一特定的自然序列(可以是自然序、字母序或者用戶自己設(shè)定的序列)設(shè)計為一個項目頭表。

(2)創(chuàng)建根節(jié)點root。

(3)掃描數(shù)據(jù)庫，并將每一條事務(wù)的記錄按照項目頭表進(jìn)行排序，接著對每一個數(shù)據(jù)項data進(jìn)行樹的節(jié)點插入操作，操作過程如步驟(4)。

(4)按照順序結(jié)構(gòu)訪問與data同名節(jié)點的文件位置。當(dāng)訪問到data對應(yīng)的已經(jīng)建立的同名節(jié)點的父節(jié)點時，如果檢查到與已經(jīng)存在的事務(wù)中項data的前項名相同，計數(shù)器自加。如果不同，則創(chuàng)建一個新的節(jié)點newnode1，新節(jié)點newnode1的父節(jié)點應(yīng)該與插入事務(wù)中的data項的前項名相同；返回步驟(4)，全部事務(wù)插入完成訪問結(jié)束。

3.3 頻繁項的挖掘過程

文中算法設(shè)置了一個項頭數(shù)據(jù)表，與FP-Growth算法一樣，該表中的關(guān)系模式(關(guān)系型)，第一包含基本實體信息，有關(guān)全部數(shù)據(jù)庫項目的信息及其計數(shù)，第二還包含鏈接信息，指向CAN-tree中項目的第一個節(jié)點和最后一個節(jié)點的邏輯地址。為了可以從樹中提取頻繁模式，還附加了一個頻繁項目列表，通過對表的訪問實現(xiàn)頻繁模式挖掘運算。按照算法的順序結(jié)構(gòu)，本算法的流程分為三步。按照順序從前往后描述，第一步是從CAN-tree的項頭表中選擇符合最小支持度閾值的項目為初始頻繁項目；第二步是對上一步得到的頻繁項目排序，排序規(guī)則是按照訪問計數(shù)升序排列，重新存儲到頻繁項目列表；第三步是從已有頻繁項目列表的最不頻繁(最小頻繁數(shù))的項目(首條記錄)開始，在樹中找到對應(yīng)的第一個節(jié)點，目的是為了提取結(jié)束點為這個節(jié)點的頻繁模式。在處理完第一個節(jié)點之后，包含相同項目的同級別節(jié)點被傳入。算法的復(fù)雜性體現(xiàn)于，要對包含該項目的每個節(jié)點執(zhí)行，挖掘過程重復(fù)進(jìn)行。挖掘操作從樹葉向樹根進(jìn)行，使用向上移動函數(shù)，提取出以當(dāng)前項結(jié)束的頻繁模式，挖掘操作從當(dāng)前節(jié)點向根進(jìn)行移動，每向上移動一次，樹會增長，因為要將它們存儲在條件模式列表中。并且還要對已經(jīng)添加到條件模式列表中的以當(dāng)前項目結(jié)束的頻繁項目集構(gòu)建新的CAN-tree，直到CAN-tree不再增長。

從上述算法的步驟可以看到，在執(zhí)行CAN-tree子樹時，按項集自己的特點能夠插入樹中的項目才是頻繁的項目，這是該挖掘算法的優(yōu)點，提高了挖掘效率，降低了時間復(fù)雜度。算法總的執(zhí)行過程是按樹的結(jié)構(gòu)向樹根部移動的過程中，函數(shù)(向上移動)會不斷檢查每個節(jié)點，以便判斷這個節(jié)點是否存在于頻繁項目列表中，也就是說，該項目達(dá)到頻繁與否。為了檢測新樹中的頻繁模式，重復(fù)執(zhí)行挖掘算法。發(fā)現(xiàn)沒有出現(xiàn)在頻繁模式列表中的屬性或?qū)傩约瘯r，將當(dāng)前項目追加到這些模式的表中。當(dāng)前項目末尾的所有頻繁模式都被添加到頻繁模式列表中，這是結(jié)束挖掘的條件。

具體挖掘過程如下：

(1)從CAN-tree自下而上挖掘，首先找到最下面的item(項)，構(gòu)建每個item(項)的條件模式基。順著CAN-tree樹，找出所有包含該item(項)的條件模式基(CPB)，即前綴路徑；所有這些CPB的頻繁度(總數(shù))為該路徑上item的頻繁度(總數(shù))。

(2)定義一個計數(shù)器，保存每個CPB上的item的頻繁度個數(shù)，排除低于閾值的屬性列表，構(gòu)建FP-tree。

(3)用不斷迭代的方法訪問每個條件FP-tree，對后綴頻繁項集進(jìn)行累加，迭代的終止條件有兩個，第一是找到整個CAN-tree為空，第二是CAN-tree只有一條路徑。第二種情況下，所有在路徑上item的組合都是頻繁項集，如圖2所示。

圖2 頻繁項的挖掘過程

4 實驗與性能分析

4.1 實驗數(shù)據(jù)及方法

實驗數(shù)據(jù)爬取自網(wǎng)站，文中所用的數(shù)據(jù)集，通過用戶簽到就可以分享他們的位置。取自用戶從2012年 1月至2013年1月共12個月的信息，即一個自然年的信息。實驗過程是用離線挖掘的模式。對于爬取的數(shù)據(jù)，經(jīng)過預(yù)處理，生成了1 200 000條數(shù)據(jù)，數(shù)據(jù)涉及到的用戶有200 000個，256 000個位置點。影響挖掘方案的性能有幾個方面，如何設(shè)置好各個方面對挖掘性能影響的權(quán)重是相對復(fù)雜的問題。如區(qū)域網(wǎng)格化、置信度、數(shù)據(jù)增量、支持度對性能都有影響。對于離線模式的數(shù)據(jù)挖掘，主要找到具有最大置信度的關(guān)聯(lián)規(guī)則。為了提高數(shù)據(jù)挖掘的實驗效果，能夠選擇最大規(guī)則數(shù)量，文中將支持度的閾值設(shè)置為總訪問請求數(shù)的0.000 16，即s=p=0.06%，置信度閾值為1.2%，即s=p=1.2%，進(jìn)行實驗，以確定不同的區(qū)域網(wǎng)格化水平評估指標(biāo)的變化，同時增加輸入數(shù)據(jù)集來提高測試增量下算法的性能。進(jìn)行實驗驗證之后，將文中提出的CSAR挖掘算法與文獻(xiàn)[11]提出的FPPN算法和文獻(xiàn)[12]提出的APFTC算法進(jìn)行了比較。

4.2 實驗結(jié)果和分析

從表 1可以看出，當(dāng)網(wǎng)格級別增加時，相同數(shù)據(jù)數(shù)量下，程序的執(zhí)行時間遞減的速度由迅速變緩慢。這是因為按照地理位置關(guān)系進(jìn)行數(shù)據(jù)的劃分，區(qū)域的劃分必將導(dǎo)致不相鄰數(shù)據(jù)單元之間關(guān)聯(lián)規(guī)則的丟失，也就是挖掘出關(guān)聯(lián)規(guī)則數(shù)會減少。無論進(jìn)行哪個類型，哪種數(shù)據(jù)的挖掘，都要根據(jù)實際應(yīng)用場景對挖掘的數(shù)據(jù)進(jìn)行最恰當(dāng)?shù)膭澐旨墑e設(shè)置。

表1 網(wǎng)格級別與整體挖掘時間關(guān)系

表2中，實驗數(shù)據(jù)的變化以萬級數(shù)據(jù)為單位。在數(shù)據(jù)量不同的情況下，對算法進(jìn)行了執(zhí)行時間的對比。由于區(qū)域間的數(shù)據(jù)的關(guān)聯(lián)規(guī)則數(shù)據(jù)的減少，為了保證一定的關(guān)聯(lián)規(guī)則數(shù)量，實驗中對劃分級別全部都是選擇的10行×10列。從表2中可以看出，CSAR的執(zhí)行效率比FPPN、APFTC[13]要高100到200秒。算法之間的差距會隨著數(shù)據(jù)量的增大而增大。原因在于FPPN、APFTC算法[14]有一個項頭表，新加入數(shù)據(jù)后項頭表要重新進(jìn)行排序，所以花費時間較CSAR多。從表1和表2的實驗對比來看，提出的CSAR算法，對于時空增量數(shù)據(jù)處理的效率有一定的提高和改善。

表2 三種挖掘算法在數(shù)據(jù)增量下的時間效率對比 s

5 結(jié)束語

提出的CSAR算法，是一種基于CAN-tree的時空關(guān)聯(lián)規(guī)則挖掘算法。在文中詳細(xì)闡述了算法的實現(xiàn)過程[15]、設(shè)計思路、執(zhí)行流程，最后驗證了該算法的有效性。概括來描述，首先將用戶訪問請求的歷史數(shù)據(jù)抽象到時空分量范圍內(nèi)，然后使用區(qū)域網(wǎng)格劃分的方法操作空間分量數(shù)據(jù)，算法結(jié)合了CAN-tree，在減少計算量的基礎(chǔ)上，對關(guān)聯(lián)規(guī)則動態(tài)變化問題進(jìn)行解決。另一方面，還在時間分量上考慮了時間分量值的衰減[16]，挖掘出的規(guī)則更具有實際參考價值。在驗證本算法的基礎(chǔ)上，與FPPN、APFTC算法進(jìn)行對比分析。最后通過表格對比列出驗證結(jié)果。所提出的CSAR算法對于時空數(shù)據(jù)領(lǐng)域的增量問題起到了一定的作用[17]，在時空數(shù)據(jù)分量的挖掘時間[18]效率上有所提高，可以顯著減少用戶，為決策者對數(shù)據(jù)的分析判斷做了相應(yīng)的準(zhǔn)備工作[19]。

CAN-Tree顯著減少了運算時間，因為它查找可合并的路徑比較簡單，且只需要向上的路徑遍歷。構(gòu)建CAN-Tree的運算時間是O(mn)，m是事務(wù)項的最大長度，n是事務(wù)的個數(shù)。盡管CAN-Tree提供了一個簡單的單次構(gòu)建過程，與FP-Tree相比，顯然占的空間還是比較大的。為了縮減樹的大小，在后續(xù)的過程分類中樹的調(diào)整過程可以被實施。通過分布式運算分類，CAN-Tree的這種構(gòu)建方式可以有效地減少運算時間。