韓萌 丁劍

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

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

中圖分類號(hào)： TP18

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

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

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

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

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

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

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

1 基本概念

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

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

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

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

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

1）約束Constraint1：對(duì)任意一個(gè)頻繁項(xiàng)集P，如果其包含項(xiàng){a}，則稱其滿足約束Constraint1。即Constraint1（P）≡（{a}P）。

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

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

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

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

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

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

2.1 全集頻繁模式

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

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

2.2 閉合頻繁模式

閉合頻繁模式（Closed Frequent Patterns， CFPs）是強(qiáng)大的頻繁模式的表現(xiàn)方式，因?yàn)樗鼈兿哂嘈畔ⅰＲ话銇?lái)說(shuō)，閉合頻繁模式比全集頻繁模式中的模式數(shù)量少得多，且閉合模式包含了全集頻繁模式中的全部信息，是一種無(wú)損壓縮模式。

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

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

2.3 最大頻繁模式

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

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

2.4 top-k頻繁模式

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

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

2.5 約束頻繁模式

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

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

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

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

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

3.1 窗口方法

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

數(shù)據(jù)流挖掘最常用的窗口模型是滑動(dòng)窗口模型（Slidng Window Model， SWM）?；瑒?dòng)窗口模型包括固定SWM與可變SWM。在任意時(shí)刻，前者中窗口內(nèi)最新事務(wù)的個(gè)數(shù)是固定的;而后者的最新事務(wù)個(gè)數(shù)是可變的。算法設(shè)計(jì)對(duì)窗口內(nèi)的最新事務(wù)進(jìn)行處理。

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

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

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

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

3.2 衰減方法

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

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

4 其他模式技術(shù)

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

4.1 序列模式

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

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

4.2 高效用模式

高效用模式（High Utility Patterns， HUPs）挖掘用于發(fā)現(xiàn)事務(wù)數(shù)據(jù)集合中效用不低于用戶定義閾值的項(xiàng)或項(xiàng)集。在真實(shí)應(yīng)用中，效用可以指單位利潤(rùn)或者購(gòu)買(mǎi)數(shù)量等。高效用模式挖掘方法通?？梢苑譃橐浑A段和二階段兩類。

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

4.3 其他模式

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

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

5 進(jìn)一步的研究方向

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

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

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

3） 基于模式的分類方法研究。數(shù)據(jù)流中包含無(wú)限的數(shù)據(jù)，這些數(shù)據(jù)包含大量的冗余信息甚至是噪聲，而模式發(fā)現(xiàn)可以去除數(shù)據(jù)中的冗余信息且不受噪聲的影響。因此，挖掘有趣的、頻繁的和有區(qū)分力的模式，可以用于有效的分類或聚類。基于模式的分類或聚類具有更高的準(zhǔn)確性，并且可以很好地解決缺失值的問(wèn)題。可以進(jìn)一步對(duì)基于模式的數(shù)據(jù)分類方法進(jìn)行研究。

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

參考文獻(xiàn) （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] 李國(guó)徽，陳輝.挖掘數(shù)據(jù)流任意滑動(dòng)時(shí)間窗口內(nèi)頻繁模式[J].軟件學(xué)報(bào)，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í)間敏感數(shù)據(jù)流上的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)學(xué)報(bào)，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ù)處理可變數(shù)據(jù)流[J].計(jì)算機(jī)學(xué)報(bào)，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í)間衰減模型的數(shù)據(jù)流頻繁模式挖掘[J].自動(dòng)化學(xué)報(bào)，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] 廖國(guó)瓊，吳凌琴，萬(wàn)常選.基于概率衰減窗口模型的不確定數(shù)據(jù)流頻繁模式挖掘[J].計(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í)間衰減模型的數(shù)據(jù)流閉合模式挖掘方法[J].計(jì)算機(jī)學(xué)報(bào)，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.