基于滑動窗口模型的數據流加權頻繁模式挖掘算法

馬連燈 王占剛

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

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

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

1 引言（Introduction）

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

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

2 基本概念（The basic concept）

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

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

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

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

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

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

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

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

algorithm）

3.1 矩陣的構造

（1）事務矩陣的構造

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

（2）二項集矩陣的構造

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

3.2 WFP-SW算法的基本思想

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

3.3 WFP-SW算法描述

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

該算法的偽代碼如下：

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

輸出：加權頻繁模式；

滑動窗口中的每個事務

//初始窗口階段

{

}

//滑動窗口階段

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

掃描矩陣中的前行，產生

構造二項集矩陣

//產生加權頻繁模式階段，是頻繁項集

{

擴展為項集

；

}

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

analysis）

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

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

5 結論（Conclusion）

本文提出了基于滑動窗口模型的數據流加權頻繁模式挖掘算法WFP-SW，該算法只需掃描一次數據流，數據存儲采用的是矩陣數據結構，通過矩陣之間的相關操作來產生加權頻繁模式。同時該算法在產生加權頻繁模式的時候不產生冗余模式，通過與算法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] 張晴，高廣銀.賈波數據挖掘技術在超市營銷系統中的應用[J].軟件工程，2016，19（5）：35-38.

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

16-17.

[6] FENG Tao，MURTAGH F，FARID 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] 徐嘉莉，陳佳.基于向量的數據流滑動窗口中最大頻繁項集挖掘[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] 徐建民，郝麗維，王煜.數據流頻繁項集的快速挖掘算法[J].計算機工程與應用，2008，44（34）：142-144.

作者簡介：

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

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