尹紹宏，范桂丹

基于矩陣的數(shù)據(jù)流Top-k頻繁項集挖掘算法

尹紹宏，范桂丹

(天津工業(yè)大學(xué)計算機(jī)科學(xué)與軟件學(xué)院，天津 300387)

傳統(tǒng)的數(shù)據(jù)挖掘算法在挖掘頻繁項集時會產(chǎn)生大量的冗余項集，影響挖掘效率。為此，提出一種基于矩陣的數(shù)據(jù)流Top-k頻繁項集挖掘算法。引入2個0-1矩陣，即事務(wù)矩陣和二項集矩陣。采用事務(wù)矩陣表示滑動窗口模型中的事務(wù)列表，通過計算每行的支持度得到二項集矩陣。利用二項集矩陣得到候選項集，將事務(wù)矩陣中對應(yīng)的行做邏輯與運(yùn)算，計算出候選項集的支持度，從而得到Top-k頻繁項集。把挖掘的結(jié)果存入數(shù)據(jù)字典中，當(dāng)用戶查詢時，能夠按支持度降序輸出Top-k頻繁項集。實驗結(jié)果表明，該算法在挖掘過程中能避免冗余項集的產(chǎn)生，在保證正確率的前提下具有較高的時間效率。

數(shù)據(jù)挖掘；數(shù)據(jù)流；滑動窗口；矩陣；Top-k頻繁項集

1 概述

數(shù)據(jù)流[1]是大量連續(xù)到達(dá)、隨時間不斷變化的數(shù)據(jù)序列，例如超市每天產(chǎn)生的大量售貨記錄、網(wǎng)頁的點擊流、通信領(lǐng)域內(nèi)的電話記錄數(shù)據(jù)流等。數(shù)據(jù)流產(chǎn)生的數(shù)據(jù)無法全部保存在內(nèi)存中，只能按照順序讀取一次或幾次[2]。數(shù)據(jù)流挖掘就是從連續(xù)的數(shù)據(jù)流中提取出潛在有用的信息和知識的過程。對數(shù)據(jù)流的查詢要求實時處理，顯然許多傳統(tǒng)的數(shù)據(jù)挖掘算法并不適用于數(shù)據(jù)流挖掘。數(shù)據(jù)流挖掘算法要求在單次掃描數(shù)據(jù)流的前提下獲得挖掘結(jié)果，并且產(chǎn)生的結(jié)果通常是近似結(jié)果。

在實際應(yīng)用中，人們更多地關(guān)注近期數(shù)據(jù)，因此數(shù)據(jù)流挖掘通常是基于某種特定的時間區(qū)間進(jìn)行的，從而出現(xiàn)了基于窗口的數(shù)據(jù)流挖掘算法。常用的窗口模型有3種[3]：快照模型，界標(biāo)模型，滑動窗口模型。應(yīng)用較多的模型是界標(biāo)模型和滑動窗口模型。

近來提出了許多數(shù)據(jù)流頻繁項集挖掘算法，典型的有FP-stream算法[4]。此類算法都需要用戶指定最小支持度閾值，但面對海量的數(shù)據(jù)，閾值的設(shè)定需要先驗知識和一定的專業(yè)知識，用戶就很難確定合適的閾值。當(dāng)閾值設(shè)置過小時，挖掘出的頻繁項集數(shù)量非常巨大，會占用大量的內(nèi)存空間，而挖掘出的結(jié)果往往不是用戶所需求的；當(dāng)閾值設(shè)置過大時，可能就挖掘出少量的頻繁項集。因而讓用戶指定需要挖掘的個頻繁項集，即避免了用戶設(shè)定最小閾值，又使挖掘更具有針對性。

對于Top-k頻繁項集的挖掘，學(xué)者們提出了許多算法。文獻(xiàn)[5]提出了Itemset-Loop算法，此算法在Apriori算法[6]的基礎(chǔ)上進(jìn)行了改進(jìn)，能夠挖掘出靜態(tài)數(shù)據(jù)庫中的Top-k頻繁項集，但是此算法不支持?jǐn)?shù)據(jù)的增量更新。文獻(xiàn)[7]研究了數(shù)據(jù)流最頻繁的個項的挖掘算法，但是并沒有涉及多項集的處理問題。

本文提出一種基于矩陣的數(shù)據(jù)流Top-k頻繁項集挖掘算法TKFM，該算法引入2個0-1矩陣，一個是事務(wù)矩陣，存儲事務(wù)中各項的相關(guān)信息；另一個是二項集矩陣，存儲2-項集的信息。通過2個矩陣的相關(guān)操作，將挖掘出的頻繁項集存儲到數(shù)據(jù)字典中來實現(xiàn)數(shù)據(jù)流中前個頻繁項集的挖掘。

2 基本概念

定義2滑動窗口的起始點與終止點都沒有明確的界限[8]，的終止點為當(dāng)前時刻。其中，的大小為窗口中所包含的事務(wù)數(shù)目，由用戶預(yù)先定義。每當(dāng)有一個新的事務(wù)到達(dá)窗口，窗口就滑動一次。新的事務(wù)不斷進(jìn)入窗口，舊的事務(wù)相繼被刪除，滑動窗口不斷被更新。

定義4 Top-k頻繁項集。將數(shù)據(jù)流中的所有項集按照支持度降序排列，設(shè)排在第位項集的支持度為border- sup，則中所有支持度不小于border-sup的項集的集合即Top-k頻繁項集。

假定文中所有的項都是按照全序關(guān)系排列的。

3 TKFM原理與算法

3.1 算法所用數(shù)據(jù)結(jié)構(gòu)

3.1.1 事務(wù)矩陣

行表示數(shù)據(jù)流中項的集合={1,2,…,I}，列表示依次到達(dá)的事務(wù){(diào)1,2,…,T}。設(shè)滑動窗口的大小為||=(即矩陣的列數(shù))，項集中共有個項，則建立一個(+1)×的事務(wù)矩陣，并將矩陣中的每個元素初始化為0，其中第(+1)行為count行。掃描依次到達(dá)的數(shù)據(jù)流，若窗口未滿，則將依次到來的事務(wù)T加入到矩陣中，其中，若項目在 第條事務(wù)中出現(xiàn)，則將A置1，否則置0；若窗口已滿，則需先刪除窗口中最舊的事務(wù)，然后再添加新的事務(wù)。設(shè)當(dāng)前到達(dá)的事務(wù)為T，最舊事務(wù)所在列為column，則最舊事務(wù)所在的列column為%。count記錄每列中1的個數(shù)，即事務(wù)的長度。

3.1.2 數(shù)據(jù)字典Dictionary

記錄當(dāng)前數(shù)據(jù)流中的項集及其支持度，且支持度按降序排列。Dictionary中的每一個項都是一個二元組，其中，sup表示項在當(dāng)前數(shù)據(jù)流中的支持度；item表示項。Dictionary的內(nèi)部結(jié)構(gòu)如圖1所示。

圖1 Dictionary的內(nèi)部結(jié)構(gòu)

對于Dictionary中的每個項，支持度sup是關(guān)鍵字，在整個數(shù)據(jù)字典中是唯一的，不允許重復(fù)，且一個sup可以對應(yīng)多個item。其中，存儲某個sup對應(yīng)的item時，需要在磁盤中占用一片連續(xù)的區(qū)域。

對數(shù)據(jù)字典進(jìn)行訪問是通過關(guān)鍵字sup進(jìn)行的。當(dāng)需要訪問某個sup的item集合時，首先要找出關(guān)鍵字sup，然后通過關(guān)鍵字找到對應(yīng)的item集合，按照順序讀取出對應(yīng)元素。

3.1.3 二項集矩陣

3.2 TKFM算法的基本原理

以表1所示的事務(wù)數(shù)據(jù)流為例，介紹TKFM算法的基本思想，設(shè)=2，||=5。

表1 事務(wù)數(shù)據(jù)流

3.2.1 窗口初始階段

當(dāng)窗口內(nèi)的事務(wù)數(shù)小于||時，處于窗口初始階段。在此階段，新的事務(wù)不斷進(jìn)入窗口，直到窗口滿為止。則表1中的事務(wù)數(shù)據(jù)流的事務(wù)矩陣如表2所示。

表2 窗口初始階段的事務(wù)矩陣A

3.2.2 窗口滑動階段

當(dāng)窗口滿時，處于滑動窗口階段。在此階段，最舊的事務(wù)1被刪除，新到來的事務(wù)6添加到滑動窗口中，則 表2中的事務(wù)矩陣更新為表3。

表3 滑動窗口階段的事務(wù)矩陣A

3.2.3 Top-k頻繁項集產(chǎn)生階段

Top-k頻繁項集產(chǎn)生的過程如下：

(1)計算表3中事務(wù)矩陣每行中1的個數(shù)，即每個項的支持度，然后將二元組存入Dictionary中，并按支持度降序排列，找出第2個項的支持度，此時border-sup為2，然后刪除支持度小于border-sup的項，即完成top-2頻繁一項集的尋找。

(2)根據(jù)Dictionary中的頻繁一項集構(gòu)造二項集矩陣。在構(gòu)造矩陣的同時，將支持度大于等于border-sup的2-項集存入2中，同時將二元組存入Dictionary中，并按支持度降序排列，找出第個項集的支持度，更新border-sup為3，并刪除支持度小于border-sup的項。二項集矩陣如表4所示。

表4 二項集矩陣B

(3)根據(jù)C中的項和中的信息，可以將頻繁2-項集擴(kuò)展到3-項集{{1,2,3}、{1,2,4}}，再將事務(wù)矩陣中的各相關(guān)行做邏輯與運(yùn)算，將支持度大于等于border-sup的二元組存入Dictionary中。本例中的3項集不滿足條件，算法 結(jié)束。

此例得到的top-2頻繁項集如圖2所示。

圖2 top-2頻繁項集

3.3 TKFM算法描述

根據(jù)上述分析，算法包括3個關(guān)鍵步驟：窗口初始階段，滑動窗口階段，Top-k頻繁項集產(chǎn)生階段。下面給出算法的偽代碼。

輸入數(shù)據(jù)流，用戶指定的，滑動窗口的大小||

輸出Top-k頻繁項集

(1)滑動窗口中的每個事務(wù)Tj

if(W is not full)//窗口初始階段

{

for(i=1;i<=m;i++)

if(Iiin Tj)

A[i,j]=1;

else A[i,j]=0;

}

(2)else//窗口滑動階段

int column=j%w;

更新矩陣A中第column列的值，其余列保持不變

(3)掃描A中的前m行，將二元組存入Dictionary中，并按支持度降序排列。若Dictionary中的項小于k，則初始化border-sup=0，否則border-sup為第k個項的支持度，刪除支持度小于border-sup的二元組

(4)根據(jù)Dictionary中的一項集構(gòu)造二項集矩陣B，產(chǎn)生候選二項集C2，同時將支持度大于等于border-sup的二元組存入Dictionary中，并按支持度降序排列，找出第k個項的支持度，更新border-sup，并刪除支持度小于border-sup的二元組

(5)//Top-k頻繁項集產(chǎn)生階段，Ck={Ii1,Ii2,…,Ii(k-1)}是頻繁//(k-1)-項集

If(B[i(k-1),iu]=1)and(B[i1,iu]=B[i2,iu]=B[i(k-2),iu]=1)

{

擴(kuò)展為k-項集{Ii1,Ii2,…, Ii(k-1),Iu}

if(sup({Ii1,Ii2,…, Ii(k-1),Iu})>=border-sup)

Lk={Ii1,Ii2,…, Ii(k-1),Iu};

將存入Dictionary中

}

(6)將Dictionary中的項統(tǒng)一按支持度降序排列，找出第k個項的支持度，更新border-sup，并刪除支持度小于border-sup的二元組

(7)重復(fù)步驟(5)和步驟(6)，直至不產(chǎn)生更大的項集為止

(8)輸出Top-k頻繁項集

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

本文算法采用IBM data generator[11]生成的模擬數(shù)據(jù)，算法的實現(xiàn)語言是C#，其開發(fā)工具是Visual Studio 2010，算法的運(yùn)行環(huán)境為Windows XP操作系統(tǒng)，Intel core 3.30 GHz CPU，3 062 MB內(nèi)存。算法采用的數(shù)據(jù)集是稀疏集T10I4D100K和稠密集T40I10D100K，其中，T表示事務(wù)的平均長度；I表示前項頻繁項集的平均長度；D表示數(shù)據(jù)流中事物的總數(shù)。實驗所用的2個數(shù)據(jù)集由10萬條事務(wù)組成，前項頻繁項集的平均長度分別為4和10。設(shè)定滑動窗口||=10 000。

設(shè)定=100，在2個數(shù)據(jù)集上測試算法的性能，結(jié)果如圖3所示。從圖中可以得到，隨著處理的事務(wù)數(shù)的不斷增大，算法所花費的時間呈近似線性增長的趨勢，在T40I10D100k數(shù)據(jù)集上所花費的時間增長較快，原因是此數(shù)據(jù)集中項的平均長度較長，在窗口滑動及更新時需花費較長時間，且在挖掘Top-k頻繁項集時也需較長時間。

圖3 不同數(shù)據(jù)集上本文算法的運(yùn)行時間

圖4通過設(shè)置不同的值，測試值對算法性能的影響。在稀疏集T10I4D100k上分別測試了4個不同的值，從圖中可以看到，隨著事務(wù)數(shù)的不斷增加，每個值所花費的時間呈平穩(wěn)增長的趨勢。在處理相同事務(wù)數(shù)的情況下，值越大，挖掘所花費的時間越長，這是因為值越大，更新、查找、插入和排序更多的頻繁項集需要較長的時間。

圖4 不同k值下本文算法的運(yùn)行時間

實驗對TKFM算法和MTKFI[12]算法進(jìn)行了比較。MTKFI算法是利用位圖存儲事務(wù)的相關(guān)信息，在Top-k頻繁項集挖掘階段，算法利用類Apriori的思想產(chǎn)生Top-k頻繁項集，并把挖掘的結(jié)果存儲在二層索引鏈表中。此算法在Top-k頻繁項集產(chǎn)生的過程中，需要不斷地進(jìn)行連接和剪枝操作，會產(chǎn)生大量的冗余項集，因而算法的時間效率不高。TKFM算法在Top-k頻繁項集產(chǎn)生的過程中，省去了連接和剪枝操作，從而避免產(chǎn)生大量冗余項集，提高了挖掘的時間效率。在挖掘5萬條事務(wù)的前提下，使用稠密集T40I10D100k進(jìn)行實驗，TKFM算法和MTKFI算法在不同值下的運(yùn)行時間如圖5所示。通過實驗可以看出，隨著值的增大，本文算法的時間效率提高得越明顯。

圖5 不同k值下2種算法的運(yùn)行時間比較

5 結(jié)束語

本文提出了一種基于矩陣的數(shù)據(jù)流Top-k頻繁項集挖掘算法，利用滑動窗口對數(shù)據(jù)流進(jìn)行逐條采樣，并用2個0-1矩陣存儲相關(guān)信息，通過邏輯與運(yùn)算計算候選項的支持度。理論分析和實驗結(jié)果均表明，該算法能夠挖掘出Top-k頻繁項集，且與MTKFI算法相比，其時間效率更高。如何減少算法的內(nèi)存消耗是下一步要研究的問題。

[1] Babcock B, Babu S, Datar M, et al. Models and Issues in Data Stream Systems[C]//Proc. of the 21st ACM SIGMOD- SIGART Symposium on Principles of Database System. New York, USA: ACM Press, 2002: 1-16.

[2] 王 磊, 黃志球, 朱小棟, 等. 數(shù)據(jù)流中基于矩陣的頻繁項集挖掘[J]. 計算機(jī)科學(xué)與探索, 2008, 2(3): 330-335.

[3] 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述[J]. 計算機(jī)科學(xué), 2007, 34(1): 1-5.

[4] Giannella C, Han Jiawei, Pei Jian, et al. Mining Frequent Patterns in Data Streams at Multiple Time Granularities[M]. Cambridge, USA: MIT Press, 2005.

[5] Fu A W, Kwong R W, Renfrew F. Mining N-most Interesting Itemsets[C]//Proc. of International Symposium on Methodo- logies for Intelligent Systems. Charlotte, USA: [s. n.], 2000: 59-67.

[6] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules[C]//Proc. of the 20th International Conference on Very Large Data Bases. Santiago, Chile: [s. n.], 1994.

[7] Metwally A. Efficient Computation of Frequent and Top-k Elements in Data Streams[C]//Proc. of International Conference on Database Theory. Edinburgh, UK: [s. n.], 2005: 398-412.

[8] Li Huafu, Lee S Y. Mining Frequent Itemsets over Data Streams Using Efficient Window Sliding Techniques[J]. Expert Systems with Applications, 2008, 33(2): 286-298.

[9] 韓家煒. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社, 2007.

[10] 徐嘉莉, 陳 佳. 基于向量的數(shù)據(jù)流滑動窗口中最大頻繁項集挖掘[J]. 計算機(jī)應(yīng)用研究, 2012, 29(3): 837-840.

[11] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules[C]//Proc. of the 20th International Conference on Very Large Database. San Francisco, USA: Morgan Kaufmann Publishers, 1994: 487-499.

[12] 劉立新. 數(shù)據(jù)流頻繁模式挖掘算法研究[D]. 長沙: 中南大學(xué), 2010.

編輯 任吉慧

Top-k Frequent Itemsets Mining Algorithm over Data Streams Based on Matrix

YIN Shao-hong, FAN Gui-dan

(School of Computer Science and Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China)

The past algorithms produce large amounts of redundant itemsets, and they affect the efficiency of data mining. Therefore, a Top-k frequent itemsets mining algorithm over data streams based on matrix is proposed. Two 0-1 matrices, transaction matrix and 2-itemsets matrix, are introduced into the algorithm.Using transaction matrix to express the transaction list of a sliding window, and 2-itemsets matrix is obtained by calculating the support of each row. Thenit can get candidate items by 2-itemsets matrix, and Top-k frequent itemsets are obtained by calculating the support of candidate items through logic and operation of correspond row in transaction matrix. Finally it saves the result of data mining into data dictionary.The algorithm can output the Top-k frequent itemsets by support in descendant order when user queries. Experimental results show that the algorithm avoids redundant itemsets in the process of data mining, and the efficiency of data mining is improved appreciably under the premise of accuracy.

data mining; data stream; sliding window; matrix; Top-k frequent itemset

1000-3428(2014)03-0055-04

A

TP311.13

尹紹宏(1964－)，女，副教授，主研方向：數(shù)據(jù)挖掘；范桂丹，碩士研究生。

2013-01-11

2013-03-10 E-mail：yinsh@tjpu.enu.cn

10.3969/j.issn.1000-3428.2014.03.011