一种基于垂直划分的数据流频繁项集挖掘算法

摘要

数据流这种数据形式广泛地存在于现实世界中。例如,传感器网络监控、气象监测数据、电话通话记录、网络通讯监测、股市实时交易数据、web用户点击数据流或者网站访问日志统计等领域都产生了大量的数据流。因此如何从应用产生的数据流数据中发掘出对人们有用的信息一直是国内外研究工作者关注的热点,而频繁项集挖掘则是数据流挖掘技术的重要分支。
　　 传统频繁项集挖掘算法大都基于集中式单处理器硬件环境设计运行,当数据到达速度以及数据规模大幅增大之后,算法将会出现数据丢失,误差增大,系统吞吐量下降等一系列问题。为此,本文在分析原有传统算法FP-Stream存在当数据量增大时数据处理速度无法同步数据到达速度、系统吞吐量不够等问题的基础上,提出了一种基于垂直划分的FP-Stream频繁项集挖掘算法。该算法运行在分布式多处理器硬件环境下,采用并行挖掘频繁项集并最终统一合并的策略,并引入新的倾斜时间窗口实现机制,将全局数据进行垂直划分为多个时间段内的子集分别进行挖掘,并由合并子系统对各子频繁项集进行统一合并,得到最终全局频繁项集结果。改进后的算法因为倾斜时间窗口的作用,使得挖掘结果仍然能够反映较早和较近时间段内频繁项集的变化情况并能提供指定时间段内频繁项集结果查询,即结果仍然具有时间特性。而且最重要的是,由于算法设计是基于分布式的,在硬件环境允许的情况下系统吞吐量可以与数据规模达到同步增长的效果。
　　 最后对算法进行了仿真实验,结果表明,本文提出的基于垂直划分的FP-Stream频繁项集挖掘算法在牺牲一定的空间需求,并保持基本不变的时间需求的情况下,能够正确的挖掘出事务数据流中的频繁项集结果。而且由于算法的可扩展性,使得算法整体吞吐量高于传统FP-Stream算法,能够解决传统FP-Stream这种集中式串行挖掘模式的算法所存在的无法有效处理大规模数据流的问题,应用前景得到了进一步扩展。