無重疊條件下的Top-k序列挖掘

武優(yōu)西,王振坤,史巧碩,劉靖宇

(河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院,天津 300401)

(河北省大數(shù)據(jù)計算重點實驗室,天津 300401)E-mail:wuc567@163.com

1 引 言

在數(shù)據(jù)挖掘議題中,序列模式挖掘一直是其中一項熱門話題.其核心要求為挖掘頻繁子模式.目前其已經(jīng)在商品推薦[1]、作者特征、預(yù)測HAS QoE[2]、影響力計算和子圖挖掘[3,4]等眾多挖掘任務(wù)中有重要應(yīng)用.為了避免挖掘出大量無關(guān)模式,近年來一種間隙約束的序列模式挖掘方式被提出.目前對于具有一定間隙的模式挖掘條件大體上可分為三類條件:無特殊條件,一次性條件和無重疊條件.舉例說明如下:設(shè)有序列S=s1s2…s6=aaatct,模式P=a[0,2]a[0,2]t,無特殊條件是指S中的任何字符都可以不計次數(shù)無限制使用,故P在S中的無特殊條件出現(xiàn)為<1,2,4>、<1,3,4>、<2,3,4>和<1,3,6>、<2,3,6>;一次性出現(xiàn)是指在序列S中,字符最多允許被使用一次,故而P在S中的一次性出現(xiàn)為<1,2,4>;而在無重疊出現(xiàn)條件下,序列中相同位置的字符不能在模式的相同位置處重復(fù)使用,故而P在S中的無重疊出現(xiàn)為<1,2,4>和<2,3,6>.可以看出無重疊條件相比前兩者而言,既減少了冗余模式,又保留了有效出現(xiàn).在無特殊條件序列模式挖掘方向,Zhang等人[5]研究了無特殊條件的間隙序列模式挖掘問題;王等人[6]設(shè)計了帶緊湊間隙約束的最小對比序列模式挖掘算法MDSP-CGC,目的是避免設(shè)置不恰當?shù)拈g隙約束導(dǎo)致出現(xiàn)大量冗余模式;在一次性條件挖掘方向,Wu等人[7]的挖掘算法解決了通配符約束下的頻繁模式挖掘問題;而在無重疊條件序列模式挖掘方向,Ding等人[8]提出了無重疊條件約束的概念,在此基礎(chǔ)上Wu等人[9]研究了無重疊條件下嚴格模式匹配的課題.Wu等人[10]提出的無重疊條件下的間隙序列模式挖掘算法NOSEP較其他序列模式挖掘算法具有更大的好處,可以有效地解決挖掘完備性與Apriori性質(zhì)難以兼顧的現(xiàn)象,并且算法具有較高的效率.除以上三種挖掘方式之外,頻繁模式的挖掘方式還有很多,例如近年來Min等人提出的用于挖掘頻繁三支模式(frequent tri-patterns)的tri-partition alphabets方法[11,12],以及采用多核處理器的并行動態(tài)挖掘法[13]等.但是,算法NOSEP設(shè)置了最小支持度閾值,旨在挖掘頻繁模式,過大的頻繁模式閾值可能會導(dǎo)致無法找到頻繁模式;而過小的閾值,可能會導(dǎo)致挖掘出的模式數(shù)量過多,不僅會給計算機帶來許多不必要的時間和空間資源消耗,而且使用所有這些模式很難對實際生活產(chǎn)生指導(dǎo)意義.因此,如何對生成的頻繁模式進行進一步篩選,從中挖掘出更有價值和意義的模式已成為研究領(lǐng)域的一個重要方向.

Top-k模式挖掘是指采用一定的模式挖掘算法得到所有模式中的前k個最頻繁模式,其中k是用戶自定義的需要挖掘的最頻繁模式數(shù)量.文獻[14]采用Top-k頻繁模式挖掘的必要性與優(yōu)點在于:首先,在大多數(shù)情況下,用戶并不十分關(guān)心某種模式是否“頻繁”,而是只對若干“最頻繁”的模式更感興趣;其次,只挖掘最頻繁的前k個模式,既保證了它們是用戶所需要的,又減少了無效信息的數(shù)量.

目前,Top-k模式挖掘已經(jīng)被進行了大量的研究.Zhu等人[15]提出了Spider-Mine挖掘算法用于從單一的大規(guī)模網(wǎng)絡(luò)中挖掘出前k種最頻繁模式;楊等人[16]為解決由于支持度閾值設(shè)置不當?shù)亩斐赡Ｊ絹G失的問題提出了帶間隔約束的Top-k對比模式挖掘算法kDSP-Miner.Wu等人[17]研究了帶周期間隙約束的Top-k挖掘算法MAPBOK,該算法旨在得到各模式長度下支持率大于閾值ρ的前k種最頻繁模式,但該算法是在無約束條件下完成的并且需要設(shè)置最小支持度閾值;最新研究表明,在無重疊條件下進行模式挖掘,既避免了無約束條件下的丟失解問題,同時又避免了一次性條件下的NP-Hard問題[10].在支持度計算準確的情況下,模式挖掘才更有意義.在無重疊條件下的Top-k模式挖掘中,Chai等人[18]為了更好地適應(yīng)用戶需求,在全體Top-k模式挖掘的基礎(chǔ)上,提出了各長度模式下的Top-k模式挖掘算法NOSEPMOK,但是該文提出的NOSEPMOK算法本身是一種啟發(fā)式算法,不具備完備性.有鑒于此,本文研究完備性的無重疊條件的Top-k序列模式挖掘,并提出了有效的TOPMINING算法,該算法應(yīng)用了模式增長策略,并結(jié)合我們提出的Gfp-tree這一數(shù)據(jù)結(jié)構(gòu),可在挖掘過程中動態(tài)提升支持度邊界值,從而縮減了無用候選模式的生成數(shù)量,進而提高了算法的效率.

本文結(jié)構(gòu)如下:第1節(jié)敘述課題的背景及研究意義;第2節(jié)敘述方法所需要的關(guān)鍵概念及定義;第3節(jié)敘述算法內(nèi)容并給出完備性證明與時間復(fù)雜度分析;第4～5節(jié)是實驗與總結(jié)展望.

2 概念及定義

本算法所涉及的主要概念有:事務(wù)數(shù)據(jù)庫(序列)、模式、無重疊出現(xiàn)、無重疊支持度、Top-k模式等.

定義1.事務(wù)數(shù)據(jù)庫(序列)、模式:多種事件的集合稱為事件集;將事件集中的事件有序排列即構(gòu)成事務(wù)數(shù)據(jù)庫,又稱序列.用大寫字母S表示,記作S=s1s2…sn,其中n表示S中事件的數(shù)量.

從事務(wù)數(shù)據(jù)庫中依序提取一系列事件,將它們首尾相接構(gòu)成的序列稱為模式,用大寫字母P表示.記作P=p1p2…pm,(m≤n)其中m表示模式的長度.

定義2.出現(xiàn):設(shè)有長度為m的模式P和長度為n的序列S.若存在m個整數(shù),l1,l2,…,lm,如果滿足1≤l1是P在S上的一個出現(xiàn).

定義3.符合間隔約束的出現(xiàn):給定某一間隙約束gap=[mingap,maxgap](0

例1.給定事務(wù)數(shù)據(jù)庫S=s1s2…s8=aaggagga,模式P=a[0,2]g[0,2]a.其中,出現(xiàn)<1,3,5>就是一個滿足間隙約束的出現(xiàn).因為3-1-1=1和5-3-1=1均位于0和2之間;同時,出現(xiàn)<2,6,8>就不是滿足間隙約束的出現(xiàn),因為6-2-1=3>2.

定義4.滿足無重疊條件的出現(xiàn):假設(shè)L=和L′=是模式P在事務(wù)數(shù)據(jù)庫S中的兩個出現(xiàn),且對于任意1≤j≤m,都有l(wèi)j≠lj′,那么就稱L和L′是P在S中的兩個滿足無重疊條件的出現(xiàn).

定義5.無重疊支持度:給定事務(wù)數(shù)據(jù)庫S與相應(yīng)的模式P,將P在S中所有滿足無重疊條件的出現(xiàn)組成一個集合set,則稱該集合中元素的個數(shù)為P在S下的無重疊支持度.記作sup(p).

例2.設(shè)事務(wù)數(shù)據(jù)庫S=s1s2…s6=aaatcc,模式P=a[0,2]a[0,2]t,此時P在S上所有滿足無重疊條件的出現(xiàn)所組成的集合為{<1,2,4>,<2,3,6>}.從而sup(p)=2.

定義6.Top-k模式:在事務(wù)數(shù)據(jù)庫S中,所有序列模式中支持度最高的k個模式,這種挖掘方式所挖掘出的模式稱為S上的Top-k模式.

3 算法介紹

為了高效挖掘Top-k模式,依據(jù)Apriori性質(zhì),我們需要解決以下問題:如何有效計算模式在序列中的支持度;如何高效生成超模式;如何得到最終的Top-k模式并確保完備性.基于以上要求,本文使用的算法為:Top-k模式挖掘算法TOPMINING.

3.1 網(wǎng)樹與模式支持度計算

挖掘Top-k模式的其中一項工作就是計算各候選模式的支持度.為了有效計算模式支持度,先介紹下網(wǎng)樹的定義及有關(guān)概念.

定義7.網(wǎng)樹:網(wǎng)樹在本質(zhì)上是一種有向無環(huán)圖.與傳統(tǒng)的樹類似,也有根、葉子、路徑等概念.兩者的主要區(qū)別在于:

1)網(wǎng)樹可以有超過一個的根節(jié)點;

2)除根節(jié)點以外,其他節(jié)點可能有不止一個雙親;

3)從根節(jié)點到葉子結(jié)點可能存在不止一條路徑;

本質(zhì)上,樹可以被看作一種特殊的網(wǎng)樹.

定義8.絕對葉子結(jié)點:若網(wǎng)樹高度為l,則處在第l層的葉子結(jié)點被稱作該網(wǎng)樹的絕對葉子結(jié)點.

定義9.完全路徑:從樹根節(jié)點開始向下搜索,直到到達某一絕對葉子結(jié)點為止,之間經(jīng)過的路徑稱為完全路徑.

依據(jù)定義5,計算模式P在序列S中支持度的關(guān)鍵在于生成S中關(guān)于P的無重疊出現(xiàn)的集合.這項工作看似很復(fù)雜,但在引入網(wǎng)樹后,就可將“尋找P在S中的無重疊出現(xiàn)”轉(zhuǎn)化為:建立一棵關(guān)于P在S中對應(yīng)的網(wǎng)樹,而后尋找完全路徑并計算其數(shù)目.最終得到的完全路徑集合就是S中關(guān)于P的無重疊出現(xiàn)的集合;相應(yīng)地,完全路徑的數(shù)目就是模式P在序列S中的支持度.

例3.設(shè)模式P=a[0,2]g[0,2]a,序列S=s1s2…s15=aagagcctgaagaaa,建立關(guān)于P在S中對應(yīng)的網(wǎng)樹T并初步剪枝后如圖1所示.

因為圖1中網(wǎng)樹不滿足無重疊條件,算法無法結(jié)束.繼續(xù)執(zhí)行后得到如圖2所示的最終網(wǎng)樹.

圖1 實例對應(yīng)的一棵網(wǎng)樹Fig.1 Nettreefortheinstance圖2 剪枝后網(wǎng)樹Fig.2 Nettreeafterpruninguselessnodes

從圖2中得到P在S中的兩個無重疊出現(xiàn)為<1,3,4>和<10,12,13>,算法結(jié)束.

3.2 模式增長策略與候選模式增長樹Gfp-tree

為了解決高效生成超模式的問題,先提出最大前綴子串與最大后綴子串的概念.

定義10.模式P的最大前綴子串、最大后綴子串:P中除去尾字符外的其他字符構(gòu)成的新模式稱為P的最大前綴子串,記作P′;同理,P中除去首字符外的其他字符構(gòu)成的新模式稱為P的最大后綴子串,記作P″.

特別地,當模式長度為1時,其最大前綴與最大后綴子串均為空.

例如:模式“atc”的最大前綴子串為“at”,最大后綴子串為“tc”;而模式“a”的最大前綴子串和最大后綴子串均為空.

對于生成元素的超模式問題,我們使用“模式增長”的策略去生成新的超模式.過程是:對每一個topbasic中的長度最大的模式,將其長度記為n.記錄其最大后綴子串,在topbasic中尋找這樣的模式:其最大前綴子串與該選定模式的最大后綴子串相同.然后他們就可以生成長度為n+1的新模式.例如:模式P1=p1p2…pn,P2=p2…pnpn+1,生成的新模式P=p1p2…pnpn+1.這樣做的好處在于:如果采用枚舉法,若該序列共含有m種字符,那每個長度為n的模式都會生成m個新模式;而使用模式增長的方法,每個長度為n的模式只與那些最大前綴子串與自己的最大后綴子串相同的模式生成新模式,顯然數(shù)目小于m.再配合剪枝策略,使用該方法將大大減少候選超模式數(shù)量.

下一個問題是,如何在候選模式中,快速尋找到那些最大前綴子串與該選定模式的最大后綴子串相同的模式？受二叉線索樹的啟發(fā),我們使用“模式增長樹”(Gfp-tree,Gain-frequence-pattern-tree)解決這一問題.

下面給出Gfp-tree(Gain-frequence-pattern-tree)的定義.

定義11.Gfp-tree:Gfp-tree本質(zhì)上是一棵特殊的二叉線索樹,與一般的二叉線索樹相比,Gfp-tree還具有以下特點:

1)根節(jié)點數(shù)據(jù)域為空且唯一;

2)Gfp-tree中的每個節(jié)點的孩子節(jié)點(如有)其一為第一個超模式,另一為與其同最大前綴子串的下一個節(jié)點;

3)除根節(jié)點外,其余節(jié)點的線索指向該節(jié)點的最大后綴子串.

使用Gfp-tree,對每一個模式而言,尋找最大前綴子串與自己的最大后綴子串相同的模式只需兩步:先通過自身的線索尋找到自己的最大后綴子串,而后其所有的子節(jié)點就是所要找的模式.這樣做的優(yōu)勢在于:當Gfp-tree構(gòu)建完成后,就單個模式而言,模式增長工作可以在線性時間內(nèi)完成;避免了頻繁掃描topbasic集合,降低了時間消耗.

例4.給定模式集合topbasic為{a,c,aa,ac,ag},建立的Gfp-tree如圖3所示,圖中節(jié)點間的實線代表父子關(guān)系,虛線代表線索.

圖3 Gfp-tree示例Fig.3 An example of Gfp-tree

3.3 Top-k模式挖掘算法TOPMINNING

定義12.集合set的支持度閾值:在模式集合set中,稱所含模式中支持度最小者的支持度數(shù)值為set的支持度閾值.

基于這一定義,我們提出了最終的Top-k模式挖掘算法TOPMINNING,該算法只需用戶輸入想要的Top-k模式數(shù)量k和間隔約束[m,n],而無需人工設(shè)置最小支持度閾值,這一工作將由算法執(zhí)行過程中生成的支持度閾值代替,該閾值同時在算法執(zhí)行期間動態(tài)調(diào)整,無需用戶干預(yù).避免了主觀因素對實驗結(jié)果的影響,同時確保了結(jié)果的完備性.

該算法具體過程是:首先完成Top-k序列模式基礎(chǔ)topbasic的構(gòu)建;然后通過使用模式增長策略生成新的候選模式,比較他們的支持度與原候選模式集合的支持度閾值的大小關(guān)系.每次將支持度大于該閾值的模式輸出到最終的Top-k模式集合中,同時計算新的支持度閾值.直到最終的Top-k模式集合的容量等于k為止.此時算法結(jié)束,最終得到的集合中的所有模式就是要求的事務(wù)數(shù)據(jù)庫上的Top-k模式.

算法1.TOPMINING算法

輸入:事務(wù)數(shù)據(jù)庫S,間隔約束[m,n],最終模式數(shù)量k;

輸出:Top-k模式集合topkset;

1. 掃描事務(wù)數(shù)據(jù)庫,生成長度為1的模式集合topbasic,并計算模式數(shù)量countset;

2. n←1;//記錄當前模式長度.

3. WHILEcounset

1) 枚舉生成n+1長度模式set,計算生成的模式個數(shù)counter;

2)topbasic←topbasic∪set;// 更新當前模式集合.

3)counset←counset+counter;// 更新當前模式數(shù)量.

4)n←n+1;

END WHILE

4.maxlen←max{topbasic中模式長度};

5. 使用模式增長策略和Gfp-tree,生成maxlen+1層的新模式.

6.flag←TRUE;//flag是布爾變量,用于指示topkset中的模式個數(shù)是(TRUE)否(FALSE)增加.

7. WHILEflag=TRUE DO

1)flag←FALSE;

2) IFnewset!=NULL THEN

① FORi1 tonewset.sizeby 1 DO

1)topkset←topkset∪{topbasic中位于首個長度模式為maxlen的模式前的所有模式};

2) 使用網(wǎng)樹結(jié)構(gòu),計算newset(i)的支持度;

3) IFnewset(i)的支持度>topbasic(k)的支持度 THEN

a.topbasic←topbasic∪newset(i);

b. 對topbasic按支持度由大到小重新排序,將支持度最大者并入topkset,并將之從topbasic中刪除;同時刪除topbasic中支持度最小者;

c.flag←TRUE;

END IF

② END FOR

3) END IF

4)maxlen←max{topbasic中模式長度};

5) 建立關(guān)于topbasic的Gfp-tree,生成maxlen+1層的新模式.

8. END WHILE

9.topkset←topkset∪topbasic;// 將所有剩余模式并入topkset,保證其中的模式個數(shù)為k.

10. RETURNtopkset;

3.4 完備性證明與時間復(fù)雜度分析

定理1.TOPMINING算法是完備的.

證明:下面用反證法證明TOPMINING算法的完備性.

首先TOPMINING算法的第1～3步生成topbasic采用了枚舉的方法,因而在模式長度不大于maxlen的情況下不會丟解.因而只需要檢驗新生成的模式中是否丟解.

假設(shè)模式長度大于maxlen的模式pat?newset,且pat∈topkset.則根據(jù)Apriori性質(zhì)的推論,模式pat的所有長度為maxlen的子模式一定也在topkset中,根據(jù)PATBEG算法,它們也必然在topbasic中,再根據(jù)Gfp-tree的定義,這些子模式將成為最初Gfp-tree的葉子結(jié)點,而在這些子模式(葉子結(jié)點)中,必然存在最大前綴子串與最大后綴子串相同的模式,從而可以向下生成.最終,pat也將成為Gfp-tree的葉子結(jié)點,從而令pat∈newset成立.原假設(shè)不成立.從而TOPMINING算法是完備的.證畢.

定理2.假定序列S的字符集大小為m,最終的Top-k集合中模式最大長度為M,數(shù)據(jù)庫中最大序列長度為N,間隔約束區(qū)間長度為w,則TOPMINING算法的最壞時間復(fù)雜度不超過O(M×M×N×w×L).

證明:由TOPMINING算法過程,構(gòu)建topbasic集合的復(fù)雜度為O(mlogmk)=O(k),而建立一棵網(wǎng)樹的時間復(fù)雜度為O(M×N×w),使用Apriori性質(zhì)剪枝,從第M-1層開始,第x層去除無效節(jié)點的數(shù)目不超過x×w個,因此去除無效節(jié)點總數(shù)不超過O(M×M×w)個.因此建立Gfp-tree的時間復(fù)雜度不超過O(M×N×w+M×M×N×w)=O(M×M×N×w).所以,最終的時間復(fù)雜度為O((M×M×N×w+L)×L)=O(M×M×N×w×L).

4 實 驗

本章所有實驗均在間隙約束為[0,3]時進行.

4.1 TOPMINING自身實驗情況

為了驗證TOPMINING算法在無重疊條件下進行Top-k挖掘的完備性與高效性,我們在一臺處理器為Intel Core i7 6700HQ@2.60GHz、8G內(nèi)存,編譯器為GCC 5.1.0的電腦上,使用DNA與蛋白質(zhì)序列展開實驗.DNA序列來自Homo Sapiens AL158070片段,蛋白質(zhì)序列來自ASTRAL95_1_161(SDB1～SDB3)和ASTRAL95_1_171(SDB4～SDB6).其中,DNA序列DNA1～DNA6的長度分別為6,000、8,000、10,000、12,000、14,000和16,000.而SDB1～SDB6的情況如表1所示.

表1 蛋白質(zhì)序列說明Table 1 Protein datasets

使用本文介紹的TOPMINING算法,挖掘上述DNA數(shù)據(jù)庫中的Top-30、Top-60、Top-90序列模式時,所耗時間如圖4所示.

圖4 在DNA序列上挖掘所耗時間Fig.4 Running time for DNA datasets

而后,為了檢驗該算法的可擴展性,對表1中的蛋白質(zhì)序列分別進行k=30、k=60、k=90時的Top-k模式挖掘.實驗結(jié)果如圖5所示.

圖5 在蛋白質(zhì)序列上挖掘所耗時間Fig.5 Running time for Protein datasets

盡管考慮到蛋白質(zhì)擁有多條序列和較大的字符集,但是結(jié)合圖4和圖5數(shù)據(jù)可以發(fā)現(xiàn):和單一序列、小字符集的DNA序列相比,在k值相同時,TOPMINING算法的處理時間很相近.由此說明:在序列個數(shù)和字符集大小增加時,TOPMINING算法執(zhí)行所消耗時間依然能保持穩(wěn)定.這也正是該算法的優(yōu)勢所在.

4.2 與其它算法的比較

對比實驗依然采用與上節(jié)相同的實驗環(huán)境.與TOPMINING算法作對比的算法為:基于NOSEP算法修改后的NOSEP-K算法:主要思想是首先計算支持度大于某一閾值下的所有頻繁模式,按支持度排序后輸出所求;以及基于枚舉思想的ENUMK算法.對比實驗結(jié)果如圖6和圖7所示.

圖6 在DNA6上的運行時間Fig.6 Running time for DNA6

綜合DNA與蛋白質(zhì)上的實驗數(shù)據(jù),我們發(fā)現(xiàn)在字符集較大的蛋白質(zhì)序列上,TOPMINING算法依然具有一定優(yōu)勢,其原因就在于該算法使用了多種策略減少了無用候選模式的生成,從而大大提高了算法效率.由上述數(shù)據(jù)可知,即使在大規(guī)模數(shù)據(jù)集的情況下,TOPMINING算法效率依然不低于其他兩種算法.

圖7 在SDB4上的運行時間Fig.7 Running time for SDB4

5 總結(jié)與展望

本文提出了一種解決無重疊條件下Top-k序列挖掘的有效算法TOPMINING,該算法利用了一種新的生成候選模式的策略——模式增長策略,在此基礎(chǔ)上引入了一種基于二叉線索樹的數(shù)據(jù)結(jié)構(gòu)——Gfp-tree,同時與動態(tài)調(diào)整支持度閾值的策略相結(jié)合,大大縮短了算法的執(zhí)行時間,實驗結(jié)果驗證了本文算法的有效性.