數據流中閉頻繁項集的并行挖掘算法

馮忠慧 尹紹宏

摘 要：閉頻繁項集包含了關于頻繁項集的完整信息，可顯著減少頻繁項集挖掘所產生的模式數量，在一定程度上降低了內存開銷、提高了時間效率。數據流的特性決定了它需要更高效的挖掘算法，為此使用分治策略，提出一種并行化閉頻繁項集挖掘算法PCFI。該算法采用垂直數據格式存儲項集的事務，通過對事務集的集合運算，可快速得到項集的支持度計數，合并具有相同事務集的頻繁項，得到初始生成子，降低了搜索空間的規模。采用分治策略對初始生成子進行并行處理，得到約簡前序集和約簡后序集，在挖掘過程中不斷地對每一生成子的搜索空間進行減枝，得到更小的約簡后序集，從而減少對冗余數據的處理。實驗分析表明，該算法的性能優于先前設計的算法。

關鍵詞：數據流；滑動窗口；垂直數據格式；并行計算；閉頻繁項集

中圖分類號：TP311.5 文獻標識碼：A

1 引言（Introduction）

數據流[1]是一串快速到達、無界的數據序列，廣泛存在于日常生活各領域。數據流的特性決定了對其進行挖掘將面臨著更多的挑戰。首先，由于存儲器的有限性，無法通過一次掃描存儲所有傳入的數據。其次，對于數據的處理效率也有更高的要求，即在新事物到來之前，需完成對當前時間段內數據的處理。因此，傳統數據挖掘算法無法直接應用于數據流挖掘，需進行適當的改進和擴展。

盡管對于如何高效的挖掘頻繁項集已取得不少研究成果[2-5]，但當最小支持度閾值設置過低或數據集存在長模式時，仍將會產生大量頻繁項集，影響著數據流挖掘的時效性。針對此問題，1999年，Pasquier等人首次提出閉頻繁項集概念[6]來減少存儲空間和處理時間。閉頻繁項集，規模小，包含頻繁項集的完整信息，作為頻繁項集的替代，可從大量的頻繁項集中進一步提取有用知識，提高挖掘效率。

Chi等人首次提出基于滑動窗口的閉頻繁項集挖掘算法，Moment算法[7]引入閉合計數樹CET結構，用來檢測閉頻繁項集及與其他項集的邊界，并通過CET中的相應節點類型轉換來處理數據流的概念變化。該算法面臨兩個問題：其一，相對于閉頻繁項集的數量而言，CET節點數目非常高。其二，以減少內存占用并加快對事物的搜索，采用FP樹存儲滑動窗口事務，并在此結構中搜索新的頻繁項集。因此需要維護大量節點，影響算法運行效率。

Lucchese等人提出的DCI-Closed算法[8]，通過生成子的前序集和后序集，來判定該生成子是否保序的方法，進行大量剪枝操作，減少了無效的檢測，實現了對頻繁項集格跳躍式的搜索閉頻繁項集。優于CLOSET+算法[9]。宋威等人在此基礎上，提出改進的DCI-CLOSED-INDEX算法[10]，采用二進制矩陣存儲數據集，索引數組組織數據，并提出約簡前序集和約簡后序集概念，進一步的縮小了搜索空間。但通過遞歸的調用方式挖掘閉頻繁項集使得效率低下。

數據流中閉頻繁模式挖掘的研究問題主要集中在兩點：（1）引入高效的數據結構存儲數據集。提高空間利用率同時提高數據存儲效率及數據處理效率。（2）算法本身性能的提升。本章通過對DCI-CLOSED-INDEX算法的改進，設計一種并行化的數據流閉頻繁項集挖掘算法。引入垂直數據格式組織數據，通過集合運算對項集進行集合操作計數判斷。對初始生成子采用分治策略，利用ForkJoin框架對其進行并行化處理。

2 相關知識（Related knowledge）

2.1 基本概念和性質

定義1：數據流DS={T1，T2，T3，…，Tn}，由以一定速度連續到達的事務Ti組成。I={i1，i2，i3，…，in}代表數據流中數據項的集合，事務Ti由數據流中部分或全體數據項構成，Ti={i1，i2，i3，…，ik}（1≤k≤n），對于任意Ti，都有TiI。

定義2：滑動窗口[11]SW={S0，S1，S2，…，Sw-1}，構成數據流的一個瞬時抽樣，窗口寬度w（w>0），即窗口內包含事務集的數量，由用戶預定義。隨時間推進，新事務的到來，滑動窗口采取可重寫循環方式不斷更新窗口內數據。

定義3：閉項集。如果項集X的直接超集都不具有和它相同的支持度計數，則稱項集X為閉項集。

定義4：閉頻繁項集。給定最小支持度閥值min_sup，若閉項集X的支持度sup（X）≥min_sup，則X是一個閉頻繁項集，其中，|X|表示窗口中事務集包含項集X的數量。

性質1：對于窗口中的任意頻繁項集X，若，則Tnew的到來對于當前窗口中已存在的頻繁項集無影響，其中Tnew代表新事務。

性質2：如果項集，則。

2.2 數據結構

2.2.1 事務矩陣

用一個m×n的矩陣存儲窗口中的事務，其中m代表事務量，n代表數據流中項的量。設定滑動窗口大小為w，則事務矩陣大小固定為w×n。窗口未滿時，按照事務到達次序，依次對矩陣賦值，若事務Ti包含項目ij，則將TMij置為1，否則置為0；窗口滑動后，采用新事務覆蓋最舊事務的方式[12]，對事務矩陣進行更新。

2.2.2 垂直數據格式

對頻繁的項集采用事務集表示，即{items：transactions}，其中items代表頻繁項集，transactions代表包括items的事務集合。通過對事務集進行交集運算，便于進行支持度計數。同時采用該方式以緊湊方式進行存儲，也可避免以bit值存儲大量0所導致的空間浪費，對于數據的存儲和處理在時空效率上均有所提高。

2.3 ForkJoin框架

ForkJoin[12]框架是由Java7提供的基于多核計算的并行處理框架，充分利用多核CPU的優勢，提高程序處理能力。主要思想是通過設置閾值和工作線程數量，將總任務分割成多個子任務并行處理，其中工作線程數量根據CPU和任務需要進行設置，閾值取決于要進行劃分的任務規模和工作線程數量。最后，通過對子任務的結果進行合并，可得到全局結果。其原理如圖1所示。

3 PCFI算法（PCFI algorithm）

該算法主要包括三部分：首先，使用事務矩陣存儲滑動窗口數據，計算頻繁1-項集，并按支持度計數降序排列以垂直數據格式結構進行存儲。之后，對頻繁1-項集進行處理，獲得初始生成子。最后，將初始生成子分組以并行方式處理，計算約簡前序集和約簡后序集，得到局部閉頻繁項集。合并子任務結果，得到全局閉頻繁項集。

以表1所示事務數據流為例，介紹PCFI算法流程，設min_sup=0.4，w=5。

3.1 處理滑動窗口數據

掃描事務矩陣count一行，如果該值不小于最小支持度計數，則該項為頻繁1-項集，可得到按支持度計數降序排列的頻繁1-項集{c，a，b，d，e}。并以垂直數據格式的方式來存儲頻繁1-項集，如表3所示。其中TID-集表示包括該項集事務TID的集合。以項集c為例，被事務TID={1，2，3，4}所包含。

3.2 初始生成子

初始生成子需滿足兩個條件：（1）沒有直接超集的項，即閉頻繁項集。（2）如果項集的事務集相同，則應將其合并。滿足其一，即可作為初始生成子。對頻繁1-項集矩陣進行處理，計算初始生成子。由于，，均不滿足條件一，因此排除項a和b。經處理后可得到的初始生成子如表4所示，同時可得到閉頻繁項集{c，d，e}。此步有效的減少了后期需要處理的數據量。

3.3 并行挖掘閉頻繁項集

全局閉頻繁項集的挖掘部分以并行化方式執行。由于對每個初始生成子進行處理時相互之間不存在關聯關系，所以根據分治策略，可將初始生成子分割成與CPU核數相匹配的子任務，對其并行處理。

3.3.1 前序集和后序集

以支持度計數降序排列的頻繁1-項集矩陣為基準，位于某項之前的項歸為該項的前序集，其后序項作為其后序集。以項b為例，其前序集為{c，a}，后序集為{d，e}。其中第一個項的前序集為空集，最后一個項的后序集為空集。

3.3.2 約簡前序集和約簡后序集

為縮減候選項集的規模，應對其用于擴展初始生成子的后序集進行約簡，以降低后期處理的復雜度。因此引入約簡前序集和約簡后序集概念。

首先，對初始生成子的前序集進行約簡。約簡規則以保證約簡前序集中項的事務集都不被其他項的事務集所包含。以初始生成子{e}為例，前序集{c，a，b，d}，其中項a的事務集被項c事務集所包含，因此項a應被約簡，同理約簡項b，得到約簡后序集{c，d}。

在得到約簡前序集的基礎上，對后序集進行約簡。如果后序集中項的事務集不被約簡前序集中項的事務集所包含，則可加入約簡后序集，從而縮小了可擴展項的數量。

經以上步驟處理后得到初始生成子的約簡前序集和約簡后序集如表5所示。

3.3.3 全局閉頻繁項集

設置ForkJoin框架的工作線程數量n，將初始生成子分成n組并行計算，充分利用多核CPU資源，提高運算速度。

當初始生成子的約簡后序集為空時，將其直接歸為閉頻繁項集，結束擴展。如初始生成子e，其約簡后序集為空集，則e為閉頻繁項集。

否則，利用約簡后序集以廣度優先方式對初始生成子進行擴展以避免遞歸式的調用。如果當前項集支持度計數大于擴展集支持度計數，則將當前項集加入全局閉頻繁項集；如果擴展集支持度計數不小于最小閾值，則將其加入生成子，繼續對其擴展；由性質2可知，非頻繁項集的超集均為非頻繁項集，對于支持度計數小于最小閾值的項集停止擴展。重復以上步驟，直到不再有新生成子時結束，即可獲得以當前初始生成子為前項的閉頻繁項集。以初始生成子c為例，用項b對其擴展，得到，由于，則c為閉頻繁項集，同時項集{cb}作為生成子，繼續擴展，得到候選項集{cbd}，因為，停止對其擴展。

合并對初始生成子擴展挖掘后得到的閉頻繁項集，即可得到全局閉頻繁項集。如圖2所示。

3.4 PCFI算法描述

算法1：滑動窗口初始化，計算頻繁1-項集。

輸入：數據流DS，最小支持度min_sup，滑動窗口大小w。

輸出：頻繁1-項集

1 掃描DS前w條事務，存儲到事務矩陣。

2 掃描事務矩陣最后一行

for（j=0；j

if（TM[last，j]>=min_sup）

Fi.item.add（item）； /*加入項*/

Fi.item.trans（transaction）； /*加入事務*/

}

3 按支持度計數降序排列頻繁1-項集

4 輸出以垂直數據格式存儲的頻繁1-項集矩陣

算法2：計算初始生成子。

輸入：頻繁1-項集矩陣

輸出：初始生成子

for each頻繁1-項集

if（fi（i）.trans和fi（j）.trans相同）

/*合并兩項，將合并后的項集作為初始生成子*/

if（fi（i）.trans?fi（j）.trans）

/*該項不能作為初始生成子*/

if（fi（i）.trans不被任何項的事務集包含）

/*該項既是初始生成子，也是頻繁1-項集*/

算法3：并行挖掘全局閉頻繁項集。

輸入：頻繁1-項集，初始生成子，線程數量n

輸出：全局閉頻繁項集

1 將初始生成子分割成子任務

THRESHOLD=（end-start）/n；

canCompute=（end-start）<=THRESHOLD；

if（canCompute）{/*核心處理部分2～6*/

}else{/*繼續分割初始生成子*/

middle=（start+end）/2；

ParallelProcessing（start，middle）；

ParallelProcessing（middle+1，end）；

}

2 計算約簡前序集

for初始生成子each前序集

if（pre_set（i）.trans?pre_set（j）.trans）

/*pre_set（i）被約簡掉*/

3 得到約簡后的前序集pre_set

4 計算約簡后序集

for初始生成子each后序集

if（post_set（i）.trans?pre_set（j）.trans）

/*post_set（i）被約簡掉*/

5 得到約簡后的后序集post_set

6 挖掘全局閉頻繁項集

if（post_set==NULL）/*將gen加入到全局閉頻繁項集*/

else

candidate.add（gen）；

for each candidate 用約簡后序集進行擴展

if（new_gen.post_set==null）

continue；

if（new_gen.sup>=min_sup）

/* 將candidate.add（new_gen）；*/

if（gen.sup>new_gen.sup）

/*將gen加入到全局閉頻繁項集*/

4 實驗結果及分析（Experimental results and

analysis）

本文算法采用Java語言實現，以MyElipse為開發平臺，部署Fork-Join框架，采用雙核的并行方式對算法進行性能測試。實驗環境為Windows 7旗艦版操作系統、AMD A4-6210 APU with AMD Radeon R3 Graphics1.80GHz、4GB內存。

采用三組數據集來模擬數據流環境進行測試，分別是稀疏集T10I4D100K、稠密集T40I10D100K和Mushroom。

為測試PCFI算法的有效性，本文將DCI-CLOSED-INDEX算法擴展為數據流中閉頻繁項集挖掘算法，標記為DCI-CLOSED-INDEX-DS。

4.1 不同數據集下運行時間的比較

設定滑動窗口大小為w=1000，最小支持度為min_sup=0.02，測試兩種算法在稀疏集T10I4D100K上的運行時間對比，如圖3所示。

如圖4所示，設定滑動窗口大小為w=1000，最小支持度為min_sup=0.05，測試兩種算法在稠密集T40I10D100K上的運行時間對比。

可以看出，兩種算法在不同數據集下運行時間均隨事務數的增多呈線性增長趨勢，但相比之下DCI-CLOSED-INDEX-DS算法增長速度更快些，也說明了本算法的穩定性；在相同事務數下，無論是稀疏集還是稠密集，PCFI算法的時間效率均高于DCI-CLOSED-INDEX-DS算法。這是由于PCFI算法在挖掘閉頻繁項集時避免了遞歸式的調用，降低了算法的時間復雜度；同時，在并行環境下，采用分治策略，利用多核CPU將初始生成子分成子任務并行處理，極大的提高了程序的執行效率。

4.2 不同支持度下運行時間的比較

如圖5所示，設定滑動窗口大小為w=1000，采用數據集Mushroom測試兩種算法在不同支持度下的運行時間對比。

圖5顯示當支持度設置較低時，PCFI算法運行時間比DCI-CLOSED-INDEX-DS快兩倍多。隨支持度變小，兩種算法的運行時間波動均較小，可以反映出閉頻繁項集的個數增加并不快，因此以閉頻繁項集替代頻繁項集也更適用于數據流中的頻繁模式挖掘，能夠以較快的運行速度挖掘出所需的完整信息。

5 結論（Conclusion）

本文針對頻繁項集在數據流環境下挖掘效率低下的問題，對DCI-CLOSED-INDEX算法的改進和擴展，提出一種數據流中閉頻繁項集的并行挖掘算法PCFI。該算法以垂直數據結構來存儲頻繁項集，通過事務集間的集合操作可以減少對事務矩陣的掃描，同時也能避免存儲大量0元素對存儲空間的浪費。根據頻繁1-項集獲取初始生成子，使用分治策略，與CPU核數及程序需求相匹配，對初始生成子進行分組并行計算，利用約簡前序集得到約簡后序集，對初始生成子進行擴展，直至擴展結束，將局部閉頻繁項集合并得到全局閉頻繁項集。實驗結果表明，基于ForkJoin框架的PCFI算法在時間效率上，相對于已有算法有了明顯的提高。

參考文獻（References）

[1] Morales G D F，Bifet A，Khan L，et al.IoT Big Data Stream Mining[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2016：2119-2120.

[2] Aliberti G，Colantonio A，Pietro R D，et al.EXPEDITE：EXPress closED ITemset Enumeration[J].Expert Systems with Applications，2015，42（8）：3933-3944.

[3] Subbulakshmi B，Dharini B，Deisy C.Recent weighted maximal frequent itemsets mining[C].International Conference on I-Smac.IEEE，2017：391-397.

[4] Huang J N，Hong T P，Chiang M C.An effective method for approximate representation of frequent itemsets[J].Intelligent Data Analysis，2017，21（3）：597-616.

[5] 張偉，石純一.Agent組織的一種遞歸模型[J].軟件學報，2002，13（11）：2149-2154.

[6] Meuer H，Simon H，Strohmaier E，et al.TOP500 supercomputer sites[EB/OL].http：//www.top500.org，2011-10-15.

[7] Johnson T F，Tinoco E T，N.Yu N.Thirty years of development and application of CFD at Boeing commercial airplane seattle[R].USA：AIAA，2003：343.

[8] Zhang H，Li S K.Description logic of tasks： From theory to practice[J].Chinese Journal of Computers，2006，29（3）：488-496.

[9] Wang J，Han J，Pei J.CLOSET+：searching for the best strategies for mining frequent closed itemsets[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2003：236-245.

[10] Graham S，Park C.Assignment of dual port memory banks for a cup and a host channel adapter in an infiniband computing node [P].US 6816889 B1，2004-10-09.

[11] Zhang Hui.Organizational coordinate behaviors modeling of virtual entity group[D].Changsha：National University of Defense Technology，2006.

[12] 梅杓春.新編英漢通信詞典[M].南京：東南大學出版社，1996.

作者簡介：

馮忠慧（1993-），女，碩士生.研究領域：數據挖掘.

尹紹宏（1964-），女，碩士，副教授.研究領域：數據挖掘.