论文部分内容阅读
数据流是一个按时间到来的数据项的序列。和传统的静态数据库不同,数据流是连续的、无限的、高速到来,并且数据分布随着时间而变化,这使得传统的频繁项集挖掘算法在数据流上难以适应。另外,频繁模式数量较大,导致生成的关联规则数量巨大,且含有冗余和无用的规则。同时挖掘频繁项集需要很大的时间和空间消耗。闭频繁模式不仅可以保证完整的信息,而且大大减少了频繁模式的规模。因此,闭频繁项集挖掘已成为数据流研究热点之一。本文对数据流中的闭频繁模式挖掘进行了研究,主要工作如下:(1)对已有频繁项集和闭频繁项集挖掘的经典算法进行了研究,详细研究了CFI-Stream算法,指出了存在的问题,并对其进行改进,提出了一种新的算法。该算法利用衰减窗口机制和近似估计方法,解决了CFI-Stream算法中挖掘的局部性和更新策略引起的数据颠簸问题,提高了挖掘效率。(2)利用滑动窗口思想,给出数据流闭频繁项集挖掘算法(data stream closed frenquent itemsets,简称DSSCI)算法。算法通过讨论事务项集间存在的包含关系,构造了DSSCI-Tree存储结构,仅存储当前滑动窗口上的所有闭项集,节省了存储空间。构造DSSCI-Tree结构时,采用深度优先搜索的策略,保证了没有重复构造节点。利用以事务为基本单位的滑动窗口机制对DSSCI-Tree进行更新,可以直接在线生成并挖掘当前闭频繁项集,提高了时间效率。(3)通过实例分析验证了算法的可行性,并利用合成数据对本算法和Moment算法进行比较,结果表明,该算法在时间效率和空间利用上有很好的性能。