论文部分内容阅读
近年来,随着计算机存储和网络通信技术的快速发展,数据流逐渐出现在日常生活中的各个领域,比如大型商场的售货记录,环境温度的检测数据,交易所的股票价格信息等。人们需要对海量的动态数据进行实时连续的收集与分析,进而挖掘数据流上的频繁模式得到越来越多的关注。与传统静态数据库相比,数据流具有持续不断、高速运行、无限到达的特点。数据流中的数据随时间的推移不断更新,而用户通常只关注近期有价值的模式。本文研究的是数据流频繁项集挖掘的一个主要方面:数据流闭合频繁项集挖掘。它是针对数据流频繁项集挖掘中得到大量冗余的频繁项集,造成内存过多的消耗和挖掘速度的极大下降而提出的。闭合频繁项集包括了挖掘出的所有频繁项集的完全集,从而避免了冗余频繁项集的产生,可以大大节省存储空间,提高挖掘效率,但是又不会丢失任何有用信息。数据流快速无限的特点及其应用领域的不断扩增,使数据流的在线挖掘技术越来越具有挑战性。提出了一种新的CMNL-SW挖掘算法(Closed Map and Num List-SlidingWindow),它沿用Moment算法的滑动窗口技术和CFI-Stream算法只维持闭合项集信息的方法,但与之不同的是,CMNL-SW算法不需产生事务的子集,也不需搜索每个子集的超集。算法使用数据结构Closed Map存储挖掘到的闭合项集和Num List存储所有不同项的序号,通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口,使之能够根据用户任意指定的支持度阈值实时输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom、Retail-chain以及人工合成数据集T40I10D100K的挖掘结果表明,提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream,并且随着数据流上处理事务数的递增和快速改变有很好的稳定性。