1.东北大学 信息科学与工程学院, 辽宁 沈阳110819;
2.东北大学 医学影像计算教育部重点实验室, 辽宁 沈阳 110819
收稿日期: 2015-05-11
基金项目: 国家自然科学基金资助项目(60903159，61173153，61402096)； 中央高校基本科研业务费专项资金资助项目(N110818001，N100218001，N130504007，N120104001)； 沈阳市科技计划项目(1091176-1-00)； 国家高技术研究发展计划项目(2015AA016005).
作者简介: 王少鹏(1984-)，男，内蒙古乌兰察布人，东北大学博士研究生;
赵 宏(1954－)，男，辽宁沈阳人，东北大学教授，博士生导师。
摘要: 针对当前关于数据流加权最大频繁项集WMFI(weighted maximal frequent itemsets)的研究无法有效地处理频繁阈值和加权频繁阈值不一致情况下WMFI的挖掘问题，提出了完全加权最大频繁项集FWMFI(full weighted maximal frequent itemsets)的概念.为了减少naive算法在处理滑动窗口下完全加权最大频繁项集挖掘时存在的冗余运算，提出了FWMFI-SW(FWMFI mining based on sliding window over data stream)算法.所提出的算法通过基于频繁约束条件的优化策略减少了naive算法中MaxW优化策略的无效调用次数；采用编辑距离比率作为WMFP-SW-tree的重构判别函数，可以有效减少该树的重构次数.实验结果表明FWMFI-SW算法是有效的，且比naive算法更有时间优势.
关键词：数据流滑动窗口编辑距离比率加权最大频繁项集重构判别函数
Mining Full Weighted Maximal Frequent Itemsets Based on Sliding Window over Data Stream
WANG Shao-peng1, WEN Ying-you1,2, ZHAO Hong1,2
1.School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2.Key Laboratory of Medical Image Computing, Ministry of Education, Northeastern University, Shenyang 110819, China
Abstract: Aiming at the problem that none of current researches on the WMFI (weighted maximal frequent itemsets) over data stream emphasizes the WMFI mining on the condition that the frequent threshold is not equal with the weighted frequent threshold, the concept of FWMFI (full weighted maximal frequent itemsets) was firstly promoted in this work. In order to reduce redundant operations existing in the naive algorithm which is used to handle the FWMFI mining based on sliding window over data stream, the FWMFI-SW (FWMFI mining based on sliding window over data stream) algorithm was proposed. The mining optimization strategy was adopted based on the frequent character to reduce the unnecessary call about the MaxW optimization strategy in the naive algorithm. In addition, the edit distance ratio was taken as reconstruction judge function to decide whether the updated WMFP-SW-tree should be reconstructed as the window slides. The extensive experiments showed that the FWMFI-SW algorithm is effective , and outperforms the naive algorithm in running time.
Key Words: data streamsliding windowedit distance ratioweighted maximal frequent itemsetsreconstruction judge function
挖掘数据流环境下的频繁项集是数据流挖掘领域中的重要内容[1-4].在当前有关数据流频繁项集挖掘的研究中，挖掘最大频繁项集比挖掘基本频繁项集和频繁闭项集更有效率，因为最大频繁项集个数更少，且隐含了所有频繁项集[5].但这类研究没有区分最大频繁项集中成员的重要性.针对该问题产生了加权最大频繁项集[6-9].Yun等[6]首次研究了数据流加权最大频繁项集挖掘问题，使用了界标窗口模型；Lee等[7]首次讨论了滑动窗口下数据流加权最大频繁项集挖掘问题，提出了WMFP-SW算法.
但这些研究存在一个共同问题，即项集加权频繁性与基本频繁性都基于同一个阈值判别，而实际中它们的判别阈值并不经常相同.为解决这个问题，本文将频繁条件从原有加权频繁项集条件中独立出来，给出完全加权最大频繁项集(FWMFI，full weighted maximal frequent itemsets)概念；接着研究了滑动窗口下该项集挖掘问题.为减少naive算法的冗余运算，提出了FWMFI-SW (full weighted maximal frequent itemsets mining based on sliding window over data stream)算法，最后通过实验证明了算法的有效性.
1 相关知识WMFP-SW算法是Lee等提出的首个用于处理滑动窗口下数据流FWMFI挖掘的算法[7].该算法借助WMFP-SW-tree,WMFP-SW-array和WMFP-tree执行挖掘操作.WMFP-SW-tree用于挖掘所有可能加权最大频繁项集，结构与FP-tree类似.数据流到来时，算法先构造窗口的WMFP-SW-tree，接着按由下而上顺序分别挖掘WMFP-SW-tree头表成员.当借助WMFP-tree消除所有加权频繁项集间超集关系后，树的每个分枝都是WMFP. WMFP-SW-array用于减少构建条件WMFP-SW-tree时扫描条件模式基的次数.
2 基本概念和问题说明2.1 基本概念设IS={I1,I2,…,Im}是m个item项的集合，TS= {T1,T2,…,Tn}是事务集，其中Ti为IS的子集.
定义1?数据流DS.数据流DS是一个由连续到来的事务组成的事务序列，表示为DS= {T1,T2,T3,…,Ti,…}，Ti为第i个到来的事务.
定义2?频繁项集.任给项集S，在TS中支持度为TS中包含S的事务个数与TS中事务总数|TS|的比值，记为SUP(S).若SUP(S)大于等于频繁阈值ε(0≤ε≤1)，则S为频繁项集.
定义3?基本窗口EW与滑动窗口SW.基本窗口EW是一段时间内连续到达的数据流成员，EW={Ti,Ti+1,…,Tj}(0＜i≤j).滑动窗口SW对应一个连续相邻的EW序列，SW={EW1,EW2,…,EWi,EWj,…}，其中EWi和EWj分别是SW中第i和第j个基本窗口，且?i，j，如果i≠j，EWi∩EWj =?.SW的滑动步长为一个基本窗口，SW大小为其中EW的个数，表示为|SW|；|EW|是基本窗口中数据流成员个数.
定义4?加权支持度[6-7].给定项集S={I1,I2,…，I
定义5?完全加权最大频繁项集.设S′是项集S的一个超集，Ssuper是所有S′的集合.给定频繁阈值ε(0≤ε≤1)，加权阈值Δ(0≤Δ≤1)，如果S满足如下条件，即为完全加权最大频繁项集：
①SUP(S)≥ε且WSUP(S)≥Δ；
②?S*∈Ssuper，WSUP(S*)＜Δ或SUP(S*)＜ε.
2.2 问题说明给定数据流DS，频繁阈值ε，加权阈值Δ，基本窗口及滑动窗口大小|EW|和|SW|.本文关注的是挖掘每个SW上数据流完全加权最大频繁项集.
3 FWMFI-SW算法3.1 naive算法由定义5及文献[6-7]可知，使用频繁条件过滤加权最大频繁项集能得到FWMFI集合，所以可基于WMFP-SW算法解决本文问题.另外由FP-growth算法与频繁项集向下闭包性可知，该过滤操作可在WMFP-SW算法处理每个WMFP-SW-tree及条件WMFP-SW-tree头表成员时执行.这样添加过滤条件的WMFP-SW算法被称为naive算法.
3.2 FWMFI-SW算法naive算法头表中成员是否加入prefix，决定于该成员在执行完基于频繁阈值和基于maxW优化策略2个判别操作后结果是否为真.但很多头表成员只需执行频繁判别操作就能确定，所以naive算法在这方面有冗余运算；另外，如果naive算法中窗口更新使原来WMFP-SW-tree头表中成员位置发生变化，则该树重构.但由文献[10]可知，这种情况下树的编辑距离比率若小于重构阈值γ(0≤γ≤1)，则无需重构.所以naive算法在这方面也有冗余运算.针对这2个问题做了如下工作：①提出基于频繁约束条件的优化策略；②给出WMFP-SW-tree重构判别函数；③将①，②引入naive，得到能减少冗余运算的FWMFI-SW算法.
3.2.1 基于频繁约束条件的优化策略设N为窗口中数据流成员数，WS是窗口WMFP-SW-tree，树中项的权值范围为[wh,wl]，item项出现次数和权值分别为item.count，item.weight，Sl=Δ/wh，Sh=Δ/wl.
性质1?当ε＜Sl，①如果item.count＜N×Sl，则不能加入prefix；②如果item.count≥N×Sh，则能加入prefix；③如果N×Sl≤item.count＜N×Sh，只要maxW优化策略关于item的判别为真，则能加入prefix.
①当item.count＜N×Sl，因为Sl=Δ/wh，故wh×SUP(item)＜Δ.又因为item.weight≤wh，故item.weight×SUP(item)＜Δ，item不能放入prefix.
②当item.count≥N×Sh，因为Sh=Δ/wl，所以wl×SUP(item)≥Δ.因为item.weight≥wl，所以item.weight×SUP(item)≥Δ.又因为item.count≥N×Sh>ε，所以item可以被放入prefix.
③当N×Sl≤item.count＜N×Sh，此时item.count≥N×Sl>ε成立，所以当maxW优化策略判别结果为真，该成员可放入prefix.证毕.
性质2?当Sl≤ε＜Sh，①如果item.count＜N×ε，则不能加入prefix；②如果item.count≥N×Sh，则能加入prefix；③如果N×ε≤item.count＜N×Sh，只要maxW优化策略判别结果为真，就能加入prefix.
性质3?当ε≥Sh，①如果item.count＜N×ε,则不能加入prefix；②如果item.count≥N×ε，则能加入prefix.
性质2，3证明与性质1相似.不再赘述.
把基于性质1～性质3优化naive算法的方法称为基于频繁约束条件的优化策略(OSF2C,optimization strategy based on frequent constraint condition).
3.2.2 重构判别函数RJF(reconstruction judge function)为减少naive算法中第2类冗余运算，采用文献[10]中编辑距离比率(edit distance proportion,EDP)作为WMFP-SW-tree重构判别函数.每个窗口上WMFP-SW-tree是否执行重构，取决于该树RJF值是否小于重构阈值γ(0≤γ≤1).下面给出RJF计算过程，其中M为窗口中所有项个数.
 | (1) |
 | (2) |
 | (3) |
算法1?FWMFI-SW算法
输入：DS，|SW|，|EW|，ε，Δ，γ
输出：完全加权最大频繁项集集合P
1) T=Order=H=?,N=|EW|×|SW|;//T是待建的WMFP-SW-tree
2) While there are transactions to be processed in DS
3) If T = ?
4) naive.Create_Window(T,Order);
5) aive.Restructure_Tree(T,Order);
6) H=Order;
7) Else
8) [Order,T]←naive.Update_Window(T,Order);
9) If (RJF(Order,H)＞γ)
10) naive.Restructure_Tree(T,Order);
11) H=Order;
12) Else
13) Order=H;
14) prefix=P=?;
15) get the upper and low bound of the weight about T,wh,wl;
16) Sl←Δ/wh,Sh←Δ/wl;
17) IFMine_WMFP(T,prefix,P,N,ε,Δ,Sl,Sh).
首次执行的算法先构建窗口WMFP-SW-tree，记下头表中项的排列顺序(行3～6)；当窗口滑动时，先更新WMFP-SW-tree中成员(行8)，然后基于RJF判断新WMFP-SW-tree是否重构(行9～13)；在WMFP-SW-tree确定后，先求得prefix，P，Sl，Sh，然后用IFMine_WMFP挖掘FWMFI(行14～17).这里，IFMine_WMFP算法与naive算法的Mine_WMFP子算法基本相同,不同点在于：①对于WMFP-SW-tree头表成员，先用OSF2C优化策略进行处理，根据处理结果决定是否执行maxW优化策略；②在递归调用IFMine_WMFP算法前，先确定条件树所有项权值的最大、最小以及S1和Sh的取值.
3.2.4 FWMFI-SW算法正确性分析FWMFI-SW与naive相比有2处不同：① FWMFI-SW算法引入WMFP-SW-tree的重构判别函数；②IFMine_WMFP子算法中引入基于频繁约束条件的优化策略.前者不改变naive算法结果，因为由文献[10]可知是否重构只影响树的紧凑程度；由性质1～3可知，后者也不会改变naive算法结果.
图 1是FWMFI-SW算法执行过程.这里仍用文献[7]中例子，其中Δ=0.3，ε=0.25，γ=0.2.
图 1(Fig. 1)
 | 图 1 一个FWMFI-SW算法的例子Fig.1 A FWMFI-SW algorithm example (a)—数据流及其上的滑动窗口； (b)—SW1上的WMFP-SW-tree; (c)—SW2上没有重构的WMFP-SW-tree. |
图 1a是数据流及窗口划分情况；图 1b是FWMFI-SW算法处理SW1中成员后得到的WMFP-SW-tree.Sl=0.3，Sh=0.75，由OSF2C可知G，F，D，A无需执行maxW优化策略.E的maxW优化策略结果为true，放入prefix.构建E的条件WMFP-SW-tree，该树Sl1=0.375，Sh1= 0.42.由OSF2C可知B，C不在结果中.又WSUP(E)=0.2 ＜0.3，故E不在结果中.用相同方法处理B，C可得BC模式为所求.图 1c是更新SW1后的WMFP-SW-tree，其RJF值0.182＜0.2，所以不重构.
4 实验分析所有实验在一台具有Intel(R) core(TM) i5处理器，4 GB内存的PC机上完成.算法由java实现.实验以mushroom和retail为样本.mushroom是稠密数据集，8 124条记录，大小0.54 MB，120个item，平均记录长度23；retail是稀疏数据集,88 162条记录，大小3.97 MB，16 470个item，平均记录大小13.使用这2个样本时|EW|分别为500,1 000;item权值取0.5～0.8之间随机数;实验执行次数为10.
4.1 FWMFI-SW算法的有效性设SNresult与SFresult分别为相同参数下naive与FWMFI-SW算法结果集合，|SFresult|与|SNresult|分别是它们中成员数目，Vequal是2个集合中相等成员个数.这里规定SFresult中任意成员A与SNresult中成员B，如果它们所在窗口起始位置和成员内容都相同，则A与B相等；否则不相等.基于此定义了FWMFI-SW算法相对于naive算法的查全率(recall)与查准率(precision)，分别用RFWMFI-SW与PFWMFI-SW表示.
 | (4) |
 | (5) |
图 2(Fig. 2)
 | 图 2 不同算法相对于naive算法的查全率和查准率对比Fig.2 Comparison of recall and precision of different algorithms over the naive (a)—查全率和查准率与Δ(ε=0.1,|SW|=8,γ=0.2)； (b)—查全率和查准率与ε (Δ=0.05,|SW|=8,γ=0.2). |
由图 2可见，RFWMFI-SW=PFWMFI-SW=1.这说明FWMFI-SW与naive算法结果相同.另外可以看到RWMFP-SW=1.这是因为FWMFI集合是通过使用另外一个频繁阈值ε过滤WMFI集合后得到的子集；同样理由WMFI集合中才会有不满足频繁阈值条件的成员，所以PWMFP-SW＜1，该现象也说明WMFP-SW算法不适合挖掘FWMFI.
4.2 FWMFI-SW算法的性能评价分析|SW|对算法时间的影响效果见图 3.
图 3(Fig. 3)
 | 图 3 算法在|SW|变化时的执行时间比较Fig.3 Comparison of the execution time about different algorithms when |SW| changes (a)—mushroom样本(Δ=0.05,ε= 0.1,γ=0.2)； (b)—retail样本(Δ=0.001,ε=0.1,γ<=0.2). |
由图 3可见2种样本下WMFP-SW算法时间随|SW|增加分别减少和增加，这与文献[7]描述一致.另外还可以看到WMFP-SW时间大于naive，这是因为naive算法不用处理WMFP-SW-tree与条件WMFP-SW-tree头表中很多非频繁成员；另外naive与FWMFI-SW算法时间都随|SW|增加而增加.这是因为窗口越大，其中频繁项越多，WMFP-SW-tree头表会有更多成员需要处理.
Δ对算法执行时间的影响，见图 4.由图 4可见,WMFP-SW算法时间随Δ的增加而减少.这是因为Δ越大，maxW优化策略效果越好，另外还可以看到naive与FWMFI-SW算法执行时间都与Δ无关.这是因为当前参数下所有频繁项也满足maxW优化策略判别条件.FWMFI-SW算法因为不需要执行naive算法中所有的maxW优化策略，同时也引入了重构判别机制，所以执行时间小于naive算法.
图 4(Fig. 4)
 | 图 4 算法在Δ变化时的执行时间比较Fig.4 Comparison of the execution time about different algorithms when Δ changes (a)—mushroom样本 (|SW|=8,ε=0.1,γ=0.2)； (b)—retail样本(|SW|=5,ε=0.1,γ=0.2). |
ε对算法执行时间的影响见图 5.由图 5可以看到WMFP-SW算法时间不随ε变化发生改变.这是因为该算法与ε无关，另外还可以看到WMFP-SW算法时间大于naive算法，这是因为naive算法不用处理WMFP-SW-tree与条件WMFP-SW-tree头表中的非频繁成员；其他2类算法时间随ε取值增加而递减.这是因为ε越大，WMFP-SW-tree头表中要处理的成员越少.另外可以看到FWMFI-SW执行时间小于naive算法，说明FWMFI-SW使用的策略有效.
图 5(Fig. 5)
 | 图 5 算法在ε变化时的执行时间比较Fig.5 Comparison of the execution time about different algorithms when ε changes (a)—mushroom样本(|SW|=8,Δ=0.05,γ=0.2)； (b)—retail样本(|SW|=5,Δ=0.001,γ=0.2). |
γ对算法执行时间的影响见图 6.由图 6可见WMFP-SW算法时间大于naive算法，这是因为naive算法忽略WMFP-SW-tree与条件WMFP-SW-tree头表中很多非频繁成员.另外可以看到,当γ在0～0.2间递增取值时，FWMFI-SW算法的时间小于naive算法的，而且会随γ增加而减少.这是因为RJF值小于γ的WMFP-SW-tree在重构后结构变化不大，重构操作会增加时间开销.当γ在0.2～1间递增取值时，FWMFI-SW算法时间增加.这是因为随着γ增加，很多RJF值较大的WMFP-SW-tree没有重构.
图 6(Fig. 6)
 | 图 6 算法在γ变化时的执行时间比较Fig.6 Comparison of the execution time about different algorithms when γ changes (a)—mushroom样本(|SW|=8,Δ=0.05,ε=0.1)； (b)—retail样本(|SW|=5,Δ=0.001,ε=0.1). |
另外由图中可见,当γ在[0,0.2]与[0.2,1]范围内递增取值时,FWMFI-SW算法时间分别会单调递减和单调增加.所以γ=0.2时FWMFI-SW算法中的重构判别效果最好.
5 结论本文提出了数据流完全加权最大频繁项集概念，并给出了滑动窗口下该项集挖掘算法——FWMFI-SW.该算法在naive算法上增加了基于频繁约束条件的优化策略；同时利用编辑距离比率作为窗口更新后是否重构WMFP-SW-tree的判别函数.这些策略有效减少了naive算法的冗余运算.实验结果表明FWMFI-SW时间开销小于naive算法，是处理滑动窗口下数据流FWMFI挖掘的有效方法.
参考文献
| [1] | 李国徽, 陈辉. 挖掘数据流任意滑动窗口内频繁模式[J].软件学报, 2008, 19(10): 2585–2596. ( Li Guo-hui, Chen Hui. Mining the frequent patterns in an arbitrary sliding window over online data stream[J].Journal of Software, 2008, 19(10): 2585–2596.)(  0) |
| [2] | Gao C C,Wang J Y,Yang Q Y.Efficient mining of closed sequential patterns on stream sliding window[C]// Proceedings of the 11th IEEE International Conference on Data Mining.Los Alamitos:IEEE Computer Society,2011:1044-1049.(0) |
| [3] | Yang S Y, Chao C M, Chen P Z, et al. Incremental mining of closed sequential patterns in multiple data streams[J].Journal of Networks, 2011, 6(5): 728–735.(0) |
| [4] | Li H F,Zhang N.A simple but effective stream maximal frequent itemset mining algorithm[C]// Proceedings of the 7th International Conference on Computational Intelligence and Security.Piscataway:IEEE Computer Society,2011:1268-1272.(0) |
| [5] | 敖富江, 颜跃进, 刘宝宏, 等. 在线挖掘数据流滑动窗口中最大频繁项集[J].系统仿真学报, 2009, 21(4): 1134–1139. ( Ao Fu-jiang, Yan Yue-jin, Liu Bao-hong, et al. Online mining maximal frequent item sets in sliding window over data stream[J].Journal of System Simulation, 2009, 21(4): 1134–1139.)( 0) |
| [6] | Yun U, Lee G, Ryu K H. Mining maximal frequent patterns by considering weight conditions over data streams[J].Knowledge-Based Systems, 2014, 55: 49–65.(0) |
| [7] | Lee G, Yun U, Ryu K H. Sliding window based weighted maximal frequent pattern mining over data streams[J].Expert Systems with Applications, 2014, 41(2): 694–708.(0) |
| [8] | Wang J,Yu Z.DSWFP:efficient mining of weighted frequent pattern over data streams[C]//Proceedings of the 8th International Conference on Fuzzy Systems and Knowledge Discovery.Piscataway:IEEE Computer Society,2011:942-946.(0) |
| [9] | Yun U, Shin H, Ryu K H, et al. An efficient mining algorithm for maximal weighted frequent patterns in transactional databases[J]. Knowledge-Based Systems, 2012, 33: 53–64.(0) |
| [10] | Yun S K,Gillian D.Efficient single pass ordered incremental pattern mining[C]//Proceedings of the 13th International Conference on Data Warehousing and Knowledge Discovery.Berlin:Springer,2011:265-276.(0) |
