馬連燈 王占剛

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

關鍵詞：數(shù)據(jù)流；滑動窗口；加權頻繁模式；矩陣

中圖分類號：TP311.13 文獻標識碼：A

1 引言（Introduction）

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

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

2 基本概念（The basic concept）

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

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

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

定義4：設加權最小支持度為，如果項集是頻繁項集，則加權支持度大于或等于，即。

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

定義6：全序關系。根據(jù)字母在字典中的順序，如果小于，則有，比如[7]。同理，可以給出項集在字典中的順序為，比如。

在本文中，假設全部項都是依照全序關系排序的。

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

algorithm）

3.1 矩陣的構造

（1）事務矩陣的構造

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

（2）二項集矩陣的構造

設項集中有個項，那么構造的加權二項集矩陣是的二項集矩陣，同時初始化矩陣中的所有元素為0。對于加權頻繁項集中的兩個項和，如果，讓中的第行與第行參與邏輯與運算，若支持度不小于，則項集就是加權頻繁項集，同時把的值設置成1，反之，把它的值設置為0。

3.2 WFP-SW算法的基本思想

加權頻繁項集的產(chǎn)生：項集是通過對加權頻繁項集的擴展產(chǎn)生的。設是加權頻繁項集，在二項集矩陣中，若，且，則就可以擴充為項集。同時在矩陣中，讓對應的個項的行做邏輯與運算，如果得到的結果不小于，則是加權頻繁項集。重復這個操作，當沒有新的項集產(chǎn)生的時候，結束算法。

3.3 WFP-SW算法描述

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

該算法的偽代碼如下：

輸入：數(shù)據(jù)流事務，滑動窗口大小，每個項目權重，用戶設定的最小加權支持度；

輸出：加權頻繁模式；

滑動窗口中的每個事務

//初始窗口階段

{

}

//滑動窗口階段

對矩陣中第列的值進行更新，其他列的值不變

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

構造二項集矩陣

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

{

擴展為項集

；

}

4 實驗結果及分析（The experimental results and

analysis）

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

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

5 結論（Conclusion）

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

參考文獻（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ù)挖掘技術在超市營銷系統(tǒng)中的應用[J].軟件工程，2016，19（5）：35-38.

[5] 孫黎明.探索軟件工程數(shù)據(jù)挖掘技術[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ù)流滑動窗口中最大頻繁項集挖掘[J].計算機應用研究，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ù)流頻繁項集的快速挖掘算法[J].計算機工程與應用，2008，44（34）：142-144.

作者簡介：

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

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