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

(1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學通信新技術應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

1 引言

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

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

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

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

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

2 相關概念

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

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

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

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

性質1(超集檢測) 對于任意項集X和Y，且X?Y，若判定X為非頻繁項集，則Y也一定不會是頻繁項集。

3 頻繁項集挖掘

3.1 窗口更新

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

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

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

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

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

Table 2 Compressed bit table表2 壓縮位表

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

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

3.2 支持度更新

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

3.3 頻繁項集挖掘算法

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

Table 4 Frequent 1-itemset table表4 頻繁1-項集位表

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

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

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

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

輸入：頻繁1-項集壓縮位表D。

輸出：所有頻繁項集。

1.For所有i維組合

2. {

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

4. {

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

6. 刪除該i-項集;

7.Else

8.count=D中的i-項集相與結果之和;

9.EndIf

10.Ifcount≥minsup

11. 記錄該項集為頻繁項集;

12.Else

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

14.EndIf

15. }EndFor

16. 輸出所有頻繁項集;

17. }EndFor

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

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

4 實驗結果分析

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

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

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

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

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

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

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

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

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

5 結束語

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