基于AO算法的數(shù)據(jù)流頻繁項(xiàng)集挖掘*

文 凱,耿小海，朱璐偉，許萌萌

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065；3.重慶信科設(shè)計(jì)有限公司，重慶 401121)

1 引言

互聯(lián)網(wǎng)的快速發(fā)展和5G的到來，使得數(shù)據(jù)發(fā)生了爆炸性的增長，而現(xiàn)在絕大多數(shù)的數(shù)據(jù)都是以流的形式出現(xiàn)，數(shù)據(jù)流[1]的應(yīng)用已經(jīng)涉及到各方各面，隨著時(shí)代不斷進(jìn)步，人工智能、模式識(shí)別中的搜索算法和建模技術(shù)也在數(shù)據(jù)流挖掘中得到了廣泛應(yīng)用，并且吸納了多個(gè)領(lǐng)域中的優(yōu)秀知識(shí)和思想[2]。大數(shù)據(jù)從批處理，再到現(xiàn)在的實(shí)時(shí)處理，以及混合兩者的處理，經(jīng)過了3次技術(shù)革新[3]。數(shù)據(jù)流頻繁項(xiàng)集挖掘已成為當(dāng)前數(shù)據(jù)挖掘中的一項(xiàng)重要任務(wù)，并隨著大數(shù)據(jù)實(shí)時(shí)分析的發(fā)展變得越來越重要。

相較于國內(nèi)，國外在數(shù)據(jù)流頻繁項(xiàng)集挖掘方面的研究開始得比較早。在數(shù)據(jù)流處理模型中主要有3種不同的窗口模型[4]：界標(biāo)窗口、衰減窗口和滑動(dòng)窗口，目前使用最多的是滑動(dòng)窗口模型?；瑒?dòng)窗口模型由Mozafari等[5]引入，并且提出了SWIM(Sliding Window Incremetal Miner)算法，它能夠根據(jù)數(shù)據(jù)流調(diào)節(jié)滑動(dòng)窗口的大小，因此算法具有良好的自適應(yīng)性和擴(kuò)展性。基于 Hadoop平臺(tái)的并行化框架和固定的滑動(dòng)窗口，CanTree-GTree算法[6]進(jìn)行數(shù)據(jù)流頻繁項(xiàng)集挖掘在滑動(dòng)窗口滿事務(wù)后，新的數(shù)據(jù)流流入，舊事務(wù)流出；文獻(xiàn)[7]中的SysTree(Systolic Tree)算法采用2種窗口進(jìn)行數(shù)據(jù)流頻繁項(xiàng)集挖掘，該算法基于樹結(jié)構(gòu)，在挖掘頻繁項(xiàng)集時(shí)分別使用了滑動(dòng)窗口和界標(biāo)窗口；寇香霞等[8]提出的FIUT-Stream算法，用位圖壓縮數(shù)據(jù)流，提高了空間效率，但采用FIUT結(jié)構(gòu)挖掘頻繁項(xiàng)集時(shí)會(huì)產(chǎn)生大量候選項(xiàng)集，構(gòu)造FIU-tree也消耗大量?jī)?nèi)存。

針對(duì)高效用模式的挖掘，SHU-Growth算法[9]使用滑動(dòng)窗口進(jìn)行挖掘，該算法根據(jù)類FP-tree(Frequent Pattern-tree)結(jié)構(gòu)來存儲(chǔ)高效用項(xiàng)集，降低了候選項(xiàng)集的空間消耗；HAUPM(High Average Utility Pattern Mining)算法[10]只關(guān)注新近事務(wù)中的高效用模式，結(jié)合衰減窗口模型，挖掘平均高效用模式，并且采用新的衰減平均效用樹結(jié)構(gòu)來提高挖掘效率。

現(xiàn)在的應(yīng)用有許多不僅僅是單數(shù)據(jù)流，學(xué)者們也在研究多數(shù)據(jù)流挖掘算法，例如王鑫等[11]提出的MCMD-Stream(Mining Collaborative frequent itemsets in Multiple Data Stream)，采用多個(gè)數(shù)據(jù)流同時(shí)挖掘，效率顯著增加；Guo等[12]結(jié)合目前諸多的應(yīng)用提出的H-Stream(Hybrid-Stream)算法，也是對(duì)多數(shù)據(jù)流進(jìn)行挖掘。

針對(duì)現(xiàn)有數(shù)據(jù)流頻繁項(xiàng)集挖掘算法挖掘頻繁項(xiàng)集時(shí)間效率不高等問題，本文提出一種高效挖掘數(shù)據(jù)流頻繁項(xiàng)集的AO算法，提高了FIUT-Stream算法的挖掘效率。本文的AO算法在挖掘頻繁項(xiàng)集的過程中，采用超集檢測(cè)的策略，極大地過濾掉非頻繁項(xiàng)集。實(shí)驗(yàn)表明，改進(jìn)算法在時(shí)間效率的提升上比較明顯。

2 相關(guān)概念

定義1設(shè)項(xiàng)目集合I={I1,I2,I3,…,Im}，對(duì)于該項(xiàng)目集中的每一個(gè)元素，稱之為項(xiàng)，若一個(gè)集合中所有元素均包含于I中，則該集合稱為項(xiàng)集，包含k個(gè)元素的項(xiàng)集稱為k-項(xiàng)集。

定義2數(shù)據(jù)流DS(Data Stream)是由連續(xù)不斷到達(dá)的事務(wù)數(shù)據(jù)組成的有序序列DS={T1,T2,…}。其中Ti(i=1,2,3,…)稱為事務(wù)，數(shù)據(jù)流中的每個(gè)事務(wù)Ti滿足Ti?I。

定義3若minsup為用戶設(shè)定的最小支持度閾值，對(duì)于任意項(xiàng)集X，若項(xiàng)集X的出現(xiàn)頻率sup(X)≥minsup，則稱項(xiàng)集X為頻繁項(xiàng)集。

定義4將數(shù)據(jù)流按w大小等分成若干塊，每一塊對(duì)應(yīng)一個(gè)基本窗口，每一個(gè)基本窗口有相同的事務(wù)數(shù)，這些事務(wù)數(shù)個(gè)數(shù)|w|即為基本窗口的大小。

性質(zhì)1(超集檢測(cè)) 對(duì)于任意項(xiàng)集X和Y，且X?Y，若判定X為非頻繁項(xiàng)集，則Y也一定不會(huì)是頻繁項(xiàng)集。

3 頻繁項(xiàng)集挖掘

3.1 窗口更新

FIUT-Stream算法在數(shù)據(jù)流中挖掘頻繁項(xiàng)集時(shí)，采用的是滑動(dòng)窗口的方式。該算法首先將數(shù)據(jù)流壓縮到FIUT結(jié)構(gòu)的位表中，然后以滑動(dòng)窗口的方式對(duì)位表中的數(shù)據(jù)進(jìn)行更新，進(jìn)而對(duì)FIUT中的數(shù)據(jù)聚類得到所有的k-項(xiàng)集，然后以構(gòu)建FP-tree的方式構(gòu)建FIU-tree，根據(jù)FIU-tree來挖掘出所有的頻繁項(xiàng)集。

與其它數(shù)據(jù)流頻繁項(xiàng)集挖掘算法相比，F(xiàn)IUT-Stream算法采用一種位表進(jìn)行數(shù)據(jù)壓縮，極大地降低了內(nèi)存消耗，從而極大提高了空間效率；從FIUT-Stream算法的構(gòu)建可以看出，該算法需要2個(gè)結(jié)構(gòu)進(jìn)行數(shù)據(jù)流的存儲(chǔ)，一個(gè)是位表，一個(gè)是項(xiàng)表，這就導(dǎo)致在處理大量數(shù)據(jù)時(shí)，空間消耗極大，并且該算法采用類FP-tree算法進(jìn)行頻繁項(xiàng)集挖掘的過程中，會(huì)產(chǎn)生大量候選項(xiàng)集，必然對(duì)時(shí)間效率產(chǎn)生一定的影響，隨著數(shù)據(jù)的增多，這個(gè)影響就更明顯；而且該算法在更新數(shù)據(jù)流時(shí)，需要隨著數(shù)據(jù)流的到來同步更新支持度，這進(jìn)一步降低了時(shí)間效率。

本文提出的改進(jìn)算法在進(jìn)行數(shù)據(jù)壓縮時(shí)，只采用一個(gè)位表，在一定程度上提高了空間效率，在頻繁項(xiàng)集挖掘的時(shí)候，直接通過位表采用數(shù)學(xué)中的與運(yùn)算(And Operation)就可以得到所有的頻繁項(xiàng)集；另外，在支持度計(jì)算時(shí)，簡(jiǎn)單使用加減計(jì)算即可完成，減少了聚類操作，減少了在數(shù)據(jù)流頻繁項(xiàng)集挖掘時(shí)的FIU-tree結(jié)構(gòu)的構(gòu)建，極大提高了效率。具體思路如下：如表1所示為本文所用到的數(shù)據(jù)流，分裝在4個(gè)Pane中，每個(gè)Pane包含3個(gè)事務(wù)，即代表一個(gè)窗口。在FIUT-Stream算法中，新的數(shù)據(jù)到來，按表格箭頭所指方向進(jìn)行流動(dòng)，新簇流入，舊簇流出，以此更新數(shù)據(jù)。

Table 1 Dataset表1 數(shù)據(jù)集

表2是對(duì)數(shù)據(jù)集3個(gè)窗口的數(shù)據(jù)壓縮得到的位表，且在位表最后一行進(jìn)行項(xiàng)支持度的計(jì)算，該方法減少了項(xiàng)表的構(gòu)建，且支持度計(jì)算在位表最后一行完成，極大提高了效率。其中，Tid代表事務(wù)編號(hào)。

Table 2 Compressed bit table表2 壓縮位表

FIUT-Stream算法是以一種滑動(dòng)窗口的形式更新窗口，新簇流入，舊簇流出，數(shù)據(jù)更新需要所有的數(shù)據(jù)流動(dòng)，一定程度上降低了效率。本文采用一種取余[13]的方式進(jìn)行窗口更新，每次只需要對(duì)一個(gè)事務(wù)進(jìn)行流動(dòng)即可完成數(shù)據(jù)更新。具體方法是：當(dāng)窗口中數(shù)據(jù)已滿，對(duì)于新來的事務(wù)Ti，使用i%n(n為當(dāng)前窗口中的所有事務(wù)數(shù))取余將該事務(wù)插入到對(duì)應(yīng)的窗口位置實(shí)現(xiàn)數(shù)據(jù)更新，用這種方式進(jìn)行數(shù)據(jù)流更新只需要對(duì)特定事務(wù)進(jìn)行操作，而不需像FIUT-Stream算法那樣，對(duì)窗口中的所有數(shù)據(jù)進(jìn)行操作，復(fù)雜度從O(m)降到了O(1)，使得挖掘效率得到極大提高。如表3是用取余將BW4中的數(shù)據(jù)更新得到的更新表。

Table 3 Updated data stream compression bit table表3 更新的數(shù)據(jù)流壓縮位表

3.2 支持度更新

在FIUT-Stream算法中，支持度的更新是要對(duì)整個(gè)位表中的數(shù)據(jù)進(jìn)行更新，當(dāng)數(shù)據(jù)流到來，滑動(dòng)窗口滑動(dòng)之后，位表就發(fā)生了變化，在進(jìn)行支持度更新時(shí)需要對(duì)所有窗口中的數(shù)據(jù)進(jìn)行計(jì)算，而本文算法只需要在進(jìn)行窗口取余更新的時(shí)候計(jì)算當(dāng)前事務(wù)，然后計(jì)算支持度即可。如計(jì)算項(xiàng)a的支持度，當(dāng)窗口中新插入事務(wù)T10，根據(jù)取余更新的方式，用T10替換位表中的T1事務(wù)，此時(shí)將壓縮成位表的T10與T1相減，然后將相減的結(jié)果與count相加，即可得到數(shù)據(jù)更新后所有項(xiàng)的支持度，如表3是按此方法更新支持度得到的更新位表，這種方法相較于FIUT-Stream算法的支持度更新有了進(jìn)一步提升。

3.3 頻繁項(xiàng)集挖掘算法

當(dāng)數(shù)據(jù)流到來時(shí)，再經(jīng)過一次數(shù)據(jù)掃描壓縮之后得到表3，然后根據(jù)表3中的支持度計(jì)數(shù)count與最小支持度閾值minsup進(jìn)行比較即可得到所有的頻繁1-項(xiàng)集，然后根據(jù)刪除非頻繁1-項(xiàng)集后的壓縮位表，結(jié)合性質(zhì)1，挖掘所有的頻繁k-項(xiàng)集(k≥2)。設(shè)定最小支持度閾值minsup=4，根據(jù)表3中的支持度計(jì)數(shù)count，與最小支持度閾值minsup比較得到所有的頻繁1-項(xiàng)集為：a、b、d、f。刪除所有的非頻繁1-項(xiàng)集之后，得到表4。

Table 4 Frequent 1-itemset table表4 頻繁1-項(xiàng)集位表

挖掘出所有的頻繁1-項(xiàng)集之后，就可以根據(jù)頻繁1-項(xiàng)集進(jìn)行頻繁2-項(xiàng)集的挖掘。本文采用數(shù)學(xué)中的And Operation進(jìn)行頻繁k-項(xiàng)集的挖掘，如要挖掘出所有的頻繁2-項(xiàng)集，只需要對(duì)進(jìn)行挖掘的2-項(xiàng)集的項(xiàng)所在的列相與，相與結(jié)果中1的個(gè)數(shù)即為該2-項(xiàng)集的支持度計(jì)數(shù)，再和minsup進(jìn)行比較，不小于minsup即為頻繁項(xiàng)集，按照此方法即可挖掘出所有的頻繁2-項(xiàng)集。

根據(jù)表4，在對(duì)2-項(xiàng)集bd進(jìn)行頻繁項(xiàng)集判斷時(shí)，對(duì)這2項(xiàng)所在的列進(jìn)行相與，得到b、d在事務(wù)T1、T2、T3、T8中相與結(jié)果為1，所以得到2-項(xiàng)集bd的支持度為4，等于最小支持度計(jì)數(shù)，所以2-項(xiàng)集bd為一個(gè)頻繁2-項(xiàng)集；同時(shí)，b、d項(xiàng)在T1、T2、T3、T8事務(wù)中均存在，也就驗(yàn)證了該方法的正確性。同理得到2-項(xiàng)集df支持度為2，所以2-項(xiàng)集df為非頻繁項(xiàng)集。

在進(jìn)行頻繁k-項(xiàng)集挖掘時(shí)，本文首先會(huì)根據(jù)非頻繁(k-1)-項(xiàng)集進(jìn)行超集檢測(cè)，利用非頻繁項(xiàng)集的超集也是非頻繁項(xiàng)集來提高挖掘效率。在本文算法中，會(huì)記錄所有非頻繁(k-1)-項(xiàng)集，然后在k-項(xiàng)集挖掘的時(shí)候，判斷k-項(xiàng)集是否是非頻繁(k-1)-項(xiàng)集的超集，如果是，則不再對(duì)其進(jìn)行頻繁項(xiàng)集的判斷；如果不是，對(duì)其計(jì)算支持度，判斷其是否為頻繁項(xiàng)集。在本例中，根據(jù)上文得到df為非頻繁項(xiàng)集，所以記錄此項(xiàng)集，在進(jìn)行3-項(xiàng)集adf、bdf的挖掘時(shí)，首先通過超集檢測(cè)判定這2個(gè)項(xiàng)集均是項(xiàng)集df的超集，所以這2個(gè)項(xiàng)集不可能是頻繁項(xiàng)集，不再對(duì)其進(jìn)行下一步的判斷。根據(jù)表4，得到這2個(gè)項(xiàng)集支持度分別為：adf：1，bdf：2，均小于minsup，所以它們都不是頻繁項(xiàng)集，可以驗(yàn)證該性質(zhì)的正確性。該性質(zhì)在龐大數(shù)據(jù)流中挖掘頻繁項(xiàng)集時(shí)能極大地提高效率，減少需要挖掘的候選項(xiàng)集數(shù)據(jù)量。

算法1頻繁k-項(xiàng)集挖掘(k≥2)

輸入：頻繁1-項(xiàng)集壓縮位表D。

輸出：所有頻繁項(xiàng)集。

1.For所有i維組合

2. {

3.For所有非頻繁(i-1)-項(xiàng)集

4. {

5.If(i-項(xiàng)集是非頻繁(i-1)-項(xiàng)集的超集

6. 刪除該i-項(xiàng)集;

7.Else

8.count=D中的i-項(xiàng)集相與結(jié)果之和;

9.EndIf

10.Ifcount≥minsup

11. 記錄該項(xiàng)集為頻繁項(xiàng)集;

12.Else

13. 記錄該項(xiàng)集為非頻繁i-項(xiàng)集，并刪除非頻繁(i-1)-項(xiàng)集;

14.EndIf

15. }EndFor

16. 輸出所有頻繁項(xiàng)集;

17. }EndFor

經(jīng)過算法1和利用超集檢測(cè)性質(zhì)，就可以挖掘出所有的頻繁項(xiàng)集。本文算法相較于FIUT-Stream算法在時(shí)間和空間效率上有了很大程度的提升，本文算法只需構(gòu)建FIUT中的1個(gè)位表，頻繁項(xiàng)集的挖掘不需要通過創(chuàng)建FIU-tree結(jié)構(gòu)來實(shí)現(xiàn)，直接通過位表進(jìn)行數(shù)學(xué)中的簡(jiǎn)單And Operation即可得到所有項(xiàng)集的支持度計(jì)數(shù)，并以此挖掘出所有的頻繁項(xiàng)集，這更能滿足如今對(duì)數(shù)據(jù)流頻繁項(xiàng)集挖掘效率要求極高的需求。

在各種監(jiān)控視頻遍布的今天，可以利用這種高效的數(shù)據(jù)流頻繁項(xiàng)集挖掘方式進(jìn)行恐怖分子的搜查，對(duì)在一個(gè)時(shí)間段同一個(gè)地方頻繁出現(xiàn)的人可以給予很大的懷疑度，從而給警方縮小排查范圍，在一定程度上為破案提供幫助；另外，現(xiàn)在電商行業(yè)的飛速發(fā)展，促使網(wǎng)上數(shù)據(jù)流激增，對(duì)用戶網(wǎng)上瀏覽商品的數(shù)據(jù)流進(jìn)行分析，可以對(duì)用戶進(jìn)行個(gè)性化推薦，增加用戶的購買量；或者根據(jù)天氣的實(shí)時(shí)變化趨勢(shì)圖，做出天氣預(yù)報(bào)，隨著信息化社會(huì)的發(fā)展，數(shù)據(jù)流頻繁項(xiàng)集挖掘的應(yīng)用會(huì)變得越來越廣泛。

4 實(shí)驗(yàn)結(jié)果分析

本文實(shí)驗(yàn)采用Java語言進(jìn)行實(shí)驗(yàn)程序的編寫，實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz，8 GB內(nèi)存，Windows 10的64位操作系統(tǒng)。實(shí)驗(yàn)采用T10I4D100K數(shù)據(jù)集和真實(shí)數(shù)據(jù)集KOSARAK，T10I4D100K數(shù)據(jù)集是由IBM數(shù)據(jù)生成器生成的模擬數(shù)據(jù)集，該數(shù)據(jù)集包含了100 000個(gè)事務(wù)，總共870個(gè)項(xiàng)目，屬于相對(duì)稀疏的數(shù)據(jù)集；真實(shí)數(shù)據(jù)集KOSARAK是一種實(shí)時(shí)的點(diǎn)擊流數(shù)據(jù)，來自于匈牙利一家在線新聞門戶網(wǎng)站，包含990 002個(gè)事務(wù)，共36 841個(gè)項(xiàng)目，屬于相對(duì)稠密的數(shù)據(jù)集。采用稠密和稀疏2種數(shù)據(jù)集能更好地體現(xiàn)算法的優(yōu)越性。

首先比較了SysTree算法、FIUT-Stream算法和本文改進(jìn)算法在稀疏數(shù)據(jù)集T10I4D100K和稠密數(shù)據(jù)集KOSARAK上的時(shí)間開銷。分別設(shè)定T10I4D100K數(shù)據(jù)集的支持度為(0.5,0.1,0.15,0.2,0.25)，滑動(dòng)窗口大小為2；KOSARAK數(shù)據(jù)集的支持度為(0.75,0.8,0.85,0.9,0.95)，滑動(dòng)窗口大小為4，得到如圖1和圖2所示的時(shí)間消耗對(duì)比圖。

Figure 1 Comparison of time consumption on T10I4D100K dataset 圖1 數(shù)據(jù)集T10I4D100K上的時(shí)間消耗對(duì)比

Figure 2 Comparison of time consumption on KOSARAK dataset 圖2 數(shù)據(jù)集KOSARAK上的時(shí)間消耗對(duì)比

如圖1和圖2所示分別是這幾種算法在數(shù)據(jù)集T10I4D100K和數(shù)據(jù)集KOSARAK上的時(shí)間消耗對(duì)比圖，從圖中可以看出，本文的改進(jìn)算法在稀疏數(shù)據(jù)集和稠密數(shù)據(jù)集上的時(shí)間性能均優(yōu)于另外2種算法的，并且隨著支持度的降低，優(yōu)勢(shì)更為明顯；另外，在稠密數(shù)據(jù)集上的優(yōu)勢(shì)更為明顯，這是因?yàn)槌砻軘?shù)據(jù)集的項(xiàng)目數(shù)較多，本文改進(jìn)算法在挖掘頻繁項(xiàng)集時(shí)采用And Operation，能更高效地挖掘出所有的頻繁項(xiàng)集。

接下來進(jìn)行空間消耗的對(duì)比，比較3種算法的空間消耗性能。設(shè)定稀疏數(shù)據(jù)集T10I4D100K的滑動(dòng)窗口大小分別為4,6,8,10，設(shè)定稠密數(shù)據(jù)集KOSARAK的滑動(dòng)窗口大小分別為5,6,7,8，得到如圖3和圖4所示的空間消耗對(duì)比圖。

從圖3和圖4中可以看出，本文的改進(jìn)算法在稀疏數(shù)據(jù)集和稠密數(shù)據(jù)集上的表現(xiàn)均優(yōu)于另外2種算法的，并且隨著Pane大小增加，這種優(yōu)勢(shì)更明顯。對(duì)比圖3和圖4發(fā)現(xiàn)，在稠密數(shù)據(jù)集KOSARAK上，本文改進(jìn)算法的優(yōu)勢(shì)更為突出。這是因?yàn)楸疚乃惴ú捎昧顺瘷z測(cè)策略，首先通過超集檢測(cè)減少了大量候選項(xiàng)集，這樣就可以提前刪除非頻繁項(xiàng)集，提高了空間效率。

Figure 3 Comparison of space consumption on T10I4D100K dataset 圖3 數(shù)據(jù)集T10I4D100K上的空間消耗對(duì)比

Figure 4 Comparison of space consumption on KOSARAK dataset 圖4 數(shù)據(jù)集KOSARAK上的空間消耗對(duì)比

5 結(jié)束語

本文主要針對(duì)FIUT-Stream算法在挖掘頻繁項(xiàng)集的時(shí)候需要構(gòu)建FIU-tree結(jié)構(gòu)增加了空間消耗，在頻繁項(xiàng)集挖掘時(shí)通過類FP-tree遍歷使得挖掘效率不高的問題進(jìn)行改進(jìn)，改進(jìn)算法在一定程度上提高了時(shí)間和空間效率。本文首先在進(jìn)行數(shù)據(jù)流處理時(shí)采用高效的位表進(jìn)行壓縮，然后用窗口的思想將數(shù)據(jù)流等塊分割，在窗口中數(shù)據(jù)更新時(shí)只需對(duì)窗口中數(shù)據(jù)進(jìn)行簡(jiǎn)單加減運(yùn)算即可計(jì)算支持度，最后采用簡(jiǎn)單高效的And Operation即可挖掘出所有的頻繁項(xiàng)集，同時(shí)在挖掘過程中采用超集檢測(cè)減少不必要項(xiàng)集的挖掘，在時(shí)間和空間效率上都比原算法高，適合當(dāng)前大數(shù)據(jù)環(huán)境下的海量數(shù)據(jù)流挖掘。