数据流频繁模式挖掘及数据预测算法研究

论文摘要

在过去的几年里，数据流广泛出现在传感器网络、金融证券管理、网络监控、Web日志以及通信数据在线分析等新型应用领域中。由于数据流中数据的规模一般都十分庞大、且增长迅速，因此，有限的存储空间中根本无法完整地保存数据流上的全部数据，这给数据流上的数据处理带来了巨大的挑战。此外，由于数据流数据的连续性与流动性，随着新的流数据连续到达，数据流所包含的知识信息总是在连续不断地变化。而对于实际的数据流应用而言，挖掘出数据流上知识的变化趋势往往比挖掘知识本身更为重要。因此，人们往往更希望挖掘出数据流上最近的某个滑动时间窗口内交易数据所包含的知识信息。挖掘数据流上的频繁模式在数据流的应用中有着重要研究意义，例如：在网络监控中，对应于异常流量的频繁模式可能意味着存在网络攻击或者网络拥塞；在商业销售记录中，频繁模式总是反映那些热门销售的产品以及它们之间的关联关系；而在传感器网络数据管理中，挖掘其中的频繁数据集可以有助于去估计那些丢失的数据值。然而，由于流数据的特点，传统的静态数据库挖掘方法不可能直接应用流数据的频繁模式挖掘，而必须研究新的数据流频繁模式挖掘方法。数据流上的频繁模式挖掘算法要求能够在单遍扫描流数据的基础上增量处理连续不断到达的流数据，并用尽可能小的代价维护数据流上最新的数据大纲。此外，随着新到达的流数据进入滑动时间窗口，窗口内最古老的历史数据将从窗口中移出而变得过期。为了消除历史流数据对当前挖掘结果的影响，数据流滑动时间窗口内频繁模式挖掘方法还需要定期删除数据大纲上维护的历史流数据的模式信息，从而提高模式挖掘的正确性。数据流最近的频繁模式挖掘方法应用模式树（RFP-tree）增量地维护数据流上新到达流数据所包含的模式信息，并周期性地对模式树进行剪枝，删除那些过期流数据所包含的模式分枝以及不频繁的模式分枝。RFP-tree以维护数据流上最近的不多于2N个流数据所包含的模式信息为代价，保守地维护了数据流上最近的大小为N的滑动时间窗口内流数据的全部频繁模式信息。方法还应用保守的计算策略计算模式在滑动时间窗口内的近似支持数，而由保守计算策略得到的模式的近似支持数总是不小于模式的真实支持数的，因此，方法总能够保证滑动时间窗口内模式挖掘的覆盖率达到100%。为了适应性维护数据流上大小可变的滑动时间窗口内的频繁模式，数据流任意大小滑动时间窗口内频繁模式挖掘方法应用滑动窗口树（SW-tree）增量维护数据流滑动时间窗口内的模式信息。同时，它还应用时间衰减模型衰减流数据所包含模式支持数的权重，并以此来区分新产生流数据与历史流数据所包含的模式。为了保证模式挖掘的覆盖率和精度，方法分析了时间衰减模型对模式支持数的影响，并给出了衰减因子在保证模式挖掘正确性条件下的边界值。并且，当滑动时间窗口的大小改变时，仅需重新设定合适的衰减因子的值即可重新保证在新的滑动时间窗口下模式挖掘的正确性。在实际的数据流应用中，由于流数据的连续不断变化导致流数据所包含的模式信息也在不断地变化，因此很难事先估计数据流上的频繁模式信息并给出一个合适的最小支持度门限。数据流滑动时间窗口内Top-K频繁模式挖掘方法提供了一个更加直接的挖掘数据流上频繁模式的方法。它无需用户提供最小支持度门限，而仅需用户提供预期的频繁模式集的大小K。它使用Chernoff边界理论估计窗口内第K频繁模式的支持度，并将其用于动态维护窗口内潜在频繁的模式信息。根据理论分析，Chernoff边界理论能够为模式挖掘的正确性提供了概率保证。研究数据流上的历史数据的变化趋势，并预测数据流在未来时间窗口内的可能值是数据流挖掘的一项重要工作。基于马尔可夫模型的数据流预测查询算法以实数数据流为例，通过将实数数据流上大小可能无限的流数据空间映射到一个有限的流数据状态空间中，从而将数据流上的流数据变化序列转变成为一个流数据状态变迁序列。通过使用数据流状态变迁有向图（SSTD）维护流数据状态变迁序列的统计信息，可以得到流数据状态变迁的概率矩阵，从而应用马尔可夫模型可以去预测数据流在未来时刻的可能值。

论文目录

• 摘要
• Abstract
• 符号对照表
• 1 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 论文工作与结构
• 2 数据流处理模型与频繁模式挖掘
• 2.1 数据流处理模型
• 2.2 数据流频繁模式挖掘技术
• 2.3 数据流滑动时间窗口内频繁模式挖掘
• 2.4 小结
• 3 基于保守策略的频繁模式挖掘算法
• 3.1 引言
• 3.2 相关工作
• 3.3 算法设计与分析
• 3.4 基于保守策略的频繁模式挖掘算法
• 3.5 实验分析
• 3.6 小结
• 4 基于衰减机制的频繁模式挖掘算法
• 4.1 引言
• 4.2 相关工作
• 4.3 算法设计与分析
• 4.4 基于衰减策略的频繁模式挖掘算法
• 4.5 实验分析
• 4.6 小结
• 5 Top-K频繁模式挖掘算法
• 5.1 引言
• 5.2 相关工作
• 5.3 算法设计与分析
• 5.4 Top-K频繁模式挖掘算法
• 5.5 实验分析
• 5.6 小结
• 6 基于马尔可夫模型的预测算法
• 6.1 引言
• 6.2 相关工作
• 6.3 算法设计与分析
• 6.4 基于马尔可夫模型的预测算法
• 6.5 实验分析
• 6.6 小结
• 7 总结与展望
• 7.1 论文总结
• 7.2 研究展望
• 致谢
• 参考文献
• 附录1 攻读学位期间发表的学术论文
• 附录2 攻读学位期间参与的科研项目