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

尹紹宏，范桂丹

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

尹紹宏，范桂丹

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

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

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

1 概述

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

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

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

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

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

2 基本概念

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

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

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

3 TKFM原理與算法

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

3.1.1 事務(wù)矩陣

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

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

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

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

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

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

3.1.3 二項(xiàng)集矩陣

3.2 TKFM算法的基本原理

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

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

3.2.1 窗口初始階段

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

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

3.2.2 窗口滑動(dòng)階段

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

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

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

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

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

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

表4 二項(xiàng)集矩陣B

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

此例得到的top-2頻繁項(xiàng)集如圖2所示。

圖2 top-2頻繁項(xiàng)集

3.3 TKFM算法描述

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

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

輸出Top-k頻繁項(xiàng)集

(1)滑動(dòng)窗口中的每個(gè)事務(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//窗口滑動(dòng)階段

int column=j%w;

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

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

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

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

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

{

擴(kuò)展為k-項(xiàng)集{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中的項(xiàng)統(tǒng)一按支持度降序排列，找出第k個(gè)項(xiàng)的支持度，更新border-sup，并刪除支持度小于border-sup的二元組

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

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

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

本文算法采用IBM data generator[11]生成的模擬數(shù)據(jù)，算法的實(shí)現(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表示前項(xiàng)頻繁項(xiàng)集的平均長度；D表示數(shù)據(jù)流中事物的總數(shù)。實(shí)驗(yàn)所用的2個(gè)數(shù)據(jù)集由10萬條事務(wù)組成，前項(xiàng)頻繁項(xiàng)集的平均長度分別為4和10。設(shè)定滑動(dòng)窗口||=10 000。

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

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

圖4通過設(shè)置不同的值，測(cè)試值對(duì)算法性能的影響。在稀疏集T10I4D100k上分別測(cè)試了4個(gè)不同的值，從圖中可以看到，隨著事務(wù)數(shù)的不斷增加，每個(gè)值所花費(fèi)的時(shí)間呈平穩(wěn)增長的趨勢(shì)。在處理相同事務(wù)數(shù)的情況下，值越大，挖掘所花費(fèi)的時(shí)間越長，這是因?yàn)橹翟酱螅隆⒉檎摇⒉迦牒团判蚋嗟念l繁項(xiàng)集需要較長的時(shí)間。

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

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

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

5 結(jié)束語

本文提出了一種基于矩陣的數(shù)據(jù)流Top-k頻繁項(xiàng)集挖掘算法，利用滑動(dòng)窗口對(duì)數(shù)據(jù)流進(jìn)行逐條采樣，并用2個(gè)0-1矩陣存儲(chǔ)相關(guān)信息，通過邏輯與運(yùn)算計(jì)算候選項(xiàng)的支持度。理論分析和實(shí)驗(yàn)結(jié)果均表明，該算法能夠挖掘出Top-k頻繁項(xiàng)集，且與MTKFI算法相比，其時(shí)間效率更高。如何減少算法的內(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ù)流中基于矩陣的頻繁項(xiàng)集挖掘[J]. 計(jì)算機(jī)科學(xué)與探索, 2008, 2(3): 330-335.

[3] 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述[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ù)流滑動(dòng)窗口中最大頻繁項(xiàng)集挖掘[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