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

1、基于滑動窗口模型的數(shù)據(jù)流加權頻繁模式挖掘算法1 引言(Introduction)加權頻繁模式與傳統(tǒng)的頻繁模式挖掘是不同的，它不僅取決于項集出現(xiàn)的次數(shù)，而且要考慮到數(shù)據(jù)庫中項集重要性。在很多實際的應用中，不同的數(shù)據(jù)項的重要程度是不同的。例如，在零售市場分析的時候，雖然貴重的商品沒有在事務數(shù)據(jù)庫中出現(xiàn)非常多的次數(shù)，但是它們卻貢獻了很大一部分的收入。所以，加權頻繁模式挖掘比傳統(tǒng)的頻繁模式挖掘更能在現(xiàn)實世界中發(fā)揮更實際的作用。本文提出了基于滑動窗口模型的數(shù)據(jù)流加權頻繁模式挖掘方法WFP-SW,該算法中數(shù)據(jù)存儲采用的是矩陣數(shù)據(jù)結構，通過矩陣之間的相關操作得到加權頻繁模式。實驗結果顯示，該算法在產(chǎn)生加權頻

2、繁模式的時候不產(chǎn)生冗余模式，比傳統(tǒng)的加權頻繁模式挖掘算法有更好的效率。2 基本概念(The basic concept)在本文中，假設全部項都是依照全序關系排序的。3 WFP-SW原理與算法(WFP-SW principle and algorithm)3.1 矩陣的構造(1)事務矩陣的構造4 實驗結果及分析(The experimental results and analysis)本文中算法采用的實驗平臺：Windows 7操作系統(tǒng)，Eclipse開發(fā)工具，編程語言是java。采用IBM data generator生成的數(shù)據(jù)作為實驗所用的數(shù)據(jù)。本文采用稠密數(shù)據(jù)集T40I10D100K，其

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

4、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 Pruni

5、ng Technique.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

6、Loss.International Journal on Artificial Intelligence Tools,2015,24(1):01-28.【4】 張晴,高廣銀.賈波數(shù)據(jù)挖掘技術在超市營銷系統(tǒng)中的應用.軟件工程,2016,19(5):35-38.【5】 孫黎明.探索軟件工程數(shù)據(jù)挖掘技術.軟件工程,2015,18(5):16-17.【6】 FENG Tao,MURTAGH F,FARID M.Weighted Association Rule Mining Using weighted support and significance framework.Proc.of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM Press,2003:661-666.【7】 徐嘉莉,陳佳.基于向量的數(shù)據(jù)流滑動窗口中最大頻繁項集挖掘.計算機應用研究,2012,29(3):837-840. AGRAWAL R,SRIKANT R.Fast Algorithms for Mining Association Rules.Proc of the 20th International Conference on Very Large Database.