王鑫 劉方愛

摘要：針對已有的多數(shù)據(jù)流協(xié)同頻繁項集挖掘算法存在內(nèi)存占用率高以及發(fā)現(xiàn)頻繁項集效率低的問題，提出了改進的多數(shù)據(jù)流協(xié)同頻繁項集挖掘（MCMDStream）算法。首先，該算法利用單遍掃描數(shù)據(jù)庫的字節(jié)序列滑動窗口挖掘算法發(fā)現(xiàn)數(shù)據(jù)流中的潛在頻繁項集和頻繁項集；其次，構(gòu)建類似頻繁模式樹（FPTree）的壓縮頻繁模式樹（CPTree）存儲已發(fā)現(xiàn)的潛在頻繁項集和頻繁項集，同時更新CPTree樹中每個節(jié)點生成的對數(shù)傾斜時間表中的頻繁項計數(shù)；最后，通過匯總分析得出在多條數(shù)據(jù)流中多次出現(xiàn)的且有價值的頻繁項集，即協(xié)同頻繁項集。相比AStream和HStream算法，MCMDStream算法不僅能夠提高多數(shù)據(jù)流中協(xié)同頻繁項集挖掘的效率，并且還降低了內(nèi)存空間的使用率。實驗結(jié)果表明MCMDStream算法能夠有效地應用于多數(shù)據(jù)流的協(xié)同頻繁項集挖掘。

關鍵詞：

流數(shù)據(jù)挖掘；多數(shù)據(jù)流；滑動窗口；頻繁項集；協(xié)同頻繁項集

中圖分類號： TP301.6 文獻標志碼：A

0引言

隨著萬維網(wǎng)技術的迅速發(fā)展，復雜多樣的數(shù)據(jù)呈現(xiàn)爆炸式增長。數(shù)據(jù)流作為一種特殊形態(tài)的數(shù)據(jù)已在眾多領域中廣泛地應用，例如網(wǎng)絡實時監(jiān)控的數(shù)據(jù)[1]、傳感器采集的數(shù)據(jù)[2]和金融市場的證券交易信息等。相對于傳統(tǒng)靜態(tài)數(shù)據(jù)而言，流數(shù)據(jù)具有實時、連續(xù)、大量、不確定和隨時間變化的特點，因此，在不斷變化的流數(shù)據(jù)上進行頻繁項集挖掘更具有挑戰(zhàn)性。

近年來，流數(shù)據(jù)頻繁項集挖掘[3]成為研究的熱點問題。1998年，Henzinger等[4]首次將流數(shù)據(jù)作為一種數(shù)據(jù)模型提出來。根據(jù)處理數(shù)據(jù)流時所采用的時序范圍，將數(shù)據(jù)流模型劃分為3個范疇：界標模型、快照模型和滑動窗口模型。以界標模型為基礎，Manku等[5]提出了一種近似數(shù)據(jù)流頻繁項集挖掘（Lossy Counting）算法，該算法能夠有損耗地計算整個數(shù)據(jù)流中元素出現(xiàn)的近似頻率，但因其效率不高、動態(tài)性不強；Yu等[6]提出了以假消極結(jié)果為導向在有限內(nèi)存中挖掘數(shù)據(jù)流中頻繁項集的流數(shù)據(jù)頻繁模式挖掘（Frequent Data Stream Pattern Mining， FDPM）算法，但是Lossy Counting和FDPM算法只能得到近似的結(jié)果，因此，從流數(shù)據(jù)中獲得當前準確頻繁項集的科研成果隨之涌現(xiàn)。Mozafari等[7]將滑動窗口引入數(shù)據(jù)流的傳送中，并提出了一種新的技術概念Vertification，以此為基礎設計了根據(jù)滑動窗口的大小調(diào)節(jié)性能和擴展性的滑動窗口增量挖掘（Sliding Window Incremental Miner， SWIM）算法。Leung等[8]構(gòu)造了一種能夠精確地挖掘數(shù)據(jù)流中頻繁項集的新型樹形索引結(jié)構(gòu)（Data Stream Tree，請補充DSTree的英文全稱。 DSTree）。以上算法只針對單數(shù)據(jù)流頻繁項集的挖掘，但是結(jié)合當前的諸多應用，需要解決在多數(shù)據(jù)流環(huán)境[9-10]中頻繁項集挖掘的問題，因此，Guo等[11]提出了HStream算法，目的是發(fā)現(xiàn)多數(shù)據(jù)流中的頻繁項集問題。該算法以FPGrowth算法[12]為基礎挖掘單條數(shù)據(jù)流中的頻繁項集并將其頻數(shù)存儲于節(jié)點的自然傾斜時間窗口表中，通過匯總挖掘在多條數(shù)據(jù)流中多次出現(xiàn)的頻繁項集。在此過程中需要多遍掃描數(shù)據(jù)庫以及生成大量不必要的單位時間窗口，從而導致發(fā)現(xiàn)頻繁項集時既耗時又浪費內(nèi)存占用空間。

針對上述HStream算法低效、內(nèi)存利用率不高的問題，本文提出了一種基于滑動窗口的多數(shù)據(jù)流協(xié)同頻繁項集挖掘（Mining Collaborative Frequent Itemsets in Multiple Data Stream， MCMDStream）算法。該算法首先通過基于字節(jié)序列的滑動窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on based on bitsequence， TISWMFI）算法發(fā)現(xiàn)數(shù)據(jù)流中的潛在頻繁項集和頻繁項集；然后構(gòu)建CPTree用來存儲多數(shù)據(jù)流中的頻繁項集和潛在頻繁項集，同時更新樹節(jié)點中對數(shù)傾斜時間表中項集對應的頻數(shù)；最后匯總分析得出多數(shù)據(jù)流中的協(xié)同頻繁項集。與HStream算法中HTree的自然傾斜時間窗口表相比，MCMDStream算法中新引入的對數(shù)傾斜時間窗口表能夠增量更新CPTree；同時還能夠大量地減少節(jié)點總數(shù)，從而降低了算法的維護代價與空間復雜度；本文新引入的TISWMFI算法相比HStream中的FPGrowth而言，能夠減少對數(shù)據(jù)庫的遍歷次數(shù)以及查詢時間，因此，MCMDStream算法具有更強的適應性和擴展性。

1相關描述與問題定義

設S={S1，S2，…，Sn}為一組數(shù)據(jù)流集合，其中：Si表示一組大量的連續(xù)到達的流數(shù)據(jù)d1j，d2j，…，dij的數(shù)據(jù)序列，dij（i≥1，1≤j≤n）表示在第i時刻第j條數(shù)據(jù)流的值。

定義1項集I[5]。令I={i1，i2，…，im}為所有項的非空集合，其中m為項集的長度，包含k個項的項集稱為k項集。例如項集{a，b}為2項集。

定義2事務數(shù)據(jù)流T[5]。表示一個連續(xù)的事務序列，即T=T1，T2，…，Tn，且TI。設Tid為事務數(shù)據(jù)流Ti的唯一標識符，TUid為時間單位標識符，事務T={TUid，Tid，Itemset}。

定義3滑動窗口SW[4]。指在單位時間內(nèi)進行滑動的一個獨立窗口，其中單位時刻TUi包含一個變量，即SW=[TUn-w+1，TUn-w+2，…，TUn]。其中：n-w+1表示當前滑動窗口單位時間標識號；w表示SW的總長度，且w=TUn-w+1+TUn-w+2+…+TUn。

定義4頻繁項集（Frequent Itemset， FI）[4]。設項集X在滑動窗口SW中的支持度為Sup（X）SW，若Sup（X）SW≥θ·w，則稱X為一個頻繁項集（FI）。其中，θ（θ∈[0，1]）表示用戶自定義的最小支持度閾值。

定義5協(xié)同頻繁項集（Collaborative Frequent ItemsetCFI的英文全稱補充得是否正確？請明確。， CFI）。設在給定數(shù)據(jù)流Si中的項集O，若tOSimax-tOSimin≤θ（tOSimax=max{t1，t2，…，tk}，tOSimin=min{t1，t2，…，tk}），則O是一個協(xié)同項集（Collaborative Itemset， CI）。若協(xié)同項集CI在隨后給定的時間里以同樣的方式在數(shù)據(jù)流集合Φ的數(shù)據(jù)流Si中頻繁出現(xiàn)，則稱CI為一個協(xié)同頻繁項集。

定義6最大誤差因子ε。令ε在系統(tǒng)允許范圍內(nèi)控制算法精度。若ε≤Sup（X）SW≤θ，則項集X為潛在頻繁項集（Potential Frequent Itemset， PFI）；若Sup（X）SW≤ε，則項集X為非頻繁項集（UnFrequent Itemset請補充PFI、UFI的英文全稱。， UFI）。PFI、UFI都是針對特定時間段定義的。例如，在時間段t1內(nèi)，項集X為FI；而在t2內(nèi)，X可能為PFI或UFI。

2算法描述

在本文中，將多數(shù)據(jù)流協(xié)同頻繁項集挖掘分為3步：

第1步利用新引入的TISWMFI算法從數(shù)據(jù)流中產(chǎn)生一組潛在頻繁項集以及頻繁項集；

第2步構(gòu)建一棵基于字典序列的前綴樹CPTree用來保存數(shù)據(jù)流中頻繁項集動態(tài)的變化趨勢，在此重新設計了CPTree結(jié)構(gòu)，加入了對數(shù)傾斜時間窗口記錄FI的頻繁數(shù)；

第3步利用MCMDStream算法從潛在頻繁項集中發(fā)現(xiàn)協(xié)同頻繁項集。

2.1CPTree結(jié)構(gòu)

結(jié)構(gòu)上，CPTree由MTree、Header Table和Logarithmic Tilted Window三部分組成，該結(jié)構(gòu)如圖1所示。

1）MTree。記錄頻繁項集動態(tài)變化的一棵字典序列前綴樹，用來存儲數(shù)據(jù)流中頻繁的和潛在頻繁的項集。

2）Header Table。一個指向MTree中不同層中節(jié)點指針的數(shù)組。利用Header Table，能夠高效地從MTree中挖掘出頻繁的和潛在頻繁的項集，減少更新樹中頻繁項集的時間，從而提高遍歷樹結(jié)構(gòu)的效率。

3）Logarithmic Tilted Window。為了進一步地降低內(nèi)存占用率以及算法的空間復雜度，新增加了對數(shù)傾斜時間窗口LW?；瑒哟翱赟W由大小固定且連續(xù)的LW序列組成，記為{LW1，LW2，…，LWm}。在每個時間間隔內(nèi)，LW為每個節(jié)點都創(chuàng)建了相對應的時間窗口表保留頻繁項集的計數(shù)值。在n組數(shù)據(jù)流中，每個頻繁項所需操作的數(shù)是對整個數(shù)據(jù)流數(shù)據(jù)進行操作的總數(shù)再除以N。

2.2TISWMFI算法

針對在有限的物理存儲空間挖掘頻繁項集會多次掃描數(shù)據(jù)庫的問題，本文提出了一種新穎的單程掃描算法，即基于字節(jié)序列的滑動窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on sequence of bytes， TISWMFI）算法，目的是挖掘給定時間t中SW內(nèi)數(shù)據(jù)流Si的頻繁項集。TISWMFI將SW內(nèi)所有的數(shù)據(jù)項都以字節(jié)序列的形式表示，保證所有的項只被掃描一次，因此，該算法不僅能夠提高內(nèi)存利用率，而且還提高了動態(tài)存儲事務的速度。

2.2.1字節(jié)序列表示法

字節(jié)序列表示法是指用二進制位（0或1）表示在SW內(nèi)數(shù)據(jù)流Si的事務Ti中項X的支持度計數(shù)Sup（X）和出現(xiàn)的頻數(shù)fx，項X的字節(jié)序列表示為Bit（X）。設在當前SW中項X存在于Ti中，則項X的第i位記為1，即Bit（X）=1；否則記為0，即Bit（X）=0。隨著窗口的不斷滑動，需要維護項的字節(jié)序列，因此，在計算Sup（X）時，2個k項集的字節(jié)序列進行“按位與”操作，便得到（k+1）項集（k≥0）的字節(jié)序列；而在進行刪除操作時只需將原有的字節(jié)序列按位左移一位。該方法能夠使窗口快速地滑動而且還能用較小的存儲空間保存所有項集出現(xiàn)的情況。

在滑動窗口SW1和SW2中的事務數(shù)據(jù)流的項集字節(jié)序列為例。在表1中，SW1由〈T1，（abc）〉、〈T2，（bce）〉和〈T3，（abce）〉三條事務組成，并且項a在SW1的T1和T3中存在，因此Bit（a）=101、Bit（b）=111、Bit（c）=111、Bit（d）=000和Bit（e）=011。

2.2.2TISWMFI算法描述

TISWMFI算法由窗口初始化、窗口滑動和頻繁項集生成3個階段組成。具體過程如下。

步驟1滑動窗口初始化階段。當SW=Null時，將單位時間TUi內(nèi)事務Ti中所有項按照字節(jié)序列表示法將其轉(zhuǎn)變?yōu)橄鄬淖止?jié)序列，直到SW=Full時結(jié)束。

步驟2窗口滑動階段。在步驟1的基礎上，將項X的字節(jié)序列“按位左移”即可將當前SW中失效事務中的項集移除。若Sup（X）SW=0，則可刪除項X。

步驟3頻繁項集產(chǎn)生階段。即已知的頻繁（K-1）項集以逐層迭代的方式構(gòu)成候選K項集，并將相應的字節(jié)序列作“按位與”操作計算頻繁項集的支持度，即Bit（X）中字節(jié)1的總數(shù)。主要子步驟如下：

1）單遍掃描數(shù)據(jù)流Si，計算每個項的支持度，刪除支持度小于θ的項，構(gòu)成頻繁1項集FI1；

2）將兩個FI1以自連接的方式構(gòu)成包含候選2項集，保留支持度大于θ的項，形成頻繁2項集FI2；

3）以此類推，逐層迭代，直到?jīng)]有新的頻繁項集產(chǎn)生為止。

滑動窗口SW1和SW2四條事務數(shù)據(jù)流中的頻繁項集如表2所示，SW2由事務T2、T3和T4組成，現(xiàn)以SW2中頻繁項集生成過程為例。設θ=0.6，w=3，Sup（X）SW2=0.6×3=1.8。由此可得，Sup（b）=111、Sup（b）=3>1.8，Bit（c）=110、Sup（c）=2>1.8和Bit（e）=110、Sup（e）=2>1.8，即（b）、（c）和（e）構(gòu)成FI1；利用FI1執(zhí)行“按位與”操作，得到FI2，Bit（bc）=Bit（b） & Bit（c）=110、Sup（bc）=2，同理，Sup（be）=2、Sup（ce）=2；利用FI2執(zhí)行“按位與”操作，得到FI3，Bit（bce）=Bit（bc） & Bit（be） & Bit（ce），Sup（bce）=2>1.8，因此，F(xiàn)I3為（bce）。

2.3MCMDStream算法

MCMDStream算法將TISWMFI算法中發(fā)現(xiàn)的頻繁項集保存在CPTree中，由θ控制FI的數(shù)量，ε控制CPTree剪枝率；其次，通過插入新的FI、PFI和刪除UFI持續(xù)更新CPTree；最后，深度優(yōu)先遍歷CPTree發(fā)現(xiàn)多條數(shù)據(jù)流中的協(xié)同頻繁項集。假設n條數(shù)據(jù)流Si的集合Φ以批處理的方式挖掘，其中在時間間隔ti（i≥1）產(chǎn)生的第j（1≤j≤n）條數(shù)據(jù)流被標記為dij，遍歷自定義數(shù)據(jù)結(jié)構(gòu)中的頻繁項集。多數(shù)據(jù)流協(xié)同頻繁項集挖掘算法偽代碼如下。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：用戶自定義的最小支持度閾值θ；n條數(shù)據(jù)流集合S；最大誤差率ε；協(xié)同頻繁項集集合α。

輸出：協(xié)同頻繁項集。

//步驟1：Construct CPTree

1）

FI=Null， PFI=Null， i=1；

2）

for j=1 to n do

3）

FI= FI∪TISWMFI（dij，θ）；

PFI=CI∪TISWMFI（dij，θ，ε）；

4）

end for

5）

MTree=Initialize_MTree（FI，PFI）

//步驟2：Update CPTree

6）

While S≠Null do

7）

I=Null，i=i+1；

8）

Ci1，Ci2，…，Cin=Preprocessing（di1，di2，…，din，MTree，θ，ε）

9）

for j=1 to n do

10）

I=I∪TISWMFI（Cij）；

11）

end for

12）

MTree=Insert_CPTree（I），MTree=Prune_CPTree（MTree，θ，ε）；

13）

end while

//步驟3：Mining collaborative Frequent Itemsets across //Multiple Streams（在多數(shù)據(jù)流中挖掘協(xié)同頻繁項集）

14）

CFI=Collaboration_Mining（α）

15）

Output CFI

程序后

具體算法步驟如下。

步驟1利用TISWMFI算法從第一批數(shù)據(jù)流dij中提取FI和PFI。

步驟2構(gòu)造CPTree，并初始化CPTree的MTree、Header Table和Logarithmic Tilted Window。計算各項集在指定時間窗口內(nèi)的平均頻數(shù)并降序排列。將所有數(shù)據(jù)項E∈{FI∪PFI}插入到MTree中；同時將所有數(shù)據(jù)流中數(shù)據(jù)項E的頻繁項計數(shù)寫入每個節(jié)點相對應的對數(shù)時間窗口表中。根據(jù)頻繁計數(shù)對數(shù)據(jù)項E分類，同時，在Header Table增加一個指針指向MTree每一層首節(jié)點。

步驟3利用最新的數(shù)據(jù)流更新MTree。該過程有如下4個子步驟：

1）預處理最新的數(shù)據(jù)流，刪除dij中的UFI。

2）查找項集I，在每一條被預處理的數(shù)據(jù)流中查找未被剪枝的項集。

3）將數(shù)據(jù)項集I插入MTree中，若I已插入樹中，則僅更新窗口表中相對應數(shù)據(jù)項的計數(shù)值；否則，將在MTree插入I，同時更新CPTree的三部分。

4）調(diào)用末端剪枝函數(shù)Prune_CPTree（）刪除窗口末端的UFI。

步驟4當所有的數(shù)據(jù)流更新完成后，深度優(yōu)先遍歷MTree，在多數(shù)據(jù)流集合Φ中挖掘協(xié)同頻繁項集CFI。

2.4算法性能分析

3實驗結(jié)果與分析

實驗環(huán)境配置為：Windows 7 Professional操作系統(tǒng)，Intel Core CPU i33220 @2.93GHz，1TB RAM。使用Microsoft Visual C++ Version 6.0實現(xiàn)算法以及數(shù)據(jù)流模擬生成模塊。模擬實驗主要從存儲代價、算法響應時間、查準率和查全率4個方面分別對AStream、HStream和MCMDStream算法進行對比分析。其中AStream算法是基于Aprior算法的挖掘頻繁項集的算法，通過對數(shù)據(jù)流進行多次掃描、自底向上的寬度優(yōu)先搜索得到協(xié)同頻繁項集的一種算法。測試數(shù)據(jù)集是由IBM Quest MarketBasket合成數(shù)據(jù)生成器產(chǎn)生的6條數(shù)據(jù)流。每條數(shù)據(jù)流中包含2000個事務，其中：TLen表示每個事務的平均長度，NItems表示每個事務中每個項集的平均長度，如表3所示。

3.1存儲代價

內(nèi)存使用量影響著算法的可擴展性，將MCMDStream與另外兩個多數(shù)據(jù)流頻繁項集挖掘算法AStream和HStream進行對比。假定在已處理的數(shù)據(jù)規(guī)模不變的情況下，測試IBM合成6條數(shù)據(jù)流分批到達構(gòu)建CPTree樹結(jié)構(gòu)時所產(chǎn)生的節(jié)點的總數(shù)。在最小支持度閾值和最大誤差率不變的前提下，分批處理事務數(shù)據(jù)流長度為5～30，步長為5。當所有的數(shù)據(jù)項插入CPTree后，各算法生成樹節(jié)點的總數(shù)如圖2所示。

從圖2可得，MCMDStream算法中樹結(jié)構(gòu)生成的節(jié)點數(shù)量與AStream和HStream相比最少，因此所占用的內(nèi)存空間最小，算法的存儲空間最低，即MCMDStream算法的空間復雜度較小。這是因為AStream算法僅用ε控制樹的剪枝率，因此包含了大量的潛在頻繁項集，HStream使用θ與ε同時控制剪枝率，而MCMDStream算法在使用θ與ε控制CPTree剪枝率的基礎上采用對數(shù)傾斜時間窗口，減少了每個節(jié)點中時間窗口的數(shù)量，便于冗余剪枝。最終減小了樹結(jié)構(gòu)的內(nèi)存使用率，從而降低了存儲代價。

3.2算法響應時間

該算法根據(jù)不同的支持度閾值產(chǎn)生不同的響應時間。測試各算法在IBM合成的6條數(shù)據(jù)流的響應時間。設在IBM數(shù)據(jù)集的支持度閾值變化范圍為1～5，步長為1。實驗結(jié)果分別如圖3所示。

從圖3中得出，HStream算法具有較高的事務敏感性。當事務數(shù)據(jù)量逐漸增大時，該算法因受剪枝策略的影響會產(chǎn)生較冗余的分支。HStream算法是在FPGrowth算法的基礎上進行頻繁項集挖掘，不僅需要掃描兩遍數(shù)據(jù)庫，而且還會產(chǎn)生大量的候選頻繁項集，因此在進行挖掘過程中消耗大量的時間。MCMDStream算法是基于字節(jié)序列的滑動窗口的頻繁項集挖掘，其在查詢過程中，只需建立一棵頻繁模式樹且只掃描一遍數(shù)據(jù)庫，因此節(jié)省了查詢響應時間，從而降低了MCMDStream算法的時間復雜度，查詢效率高于HStream和AStream。

3.3查準率和查全率

最大誤差值ε是算法中一項重要的剪枝參數(shù)，查準率是指算法發(fā)現(xiàn)的實際協(xié)同頻繁項集數(shù)與算法發(fā)現(xiàn)輸出數(shù)量的百分比，而查全率則為算法發(fā)現(xiàn)的實際協(xié)同頻繁項集數(shù)與真實數(shù)量的百分比。挖掘數(shù)據(jù)集的協(xié)同頻繁項集以最大誤差值ε作為剪枝參數(shù)，在更新樹結(jié)構(gòu)時能夠影響算法的查準、查全率。圖4～5分別評估了在IBM合成的6條數(shù)據(jù)流中不同誤差值對算法查準、查全率的影響。假定誤差值ε分別為0.0002，0.0008，0.0014和0.002時IBM合成數(shù)據(jù)流中S1、S2和S3三條數(shù)據(jù)流的查準率和查全率。

從圖4和圖5中可以看出，對于不同的誤差值，MCMDStream算法的查準率和查全率高于其他算法。當誤差值增大時，頻繁項集的數(shù)量減少，因此用戶指定的誤差值越大，頻繁項集數(shù)量越少，挖掘多條數(shù)據(jù)流中的協(xié)同頻繁項集時的準確率和查全率就會越高。

4結(jié)語

本文提出了一種能夠高效地挖掘多數(shù)據(jù)流協(xié)同頻繁項集的MCMDStream算法。該算法不僅能夠減小內(nèi)存利用率、縮短挖掘的查詢響應時間，而且還可以提高算法的查準率和查全率。模擬實驗利用IBM合成數(shù)據(jù)集驗證了該算法的性能優(yōu)于AStream和HStream算法，能夠很好地應用于多數(shù)據(jù)流協(xié)同頻繁項集的挖掘，但是本文只考慮了單機上的多數(shù)據(jù)流頻繁項集挖掘問題，在今后的研究中，將采用分布式集群這一有效的途徑，實現(xiàn)大規(guī)模多數(shù)據(jù)流中協(xié)同頻繁項集發(fā)現(xiàn)問題。

參考文獻：

[1]

BHATTACHARYA S， MOON S. Network performance monitoring and measurement： techniques and experience [M]// Universal Access in HumanComputer Interaction. Access to Interaction. Berlin： Springer， 2015： 528-537.

[2]

王爽，王國仁.面向不確定感知數(shù)據(jù)的頻繁項查詢算法[J].計算機學報，2013，36（3）：571-581.（WANG S， WANG G R. Frequent items query algorithm for uncertain sensing data [J]. Chinese Journal of Computers， 2013， 36（3）： 571-581.）

[3]

金澈清，錢衛(wèi)寧，周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學報，2004，15（8）：1172-1181.（JIN C Q， QIAN W N， ZHOU A Y. Analysis and management of streaming data [J]. Journal of Software， 2004， 15（8）： 1172-1181.

[4]

HENZINGER M R， RAGHAVAN P， RAJAGOPALAN S. Computing on data streams [C]// Proceedings of the 1999 External Memory Algorithms： DIMACS Workshop External Memory and Visualization. Boston： American Mathematical Society， 1999： 107-118.

[5]

MANKU G， MOTWANI R. Approximate frequency counts over data streams [C]// Proceedings of the 28th International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2002： 346-357.

[6]

YU J， CHONG Z， LU H， et al. False positive or false negative： mining frequent itemsets from high speed transactional data streams [C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2004： 204-215.

[7]

MOZAFARI B， THANKKAR H， ZANIOLO C. Verifying and mining frequent patterns from large windows over data streams [C]// ICDE 2008： Proceedings of the IEEE 24th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2008： 179-188.

[8]

LEUNG C K S， KHAN Q. DSTree： a tree structure for the mining of frequent sets from data streams [C]// ICDM06： Proceedings of the 2006 Sixth International Conference on Data Mining. Piscataway， NJ： IEEE， 2006： 928-932.

[9]

HRISTIDIS V， VALDIVIA O， VLACHOS M， et al. Information discovery across multiple streams [J]. Information Sciences， 2009， 179（19）： 3268-3285.

[10]

YEH M Y， DAI B R， CHEN M S. Clustering over multiple evolving streams by events and correlations [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（10）： 1349-1362.

[11]

GUO J， ZHANG P， TAN J， et al. Mining frequent patterns across multiple data streams [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 2325-2328.

[12]

HAN J， PEI J， YIN Y， et al. Mining frequent patterns without candidate generation： a frequentpattern tree approach [J]. Data Mining and Knowledge Discovery， 2004， 8（1）： 53-87.

[13]

CHANG J H， LEE W S. Finding recent frequent itemsets adaptively over online data streams [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 487-492.

[14]

AGRAWAL R， SRIKANT R. Privacypreserving data mining [C]// Proceedings of the 2009 ACM SIGMOD Record. New York： ACM， 2000， 29（2）： 439-450.

[15]

BERNECKER T， CHENG R， CHEUNG D W， et al. Modelbased probabilistic frequent itemset mining [J]. Knowledge and Information Systems， 2013， 37（1）： 181-217.