基于滑動(dòng)窗口模型的數(shù)據(jù)流加權(quán)頻繁模式挖掘算法

馬連燈 王占剛

摘 要：加權(quán)頻繁模式挖掘比傳統(tǒng)的頻繁模式挖掘更加的具有實(shí)際意義，針對(duì)數(shù)據(jù)流中的數(shù)據(jù)只能掃描有限次的性質(zhì)，提出了基于滑動(dòng)窗口模型的數(shù)據(jù)流加權(quán)頻繁模式挖掘方法WFP-SW，該算法中數(shù)據(jù)存儲(chǔ)采用的是矩陣數(shù)據(jù)結(jié)構(gòu)，通過矩陣之間的相關(guān)操作來產(chǎn)生加權(quán)頻繁模式。實(shí)驗(yàn)結(jié)果顯示，該算法在產(chǎn)生加權(quán)頻繁模式的時(shí)候不產(chǎn)生冗余模式，比傳統(tǒng)的頻繁模式挖掘算法有更好的效率。

關(guān)鍵詞：數(shù)據(jù)流；滑動(dòng)窗口；加權(quán)頻繁模式；矩陣

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

加權(quán)頻繁模式與傳統(tǒng)的頻繁模式挖掘是不同的[1-3]，它不僅取決于項(xiàng)集出現(xiàn)的次數(shù)，而且要考慮到數(shù)據(jù)庫中項(xiàng)集重要性。在很多實(shí)際的應(yīng)用中[4，5]，不同的數(shù)據(jù)項(xiàng)的重要程度是不同的。例如，在零售市場分析的時(shí)候，雖然貴重的商品沒有在事務(wù)數(shù)據(jù)庫中出現(xiàn)非常多的次數(shù)，但是它們卻貢獻(xiàn)了很大一部分的收入。所以，加權(quán)頻繁模式挖掘比傳統(tǒng)的頻繁模式挖掘更能在現(xiàn)實(shí)世界中發(fā)揮更實(shí)際的作用。

本文提出了基于滑動(dòng)窗口模型的數(shù)據(jù)流加權(quán)頻繁模式挖掘方法WFP-SW，該算法中數(shù)據(jù)存儲(chǔ)采用的是矩陣數(shù)據(jù)結(jié)構(gòu)，通過矩陣之間的相關(guān)操作得到加權(quán)頻繁模式。實(shí)驗(yàn)結(jié)果顯示，該算法在產(chǎn)生加權(quán)頻繁模式的時(shí)候不產(chǎn)生冗余模式，比傳統(tǒng)的加權(quán)頻繁模式挖掘算法有更好的效率。

2 基本概念（The basic concept）

定義1：設(shè)是項(xiàng)的集合，數(shù)據(jù)流是一個(gè)以一定速度連續(xù)到達(dá)的數(shù)據(jù)項(xiàng)序列，其中表示第個(gè)事務(wù)，對(duì)于任意都有。每個(gè)項(xiàng)目中都有一個(gè)代表此項(xiàng)的重要性的非負(fù)實(shí)數(shù)的權(quán)值，。

定義2：由數(shù)據(jù)項(xiàng)組成的集合定義為項(xiàng)集，其中，含有個(gè)項(xiàng)的集合定義為項(xiàng)集。

定義3：項(xiàng)集的權(quán)值是數(shù)據(jù)流中含有該項(xiàng)目的事務(wù)項(xiàng)集權(quán)值的匯總[6]。

定義4：設(shè)加權(quán)最小支持度為，如果項(xiàng)集是頻繁項(xiàng)集，則加權(quán)支持度大于或等于，即。

定義5：滑動(dòng)窗口的起點(diǎn)與終點(diǎn)都沒有清晰的限制，的終點(diǎn)就是當(dāng)前的時(shí)間點(diǎn)。的大小是窗口中事務(wù)的多少，這個(gè)值是提前設(shè)置好的。每當(dāng)有一個(gè)新的事務(wù)到達(dá)時(shí)，就滑動(dòng)一次窗口。新的事務(wù)連續(xù)進(jìn)入窗口，同時(shí)，舊的事務(wù)被刪除，滑動(dòng)窗口一直被更新。

定義6：全序關(guān)系。根據(jù)字母在字典中的順序，如果小于，則有，比如[7]。同理，可以給出項(xiàng)集在字典中的順序?yàn)?，比如?/p>

在本文中，假設(shè)全部項(xiàng)都是依照全序關(guān)系排序的。

3 WFP-SW原理與算法（WFP-SW principle and

algorithm）

3.1 矩陣的構(gòu)造

（1）事務(wù)矩陣的構(gòu)造

用矩陣的行來標(biāo)識(shí)數(shù)據(jù)流中項(xiàng)的集合，用矩陣的列標(biāo)識(shí)連續(xù)到達(dá)的事務(wù)。設(shè)滑動(dòng)窗口的大小為，如果項(xiàng)集中包含個(gè)項(xiàng)，則構(gòu)造一個(gè)的事務(wù)矩陣，同時(shí)初始化矩陣中的所有元素為0。掃描連續(xù)到達(dá)的數(shù)據(jù)流，如果窗口沒有滿，那么就將連續(xù)到達(dá)的事務(wù)存儲(chǔ)進(jìn)矩陣中，如果項(xiàng)目出現(xiàn)在第條事務(wù)中，那么就設(shè)置為1，如果沒有出現(xiàn)則設(shè)置為0；當(dāng)窗口滿的時(shí)候，首先把窗口中最舊的事務(wù)刪除，然后把新到達(dá)的事務(wù)添加進(jìn)去。假設(shè)事務(wù)即將到達(dá)，代表最舊事務(wù)的列，則最舊事務(wù)的刪除方法是：。用于記錄每列中1的個(gè)數(shù)，即事務(wù)的長度。

（2）二項(xiàng)集矩陣的構(gòu)造

設(shè)項(xiàng)集中有個(gè)項(xiàng)，那么構(gòu)造的加權(quán)二項(xiàng)集矩陣是的二項(xiàng)集矩陣，同時(shí)初始化矩陣中的所有元素為0。對(duì)于加權(quán)頻繁項(xiàng)集中的兩個(gè)項(xiàng)和，如果，讓中的第行與第行參與邏輯與運(yùn)算，若支持度不小于，則項(xiàng)集就是加權(quán)頻繁項(xiàng)集，同時(shí)把的值設(shè)置成1，反之，把它的值設(shè)置為0。

3.2 WFP-SW算法的基本思想

加權(quán)頻繁項(xiàng)集的產(chǎn)生：項(xiàng)集是通過對(duì)加權(quán)頻繁項(xiàng)集的擴(kuò)展產(chǎn)生的。設(shè)是加權(quán)頻繁項(xiàng)集，在二項(xiàng)集矩陣中，若，且，則就可以擴(kuò)充為項(xiàng)集。同時(shí)在矩陣中，讓對(duì)應(yīng)的個(gè)項(xiàng)的行做邏輯與運(yùn)算，如果得到的結(jié)果不小于，則是加權(quán)頻繁項(xiàng)集。重復(fù)這個(gè)操作，當(dāng)沒有新的項(xiàng)集產(chǎn)生的時(shí)候，結(jié)束算法。

3.3 WFP-SW算法描述

綜合上面的分析可知，WFP-SW算法有如下關(guān)鍵步驟：初始窗口階段、滑動(dòng)窗口階段、產(chǎn)生加權(quán)頻繁模式階段。

該算法的偽代碼如下：

輸入：數(shù)據(jù)流事務(wù)，滑動(dòng)窗口大小，每個(gè)項(xiàng)目權(quán)重，用戶設(shè)定的最小加權(quán)支持度；

輸出：加權(quán)頻繁模式；

滑動(dòng)窗口中的每個(gè)事務(wù)

//初始窗口階段

{

}

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

對(duì)矩陣中第列的值進(jìn)行更新，其他列的值不變

掃描矩陣中的前行，產(chǎn)生

構(gòu)造二項(xiàng)集矩陣

//產(chǎn)生加權(quán)頻繁模式階段，是頻繁項(xiàng)集

{

擴(kuò)展為項(xiàng)集

；

}

4 實(shí)驗(yàn)結(jié)果及分析（The experimental results and

analysis）

本文中算法采用的實(shí)驗(yàn)平臺(tái)：Windows 7操作系統(tǒng)，Eclipse開發(fā)工具，編程語言是java。采用IBM data generator[8]生成的數(shù)據(jù)作為實(shí)驗(yàn)所用的數(shù)據(jù)。本文采用稠密數(shù)據(jù)集T40I10D100K，其中D代表事務(wù)的總數(shù)，I代表最大頻繁項(xiàng)集長度的平均，T代表事務(wù)長度的平均值，即實(shí)驗(yàn)中事務(wù)總數(shù)是10萬條，最大頻繁項(xiàng)集的平均長度是10，事務(wù)長度的平均值是40。

實(shí)驗(yàn)對(duì)WFP-SW算法和FIM-SW[9]算法進(jìn)行對(duì)比。其中后者是利用Apriori性質(zhì)產(chǎn)生頻繁K-項(xiàng)集，并且在頻繁項(xiàng)集產(chǎn)生的過程中，需要進(jìn)行連接和剪枝操作，所以算法的時(shí)間效率比較低。WFP-SW算法在產(chǎn)生加權(quán)頻繁項(xiàng)集的時(shí)候，沒有產(chǎn)生大量的候選項(xiàng)集，這樣就省去了連接和剪枝的操作，算法的效率顯著提高。圖1給出了在窗口大小，的前提下，WFP-SW算法和FIM-SW算法隨事務(wù)數(shù)變化的挖掘時(shí)間比較；圖2給出了在，挖掘五萬條事務(wù)的前提下，WFP-SW算法和FIM-SW算法隨支持度變化的挖掘時(shí)間比較。

5 結(jié)論（Conclusion）

本文提出了基于滑動(dòng)窗口模型的數(shù)據(jù)流加權(quán)頻繁模式挖掘算法WFP-SW，該算法只需掃描一次數(shù)據(jù)流，數(shù)據(jù)存儲(chǔ)采用的是矩陣數(shù)據(jù)結(jié)構(gòu)，通過矩陣之間的相關(guān)操作來產(chǎn)生加權(quán)頻繁模式。同時(shí)該算法在產(chǎn)生加權(quán)頻繁模式的時(shí)候不產(chǎn)生冗余模式，通過與算法FIM-SW的對(duì)比，驗(yàn)證了WFP-SW算法具有更高的效率。

參考文獻(xiàn)（References）

[1] G.Lee，U.Yun，H.Ryang.Mining Weighted Erasable Patterns by Using Underestimated Constraint-based Pruning Technique[J].Intell.Fuzzy Syst.，2015，28（3）：1145-1157.

[2] G.Lee，U.Yun，K.H.Ryu.Sliding Window Based Weighted Maximal Frequent Pattern Mining Over Data Streams，Expert Syst.Appl，2014，41（2）：694-708.

[3] U.Yun，G.Pyun，E.Yoon.Efficient Mining of Robust Closed Weighted Sequential Patterns Without Information Loss[J].International Journal on Artificial Intelligence Tools，2015，24（1）：01-28.

[4] 張晴，高廣銀.賈波數(shù)據(jù)挖掘技術(shù)在超市營銷系統(tǒng)中的應(yīng)用[J].軟件工程，2016，19（5）：35-38.

[5] 孫黎明.探索軟件工程數(shù)據(jù)挖掘技術(shù)[J].軟件工程，2015，18（5）：

16-17.

[6] FENG Tao，MURTAGH F，F(xiàn)ARID M.Weighted Association Rule Mining Using weighted support and significance framework[C].Proc.of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM Press，2003：661-666.

[7] 徐嘉莉，陳佳.基于向量的數(shù)據(jù)流滑動(dòng)窗口中最大頻繁項(xiàng)集挖掘[J].計(jì)算機(jī)應(yīng)用研究，2012，29（3）：837-840.

[8] AGRAWAL R，SRIKANT R.Fast Algorithms for Mining Association Rules[C].Proc of the 20th International Conference on Very Large Database.San Francisco：Morgan Kaufmann Publishers，1994：487-499.

[9] 徐建民，郝麗維，王煜.數(shù)據(jù)流頻繁項(xiàng)集的快速挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（34）：142-144.

作者簡介：

馬連燈（1992-），男，碩士，碩士生.研究領(lǐng)域：大數(shù)據(jù)，數(shù)據(jù)挖掘.

王占剛（1975-），男，博士，副教授.研究領(lǐng)域：大數(shù)據(jù)，計(jì)算機(jī)檢測應(yīng)用，計(jì)算機(jī)網(wǎng)絡(luò)安全.