挖掘滑动窗口中的数据流频繁模式
摘 要:随着数据流应用的不断增多,数据流环境下的数据挖掘技术受到了越来越多的关注.文章结合数据流的特点,提出一 种新的基于滑动窗口的频繁模式挖掘算法:DSFPM.算法分块挖掘数据流,在内存中维持一个用于保存所有潜在的频繁模式信 息的存储结构DSFPM-Tree,并在各个基本窗口进入滑动窗口后动态更新该存储结构.算法仅处理和保存各个基本窗口的临界 频繁闭合项集,极大地提高了时间和空间效率.实验结果表明,该算法具有良好的性能.
1 引 言
数据流作为一种新型的数据模型已经出现在多种应用 中,如传感器网络、网络监控、通信数据管理、股票分析等.频 繁模式挖掘作为数据挖掘的最基本问题之一,在过去十几年 中已经得到了国内外学者的广泛研究.但由于数据流具有大 量数据连续、实时到达,数据潜在无限并且无法预知等特点, 传统的频繁模式挖掘方法在数据流环境下很难适用.数据流 环境下的频繁模式挖掘成为了一个极具挑战性的研究方向.
根据不同的时序范围可以将数据流环境中的查询窗口划 分成界标窗口(起始时间固定,结束时间变化)、滑动窗口(起 始时间和结束时间均变化)和快照窗口(起始时间和结束时间 均固定).近年来,一些针对数据流环境的界标窗口中的频繁 模式挖掘算法[1-5]已经被相继提出:文献[1]提出了Sticky Sampling和Lossy Counting两个算法,引入了误差因子ε,给 出了求解单个频繁模式的有效算法.文献[2]提出了FP- stream算法,利用一种类似于FP-Tree[6]的前缀树Pattern- Tree结构来存储过去时间窗口的潜在频繁模式信息,并引入 倾斜时间窗口技术以解决历史数据的时间敏感性问题.Met- wally等人在文献[4]中提出了一个综合性的近似方法,可以 同时解决在数据流环境下挖掘频繁模式和找出最频繁的K个 项两个问题.文献[5]对频度提出了一种新的定义,给出了一 趟遍历的在线算法OFSD,算法可在网络搜索引擎的查询流 中挖掘出频繁模式.由于在现实应用中,人们往往更关心滑动 窗口内最新到达的数据,因此数据流环境下滑动窗口中的频 繁模式挖掘[7-11]受到人们越来越多地关注.文献[7]研究了在 长度固定和长度变化的两种滑动窗口中利用有限存储空间维 护ε近似计数的算法.文献[9]给出两个算法来动态计算滑动 窗口中的频度计数,第一个算法构造子窗口来保存概要数据 结构,并删除过期的子窗口;第二个算法则提供最近N个元素 的频度查询.Yishan等人在文献[10]中提出了一种介于传统 的全历史模型和时间衰减模型之间的多滑动窗口模型,该模 型基于合理的单调性假设,区分数据流中不同时期的数 据项.文献[11]研究了在数据流的滑动窗口中挖掘频繁闭合 模式的问题,给出了一种新的数据结构闭合枚举树(closed enumeration tree),用来存储动态选定项及其边界,由于任何 非频繁项变为频繁项的发生必须通过边界,而边界是相对稳 定的,因此降低了挖掘频繁闭合模式算法的时间代价.
本文提出了一种新的基于滑动窗口的数据流频繁模式挖 掘算法:DSFPM.该算法采用一种新型的存储结构DSFPM- Tree来存储滑动窗口中的所有潜在频繁模式,并随着滑动窗 口的不断滑动实时更新和维护该结构,最后从中挖掘出频繁 模式.
3 算法描述
3.1 算法简介
DSFPM算法将数据流分成等长的数据块,每一个数据 块作为一个基本窗口,而若干个连续的基本窗口组成一个滑 动窗口.算法在第一个基本窗口进入滑动窗口后生成一个临 界频繁1-项集的排序表f-list,并且在以后每个新的基本窗口 进入滑动窗口后实时更新该f-list.算法采用DSFPM-Tree结 构存储滑动窗口中的潜在频繁模式集.在每个新的基本窗口 进入滑动窗口时,算法根据更新的f-list对DSFPM-Tree进 行重构.在重构的过程中,删除退出滑动窗口的旧基本窗口的 模式信息,并将DSFPM-Tree的每个分枝上的结点都按当前 滑动窗口中的临界频繁1-项集的支持度计数降序排序.这样 可以使得出现频率越高的项目出现在离树根越近的地方,使 更多的模式能共用前缀,增加压缩效率,并且能为以后模式的 查找和插入以及频繁模式的输出带来便利.在完成DSFPM- Tree的重构工作后,DSFPM算法以误差因子ε为最小支持度 阈值,利用传统的频繁闭合模式挖掘算法挖掘新基本窗口的 临界频繁闭合模式集,并将这些模式插入到DSFPM-Tree中.
由于只需要处理和存储各个基本窗口的临界频繁闭合模式 集,这将极大地减少处理时间和数据存储量.最后,算法利用 一个频繁模式输出表fpo-list来统计保存在DSFPM-Tree中 的所有潜在频繁模式信息,并从fpo-list中输出滑动窗口中 的所有频繁模式.
上的优势会随着最小支持度阈值取值的增加而减小. 最后,比较了两算法在3个不同数据集上对每100K事务 的平均处理时间.取最小支持度阈值ζ=0.5%.图5(见上页) 给出了实验结果.实验结果说明,FP-stream算法的性能随着 事务集中事务平均长度的增长而急剧下降,而DSFPM算法 的性能受事务集中事务平均长度的影响较小.
5 结束语
本文提出了一种基于滑动窗口的数据流频繁模式挖掘算 法DSFPM.该算法用一种DSFPM-Tree的数据结构存储滑动 窗口中的潜在频繁模式集.在每个基本窗口中,DSFPM算法 只处理和保存该基本窗口的临界频繁闭合模式集,极大地减 少了模式插入的操作次数和模式的存储量.DSFPM算法在 每个新的基本窗口进入滑动窗口时,对DSFPM-Tree进行了 有效的重构,以保证每根树枝都按临界频繁1-项集的降序排 序,有效地提高了DSFPM-Tree的压缩效率,并为模式的查找 和插入以及频繁模式的输出带来了便利.实验表明,DSFPM 算法具有良好的性能.
|
