馮忠慧 尹紹宏

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

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

中圖分類號：TP311.5 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

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

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

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

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

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

2 相關(guān)知識（Related knowledge）

2.1 基本概念和性質(zhì)

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

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

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

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

性質(zhì)1：對于窗口中的任意頻繁項(xiàng)集X，若，則Tnew的到來對于當(dāng)前窗口中已存在的頻繁項(xiàng)集無影響，其中Tnew代表新事務(wù)。

性質(zhì)2：如果項(xiàng)集，則。

2.2 數(shù)據(jù)結(jié)構(gòu)

2.2.1 事務(wù)矩陣

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

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

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

2.3 ForkJoin框架

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

3 PCFI算法（PCFI algorithm）

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

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

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

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

3.2 初始生成子

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

3.3 并行挖掘閉頻繁項(xiàng)集

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

3.3.1 前序集和后序集

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

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

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

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

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

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

3.3.3 全局閉頻繁項(xiàng)集

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

當(dāng)初始生成子的約簡后序集為空時，將其直接歸為閉頻繁項(xiàng)集，結(jié)束擴(kuò)展。如初始生成子e，其約簡后序集為空集，則e為閉頻繁項(xiàng)集。

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

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

3.4 PCFI算法描述

算法1：滑動窗口初始化，計算頻繁1-項(xiàng)集。

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

輸出：頻繁1-項(xiàng)集

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

2 掃描事務(wù)矩陣最后一行

for（j=0；j

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

Fi.item.add（item）； /*加入項(xiàng)*/

Fi.item.trans（transaction）； /*加入事務(wù)*/

}

3 按支持度計數(shù)降序排列頻繁1-項(xiàng)集

4 輸出以垂直數(shù)據(jù)格式存儲的頻繁1-項(xiàng)集矩陣

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

輸入：頻繁1-項(xiàng)集矩陣

輸出：初始生成子

for each頻繁1-項(xiàng)集

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

/*合并兩項(xiàng)，將合并后的項(xiàng)集作為初始生成子*/

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

/*該項(xiàng)不能作為初始生成子*/

if（fi（i）.trans不被任何項(xiàng)的事務(wù)集包含）

/*該項(xiàng)既是初始生成子，也是頻繁1-項(xiàng)集*/

算法3：并行挖掘全局閉頻繁項(xiàng)集。

輸入：頻繁1-項(xiàng)集，初始生成子，線程數(shù)量n

輸出：全局閉頻繁項(xiàng)集

1 將初始生成子分割成子任務(wù)

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 挖掘全局閉頻繁項(xiàng)集

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

else

candidate.add（gen）；

for each candidate 用約簡后序集進(jìn)行擴(kuò)展

if（new_gen.post_set==null）

continue；

if（new_gen.sup>=min_sup）

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

if（gen.sup>new_gen.sup）

/*將gen加入到全局閉頻繁項(xiàng)集*/

4 實(shí)驗(yàn)結(jié)果及分析（Experimental results and

analysis）

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

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

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

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

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

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

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

4.2 不同支持度下運(yùn)行時間的比較

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

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

5 結(jié)論（Conclusion）

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

參考文獻(xiàn)（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].軟件學(xué)報，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].南京：東南大學(xué)出版社，1996.

作者簡介：

馮忠慧（1993-），女，碩士生.研究領(lǐng)域：數(shù)據(jù)挖掘.

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