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

石秀金 蔡藝松

摘 要： 相對于傳統的頻繁模式挖掘，加權頻繁模式挖掘能發現更有價值的模式信息。針對數據流中的數據只能一次掃描，本文提出了一種基于滑動窗口模型的數據流加權頻繁模式挖掘方法WFP-SW（Sliding Window based Weighted Frequent Pattern minig），算法采用WE-tree（Weighted Enumeration Tree）存儲模式和事務信息，利用虛權支持度維持模式的向下閉合特性，同時獲取臨界頻繁模式。對臨界頻繁模式進一步計算其加權支持度獲取加權頻繁模式，使得計算更新模式更加便捷。實驗結果顯示算法具有較高的挖掘效率并且所需的內存更少。

關鍵詞： 事務數據流；數據流挖掘；加權頻繁模式挖掘；滑動窗口模型

Abstract：Relative to traditional frequent-pattern mining the weighted frequent-pattern mining can find more valuable pattern information. For the data in the data stream only scanned for one time this paper proposes a data flow weighted frequent-pattern mining method based on sliding window. The algorithm adopts WE-tree storage mode and transaction information and utilizes the virtual weight support to maintain the downward closing characteristic of the mode meanwhile obtains the critical frequent mode. Furthermore the research uses the critical frequent mode to calculate the weighted support of the mode so as to make the computing mode and updating mode more convenient. Experimental results show that the algorithm is efficient and requires less memory.

Key words： transaction data flow；data stream mining；weighted frequent-pattern mining；sliding window model

引言

頻繁模式挖掘在數據挖掘和知識發現領域扮演了重要的角色[1]，但是卻并未重點關注事務中不同項的不同重要性[2]。考慮到現實環境中不同的項有不同的權重，為了挖掘更加重要的模式，學界提出了加權頻繁模式挖掘算法。例如，貴重的首飾被購買的頻度比一只筆低得多，因此僅僅通過頻度去挖掘很容易使得高權重的模式發生丟失，而加權頻繁模式挖掘的推出即解決了這一問題。

在加權頻繁模式挖掘領域，根據加權對象不同，可以將加權頻繁模式挖掘方法分為2類。研究可得分類內容如下：

（1）項的權重信息。在挖掘過程中，通過使用項集的加權支持度代替傳統模式挖掘算法的頻繁支持度確定加權頻繁模式。此類算法從WFIM[3]開始，擴展到許多不同的應用領域中，例如序列模式挖掘[4-5]、流數據挖掘[6]、最大模式挖掘[7-8]，閉合模式挖掘[9]等。其中，WFIM是使用基于FP-tree結構的深度優先搜索（DFS）算法，需要2次掃描數據庫，并通過計算每個項集的平均權重獲得加權頻繁項集。而WFP-SW算法采用廣度優先的搜索方式僅需掃描一遍數據，在獲得下層節點的同時剔除非加權頻繁模式，極大地改善了內存的使用情況。

（2）效用模式挖掘[10 -11]，考慮到了項的權重和數量。效用模式挖掘根據不同的挖掘形式可進一步劃分為增量效用模式挖掘[12]、流效用挖掘[13]和最大效用模式挖掘[14]等。

基于此，本文提出了一種基于滑動窗口的數據流加權頻繁模式挖掘算法WFP-SW。該算法能夠在數據流環境中僅用一次掃描來發現加權頻繁模式。除了零售市場數據，算法還可以用于挖掘加權網絡的遍歷路徑。眾所皆知，不同的網站有不同的重要性，本算法可以發現網絡遍歷路徑的加權頻繁信息。此外，在生物醫學和DNA數據分析領域[15]，不同的基因有不同的權重，通過發現加權后的基因序列組合模式，可以檢測疾病并根據標準確定相應的藥物。其它的應用包括Web導航信息處理[16]、股票數據分析[17]等。

算法采用滑動窗口模型挖掘最近窗口范圍內的事務，并采用枚舉樹WE-tree結構以更好地維持滑動窗口中的事務從而快速計算項集的加權支持度。算法僅需要少量的內存用于存儲窗口中的內容以及加權頻繁項集，還能解決概念漂移現象。實驗結果顯示算法具有較高的挖掘效率，并且僅需更少的內存。

1 基本概念

當模式P的加權支持度大于等于最小閾值時，稱為加權頻繁模式。

定義6 虛權支持度 每個項集的頻度與最大權重的乘積稱為虛權支持度。

由模式挖掘中的向下閉合特性可以推知：如果一個模式是不頻繁的，那么其所有的超集模式也是不頻繁的。然而，WFIM算法顯示出加權頻繁模式挖掘算法面臨的主要問題是，加權頻繁模式挖掘將失去向下閉合特性。WFIM通過把每個項集的頻度與最大權重相乘以維持這個特性。WFP-SW算法采用WE-tree結構，為了防止在剪枝過程中出現信息丟失，需要用到向下閉合特性。在算法中，虛權不僅能維持模式的向下閉合特性，在計算加權頻繁模式時還能剔除許多非加權頻繁項，減少WE-tree的維護代價。

2 WFP-SW算法

在本部分，將對WFP-SW算法進行全面詳盡論述。算法通過一種高效率的數據結構WE-tree存儲頻繁模式以及事務信息，使得計算更新模式更加便捷，并且對內存的消耗更小。

2.1 計算加權支持度

在WFP-SW算法中，模式的支持度通過計算包含此模式的事務ID的個數，再通過公式（1）求出模式的權重，進而得出加權支持度。以圖1為例，在窗口SW1中有3個事務包含項A，即A的支持度為3，假設權重為0.6，則A的加權支持度為1.8。而項集的支持度則通過事務的交集獲得。如，T2、T3的交集為AD，則AD支持度為2。同樣的，K項集支持度通過計算K-1項集的交集獲得。

2.2 構建枚舉樹

算法采用WE-tree數據結構，用于存儲項集信息以及模式的加權支持度。樹的每個節點代表一個加權頻繁或者臨界加權頻繁項集（小于虛權、大于實際權重），WE-tree存儲維護每個項集的Tid列表，并據此得出項集的加權支持度。表1顯示了每個項的Tid列表，W是每個項的權重（項的權重由實際應用環境決定，如在挖掘零售市場數據時，項權重則由商品價值具體決定）。例如，項A在SW1的事務列表是1、2、3，加權支持度為1.8。

圖2即直觀給出了第一個窗口的WE-tree存儲結果。樹的第一層存儲每個項及其對應的Tid列表、加權支持度。其中，虛線矩形中的數值是項集的虛權支持度，以維持向下閉合特性，防止項集被過早舍棄引起數據丟失。Hash Table用來存儲加權頻繁項集。

假設最小加權支持度為1。則樹的第一層中，只有A（Ws為1.8）和B（Ws為1）是加權頻繁項集。而節點D加權支持度為0.8，但是其虛權為1.2，因此不能舍棄，否則模式AD將會丟失。并且在窗口滑動過程中，第一層的單項節點的數據信息需要用來求得下層的頻繁項集，無論頻繁與否，不剪枝。

當窗口初始化時，便能得到每一個項的Tid列表，由此構建WE-tree。接著通過遞歸的方式將第K-1層的Tid列表相交得到K層節點。假若節點的虛權大于最小加權支持度，便插入成為一個新的節點，否則將其忽略。如圖2所示，通過將節點A、D相交得到節點AD的虛權為1.2，模式AD插入為一個新的節點，求得加權支持度為1，插入Hash表。當獲得窗口中所有的加權頻繁項集后，隨著窗口滑動，第一層節點將被更新。WE-tree創建過程的偽代碼可詳見如下：

2.3 剪枝過程

當窗口滑動時，舊事務需要被刪除，樹節點中需要將舊事務的Tid去除，而其它的Tid保持不變。當刪除舊事務后，如果項集仍然是加權頻繁，只更新支持度信息；如果項集不再加權頻繁就需要從哈希表中刪除；如果項集的虛權小于最小支持度，將節點從樹中刪除。針對圖2，可得在刪除事務以后的狀態如圖3所示。節點A支持度衰減為1.2。研究中，剪枝過程的偽代碼設計可描述為：

2.4 添加新事務

當新事務到達時，新事務的Tid需要添加到對應的節點當中，更新加權支持度和虛權。這個過程和構建WE-tree相似，即通過遞歸的方式獲得更高層級的模式信息。綜上可得，圖3添加T5后的存儲狀態則如圖4所示。

至此，可得添加過程偽代碼的研究表述如下：

3 實驗結果與分析

算法的實驗環境為：Window7操作系統，算法用C語言實現，在Visual C++ 6.0上運行。實驗采用IBM模擬數據生成器產生數據，模擬數據流包括T15I10D1000K、T20I10D1000K、T25I10D1000K、T25I6D1000K和T25I15D1000K。其中，T15I10D1000K表示事務的平均長度為15，平均模式長度為10，數據流事務個數為100萬條。

圖5設計提供了在不同的滑動窗口大小下，算法在不同的模擬數據流上的最大內存消耗和執行時間。從圖5（a）中可以看出，滑動窗口大小和內存消耗成正比關系。原因是當窗口增大時，WE-tree需要維持的Tid也成倍增加；而在同樣的模式長度和窗口下，事務長度的變化對內存影響并不明顯；當平均模式長度變大時，WE-tree的深度隨之增加，即樹節點增多，內存消耗也表現出上升態勢。圖5（b）顯示的是算法在不同窗口大小下不同數據流的執行時間。由于算法采用交集的方式（時間復雜度O（n））求得更高層模式信息，窗口對執行時間的影響基本呈線性增長。而由于事務長度的增加會導致交集運算次數也隨即增多，對時間的影響較大，平均模式長度影響較小，因而算法更適合挖掘稀疏或者長模式數據集。

實驗將WFP-SW與WIT-FWI[18]在不同最小閾值下的執行情況及其挖掘效果展開了測試對比，實驗數據流采用T10I5D1000K。如圖6所示，實驗結果表明，算法WFP-SW相較于WIT-FWI在執行時間和內存消耗上都有更好的表現。

算法WIT-FWI采用WIT-tree的數據結構需要存儲全部的事務信息，在獲取頻繁模式信息時將發生多次遞歸，實現過程中即需要消耗更多的處理時間。而算法WFP-SW在挖掘過程中，WE-tree僅需存儲加權頻繁模式信息，對于不頻繁模式則免于存儲，因此所需的內存更少。同時，圖7又研究指出了WFP-SW算法的查全率（Recall）和查準率（Precision）都要優勝于WIT-FWI算法的方針結果。

4 結束語

已有研究表明，僅僅通過模式的頻度挖掘會引起數據丟失，而數據流加權頻繁模式挖掘能提煉得到更富有價值的信息。為此，本文提出了一種基于滑動窗口模型的數據流加權頻繁模式挖掘算法WFP-SW。算法采用枚舉樹WE-tree結構通過維護Tid列表計算模式加權支持度，列表間的交集獲得更高層的模式信息；通過虛權維持WE-tree的向下閉合特性防止信息丟失。大量的仿真實驗表明，WFP-SW算法有較低的運行時間，并且所需的內存也將會更少。

參考文獻

[1] MEMAR M DEYPIR M SADREDDINI M H et al. An efficient frequent itemset mining method over high-speed data streams[J]. Computer Journal 2012 55（11）：1357-1366.

[2] LIN J C W GAN Wensheng FOURNIER-VIGER P et al. Weighted frequent itemset mining over uncertain databases[J]. Applied Intelligence 2016 44（1）：232-250.

[3] YUN U. On pushing weight constraints deeply into frequent itemset mining[J]. Intelligent Data Analysis 2009 13（2）：359-383.

[4] [WB]TANBEER S K AHMED C F JEONG B S et al. Sliding window-based frequent pattern mining over data streams[J].Infor[DW]mation Sciences： An International Journal 2009 179（22）：3843-3865.

[5] YUN U PYUN G YOON E. Efficient mining of robust closed weighted sequential patterns without information loss[J]. International Journal on Artificial Intelligence Tools 2015 24（1）：1550007（1）-1550007（28）.

[6] 李國徽，陳輝. 挖掘數據流任意滑動時間窗口內頻繁模式[J]. 軟件學報，2008 19（19）： 2585-2596.

[7] YUN U LEE G RYU K H. Mining maximal frequent patterns by considering weight conditions over data streams[J]. Knowledge-Based Systems 2014 55（55）：49-65.

[8] WOO H J LEE W S. estMax： Tracing maximal frequent item sets instantly over online transactional data streams[J]. IEEE Transactions on Knowledge & Data Engineering 2009 21（10）：1418-1431.

[9] 韓蔭，王志海，原繼東. 一種基于時間衰減模型的數據流閉合模式挖掘方法[J]. 計算機學報，2015 38（7）： 1473-1483.

[10]RYANG H YUN U RYU K H. Discovering high utility itemsets with multiple minimum supports[J]. Intelligent Data Analysis 2014 18（6）：1027-1047.

[11]SHIE B E HSIAO H F TSENG V S et al. Mining high utility mobile sequential patterns in mobile commerce environments[M] //YU J X KIM M H UNLAND R. Database Systems for Advanced Applications. DASFAA 2011. Lecture Notes in Computer Science Berlin/Heidelberg：Springer，2011，6587：224-238.

[12]YUN U RYANG H. Incremental high utility pattern mining with static and dynamic databases[J]. Applied Intelligence 2015 42（2）：323-352.

[13]AHMED C F TANBEER S K JEONG B S et al. Interactive mining of high utility patterns over data streams[J]. Expert Systems with Applications 2012 39（15）：11979-11991.

[14]LIN M Y TU T F HSUEH S C. High utility pattern mining using the maximal itemset property and lexicographic tree structures[J]. Information Sciences 2012 215（23）：1-14.

[15]SUN Hong BIE T D STORMS V et al. ModuleDigger： An itemset mining framework for the detection of cis-regulatory modules[J]. BMC Bioinformatics 2009 10 （S1）：S30.

[16]KIM Y S. Streaming association rule （SAR） mining with a weighted order-dependent representation of Web navigation patterns[J]. Expert Systems with Applications 2009 36（4）：7933-7946.

[17]BARALIS E CAGLIERO L CARZA P. Planning stock portfolios by means of weighted frequent itemsets[J]. Expert System with Applications，2017 86（15）： 1-17.

[18]VO B COENEN F LE B. A new method for mining frequent weighted itemsets based on WIT-trees[J]. Expert Systems with Applications 2013 40（4）： 1256-1264.