數(shù)據(jù)流中閉頻繁項集的并行挖掘算法

馮忠慧 尹紹宏

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

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

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

1 引言（Introduction）

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

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

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

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

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

2 相關知識（Related knowledge）

2.1 基本概念和性質

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

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

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

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

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

性質2：如果項集，則。

2.2 數(shù)據(jù)結構

2.2.1 事務矩陣

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

2.2.2 垂直數(shù)據(jù)格式

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

2.3 ForkJoin框架

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

3 PCFI算法（PCFI algorithm）

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

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

3.1 處理滑動窗口數(shù)據(jù)

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

3.2 初始生成子

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

3.3 并行挖掘閉頻繁項集

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

3.3.1 前序集和后序集

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

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

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

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

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

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

3.3.3 全局閉頻繁項集

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

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

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

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

3.4 PCFI算法描述

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

輸入：數(shù)據(jù)流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 按支持度計數(shù)降序排列頻繁1-項集

4 輸出以垂直數(shù)據(jù)格式存儲的頻繁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-項集，初始生成子，線程數(shù)量n

輸出：全局閉頻繁項集

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

THRESHOLD=（end-start）/n；

canCompute=（end-start）<=THRESHOLD；

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

}else{/*繼續(xù)分割初始生成子*/

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語言實現(xiàn)，以MyElipse為開發(fā)平臺，部署Fork-Join框架，采用雙核的并行方式對算法進行性能測試。實驗環(huán)境為Windows 7旗艦版操作系統(tǒng)、AMD A4-6210 APU with AMD Radeon R3 Graphics1.80GHz、4GB內存。

采用三組數(shù)據(jù)集來模擬數(shù)據(jù)流環(huán)境進行測試，分別是稀疏集T10I4D100K、稠密集T40I10D100K和Mushroom。

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

4.1 不同數(shù)據(jù)集下運行時間的比較

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

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

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

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

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

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

5 結論（Conclusion）

本文針對頻繁項集在數(shù)據(jù)流環(huán)境下挖掘效率低下的問題，對DCI-CLOSED-INDEX算法的改進和擴展，提出一種數(shù)據(jù)流中閉頻繁項集的并行挖掘算法PCFI。該算法以垂直數(shù)據(jù)結構來存儲頻繁項集，通過事務集間的集合操作可以減少對事務矩陣的掃描，同時也能避免存儲大量0元素對存儲空間的浪費。根據(jù)頻繁1-項集獲取初始生成子，使用分治策略，與CPU核數(shù)及程序需求相匹配，對初始生成子進行分組并行計算，利用約簡前序集得到約簡后序集，對初始生成子進行擴展，直至擴展結束，將局部閉頻繁項集合并得到全局閉頻繁項集。實驗結果表明，基于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-），女，碩士生.研究領域：數(shù)據(jù)挖掘.

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