石秀金 蔡藝松

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

關(guān)鍵詞： 事務(wù)數(shù)據(jù)流；數(shù)據(jù)流挖掘；加權(quán)頻繁模式挖掘；滑動(dòng)窗口模型

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

引言

頻繁模式挖掘在數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)領(lǐng)域扮演了重要的角色[1]，但是卻并未重點(diǎn)關(guān)注事務(wù)中不同項(xiàng)的不同重要性[2]?？紤]到現(xiàn)實(shí)環(huán)境中不同的項(xiàng)有不同的權(quán)重，為了挖掘更加重要的模式，學(xué)界提出了加權(quán)頻繁模式挖掘算法。例如，貴重的首飾被購(gòu)買(mǎi)的頻度比一只筆低得多，因此僅僅通過(guò)頻度去挖掘很容易使得高權(quán)重的模式發(fā)生丟失，而加權(quán)頻繁模式挖掘的推出即解決了這一問(wèn)題。

在加權(quán)頻繁模式挖掘領(lǐng)域，根據(jù)加權(quán)對(duì)象不同，可以將加權(quán)頻繁模式挖掘方法分為2類。研究可得分類內(nèi)容如下：

（1）項(xiàng)的權(quán)重信息。在挖掘過(guò)程中，通過(guò)使用項(xiàng)集的加權(quán)支持度代替?zhèn)鹘y(tǒng)模式挖掘算法的頻繁支持度確定加權(quán)頻繁模式。此類算法從WFIM[3]開(kāi)始，擴(kuò)展到許多不同的應(yīng)用領(lǐng)域中，例如序列模式挖掘[4-5]、流數(shù)據(jù)挖掘[6]、最大模式挖掘[7-8]，閉合模式挖掘[9]等。其中，WFIM是使用基于FP-tree結(jié)構(gòu)的深度優(yōu)先搜索（DFS）算法，需要2次掃描數(shù)據(jù)庫(kù)，并通過(guò)計(jì)算每個(gè)項(xiàng)集的平均權(quán)重獲得加權(quán)頻繁項(xiàng)集。而WFP-SW算法采用廣度優(yōu)先的搜索方式僅需掃描一遍數(shù)據(jù)，在獲得下層節(jié)點(diǎn)的同時(shí)剔除非加權(quán)頻繁模式，極大地改善了內(nèi)存的使用情況。

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

基于此，本文提出了一種基于滑動(dòng)窗口的數(shù)據(jù)流加權(quán)頻繁模式挖掘算法WFP-SW。該算法能夠在數(shù)據(jù)流環(huán)境中僅用一次掃描來(lái)發(fā)現(xiàn)加權(quán)頻繁模式。除了零售市場(chǎng)數(shù)據(jù)，算法還可以用于挖掘加權(quán)網(wǎng)絡(luò)的遍歷路徑。眾所皆知，不同的網(wǎng)站有不同的重要性，本算法可以發(fā)現(xiàn)網(wǎng)絡(luò)遍歷路徑的加權(quán)頻繁信息。此外，在生物醫(yī)學(xué)和DNA數(shù)據(jù)分析領(lǐng)域[15]，不同的基因有不同的權(quán)重，通過(guò)發(fā)現(xiàn)加權(quán)后的基因序列組合模式，可以檢測(cè)疾病并根據(jù)標(biāo)準(zhǔn)確定相應(yīng)的藥物。其它的應(yīng)用包括Web導(dǎo)航信息處理[16]、股票數(shù)據(jù)分析[17]等。

算法采用滑動(dòng)窗口模型挖掘最近窗口范圍內(nèi)的事務(wù)，并采用枚舉樹(shù)WE-tree結(jié)構(gòu)以更好地維持滑動(dòng)窗口中的事務(wù)從而快速計(jì)算項(xiàng)集的加權(quán)支持度。算法僅需要少量的內(nèi)存用于存儲(chǔ)窗口中的內(nèi)容以及加權(quán)頻繁項(xiàng)集，還能解決概念漂移現(xiàn)象。實(shí)驗(yàn)結(jié)果顯示算法具有較高的挖掘效率，并且僅需更少的內(nèi)存。

1 基本概念

當(dāng)模式P的加權(quán)支持度大于等于最小閾值時(shí)，稱為加權(quán)頻繁模式。

定義6 虛權(quán)支持度 每個(gè)項(xiàng)集的頻度與最大權(quán)重的乘積稱為虛權(quán)支持度。

由模式挖掘中的向下閉合特性可以推知：如果一個(gè)模式是不頻繁的，那么其所有的超集模式也是不頻繁的。然而，WFIM算法顯示出加權(quán)頻繁模式挖掘算法面臨的主要問(wèn)題是，加權(quán)頻繁模式挖掘?qū)⑹ハ蛳麻]合特性。WFIM通過(guò)把每個(gè)項(xiàng)集的頻度與最大權(quán)重相乘以維持這個(gè)特性。WFP-SW算法采用WE-tree結(jié)構(gòu)，為了防止在剪枝過(guò)程中出現(xiàn)信息丟失，需要用到向下閉合特性。在算法中，虛權(quán)不僅能維持模式的向下閉合特性，在計(jì)算加權(quán)頻繁模式時(shí)還能剔除許多非加權(quán)頻繁項(xiàng)，減少WE-tree的維護(hù)代價(jià)。

2 WFP-SW算法

在本部分，將對(duì)WFP-SW算法進(jìn)行全面詳盡論述。算法通過(guò)一種高效率的數(shù)據(jù)結(jié)構(gòu)WE-tree存儲(chǔ)頻繁模式以及事務(wù)信息，使得計(jì)算更新模式更加便捷，并且對(duì)內(nèi)存的消耗更小。

2.1 計(jì)算加權(quán)支持度

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

2.2 構(gòu)建枚舉樹(shù)

算法采用WE-tree數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)項(xiàng)集信息以及模式的加權(quán)支持度。樹(shù)的每個(gè)節(jié)點(diǎn)代表一個(gè)加權(quán)頻繁或者臨界加權(quán)頻繁項(xiàng)集（小于虛權(quán)、大于實(shí)際權(quán)重），WE-tree存儲(chǔ)維護(hù)每個(gè)項(xiàng)集的Tid列表，并據(jù)此得出項(xiàng)集的加權(quán)支持度。表1顯示了每個(gè)項(xiàng)的Tid列表，W是每個(gè)項(xiàng)的權(quán)重（項(xiàng)的權(quán)重由實(shí)際應(yīng)用環(huán)境決定，如在挖掘零售市場(chǎng)數(shù)據(jù)時(shí)，項(xiàng)權(quán)重則由商品價(jià)值具體決定）。例如，項(xiàng)A在SW1的事務(wù)列表是1、2、3，加權(quán)支持度為1.8。

圖2即直觀給出了第一個(gè)窗口的WE-tree存儲(chǔ)結(jié)果。樹(shù)的第一層存儲(chǔ)每個(gè)項(xiàng)及其對(duì)應(yīng)的Tid列表、加權(quán)支持度。其中，虛線矩形中的數(shù)值是項(xiàng)集的虛權(quán)支持度，以維持向下閉合特性，防止項(xiàng)集被過(guò)早舍棄引起數(shù)據(jù)丟失。Hash Table用來(lái)存儲(chǔ)加權(quán)頻繁項(xiàng)集。

假設(shè)最小加權(quán)支持度為1。則樹(shù)的第一層中，只有A（Ws為1.8）和B（Ws為1）是加權(quán)頻繁項(xiàng)集。而節(jié)點(diǎn)D加權(quán)支持度為0.8，但是其虛權(quán)為1.2，因此不能舍棄，否則模式AD將會(huì)丟失。并且在窗口滑動(dòng)過(guò)程中，第一層的單項(xiàng)節(jié)點(diǎn)的數(shù)據(jù)信息需要用來(lái)求得下層的頻繁項(xiàng)集，無(wú)論頻繁與否，不剪枝。

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

2.3 剪枝過(guò)程

當(dāng)窗口滑動(dòng)時(shí)，舊事務(wù)需要被刪除，樹(shù)節(jié)點(diǎn)中需要將舊事務(wù)的Tid去除，而其它的Tid保持不變。當(dāng)刪除舊事務(wù)后，如果項(xiàng)集仍然是加權(quán)頻繁，只更新支持度信息；如果項(xiàng)集不再加權(quán)頻繁就需要從哈希表中刪除；如果項(xiàng)集的虛權(quán)小于最小支持度，將節(jié)點(diǎn)從樹(shù)中刪除。針對(duì)圖2，可得在刪除事務(wù)以后的狀態(tài)如圖3所示。節(jié)點(diǎn)A支持度衰減為1.2。研究中，剪枝過(guò)程的偽代碼設(shè)計(jì)可描述為：

2.4 添加新事務(wù)

當(dāng)新事務(wù)到達(dá)時(shí)，新事務(wù)的Tid需要添加到對(duì)應(yīng)的節(jié)點(diǎn)當(dāng)中，更新加權(quán)支持度和虛權(quán)。這個(gè)過(guò)程和構(gòu)建WE-tree相似，即通過(guò)遞歸的方式獲得更高層級(jí)的模式信息。綜上可得，圖3添加T5后的存儲(chǔ)狀態(tài)則如圖4所示。

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

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

算法的實(shí)驗(yàn)環(huán)境為：Window7操作系統(tǒng)，算法用C語(yǔ)言實(shí)現(xiàn)，在Visual C++ 6.0上運(yùn)行。實(shí)驗(yàn)采用IBM模擬數(shù)據(jù)生成器產(chǎn)生數(shù)據(jù)，模擬數(shù)據(jù)流包括T15I10D1000K、T20I10D1000K、T25I10D1000K、T25I6D1000K和T25I15D1000K。其中，T15I10D1000K表示事務(wù)的平均長(zhǎng)度為15，平均模式長(zhǎng)度為10，數(shù)據(jù)流事務(wù)個(gè)數(shù)為100萬(wàn)條。

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

實(shí)驗(yàn)將WFP-SW與WIT-FWI[18]在不同最小閾值下的執(zhí)行情況及其挖掘效果展開(kāi)了測(cè)試對(duì)比，實(shí)驗(yàn)數(shù)據(jù)流采用T10I5D1000K。如圖6所示，實(shí)驗(yàn)結(jié)果表明，算法WFP-SW相較于WIT-FWI在執(zhí)行時(shí)間和內(nèi)存消耗上都有更好的表現(xiàn)。

算法WIT-FWI采用WIT-tree的數(shù)據(jù)結(jié)構(gòu)需要存儲(chǔ)全部的事務(wù)信息，在獲取頻繁模式信息時(shí)將發(fā)生多次遞歸，實(shí)現(xiàn)過(guò)程中即需要消耗更多的處理時(shí)間。而算法WFP-SW在挖掘過(guò)程中，WE-tree僅需存儲(chǔ)加權(quán)頻繁模式信息，對(duì)于不頻繁模式則免于存儲(chǔ)，因此所需的內(nèi)存更少。同時(shí)，圖7又研究指出了WFP-SW算法的查全率（Recall）和查準(zhǔn)率（Precision）都要優(yōu)勝于WIT-FWI算法的方針結(jié)果。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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] 李國(guó)徽，陳輝. 挖掘數(shù)據(jù)流任意滑動(dòng)時(shí)間窗口內(nèi)頻繁模式[J]. 軟件學(xué)報(bào)，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] 韓蔭，王志海，原繼東. 一種基于時(shí)間衰減模型的數(shù)據(jù)流閉合模式挖掘方法[J]. 計(jì)算機(jī)學(xué)報(bào)，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.