基于模式增長的高效用序列模式挖掘算法

唐輝軍 王樂 樊成立

序列模式挖掘作為數據挖掘領域的一項重要研究內容,在風險管理、生物信息學、基因分析等方面具有重要的應用[1?3].頻繁序列模式挖掘作為其應用的典型代表,突出了序列數據集中的高頻模式,傳統數據集上的頻繁項集閉包屬性表明:任一個頻繁項集的非空子集都是頻繁項集,非頻繁項集的任一個超集都不是頻繁項集,基于上述閉包屬性計算原則形成了序列集頻繁模式挖掘算法[4?5].然而頻繁模式沒有考慮序列集中各項的效用值.例如在零售業,冰箱的銷售要比牙刷賣的次數少的多,但其利潤可能比牙刷高的多,因此在頻繁序列模式的基礎上,提出了高效用序列模式挖掘,即將內外效用值引入到序列項集中,目前,高效用序列模式已經成為數據挖掘領域的一個熱門研究內容[6?8].2010年,Ahmed等[9]給出了高效用序列模式挖掘的完整定義和數學模型.其主要任務為在具有一定效用值的序列數據庫中找出效用值不小于預先給定閾值的所有有序項集.在定義過程中,一個項集X的總效用值為X在該數據集中有包含項集X的事務t上的效用值U(X,t)的總和.而在單一事務t中可能存在多個相同序列集,文獻選擇其中較大效用值作為項集X在該事務中的效用.同時,該文獻還提出兩種挖掘算法UtilityLevel 和UtilitySpan,其中UtilityLevel通過事務中項集按水平次序組合生成候選項集,進而判斷和識別其中高效用序列.UtilitySpan通過項集前綴垂直查找,搜索高效用項集.相比之下,UtilitySpan 的實現效率較好,但當用戶設定的閾值比較低或數據集中的不同項比較多時,兩類算法會產生眾多的候選項集,造成產生高效用序列項集的時空代價較大.2012年,Yin 等[10]在KDD會議上提出的USPAN算法,被認為能較大地提升高效用序列模式挖掘效率.其主要基于項集樹模型設計了數據庫中序列模式,所有序列模式均可從樹中的結點得到,并且基于高效用挖掘中的閉包屬性原則給出了一個SWU(Sequence-weighted utilization)模型進行剪枝操作.即一個項集的SWU值不小于用戶定義的最小效用值,該項集即為一個候選項集;反之,則該項集則不為高效用項集.另外,該文還通過設置事務中的項集的Remain-utility 進行深度剪枝操作,即一個項集的現有效用加上Remainutility如果小于最小效用值,則停止在樹中搜索該項集.USPAN的算法時空效率高于文獻[9]中的算法.但其算法基于枚舉而產生,時空效率代價也相對較大.Wang 等[11]考慮到在較小閾值下,SWU通常比最小效用值要大,提出了一個不基于閉包屬性原則的HUS-Span 算法,該算法主要設計了一種新的數據結構表示方法-效用鏈(Utility-chain),通過添加效用鏈剪枝達到計算效用值的目的.不過,該算法只在最小效用值較低或稀疏數據集時,其性能優于USPAN.首先采用層次方法或者一定的數據結構(樹、鏈)找出候選項集,然后掃描數據集計算每個候選項集的真實效用值來判斷該候選項集是否為高效用序列模式是USPAN、HUS-Span等算法的核心思想,很多算法在此基礎上進行數據結構設計改進[12?14],2017 年,Zihayat等[15]在USPAN的基礎上,提出了HUSP-Miner 算法,該算法主要設計了兩個新的數據結構ItemUtilLists(Item utility lists)和HUSP-Tree(High utility sequential pattern tree),其通過樹形鏈式模式降低挖掘過程中的候選項個數,在與USPAN的實驗比較結果中可以看到,算法的時空效率得到了一定的提升,時間效率能提高到3倍.高效用序列模式挖掘算法的時空效率有了很大的提高,但算法的代價還比較大,特別是挖掘時間效率的提升仍是本領域的一個挑戰,本文在基于高效用模式增長挖掘方法的基礎上,給出一個高效用序列模式新算法HUSP-FP(High utility sequential pattern based on FP-growth).該算法采用模式增長的方法來挖掘高效用序列模式,所有的高效用序列項集均可從樹上得的,而不用再掃描原始數據集.基于模式增長的挖掘算法已經在高效用無序數據集模式挖掘上表現出了獨特的優勢.HUIMiner[16]、FHM[17]、HUPM-FP[18]等算法相繼提出,在時空效率上得到了較大提升,目前在序列數據集上開展高效用模式增長方法的研究成果還及其罕見.本文首先給出高效用序列模式的相關數學定義;然后,給出HUSP-FP中的全局樹建立過程,重點突出從樹中挖掘高效用序列模式的過程,分析算法的時空效率優勢;最后,開展相關實驗,與前述現有較好的HUSP-Miner、UPSAN和HUS-Span 算法進行計算效率對比分析,以驗證新算法的優越性,并開展總結分析提出下一步工作方向.

1 相關定義

設D=t1,t2,···,tn為一個序列數據庫,tj為構成該數據庫的各個事務,I=i1,i2,···,im為構成該數據庫的所有項的集合.在每一個事務tj中,設置(xj1:cj1),(xj2:cj2),···,(xj v:cj v)為該事務的具體項和內部效應表示.x j k(k=1,2,···,v)為I具體的項,cj k(k=1,2,···,v)=q(x j k,tj)為其相應的效用值.p(x j k)為事務中該項相應的外部效用值.表1、表2分別為某一序列數據庫和外部效用表實例.

表1 高效用數據集Table 1 High utility dataset

定義1.項x在事務t中的效用值,記為u(x,t),其定義如下:

例如項A在事務t1中的效用值為12.由于項B在事務t2中有兩個效用值,分別為6,3.這里設定在事務中出現多個相同項集情況下,取較大值為該項的效用值,即項B的效用值為6.

表2 利潤表(外部效用值)Table 2 A Prof it Table (External utility value)

定義2.項集X在事務t中的效用值,記為u(X,t),其定義如下:

例如項集A,B在事務t1的效用值為12+9=21.考慮到項集在某一事務中可能多次出現,例如有序項集B,C在事務t4中效用值分別為3+2=5和3+4=7,這里按照定義1中的設定,取較大值7 為該有序項集在事務t4中的效用值.

定義3.序列項集X在數據集D中的效用值,設為u(X).

例如序列項集A,B在數據集中的效用為21+15+12=48.

定義4.事務t的效用值設為stu(t).其包含了所在事務中的項效用值的和,定義公式如下:

例如事務t3的效用值為9+8=17.

定義5.在數據集D的事務效用值為swu(D).其定義如下:

例如表1數據集中的事務效用值為29+17 +17 +9+34+17 +18=141.

定義6.基于數據集D,一個項集X的事務效用集不小于最小效用值,則該項集為候選項集,否則,則為非候選項集.

例如序列項集A,B在數據集中的事務效用值為29+34+18=81.

定義7.基于數據集D,一個項集的效用值u(X)大于或等于最小效用值,則該項集為高效用項集,否則為非高效用集.

性質1.高效用序列項集的事務效用值必須滿足閉包屬性:任一候選項集的非空子集是一個候選項集,任一非候選項集的超集是一個非候選項集.證明:假設序列項集X是序列項集Y 的一個子集,也即Y是X的一個超集.因為X是Y的一個子集,因此數據集D中包含Y的事務項集一定也包含X,而包含X的事務項集不一定包含Y,即包含X的事務項集個數不會小于包含Y的事務項集個數,因此swu(X)一定大于等于swu(Y).所以若Y滿足閉包屬性是一個候選項集,則X一定也是一個候選項集;若X不滿足閉包屬性,即不是一個候選項集,則Y一定也不是一個候選項集.

2 HUSP-FP算法

在本節中,我們主要介紹基于模式增長的HUSP-FP算法在高效用序列模式挖掘中的應用.其中,第2.1節給出了全局樹的建立,其可將效用事務集壓縮到一棵樹上,樹上存儲了所有效用信息.第2.2節描述了如何從全局樹上挖掘到所有的高效用序列項集模式.

2.1 全局樹的建立

以表1和表2的數據為例,設置最小閾值為35,構建全局樹步驟如下:

步驟1.掃描一遍數據集,統計各項的效用值(Utility),事務效用值(swu),進而形成數據頭表H計算結果如圖1(a)所示

步驟2.將頭表中事務效用值swu小于35的項刪除,由于F、G的swu均小于35,故刪除F、G,更新后的頭表如圖1(b)所示.

步驟3.再次掃描原始數據集,將不在頭表中出現的項刪除,并按原始項出現順序依次添加到一顆樹中.

表1中的第一個序列集(A,4)(B,3)(D,3)(E,1)添加到樹中的結果如圖1(c)所示.葉子節點保留了全部項的效用值List=[12,9,6,2].圖1(c)表示了第一個事務添加后的結果.圖1(d)為添加表1中第2個事務項集后的結果,由于在該事務中出現了兩個B項,在最后出現的B項中記錄下前一個B項在路徑中出現的位置,這里用S=1來表示,并設置鏈接指針到前一項.在添加的過程中,如果項集對應的最后一個節點在樹上已經存在了,則只需要將各項對應的效用值累加到List的對應項上.第4個事務項集添加到樹上后的結果如圖1(f)所示,依次添加第5、第6和第7 個事務集,在添加第7 個事務集中,A、B項出現了多項,第二個A中記錄第一個A出現的下標位置,第三個A記錄第二個A的下標位置,依次類推,將所有效用值保留在葉子節點中.所有事務項集添加后的結果如圖1(g)所示.頭表中的link 對相同節點按照事務出現順序進行鏈接,以便于計算相同項集的效用值.相關事務內容項指針鏈接如圖1(c)～(e)所示,為了圖例看起來清晰,圖1(f)～(g)上沒有畫出link 對應的事務內容項之間的鏈接線.

2.2 從全局樹上挖掘所有序列模式

上述過程對序列全局樹進行了有效構建,將序列數據集維護到了一顆樹和一張頭表中,算法HUSP-FP采用模式增長方式挖掘全部高效用序列集.具體算法過程如算法1所示.

圖1 序列全局樹構建實例Fig.1 An example of constructing a sequential global tree

算法1.Mining(T,H,X,minUti)

輸入:全局樹T,頭表H,初始值為空的項集X,最小效用值minUti.

輸出:高效用序列模式集HUSPs.

算法1在頭表和子頭表的創建過程中,將項集X的效用值存放在頭表中的字段Utility,因此在算法1的第4行中可以直接判斷項集X是否是高效用模式.

從頭表出發,計算包含以頭表中每一項為尾節點的項集效用值.具體到全局樹的路徑中,則對應以路徑中的葉子節點為出發點,依次處理每一項得到其相應的子表和子樹,處理完每一項即可挖掘到以該項為尾項的序列項集.在計算過程中,先通過判斷事務效用值swu是否滿足閉包屬性進而計算其序列模式是否為高效用序列模式.在圖1(g)的路徑出現過程中,A-B-D-E為第一個路徑,包含C的路徑B-C-B為第二個路徑,由于頭表中只有這5項已經全部出現,則挖掘頭表中項的順序為E-D-B-A-C.

這里以圖1(g)中的全局樹和頭表為例,說明算法1構建子樹和子頭表的過程.由于項E、D的包含項集比較簡單,這里選擇挖掘以項B為尾節點的高效用序列項集作為演示例子.當處理頭表(圖1(g))中項B時,因為頭表中項B的swu值不小于最小閾值35,因此可以為項集X=B創建子樹和子頭表,構建步驟如下:

步驟1.按照從頭表指針鏈中B點出發鏈接形成的路徑,分別按照從下往上的順序從路徑A-B上分析帶有B項的項集為A、B.從路徑B-C-B項獲取項集C、B、B、B.從路徑A-B-A-A-B(這里指針鏈接到第二個B項)上獲取項集A、B、B、B.按照項集效用和事務效用值計算規則,得到B的子頭表如圖2(a)所示.按照前述第2.1節全局樹建立規則,刪除swu 不滿足最小效用值要求的無用項集B、B和C、B得到優化后的子頭表如圖2(b)所示.

步驟2.由于子頭表不為空,繼續以子頭表中的某一項集為基項,構建以該子頭表為基礎的子樹.按照原始序列挖掘順序添加相關節點,添加第一條路徑后得到項集B的子樹如圖2(c)所示,其中Base表示了路徑基項B的效用值.所有路徑添加完畢后的結果如圖2(d)所示.繼續以子頭表中的某一項為基項得到后續子集A、A、B和B、A、B,發現其swu均小于最小效用值,基項B的序列項集處理完畢,計算得到A、B,A、A、B和B、A、B為高效用序列項集.依次類推,圖2(e)則表示了處理D為基項后的子樹和子頭表.

2.3 HUSP-FP理論分析

算法HUSP-FP將所有項的效用值維護在全局樹的葉子節點上,并且其存儲的是所有的真實效用值而不是估計值.這使得其計算中不需要產生候選項集.在子樹的創建過程中(如圖2),依據路徑葉子節點,可以得到子樹節點中每一項的真實效用值.依據事務項集閉包屬性要求,一旦子樹中的項集事務效用值swu小于最小閾值,則拋棄該項集,最終使得創建子樹和子頭表的次數得到了大幅度減少,計算效率得到了有效提升.

以下證明HUSP-FP能夠挖掘到所有的高效用序列模式.首先假設項集Z是任何一個高效用序列模式.因為Z是一個高效用序列模式,則其任何一個非空子集的swu值都不會小于最小閾值.根據算法HUSP-FP,序列項集Z中的所有項都會出現在全局樹對應的頭表中,當Z中第一個項Z1被處理,并為之創建子頭表時,因為項集Z1和Z中其余各項的組合的swu 值都不小于最小閾值,因此這些序列組合的項集都會出現在子頭表中,當處理子頭表中項Z1和Z中的第二項Z2的序列組合時,同樣項集Z1、Z2和Z中其余各項的序列組合會出現在新的子頭表中,依次處理下去,一定能夠得到Z所包含的全部高效用序列模式.

與前述基于候選集的已有算法HUSPMiner、USPAN和HUS-Span 相比,HUSP-FP能夠依據模式增長方法挖掘得到所有高效用序列模式,并且在挖掘過程中無候選項.

全局樹中的事務效用存儲結構也相對簡單,這與其他三類基于候選項剪枝進而得到高效用序列模式的方法有本質不同,這也是HUSP-FP能夠取得較好時空效率的主要原因,相關算法的復雜度比較內容可見表3所示.

圖2 序列子樹構建實例Fig.2 An example of constructing a sequential sub-tree

表3 算法復雜度比較Table 3 Comparisons of algorithm complexity

3 實驗與結果

3.1 實驗算法與平臺

算法HUSP-Miner、USPAN和HUS-Span是目前時空效率較好的高效用序列模式挖掘算法,本文新提出的算法HUSP-FP和這三類算法做了對比分析.算法均采用java 編程語言實現,實驗平臺:Windows 7,10 GB Memory (Java heap size is 1.5 GB),Intel(R)Core(TM)i5-3320 CPU@2.60 GHz.

3.2 實驗數據

本節采用的數據來自SPNF[19]和文獻[20],共4個真實數據集,包括Bible,FIFA,Kosarak 10k,SIGN.其中,Bible是一個具有中等序列長度的稠密數據集,FIFA 是一個具有較多長序列的稠密數據集,Kosarak 10k則是一個包含短序列的稀疏數據集,SIGN是一個具有超長序列類型的稠密數據集,數據集的類型豐富性是足夠的,關于數據集的具體內在特征,可見表4所示.

表4 算法復雜度比較Table 4 Data characteristics

3.3 時空效率

算法運行時間會隨著最小效用值(最小閾值)的增加而降低.第一個實驗測試了不同最小閾值下,算法的運行時間和內存消耗對比.圖3給出了在不同閾值要求下的4種算法在4個數據集的運行時間對比.

圖3 運行時間Fig.3 Running time

項的外部效用值采用文獻[21?22]中的方法,設定為隨機產生的一個數值(大于等于0.0100,小于等于10.0000).從圖3中可以看到,新算法的時間效率得到了較大提升,個別數據集上可以提高達到1個數量級以上.建立全局樹然后基于樹進行高效用序列模式挖掘是HUSP-FP算法時間消耗的兩大部分,不過隨著閾值的增加,相比其他算法來說,HUSP-FP的挖掘時間變化比較平穩.對于短序列數據集Bible和Kosarak 10k 來說,由于HUSPMiner、USPAN和HUS-Span 在實現過程中產生了較多的候選項集,從而導致算法的時間消耗較大.對于長序列稠密數據集FIFA和SIGN,三類算法更是付出了較多的時間代價,例如對于數據集SIGN,當最小閾值達到0.018%時,此時已無高效用序列模式產生,三類算法仍然消耗了大量時間進行候選項判斷,由此可見,新算法HUSP-FP在時間運行效率上取得了良好的領先結果.

3.4 算法擴展性測試

第2個實驗測試在不同數據量下算法的運行時間和內存消耗性能,分別選取稠密數據集Bible和稀疏數據集Kosarak 10k 作為測試對象,數據選擇方式為從Bible數據集中從頭到尾順序添加5 000、10 000、15 000、20 000、25 000、30 000事務數據量,且設置其最小閾值為0.026%.從Kosarak 10k 數據集中選擇100 000、200 000、300 000、400 000、500 000、600 000事務數據量,且設置其最小閾值為0.0176%.其中圖5、圖6分別表示了4類算法在不同數據量下的時空效率.從圖中可以看到,隨著數據測試集數據量的增大,HUSP-FP算法產生的高效用序列模式增多,但是HUSP-FP的時間消耗量卻相對較為穩定,這是由于算法按照閉包屬性,在模式增長過程中及時的拋棄了一些無用序列項,從而使得運行時間保持了平穩.HUSP-Miner、USPAN和HUS-Span基于層次的搜索方法產生了較多的候選項,雖然三類算法大都采用樹形結構,但它們在全局樹建立過程中采用枚舉搜索的方式增加了較大的計算時間.通過對算法的內存消耗對比,發現4類算法的內存消耗都隨著數據量的增加成線性增加模式(該測試結果不包含垃圾節點占用空間,垃圾節點累積到一定程度,系統會自動回收垃圾所占用的空間),但總體上看,HUSP-FP消耗的內存更少.由此可見,新算法在數據量增多的情形下時空效率都優于其他三類算法,特別是計算時間上優勢明顯.

圖4 內存消耗Fig.4 Memory consumption

圖5 不同數據量運行時間Fig.5 Running time under different data size

圖6 不同數據量內存消耗Fig.6 Memory consumption under different data size

圖4給出了在上述4個數據集運算中的內存消耗量對比.本節實驗中的內存消耗值的提取方法如下:在算法運行過程中,設置不同的點,提取每個點上的所用內存量,然后從所有不同點上取出最大的內存消耗量作為當前算法的內存消耗.在不同的最小閾值下,相比其他三類算法,算法HUSP-FP在空間使用效率上也有較大的優勢.當最小閾值減小,數據集中包含的高效用模式會增加,從而使得新算法HUSP-FP創建的全局樹占用空間增加,同時創建的子樹棵數也會增加,所以算法HUSP-FP會隨著最小閾值的降低而消耗更多的內存空間.但與其他三類算法相比較,HUSP-FP還是取得了較大的優勢.

第3個實驗進一步測試了在數據流窗口下的算法運算效率.圖7 給出在不同最小閾值下,4個算法在上述4類典型數據集下的運行時間(這里設置一個時間窗口包含5個序列批次,每一批次包含事務容量不大于20 k).從圖7 的實驗中可以發現,HUSP-FP的運行時間明顯小于其他三類算法,隨著實驗中最小閾值的增大,其他算法的運行時間也得到了一定的下降,但下降后的值與HUSP-FP相比,差距仍然較大.這說明HUSP-FP能夠在時間窗口數據流挖掘上具備較好的運行時間優勢.從圖8的內存消耗比較中也可以看出,HUSP-FP在數據流窗口下內存計算消耗量相對較小.圖7 和圖8表明新算法HUSP-FP在數據流窗口高效用序列模式挖掘中能夠顯示出較好的運行效率優勢.

分別設置Bible、FIFA、K0sarak 10k、SIGN的最小閾值為0.026%、0.10%、0.176%、0.014%,圖9給出了不同批處理數據容量(例如Bible-10k 表示劃分Bible 單一批處理數據集的大小不超過10k)和不同批處理數據數量(Bible-3表示一個時間窗口有3個批處理集)下的運行時間對比,從圖7 中可以看出,HUSP-Miner 相比USPAN和HUS-Span,運行時間更少,故圖9對HUSP-Miner 和HUSPFP開展了對比分析,隨著相關批處理數據容量和數量的增大,在對同一數據集的分析中可以發現,HUSP-FP和HUSP-Miner 都會增長運行時間,但HUSP-FP的增長值相對HUSP-Miner 更小,能夠保持相對的穩定,這更進一步說明了HUSP-FP在時間窗口高效用序列模式挖掘中的優越性.

4 總結

本文提出一種新的高效用序列模式挖掘算法HUSP-FP,該算法基于模式增長方式可直接挖掘高效用序列模式,而不是傳統的先得到候選項集再篩選的過程,因此算法的時空效率都得到了提升.本文采用4個典型真實數據集(包含短序列、長序列、稀疏數據集、稠密數據集)進行了靜態和時間窗口動態實驗驗證,實驗結果也表明給出算法的時間和空間效率相比目前較好的HUSP-Miner、USPAN和HUS-Span都有較大程度的提高,特別是時間效率得到了較大幅度的提高,證明該方法是可行的.同時通過實驗運行,發現HUSP-FP算法即使在最小閾值較大情況下,在維護全局和子樹環節仍然需要消耗大量時間和空間,下一步將針對此問題進行優化.

圖7 數據流運行時間Fig.7 Running time based on data stream

圖8 數據流內存消耗Fig.8 Memory consumption based on data stream

圖9 HUSP-FP和HUSP-Miner 的對比評價Fig.9 Evaluation of HUSP-FP and HUSP-Miner