韓萌 丁劍

摘 要：一些先進應(yīng)用如欺詐檢測和趨勢學(xué)習(xí)等帶來了數(shù)據(jù)流頻繁模式挖掘的發(fā)展。不同于靜態(tài)數(shù)據(jù)，數(shù)據(jù)流挖掘面臨著時空約束和項集組合爆炸等問題。對已有數(shù)據(jù)流頻繁模式挖掘算法進行綜述并對經(jīng)典和最新算法進行分析。按照模式集合的完整程度進行分類，數(shù)據(jù)流中頻繁模式分為全集模式和壓縮模式。壓縮模式主要包括閉合模式、最大模式、top-k模式以及三者的組合模式。不同之處是閉合模式是無損壓縮的，而其他模式是有損壓縮的。為了得到有趣的頻繁模式，可以挖掘基于用戶約束的模式。為了處理數(shù)據(jù)流中的新近事務(wù)，將算法分為基于窗口模型和基于衰減模型的方法。數(shù)據(jù)流中模式挖掘常見的還包含序列模式和高效用模式，對經(jīng)典和最新算法進行介紹。最后給出了數(shù)據(jù)流模式挖掘的下一步工作。

關(guān)鍵詞：數(shù)據(jù)流; 數(shù)據(jù)流挖掘; 頻繁模式挖掘; 序列模式挖掘; 高效用模式挖掘

中圖分類號： TP18

文獻標(biāo)志碼：A

文章編號：1001-9081（2019）03-0719-09

Abstract： Advanced applications such as fraud detection and trend learning lead to the development of frequent pattern mining over data streams. Data stream mining has to face more problems than static data mining like spatio-temporal constraint and combinatorial explosion of itemsets， which are different from static data mining. In the paper， the existing frequent pattern mining algorithms over data streams were reviewed， and some classical algorithms and some newest algorithms were analyzed. According to the completeness of pattern set， frequent patterns of data stream could be divided into complete patterns and compressed patterns. Compressed patterns include closed frequent patterns， maximal frequent patterns， top-k frequent patterns and combinations of them. Between them， only closed frequent patterns are losslessly compressed. And constrained frequent pattern mining was used to narrow the result set obtained， satisfying the user's demand more. Algorithms based on sliding window model and time decay model were used to better handle recent transactions which occupy an important position in data stream mining. Moreover， two of the common algorithms， sequential pattern mining and high utility pattern mining algorithms were introduced. At last， further research direction of frequent pattern mining over data streams were discussed.

Key words： data stream; data stream mining; frequent pattern mining; sequential pattern mining; high utility pattern mining

0 引言

在一些新興的應(yīng)用場景下，例如智能城市、大型基礎(chǔ)設(shè)施監(jiān)控、物聯(lián)網(wǎng)等，數(shù)據(jù)產(chǎn)生的速度越來越快。數(shù)據(jù)流（data stream）被認為是高速率數(shù)據(jù)，通常被認為是大數(shù)據(jù)，它是無限的、快速的、變化的和有序的。在某些環(huán)境下，數(shù)據(jù)流的處理方法必須快速且能適應(yīng)變化。數(shù)據(jù)流模型面臨的主要約束[1]包括：

1）數(shù)據(jù)量巨大，可以認為是無限的。因此，無法存儲所有的數(shù)據(jù)。合理的方法是存儲數(shù)據(jù)的概要信息。

2）數(shù)據(jù)到達的速度快。因此，需要實時處理數(shù)據(jù)，且處理后數(shù)據(jù)即被丟棄。

3）數(shù)據(jù)項的分布可能隨著時間而變化。因此，歷史數(shù)據(jù)會變得無用甚至有害。

在進行數(shù)據(jù)流挖掘時，需要考慮這些約束。近年來，研究者關(guān)注數(shù)據(jù)流中分類、聚類以及模式挖掘等問題的研究。頻繁模式是指在數(shù)據(jù)集中出現(xiàn)的次數(shù)高于用戶定義的最小支持數(shù)/度閾值的項的集合。數(shù)據(jù)流頻繁模式挖掘方法通?？梢苑譃閮深?。第一類是基于統(tǒng)計來估計模式頻度。如算法Sticky Sampling[2]采用統(tǒng)計抽樣技術(shù)來估計項集的支持數(shù)。它是挖掘數(shù)據(jù)流頻繁模式的近似算法，是基于概率統(tǒng)計的，丟失可能頻繁模式的概率不高于用戶定義的參數(shù)值。算法Lossy Counting[2]是數(shù)據(jù)流頻繁模式挖掘經(jīng)典方法之一，它給定了錯誤參數(shù)來挖掘數(shù)據(jù)流中的頻繁模式。第二類是基于草圖來近似估計模式頻度。草圖是一種概率數(shù)據(jù)結(jié)構(gòu)，它用于處理項出現(xiàn)頻度。最經(jīng)典的算法是CountSketch[3]，它使用有限的存儲空間來估計數(shù)據(jù)流中頻繁項，主要依賴于草圖數(shù)據(jù)結(jié)構(gòu)。Pyramid框架[4]使用草圖數(shù)據(jù)結(jié)構(gòu)來發(fā)現(xiàn)數(shù)據(jù)流中頻繁模式，該算法在算法正確率以及算法速度方面有一定的優(yōu)勢。

挖掘數(shù)據(jù)流時研究者認為新的事務(wù)比歷史事物重要得多。使用窗口模型和衰減模型可以很好地處理新事務(wù)。經(jīng)典的基于窗口模型的算法包括Lossy Counting[2]和DSM_FT[5]。最常見的窗口模型是滑動窗口模型，如算法MSW[6]、MFI-CBSW[7]、MFI-TimeSW[8]和TMFI[9]使用滑動窗口模型挖掘數(shù)據(jù)流中頻繁模式。經(jīng)典的基于衰減模型的算法有estDec[10]和estDec+[11]。除此之外，根據(jù)數(shù)據(jù)流處理方法，可以分為模式增長方法、假陽性和假陰性方法等;根據(jù)挖掘模式結(jié)果集合的精簡程度，可以分為全集模式挖掘方法和壓縮模式挖掘方法等;根據(jù)模式的特征，可以分為頻繁模式、頻繁序列模式、頻繁樹模式、頻繁圖模式挖掘方法等。這些內(nèi)容會在下文進行介紹。

1 基本概念

頻繁模式挖掘的一個很大的不足在于全集頻繁模式的數(shù)量巨大，尤其當(dāng)最小支持度閾值很小或事務(wù)長度很長時，挖掘出來的模式呈指數(shù)級增長。為了減少模式的數(shù)量，可以挖掘壓縮模式，如最大模式、閉合模式和top-k模式等，如定義2～定義4所示。

定義4 top-k頻繁模式。將所有已挖掘出的項集按照支持度由高到低的順序排序，令θ′為第k個項集的支持度。則對于頻繁項集P，若滿足條件support（P）≥θ′，則稱P為top-k頻繁模式。

示例1 包含5個事務(wù)的數(shù)據(jù)流如表1所示。令n=5，θ=0.4，則得到全集模式、最大模式、閉合模式和top-2模式如表2所示。

從表2中可以看出，壓縮模式數(shù)量明顯小于全集模式。在θ=0.4條件下可以得到13個全集模式，9個閉合模式，5個最大模式和6個top-2模式。其中閉合模式是無損壓縮形式，它包含全集模式中的所有信息，其余的為有損壓縮模式。

若定義約束為Constraint1至Constraint4所示，則可以得到滿足不同約束的頻繁模式集合如表3所示，可以得到4個滿足Constraint1，7個滿足Constraint2，4個滿足Constraint3和3個滿足Constraint4的頻繁模式。約束條件越復(fù)雜具體則得到的模式集合越有趣，更利于滿足用戶的需求。

1）約束Constraint1：對任意一個頻繁項集P，如果其包含項{a}，則稱其滿足約束Constraint1。即Constraint1（P）≡（{a}P）。

2）約束Constraint2：對任意一個頻繁項集P，如果其長度為2，則稱其滿足約束Constraint2。即Constraint2（P）≡（length（P）=2）。函數(shù)length（P）表示P的長度。

3）約束Constraint3：對任意一個頻繁項集P，如果它是滿足Constraint1的閉合模式，則稱其滿足約束Constraint3。即Constraint3（P）≡（closed（P）=true）∧（Constraint1（P）=true）。函數(shù)closed（P）用于判斷P是否為閉合模式。

4）約束Constraint4：對任意一個頻繁項集P，如果它是滿足Constraint1和Constraint2的模式，則稱其滿足約束Constraint4。即Constraint4（P）≡（Constraint1（P）=true）∧（Constraint2（P）=true）。

本章中常見的符號和函數(shù)的含義如表4所示，包含數(shù)據(jù)集合、項的取值范圍，以及常用的支持數(shù)、支持度和最小支持度閾值的表示符號。

2 數(shù)據(jù)流中頻繁模式類型

本節(jié)重點介紹壓縮模式和約束模式，表5給出了幾種模式的比較。全集模式是全部模式的集合;閉合模式是無損的壓縮方式，可以壓縮大量的模式;最大模式是有損壓縮方式，得到的模式數(shù)量少于閉合模式;top-k模式僅取k組頻度最高的模式，通常數(shù)量很少;約束模式是挖掘滿足用戶需求的模式，模式數(shù)量也會明顯小于模式全集。

2.1 全集頻繁模式

數(shù)據(jù)集合中出現(xiàn)次數(shù)不低于用戶定義閾值的所有頻繁模式集合稱為全集頻繁模式（Complete Frequent Patterns， CoFPs）。一般來說，CoFPs中包含的模式數(shù)量巨大，且包含有大量短的無意義的模式，因此不利于用戶的使用。

近年來，挖掘CoFPs的方法有很多。如算法FIS_EDS[13]采用界標(biāo)窗口模型挖掘數(shù)據(jù)流中的CoFPs。該算法設(shè)計數(shù)據(jù)結(jié)構(gòu)Bit-Table存儲模式信息。使用Bit-Table可以比較容易地得到模式頻度并且避免了解析整個窗口中的事務(wù)信息。CanTree-GTree算法[14]基于Hadoop框架挖掘數(shù)據(jù)流中的CoFPs。該算法使用投影樹結(jié)構(gòu)CanTree和GTree存儲模式信息，并采用自頂向下的遍歷方式搜索整棵樹。該算法可以得到準(zhǔn)確完整的模式集合。SysTree算法[15]采用并行技術(shù)挖掘數(shù)據(jù)流中的CoFPs。該算法基于樹結(jié)構(gòu)，且分別采用界標(biāo)窗口和滑動窗口來處理事務(wù)。當(dāng)頻繁項數(shù)量少時，該算法可以實現(xiàn)很準(zhǔn)確的挖掘過程;當(dāng)頻繁項數(shù)量大時，挖掘過程是近似的且是非假陽性的。PFIMoS算法[16]挖掘不確定數(shù)據(jù)流中的概率頻繁模式。該算法是深度優(yōu)先的，且設(shè)計了一種索引樹結(jié)構(gòu)PFIT存儲數(shù)據(jù)概要信息。由于以上策略，與已有算法相比，該算法可以減低時間和空間消耗。

2.2 閉合頻繁模式

閉合頻繁模式（Closed Frequent Patterns， CFPs）是強大的頻繁模式的表現(xiàn)方式，因為它們消除冗余信息。一般來說，閉合頻繁模式比全集頻繁模式中的模式數(shù)量少得多，且閉合模式包含了全集頻繁模式中的全部信息，是一種無損壓縮模式。

近年來，在數(shù)據(jù)流中挖掘閉合頻繁模式的方法有很多。經(jīng)典算法包括Moment[17]、CloStream+[18]和TMoment[19]等采用滑動窗口挖掘數(shù)據(jù)流的閉合頻繁模式。Moment算法使用事務(wù)滑動窗口挖掘數(shù)據(jù)流中的CFPs。該算法中設(shè)計一種新的數(shù)據(jù)結(jié)構(gòu)CET（Closed Enumeration Tree）來存儲CFPs和臨界CFPs。使用CET相比前綴樹而言，可以減少大量的樹節(jié)點，降低插入和刪除模式時的時間和空間消耗。CloStream+算法設(shè)計一種新的數(shù)據(jù)結(jié)構(gòu)挖掘數(shù)據(jù)流中的CFPs。算法設(shè)計兩個新的數(shù)據(jù)結(jié)構(gòu)ClosedTable和CidList，前者存儲與閉合模式有關(guān)的信息，后者存儲與數(shù)據(jù)流中出現(xiàn)的項（item）有關(guān)的信息。二者的交叉點是都存儲事務(wù)的標(biāo)識TID。該算法不需要消耗大量時間進行空間搜索，但是相對應(yīng)地會付出更多的時間消耗。TMoment算法使用TCET（Transaction translate Closed Enumeration Tree）數(shù)據(jù)結(jié)構(gòu)挖掘數(shù)據(jù)流中的CFPs。TCET是一種前綴樹結(jié)構(gòu)，每個節(jié)點表示一個閉合項集。當(dāng)滑動窗口更新數(shù)據(jù)時，算法使用深度優(yōu)先策略遍歷該樹來更新閉合頻繁模式信息。TCET存儲窗口中內(nèi)容和閉合模式信息時需要的內(nèi)存空間比較少。

AFPCFI-DS（Algorithm based on FP-tree for mining Closed Frequent Itemsets in Data Stream）算法[20]使用FP樹結(jié)構(gòu)挖掘每個滑動窗口中的CFPs。每次處理新的滑動窗口時，算法會首先更新頭表（head table），然后依據(jù)頭表更新FP-tree。每當(dāng)添加或刪除事務(wù)時，算法使用局部更新策略來降低時間消耗。TDMCS算法[21]采用滑動窗口模型和時間衰減模型挖掘可變數(shù)據(jù)流中的CFPs。為了提高效率，設(shè)定的閉合頻繁模式滿足支持度誤差度衰減因子這三層結(jié)構(gòu)。該算法設(shè)計一種均值衰減衰減因子，使得到的模式結(jié)果集合具有高且均衡的查全率和查準(zhǔn)率。這個算法可以有效地處理具有概念漂移問題的數(shù)據(jù)流模式挖掘過程。FLMCFI（Fast and Lossless Mining of Closed Frequent Itemsets）算法[22]提出一種新的搜索機制挖掘數(shù)據(jù)流中的CFPs。該搜索機制可以用于解決數(shù)據(jù)流中觀察到的概念漂移現(xiàn)象。

2.3 最大頻繁模式

最大頻繁模式（Maximal Frequent Patterns， MFPs）也稱為最長頻繁模式。如果一個頻繁模式?jīng)]有父模式，則它是最大頻繁模式。最大頻繁模式的目的是取長度最長的模式集合。最大頻繁模式集合中模式數(shù)量會明顯低于全集模式中的模式數(shù)量。但是由于它是一種有損壓縮方式，因此無法從最大模式集合中反推出全集模式集合。

經(jīng)典的MFPs挖掘算法之一是estDec+[11]。該算法使用壓縮前綴樹CP-tee挖掘MFPs，與前綴樹結(jié)構(gòu)相比可以降低內(nèi)存消耗。CP-tree上的每個節(jié)點都存儲多個項集的信息。因此可以通過合并或分類節(jié)點來控制CP-tree的大小。該算法可以使用有限的內(nèi)存空間存儲大量的項集信息。WMFP-SW算法[23]使用滑動窗口模型發(fā)現(xiàn)數(shù)據(jù)流中的權(quán)重MFPs。一種新的樹結(jié)構(gòu)WMFP-SW-tree和陣列結(jié)構(gòu)WMFP-SW-array用于存儲權(quán)重模式信息，可以有效提高挖掘的效率。挖掘出的MFPs需要滿足最小支持度閾值和權(quán)重約束。TV和iTV算法[24]基于spark挖掘數(shù)據(jù)流中的MFPs。該文中提出一種ASP-Tree結(jié)構(gòu)存儲模式信息，與模式增長算法相比可以降低內(nèi)存消耗，同時可以減少搜索時間。WOB點陣算法[25]同樣使用滑動窗口模型挖掘數(shù)據(jù)流中的權(quán)重MFPs。該算法使用FP樹存儲模式信息，由于使用點陣技術(shù)可以避免反復(fù)重建整個樹機構(gòu)。

2.4 top-k頻繁模式

top-k頻繁模式（Top-k Frequent Patterns， TkFPs）用于挖掘數(shù)據(jù)流中出現(xiàn)頻度最高的k組模式。一般而言，MFPs和TkFPs的壓縮程度是強于CFPs，且都是有損壓縮。已有的算法挖掘TkFPs或閉合TkFPs，如算法FSS[26]、TKRES[27]挖掘TkFPs。為了限定模式結(jié)果集的大小，算法Top-k-FCI[28]、FCI_max[29]、TFRC-Mine[30]挖掘數(shù)據(jù)流中的閉合TkFPs。

TFRC-Mine算法采用最小長度策略挖掘閉合的TkFPs。該算法不需要設(shè)置支持度閾值。為了處理項之間的冗余和興趣度關(guān)聯(lián)，算法關(guān)注閉合模式且設(shè)置了最小長度約束。算法中設(shè)計了一種新的壓縮位向量表示形式，用于剪枝無趣的候選項。TKRES算法挖掘信號數(shù)據(jù)流中的TkFPs。挖掘出的模式是連續(xù)的形式，可以稱之為片斷（episode）。這樣更利于監(jiān)督者對得到的TkFPs結(jié)果集進行分析，從而作出合理的判斷。TKRES算法采用k樹結(jié)構(gòu)來保存top-k片斷和它們的出現(xiàn)信息。TwMinSwap[31]算法采用項抽樣策略挖掘數(shù)據(jù)流中的TkFPs。核心思想是采用時間權(quán)重來統(tǒng)計模式的重要性，隨著時間的推進歷史模式權(quán)重會減少。該算法僅需要O（k）內(nèi)存空間存儲模式信息。算法采用最小長度策略挖掘閉合的TkFPs。FTK算法[32]使用任意大小的滑動窗口模型挖掘TkFPs。該算法使用的內(nèi)存空間僅與窗口大小成對數(shù)關(guān)系，而不是線性關(guān)系;因此，與已有方式相比得到的模式結(jié)果集合更準(zhǔn)確，且時間消耗會明顯減少。

2.5 約束頻繁模式

約束可以用于篩選數(shù)據(jù)或結(jié)果集，可以令用戶找到真正有興趣的內(nèi)容。在頻繁模式挖掘過程中，約束挖掘可以減少模式的數(shù)量，提高模式集合的利用率。約束挖掘（constrained mining）是指用戶僅對頻繁模式挖掘結(jié)果的一部分感興趣，即模式需要滿足用戶定義的約束，這樣挖掘出的模式稱為約束頻繁模式（Constrained Frequent Patterns， CdFPs）。

例如，最小支持度閾值約束就是反單調(diào)約束，即如果一個項集是非頻繁的，則其父項集也是非頻繁的。如一個項集P滿足約束ConstraintA（P）≡（{i， j}P），其中i， j為項。則P的父項集也滿足約束ConstraintA。即ConstraintA是滿足單調(diào)性的。如果項集P不滿足約束ConstraintA，其父項集也可能滿足約束ConstraintA。

Leung等[33]設(shè)計一種基于樹結(jié)構(gòu)的算法發(fā)現(xiàn)不確定數(shù)據(jù)流中的CdFPs。為了發(fā)現(xiàn)滿足用戶需求的模式，加入了對類值取值范圍的約束。設(shè)計樹結(jié)構(gòu)存儲滿足約束的項集，對第一批數(shù)據(jù)直接存儲內(nèi)容。樹中的節(jié)點包含兩個字段——項名和支持度。算法從樹中挖掘滿足用戶定義支持度的頻繁模式。Silva等[12]設(shè)計了多個約束發(fā)現(xiàn)數(shù)據(jù)流中的CdFPs。算法將約束加入壓縮前綴模式樹結(jié)構(gòu)從而生成滿足用戶不同約束的模式。樹中的每個節(jié)點包含一個項，一個近似支持度和最大誤差值。樹中的邊連接同時出現(xiàn)的項用于創(chuàng)建模式。這樣每個節(jié)點對應(yīng)一個近似模式，模式由根節(jié)點到這個節(jié)點中的項組成。這樣可以從全集模式中篩選出可能的模式，會降低內(nèi)存和時間消耗。Hu等[34]提出算法用于挖掘數(shù)據(jù)流中的閉合CdFPs。首先將數(shù)據(jù)流分成片段，然后使用樹結(jié)構(gòu)存儲可能的約束閉合頻繁項集。對于每一段到達的數(shù)據(jù)，首先建立相應(yīng)的局部樹數(shù)結(jié)構(gòu)，然后更新和剪枝全局樹結(jié)構(gòu)用于挖掘約束閉合頻繁模式。該算法定義了頻繁項集需要包含的項內(nèi)容的約束，最終目的是篩選頻繁模式集合，找到更有用的關(guān)聯(lián)規(guī)則。Cuzzocrea等[35]在不確定數(shù)據(jù)流中發(fā)現(xiàn)滿足用戶約束的CdFPs。該算法處理的是無限信號網(wǎng)絡(luò)數(shù)據(jù)流，設(shè)計了兩種約束簡潔反單調(diào)約束和簡潔非反單調(diào)約束的頻繁模式挖掘。算法是基于樹結(jié)構(gòu)的分布挖掘系統(tǒng)，用于發(fā)現(xiàn)滿足簡潔約束的頻繁模式，首先發(fā)現(xiàn)滿足約束的局部頻繁項集，然后發(fā)現(xiàn)滿足約束的全局頻繁項集。Kiran等[36]設(shè)計一種模式增長算法，采用周期頻繁樹結(jié)構(gòu)發(fā)現(xiàn)大數(shù)據(jù)中的周期CdFPs。這些模式滿足最小支持度閾值和最大到達間隔的約束。定義了局部周期性和周期性用于找到局部和全局頻繁模式。如果一個模式的局部周期性不滿足用于定義的最大周期閾值，則它是非周期的頻繁模式，可以用于避免對這些頻繁模式進一步搜索。因此，使用局部周期性可以降低找到周期頻繁模式的計算成本。Cagliero等[37]分析無線傳感網(wǎng)絡(luò)中的歷史信號數(shù)據(jù)流，以識別其中讀數(shù)出現(xiàn)異常趨勢的傳感器組合。作者設(shè)計基于距離的約束來發(fā)現(xiàn)信號數(shù)據(jù)流中的非頻繁權(quán)重模式。這種約束可以用于分析在不同環(huán)境或者不同條件下獲取的傳感器測量結(jié)果。

3 數(shù)據(jù)流中頻繁模式挖掘關(guān)鍵技術(shù)

數(shù)據(jù)流是海量、快速、有序的數(shù)據(jù)序列，因此在有限的時間和空間中挖掘數(shù)據(jù)流中的頻繁模式面臨很大的挑戰(zhàn)。研究者提出了許多在數(shù)據(jù)流中挖掘頻繁模式的方法，包括窗口方法、衰減方法、先驗方法、模式增長方法、精確方法、近似方法、假陽性方法、假陰性方法、在線方法和離線方法等，本文對幾種主要方法介紹。表6給出了幾種經(jīng)典數(shù)據(jù)流頻繁模式挖掘算法概述，從使用的窗口模型、衰減制度、使用方式、采用何種近似算法以及發(fā)現(xiàn)的模式類型等方面進行介紹。

3.1 窗口方法

數(shù)據(jù)流處理常用的窗口模型有三種：界標(biāo)窗口（landmark window）、滑動窗口（sliding window）和傾斜窗口/衰減窗口（damped window）。界標(biāo)窗口固定窗口的起始點s，窗口的另一端e隨著數(shù)據(jù)的不斷到達而增長，不斷地把得到的結(jié)果輸出。算法處理Ts和Te之間的最新事務(wù)數(shù)據(jù)。滑動窗口對窗口的起始與結(jié)束都沒有明確的定義，定義的是窗口的長度N。即算法處理Tnew-N+1和Tnew之間的最新事務(wù)數(shù)據(jù)。當(dāng)新事物Tnew+1到達時，歷史事務(wù)Tnew-N+1會移除窗口。處在窗口內(nèi)的事務(wù)具有相等的重要性。窗口保持一定的長度在數(shù)據(jù)流上進行滑動，不斷地把得到的結(jié)果輸出。衰減窗口是由固定的時間起點s，窗口的另一端e隨著數(shù)據(jù)流的到達不斷增長。但是不同時間段的數(shù)據(jù)具有不同的權(quán)重。即歷史數(shù)據(jù)所占權(quán)重很小，而新數(shù)據(jù)權(quán)重大。算法處理Ts和Te之間的最新事務(wù)數(shù)據(jù)。

數(shù)據(jù)流挖掘最常用的窗口模型是滑動窗口模型（Slidng Window Model， SWM）?；瑒哟翱谀Ｐ桶ü潭⊿WM與可變SWM。在任意時刻，前者中窗口內(nèi)最新事務(wù)的個數(shù)是固定的;而后者的最新事務(wù)個數(shù)是可變的。算法設(shè)計對窗口內(nèi)的最新事務(wù)進行處理。

圖1是采用固定滑動窗口處理新事務(wù)的過程。圖1（a）中處理最新事務(wù)Tnew，采用的滑動窗口大小為N。當(dāng)處理新事務(wù)Tnew′時，由于滑動窗口大小N，則事務(wù)Tnew-N+1和Tnew′-N+1之間的|new′-new|個事務(wù)將被移出窗口，如圖1（b）所示。移出的方法可以是單個移出或批量移出。為了避免出現(xiàn)窗口內(nèi)的事務(wù)出現(xiàn)概念漂移現(xiàn)象，一般窗口的大小不會很大。

以采用概念漂移檢測器調(diào)整滑動窗口為例介紹窗口的變化，當(dāng)出現(xiàn)概念漂移則收縮窗口，否則擴展窗口。假設(shè)給定窗口大小N，圖2表示了可變滑動窗口擴展和收縮的過程，其中|new′-new|表示Tnew′與Tnew之間的實例個數(shù)或者時間的距離。圖2（b）表示沒有發(fā)生概念漂移時，滑動窗口會擴展窗口的尺寸，從N擴展到N+|new′-new|。圖2（c）表示發(fā)生概念改變時，滑動窗口會縮減尺寸，窗口大小會從N收縮至N′。

固定SWM會按照經(jīng)驗給定窗口大小，且該值是固定的。如SWCA[38]、EclatDS[39]、MSW[6]、SWP-Tree[40]和SA-Miner[41]采用滑動窗口發(fā)現(xiàn)模式結(jié)果集。TKRES算法[27]使用滑動窗口模型挖掘信號數(shù)據(jù)流中的top-k頻繁模式。窗口中包含m組數(shù)據(jù)，每一組數(shù)據(jù)是用戶定義的時間單位內(nèi)產(chǎn)生的數(shù)據(jù)，如一天或者一周。CanTree-GTree算法[14]基于固定滑動窗口和Hadoop框架挖掘數(shù)據(jù)流中的全集頻繁模式。當(dāng)一個窗口裝滿事務(wù)時，歷史事務(wù)將被移出，新近事務(wù)會被加入。FTK算法[32]使用滑動窗口模型挖掘top-k頻繁模式。該算法給出了滑動窗口大小的上限，可以處理上限范圍內(nèi)任意大小窗口中的事務(wù)從而得到頻繁模式。該算法使用的內(nèi)存空間大小與窗口大小成對數(shù)關(guān)系。算法設(shè)定滑動窗口大小范圍從3600～360000個事務(wù)，用來驗證算法的優(yōu)勢。雖然是任意大小，但在每次實驗中，窗口大小是固定的。WOB點陣算法[25]使用滑動窗口模型挖掘數(shù)據(jù)流中的權(quán)重MFPs。通過窗口的滑動刪除歷史事務(wù)信息增加新近事務(wù)信息，這樣可以避免重建整個樹結(jié)構(gòu)。SysTree算法[15]基于樹結(jié)構(gòu)且分別采用界標(biāo)窗口和滑動窗口來挖掘數(shù)據(jù)流中的頻繁模式。該文中解釋道大窗口會產(chǎn)生大量的模式，小窗口會產(chǎn)生少的模式;因此，不能說明哪個窗口大小更好，這取決于不同的用戶需求。

可變滑動窗口大小的改變有多種策略。在時間衰減模型中按照高查全率假設(shè)，通過對頻繁項集的衰減頻度估計來縮短或擴大窗口[40]。FIMoTS算法[42]使用基于時間戳的滑動窗口模型，接著轉(zhuǎn)化為基于事務(wù)的可變滑動窗口進行處理。窗口大小的改變受到模式的頻度變化影響。VSW算法[43]提出一種可變大小滑動窗口發(fā)現(xiàn)數(shù)據(jù)流中的頻繁模式。窗口大小由達到數(shù)據(jù)的概念改變數(shù)量動態(tài)決定。當(dāng)概念平穩(wěn)時，窗口擴展。而當(dāng)概念改變時，窗口收縮。CCFPM算法[44]使用可變滑動窗口發(fā)現(xiàn)數(shù)據(jù)流中的閉合頻繁模式。窗口的收縮和擴展受到概念改變的影響。

3.2 衰減方法

很多數(shù)據(jù)流頻繁模式挖掘算法為每個事務(wù)賦予相同的重要性或權(quán)重。然而，一些時間敏感的數(shù)據(jù)流應(yīng)用認為最新產(chǎn)生的事務(wù)比歷史事物更重要。時間衰減模型是處理時間敏感數(shù)據(jù)流頻繁模式挖掘的一種有效方法，它是一種隨著時間的推移而逐步衰減歷史模式支持數(shù)權(quán)重的方法，它強調(diào)新近事務(wù)產(chǎn)生模式的重要性。衰減方法的核心是衰減因子的設(shè)置，通常有三類設(shè)置方式：隨機值、固定值、計算值。隨機值設(shè)置衰減因子的方法的不足在于隨機性使得得到的模式結(jié)果集合不穩(wěn)定;固定值設(shè)置方法的優(yōu)劣取決于專家知識;計算值會根據(jù)算法中設(shè)計的其他參數(shù)值，如窗口大小、最小支持度等進行計算，從實驗驗證這種方式更合理。常見的幾種設(shè)置衰減因子與衰減函數(shù)的方法如表7所示。

如MSW（Mining Sliding Window）算法[6]是使用固定滑動窗口模型和時間衰減模型挖掘數(shù)據(jù)流中的全集頻繁模式的經(jīng)典算法之一。該算法使用一種滑動窗口樹SW-tree存儲最新的模式信息，并周期性地對樹結(jié)構(gòu)剪枝，去除歷史頻繁模式和不頻繁的模式。該算法使用時間衰減模型逐步降低歷史事務(wù)模式支持數(shù)的權(quán)重，并由此來區(qū)分最近產(chǎn)生事務(wù)與歷史事務(wù)的模式。算法SWP-Tree[40]使用可變滑動窗口發(fā)現(xiàn)數(shù)據(jù)流中的頻繁模式。為了強調(diào)最新頻繁模式，使用時間衰減模型來區(qū)分新舊事務(wù)產(chǎn)生的模式;設(shè)計一種增量更新的樹結(jié)構(gòu)記錄模式信息，從而提高事務(wù)的處理速度。DFPMiner算法[45]挖掘數(shù)據(jù)流中的全局頻繁模式，它動態(tài)構(gòu)建全局模式樹， 利用時間指數(shù)衰減函數(shù)對模式樹中各模式的支持數(shù)進行統(tǒng)計， 以此發(fā)現(xiàn)界標(biāo)窗口內(nèi)的模式。PFP-growth算法[46]用于挖掘事務(wù)不確定數(shù)據(jù)流中的頻繁模式，它使用概率衰減窗口模型，通過計算各概率數(shù)據(jù)項的期望支持度以發(fā)現(xiàn)模式。IncSpam算法[47]使用固定衰減因子值的時間衰減模型發(fā)現(xiàn)可擴展滑動窗口模型中的頻繁項集。它使用可擴展排序樹存儲所有當(dāng)前滑動窗口內(nèi)的模式，可以減少時間和內(nèi)存消耗。λ-Hcount算法[48]采用時間衰減模型計算數(shù)據(jù)流中的頻度，其中設(shè)定衰減因子為0.98～1之間的常量值。采用哈希函數(shù)估計數(shù)據(jù)流中項的密度值，從而發(fā)現(xiàn)頻繁模式。TDMCS算法[49]采用衰減模型挖掘數(shù)據(jù)流中的閉合頻繁模式。提出一種均值衰減因子方法，可以得到穩(wěn)定的和查全率和查準(zhǔn)率更均衡的模式結(jié)果集合。TwMinSwap算法[31]使用衰減方法挖掘數(shù)據(jù)流中的top-k頻繁模式。該算法采用衰減評估模式的頻度，核心思想是隨著時間的推進歷史模式頻度會逐漸衰減。衰減因子的取值是范圍是（0， 1）。

4 其他模式技術(shù)

數(shù)據(jù)流中挖掘出的模式除了頻繁模式以外，還包含：序列模式（Sequential Patterns， SPs）[50-51]，用于發(fā)現(xiàn)具有先后次序的復(fù)雜項集;高效用模式（High Utility Patterns， HUPs）[52-53]，用于發(fā)現(xiàn)具有高價值或效用的項集;圖模式（SubGraphs Patterns， SGPs）[54-55]，用于發(fā)現(xiàn)滿足用戶閾值的子圖結(jié)構(gòu);片斷（EPisode， EP）[27]，用于發(fā)現(xiàn)連續(xù)的事件（event）;非頻繁模式（INFrequent Patterns， INFPs）[37]，用于發(fā)現(xiàn)出現(xiàn)頻度低的項集;概率頻繁模式（Probabilistic Frequent Patterns， PFPs）[16]，用于發(fā)現(xiàn)不確定數(shù)據(jù)流中滿足最小支持度和最小概率參數(shù)的頻繁項集;以及其他類型的模式等[56]。這些模式的相同之處是它們都是頻繁的，不同之處可以從項/項集是否有序、權(quán)重是否相等和是否連續(xù)三個方面區(qū)分，具體如表8所示。針對不同的數(shù)據(jù)特征可以挖掘出不同類型的模式，不同的模式具有不同的應(yīng)用。本章主要介紹序列模式和高效用模式。

4.1 序列模式

序列模式（Sequential Patterns， SPs）挖掘用于發(fā)現(xiàn)序列數(shù)據(jù)集合中出現(xiàn)次數(shù)不低于用戶定義閾值的項集序列，這些頻繁的項集序列稱為序列模式。最早的序列模式挖掘算法是prefixSpan[57]，這是基于投影數(shù)據(jù)庫和前綴樹結(jié)構(gòu)的靜態(tài)數(shù)據(jù)集合處理方法。它可以挖掘出全集序列模式，并且可以減少候選項集數(shù)量。

數(shù)據(jù)流中序列模式挖掘算法采用的主要數(shù)據(jù)結(jié)構(gòu)之一是樹結(jié)構(gòu)。如StrPMiner算法[58]挖掘多數(shù)據(jù)流中最優(yōu)的SPs。該算法僅對多數(shù)據(jù)流掃描一次，壓縮數(shù)據(jù)信息并使用PBuilder方法進行處理。StrPMiner算法使用T0樹結(jié)構(gòu)保存候選項集。BFSPMiner算法[59]采用滑動窗口挖掘數(shù)據(jù)流中的SPs。該算法使用倒置T0樹結(jié)構(gòu)存儲模式信息。該算法得到的模式結(jié)果集合更加準(zhǔn)確，且可以降低運行時間。算法MAHUSP[60]挖掘數(shù)據(jù)流中的高效用SPs。該算法使用一個稱為MAS-tree的樹結(jié)構(gòu)存儲可能的模式信息。當(dāng)發(fā)現(xiàn)一個可能的模式時則更新MAS-tree。算法同時設(shè)計兩個機制來更好地利用有效的存儲空間。

4.2 高效用模式

高效用模式（High Utility Patterns， HUPs）挖掘用于發(fā)現(xiàn)事務(wù)數(shù)據(jù)集合中效用不低于用戶定義閾值的項或項集。在真實應(yīng)用中，效用可以指單位利潤或者購買數(shù)量等。高效用模式挖掘方法通常可以分為一階段和二階段兩類。

較早的HUPs挖掘算法是二階段的。算法TWU[61]提出二階段方法挖掘數(shù)據(jù)集合中的高效用模式。該算法使用過估計概念，以滿足高效用模式挖掘中的抗單調(diào)性。二階段方法的主要問題之一是需要多次掃描數(shù)據(jù)集合產(chǎn)生大量候選集。數(shù)據(jù)流中挖掘HUPs的方法主要是一階段的。如算法SHU-Growth[62]使用滑動窗口技術(shù)挖掘HUPs。為了產(chǎn)生更少的候選集合降低空間消耗，該算法使用基于樹的結(jié)構(gòu)存儲HUPs。LIHUP算法[63]使用基于list的數(shù)據(jù)結(jié)構(gòu)挖掘HUPs?；趌ist的數(shù)據(jù)機構(gòu)的重建依賴于一種最優(yōu)排序策略，并且在重建的同時可以有效地更新效用信息。該算法也不產(chǎn)生候選集合，可以有效提高算法效率。Vert_top_k_DS[64]算法使用滑動窗口模型挖掘數(shù)據(jù)流中的top-k HUPs。該算法只有一層結(jié)構(gòu)，且不產(chǎn)生任何候選集合。算法中定義新的數(shù)據(jù)結(jié)構(gòu)iList用于存儲項的信息，且這個結(jié)構(gòu)在合并和刪除項時工作效率很高。HAUPM算法[65]使用衰減窗口挖掘平均HUPs。該算法使用衰減窗口關(guān)注新近事務(wù)中的HUPs，使用時間因子發(fā)現(xiàn)顯著的新近的模式信息。該算法使用新的衰減平均效用樹（DAT）結(jié)構(gòu)和事務(wù)效用list（TUL）來提高挖掘效率。HUDD-TDS算法[66]挖掘事務(wù)數(shù)據(jù)流中的HUPs，并且檢測模式效用分布的變化。該算法關(guān)注局部和全局的效用改變。其中局部效用改變是指一個模式的效用分布變化，而全部效用改變是指所有高效用模式的效用分布變化。關(guān)注這兩種變化可以提高模式挖掘的效率。Choi等[66]提出算法挖掘Twitter數(shù)據(jù)流中HUPs，用于檢測新興話題。該方法使用滑動窗口技術(shù)計算每批推特中單詞的效用，確定每批數(shù)據(jù)中的最小效用。該方法使用TP樹結(jié)構(gòu)從候選主題模式中提取實際主題模式。相比已有算法，該算法可以提高查全率。

4.3 其他模式

數(shù)據(jù)流中非頻繁模式挖掘用于提取數(shù)據(jù)集中的稀有或者異常模式，是一種新的數(shù)據(jù)流異常檢測方法[67]。Hemalatha等[68]提出一種基于最小非頻繁模式的數(shù)據(jù)流孤立點檢測方法MIP-DS。該算法挖掘數(shù)據(jù)流中的最小非頻繁模式。它首先挖掘滑動窗口內(nèi)的最新模式，再生成所有的候選后篩選非頻繁模式。通過實驗驗證，該方法可以提高孤立點檢測的效率。Duong等[69]提出算法挖掘信號數(shù)據(jù)流（不確定數(shù)據(jù)流）中的非頻繁權(quán)重模式。這些模式滿足基于距離的約束條件，用于分析兩類信號數(shù)據(jù)：一是在相同環(huán)境下彼此相似的連續(xù)信號;二是在不同環(huán)境下或不同條件下的距離信號。該算法的優(yōu)勢在于在知識提取過程中使用約束，從而挖掘出更壓縮的模式集合。

不確定數(shù)據(jù)流中發(fā)現(xiàn)的頻繁模式通常是概率頻繁模式，這些模式需要滿足最小支持度和最小概率參數(shù)。Cuzzocrea等[67]分析挖掘不確定數(shù)據(jù)集合中頻繁模式的一些算法。這些算法通常使用UF樹結(jié)構(gòu)來存儲模式，使用概率支持度的上界值來降低計算量。Li等[16]提出算法PFIMoS使用滑動窗口模型挖掘不確定數(shù)據(jù)流中的概率頻繁模式。該算法設(shè)計了一種壓縮的數(shù)據(jù)結(jié)構(gòu)概率頻繁項集樹PFIT，并采用自底向上的方式來存儲數(shù)據(jù)信息，從而有效地減低搜索空間。PFIMoS使用概率支持度估計方法來計算概率支持度的上下界值，這樣可以降低計算時間。

5 進一步的研究方向

數(shù)據(jù)流挖掘中概念漂移問題的解決方法在過去十多年中得到了一定的發(fā)展，但是現(xiàn)有的方法仍然存在著不足之處，這為研究者提供了進一步的研究方向。

1） 大規(guī)模數(shù)據(jù)流中模式挖掘結(jié)果集數(shù)量巨大，其中存在大量無用的模式。當(dāng)事務(wù)長或最小支持度閾值低時，這個問題尤其嚴重。如何挖掘更加滿足用戶需求的有趣模式，且模式的數(shù)量盡可能地壓縮;在模式挖掘過程中如何解決概念漂移帶來的頻繁與非頻繁項的轉(zhuǎn)變所帶來的丟失可能模式的現(xiàn)象等問題需要進一步研究。

2） 在某些應(yīng)用中概念漂移是可以預(yù)期的，它沿時間軸或在不同對象中的模型化區(qū)域可能重新出現(xiàn)。例如糧食需求預(yù)測，可以用模糊周期性季節(jié)的影響為對象設(shè)定特定子群，或者傳遞不同的上下文之間的學(xué)習(xí)似乎是一個潛在的研究可預(yù)測概念漂移的路線。但是在很多的應(yīng)用中，概念漂移的工作是在隱藏背景下發(fā)生，是不可觀測到的。如何更好地分析這類概念漂移現(xiàn)象還需要進一步研究。

3） 基于模式的分類方法研究。數(shù)據(jù)流中包含無限的數(shù)據(jù)，這些數(shù)據(jù)包含大量的冗余信息甚至是噪聲，而模式發(fā)現(xiàn)可以去除數(shù)據(jù)中的冗余信息且不受噪聲的影響。因此，挖掘有趣的、頻繁的和有區(qū)分力的模式，可以用于有效的分類或聚類?；谀Ｊ降姆诸惢蚓垲惥哂懈叩臏?zhǔn)確性，并且可以很好地解決缺失值的問題。可以進一步對基于模式的數(shù)據(jù)分類方法進行研究。

4） 由于云的出現(xiàn)，研究者提出了使用邊緣計算和云計算來實現(xiàn)數(shù)據(jù)流處理，這是大數(shù)據(jù)發(fā)展帶來的新計算方法[70-71]。如何更好地利用云技術(shù)來提高大數(shù)據(jù)挖掘效率也是需要繼續(xù)研究的內(nèi)容。

參考文獻 （References）

[1] BIFET A. Adaptive stream mining： pattern learning and mining from evolving data stream [C]// Proceedings of the 2010 Conference on Adaptive Stream Mining： Pattern Learning and Mining from Evolving Data Streams. Amsterdam， Netherlands： IOS Press， 2010： 1-212.

[2] MANKU G S， MOTWANI R. Approximate frequency counts over data streams [C]// Proceedings of the 28th International Conference on Very Large DataBases. San Francisco， CA： Morgan Kaufmann， 2002： 346-375.

MANKU G S， MOTWANI R. Approximate frequency counts over data streams [J]. Proceedings of the VLDB Endowment， 2012， 5（12）： 1699.

[3] CHARIKAR M， CHEN K， FARACH-COLTON M. Finding frequent items in data streams [C]// Proceedings of the 2002 International Colloquium on Automata， Languages and Programming， LNCS 2380. 2002： 693-703.

[4] YANG T， ZHOU Y， JIN H， et al. Pyramid sketch： a sketch framework for frequency estimation of data streams [J]. Proceedings of the VLDB Endowment， 2017， 10（11）： 1442-1453.

[5] LI H-F， SHAN M-K， LEE S-Y. DSM-FI： an efficient algorithm for mining frequent itemsets in data streams [J]. Knowledge Information Systems， 2008， 17（1）： 79-97.

[6] 李國徽，陳輝.挖掘數(shù)據(jù)流任意滑動時間窗口內(nèi)頻繁模式[J].軟件學(xué)報，2008，19（19）：2585-2596.（LI G H， CHEN H. Mining the frequent patterns in an arbitrary sliding window over online data streams [J]. Journal of Software， 2008， 19（10）： 2585-2596.）

[7] MEMAR M， SADREDDINI M H， DEYPIR M， et al. A block-based approach for frequent itemset mining over data streams [C]// Proceedings of the 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE， 2011： 1647-1651.

[8] LI H-F， LEE S-Y. Mining frequent itemsets over data streams using efficient window sliding techniques [J]. Expert Systems with Applications， 2009， 36（2）： 1466-1477.

[9] FAN G， YIN S. A frequent itemset mining algorithm based on matrix in sliding window over data steam [C]// ISDEA '13： Proceedings of the 2013 3rd International Conference on Intelligent System Design and Engineering Applications. Washington， DC： IEEE Computer Society， 2013： 66-69.

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

[11] SHIN S J， LEE D S， LEE W S. CP-tree： an adaptive synopsis structure for compressing frequent itemsets over online data streams [J]. Information Sciences， 2014， 278： 559-576.

[12] SILVA A， ANTUNES C. Pushing constraints into data streams [C]// BigMine '13： Proceedings of the 2nd International Workshop on Big Data， Streams and Heterogeneous Source Mining： Algorithms， Systems， Programming Models and Applications. New York： ACM， 2013： 79-86.

[13] FARHAT A， GOUIDER M S， SAID L B. New algorithm for frequent itemsets mining from evidential data streams [J]. Procedia Computer Science， 2016， 96： 645-653.

[14] KUSUMAKUMARI V， SHERIGAR D， CHANDRAN R， et al. Frequent pattern mining on stream data using Hadoop CanTreeGTree [J]. Procedia Computer Science， 2017， 115： 266-273.

[15] BUSTIO-MARTNEZ L， CUMPLIDO R， HERNNDEZ-LEN R， et al. On the design of hardware-software architectures for frequent itemsets mining on data streams [J]. Journal of Intelligent Information Systems， 2018， 50（3）： 415-440.

[16] LI H， ZHANG N， ZHU J， et al. Probabilistic frequent itemset mining over uncertain data streams [J]. Expert Systems with Applications， 2018， 112： 274-287.

[17] CHI Y， WANG H， YU P S， et al. Catch the moment： maintaining closed frequent itemsets over a data stream sliding window [J]. Knowledge and Information Systems， 2006， 10（3）： 265-294.

[18] YEN S-J， WU C-W， LEE Y-S， et al. A fast algorithm for mining frequent closed itemsets over stream sliding window [C]// Proceedings of the 2011 IEEE International Conference on Fuzzy Systems. Piscataway， NJ： IEEE， 2011： 996-1002.

[19] NORI F， DEYPIR M， SADREDDINI M H. A sliding window based algorithm for frequent closed itemset mining over data streams [J]. Journal of Systems and Software， 2013， 86（3）： 615-623.

[20] DAI C， CHEN L. An algorithm for mining frequent closed itemsets in data stream [J]. Physics Procedia， 2012， 24（C）： 1722-1728.

[21] HAN M， DING J， Li J. TDMCS： an efficient method for mining closed frequent patterns over data streams based on time decay model [J]. International Arab Journal of Information Technology， 2017， 14（6）： 851-860.

[22] REDDY V S， RAO T V， GOVARDHAN A. Fast and Lossless Mining of Closed Frequent Itemsets （FLMCFI） over data streams [J]. Journal of Advanced Research in Dynamical and Control Systrems， 2018， 10： 256-263.

[23] LEE G， YUN U， RYU K H. Sliding window based weighted maximal frequent pattern mining over data streams [J]. Expert Systems with Applications， 2014， 41（2）： 694-708.

[24] KARIM M R， COCHEZ M， BEYAN O D， et al. Mining maximal frequent patterns in transactional databases and dynamic data streams： a Spark-based approach [J]. Information Sciences， 2018， 432： 278-300.

[25] CHANG Y I， LI C E， CHOU T J， et al. A weight-order-based lattice algorithm for mining maximal weighted frequent patterns over a data stream sliding window [C]// Proceedings of the 2018 IEEE International Conference on Applied System Innovation. Piscataway， NJ： IEEE， 2018： 961-964.

[26] HOMEM N， CARVALHO J P. Finding top-k elements in data streams [J]. Information Sciences， 2010， 180（24）： 4958-4974.

[27] AMPHAWAN K， SOULAS J， LENCA P. Mining top-k regular episodes from sensor streams [C]// Proceedings of the 7th International Conference on Advances in Information Technology， 2015： 76-85.

AMPHAWAN K， SOULAS J， LENCA P. Mining top-k regular episodes from sensor streams [J]. Procedia Computer Science， 2015， 69： 76-85.

[28] LI J， GONG S. Top-k-FCI： mining top-k frequent closed itemsets in data streams [J]. Journal of Computational Information Systems， 2011， 7（13）： 4819-4826.

[29] TSAI P S M. Mining top-k frequent closed itemsets over data streams using the sliding window model [J]. Expert Systems with Applications， 2010， 37（10）： 6968-6973.

[30] AMPHAWAN K， LENCA P. Mining top-k frequent-regular closed patterns [J]. Expert Systems with Applications， 2015， 42（21）： 7882-7894.

[31] LIM Y， KANG U. Time-weighted counting for recently frequent pattern mining in data streams [J]. Knowledge and Information Systems， 2017，53（2）： 391-422.

[32] SONG C， LIU X， GE T. Top-k frequent items and item frequency tracking over sliding windows of any sizes [C]// Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2017： 199-202.

[33] LEUNG C K-S， HAO B， JIANG F. Constrained frequent itemset mining from uncertain data streams [C]// Proceedings of the 2010 IEEE 26th International Conference on Data Engineering Workshops. Washington， DC： IEEE Computer Society， 2010： 120-127.

[34] HU W-C， WANG B-N， CHENG Z-L. Mining frequent closed patterns with item constraints in data streams [C]// Proceedings of the 2008 International Conference on Machine Learning and Cybernetics. Piscataway， NJ： IEEE， 2008： 274-280.

[35] CUZZOCREA A， LEUNG C K S， MacKINNON R K. Mining constrained frequent itemsets from distributed uncertain data [J]. Future Generation Computer Systems， 2014， 37： 117-126.

[36] KIRAN R U， KITSUREGAWA M， REDDY P K. Efficient discovery of periodic-frequent patterns in very large databases [J]. Journal of Systems and Software， 2016， 112： 110-121.

[37] CAGLIERO L， CERQUITELLI T， CHIUSANO S， et al. Characterizing unpredictable patterns in wireless sensor network data [J]. Information Sciences， 2018，467： 149-162.

[38] LI C-W， JEA K-F. An adaptive approximation method to discover frequent itemsets over sliding-window-based data streams [J]. Expert Systems with Applications， 2011， 38（10）： 13386-13404.

[39] DEYPIR M， SADREDDINI M H. EclatDS： an efficient sliding window based frequent pattern mining method for data streams [J]. Intelligent Data Analysis， 2011， 15（4）： 571-587.

[40] CHEN H， SHU L， XIA J， et al. Mining frequent patterns in a varying-size sliding window of online transactional data streams [J]. Information Sciences， 2012， 215： 15-36.

[41] LI C-W， JEA K-F. An approach of support approximation to discover frequent patterns from concept-drifting data streams based on concept learning [J]. Knowledge and Information Systems， 2014， 40（3）： 639-671.

[42] 李海峰，章寧，朱建明，等.時間敏感數(shù)據(jù)流上的頻繁項集挖掘算法[J].計算機學(xué)報，2012，35（11）：2283-2293.（LI H F， ZHANG N， ZHU J M， et al. Frequent itemset mining over time sensitive streams[J]. Chinese Journal of Computers， 2012， 35（11）： 2283-2293.）

[43] DEYPIR M， SADREDDINI M H， HASHEMI S. Towards a variable size sliding window model for frequent itemset mining over data streams [J]. Computers and Industrial Engineering， 2012， 63（1）： 161-172.

[44] 韓萌，王志海，丁劍.一種頻繁模式?jīng)Q策樹處理可變數(shù)據(jù)流[J].計算機學(xué)報，2016，39（8）：1541-1554.（HAN M， WANG Z H， DING J. Efficient decision tree for evolving data streams based on frequent patterns [J]. Chinese Journal of Computers， 2016， 39（8）： 1541-1554.）

[45] 吳楓，仲妍，吳泉源.基于時間衰減模型的數(shù)據(jù)流頻繁模式挖掘[J].自動化學(xué)報，2010，36（5）：674-684.（WU F， ZHONG Y， WU Q Y. Ming frequent patterns over data stream under the time decaying model [J]. Acta Automatica Sinica， 2010， 36（5）： 674-684.）

[46] 廖國瓊，吳凌琴，萬常選.基于概率衰減窗口模型的不確定數(shù)據(jù)流頻繁模式挖掘[J].計算機研究與發(fā)展，2012，49（5）：1105-1115.（LIAO G Q， WU L Q， WANG C X. Frequent patterns mining over uncertain data streams based on probability decay window model [J]. Journal of Computer Research and Development， 2012， 49（5）： 1105-1115.）

[47] LI H， HO C， et al. A single-scan algorithm for mining sequential patterns from data streams [J]. International Journal of Innovative Computing， 2012， 8（3）： 1799-1820.

[48] CHEN L， MEI Q. Mining frequent items in data stream using time fading model [J]. Information Sciences， 2014， 257： 54-69.

[49] 韓萌，王志海，原繼東.一種基于時間衰減模型的數(shù)據(jù)流閉合模式挖掘方法[J].計算機學(xué)報，2015，38（7）：1473-1482.（HAN M， WANG Z H， YUAN J D. Efficient method for mining closed frequent patterns from data streams based on time decay model [J]. Chinese Journal of Computers， 2015， 38（7）： 1473-1482.）

[50] CHEN J， CHEN P. Sequential pattern mining for uncertain data streams using sequential sketch [J]. Journal of Networks， 2014， 9（2）： 252-258.

[51] CHENG X， SU S， XU S， et al. Differentially private maximal frequent sequence mining [J]. Computers and Security， 2015， 55（C）： 175-192.

[52] AHMED C F， TANBEER S K， JEONG B-S， et al. Single-pass incremental and interactive mining for weighted frequent patterns [J]. Expert Systems with Applications， 2012， 39（9）： 7976-7994.

[53] AHMED C F， TANBEER S K， JEONG B-S， et al. Interactive mining of high utility patterns over data streams [J]. Expert Systems with Applications， 2012， 39（15）： 11979-11991.

[54] BRAUN P， CAMERON J J， CUZZOCREA A， et al. Effectively and efficiently mining frequent patterns from dense graph streams on disk [J]. Procedia Computer Science， 2014， 35： 338-347.

[55] CUZZOCREA A， HAN Z， JIANG F， et al. Edge-based mining of frequent subgraphs from graph streams [J]. Procedia Computer Science， 2015， 60： 573-582.

[56] FOURNIER-VIGER P， LIN J C W， KIRAN R U， et al. A survey of sequential pattern mining [J]. Data Science and Pattern Recognition， 2017，1（1）： 54-77.

[57] PEI J， HAN J， MORTAZAVI-ASL B， et al. Mining sequential patterns by pattern-growth： the PrefixSpan approach [J]. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（11）： 1424-1440.

[58] TWS D， HASSANI M， BEECKS C， et al. Optimizing sequential pattern mining within multiple streams [C]// Proceedings of the Workshops of the Conference on Database Systems for Business， Technology and Web （BTW 2015）， 2015： 223-232.

TWS D， HASSANI M， BEECKS C， et al. Optimizing sequential pattern mining within multiple streams [EB/OL]. [2018-07-07]. http：//cs.emis.de/LNI/Proceedings/Proceedings242/223.pdf.

[59] HASSANI M， TWS D， SEIDL T. Understanding the bigger picture： batch-free exploration of streaming sequential patterns with accurate prediction [C]// Proceedings of the 32nd Annual ACM Symposium on Applied Computing. New York： ACM， 2017： 866-869.

[60] ZIHAYAT M， CHEN Y， AN A. Memory-adaptive high utility sequential pattern mining over data streams [J]. Machine Learning， 2017， 106（6）： 799-836.

[61] LIU Y， LIAO W， CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets [C]// Proceedings of the 2005 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 3518. Berlin： Springer， 2005： 689-695.

[62] YUN U， KIM D， RYANG H， et al. Mining recent high average utility patterns based on sliding window from stream data [J]. Journal of Intelligent and Fuzzy Systems， 2016， 30（6）： 3605-3617.

[63] YUN U， RYANG H， LEE G， et al. An efficient algorithm for mining high utility patterns from incremental databases with one database scan [J]. Knowledge-Based Systems， 2017， 124： 188-206.

[64] DAWAR S， SHARMA V， GOYAL V. Mining top-k high-utility itemsets from a data stream under sliding window model [J]. Applied Intelligence， 2017， 47（4）： 1240-1255.

[65] YUN U， KIM D， YOON E， et al. Damped window based high average utility pattern mining over data streams [J]. Knowledge-Based Systems， 2018，144： 188-205.

[66] CHOI H-J， PARK C H. Emerging topic detection in twitter stream based on high utility pattern mining [J]. Expert Systems with Applications， 2019， 115： 27-36.

[67] CUZZOCREA A， LEUNG C K. Computing theoretically-sound upper bounds to expected support for frequent pattern mining problems over uncertain big data [C]// Proceedings of the 2016 International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems， CCIS 611. Berlin： Springer， 2016： 379-392.

[68] HEMALATHA C S， VAIDEHI V， LAKSHMI R. Minimal infrequent pattern based approach for mining outliers in data streams [J]. Expert Systems with Applications， 2015， 42（4）： 1998-2012.

[69] DUONG Q-H， RAMAMPIARO H， NRVG K， et al. High utility drift detection in quantitative data streams [J]. Knowledge-Based Systems， 2018， 157： 34-51.

[70] de ASSUNO M D， da SILVA VEITH A， BUYYA R. Distributed data stream processing and edge computing： a survey on resource elasticity and future directions [J]. Journal of Network and Computer Applications， 2018， 103： 1-17.

[71] ur REHMAN M H， LIEW C S， WAH T Y， et al. Towards next-generation heterogeneous mobile data stream mining applications： opportunities， challenges， future research directions [J]. Journal of Network and Computer Applications， 2017， 79： 1-24.