2016, Vol. 37
2.东北大学 医学影像计算教育部重点实验室, 辽宁 沈阳 110819
2.Key Laboratory of Medical Image Computing, Ministry of Education, Northeastern University, Shenyang 110819, China
挖掘数据流环境下的频繁项集是数据流挖掘领域中的重要内容[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) |
将基于频繁约束条件的优化策略与关于WMFP-SW-tree的重构判别机制引入naive算法，得到解决本文所关注问题的FWMFI-SW算法.
算法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 一个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) |
类似可定义WMFP-SW算法相对于naive算法的查全率(RWMFP-SW)与查准率(PWMFP-SW).图 2给出了mushroom下算法的查全率与查准率.
|
图 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 算法在|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 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 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 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)
|