一种基于滑动窗口模型的数据流加权频繁模式挖掘方法

石秀金 蔡艺松

摘 要： 相对于传统的频繁模式挖掘，加权频繁模式挖掘能发现更有价值的模式信息。针对数据流中的数据只能一次扫描，本文提出了一种基于滑动窗口模型的数据流加权频繁模式挖掘方法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.