计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (22): 175-177.DOI: 10.3778/j.issn.1002-8331.2010.22.052

• 数据库、信号与信息处理 • 上一篇    下一篇

事务型滑动窗口下的数据流频繁模式挖掘

胡 彧,王顺平   

  1. 太原理工大学 计算机与软件学院,太原 030024
  • 收稿日期:2009-01-13 修回日期:2009-03-26 出版日期:2010-08-01 发布日期:2010-08-01
  • 通讯作者: 胡 彧

Mining frequent patterns in data stream with transaction-sensitive sliding window

HU Yu,WANG Shun-ping   

  1. College of Computer Engineering and Software,Taiyuan University of Technology,Taiyuan 030024,China
  • Received:2009-01-13 Revised:2009-03-26 Online:2010-08-01 Published:2010-08-01
  • Contact: HU Yu

摘要: 作为数据流挖掘的一个重要研究问题,滑动窗口下的数据流频繁模式挖掘近年来得到了广泛应用和研究。已有的算法大多要对数据流中所有的数据都进行处理,而现实中用户往往只关注事物的某些方面,由此借鉴MFI-TransSW算法,提出了一种基于事务型滑动窗口的算法BSW-Filter(Bit Sliding Window with Filter)。算法采用比特序列实现滑动窗口操作,同时由于增加了频繁项的筛选,减少了所需保存的数据项个数,从而减小了内存使用和提升处理速度。算法的空间复杂度与滑动窗口大小以及数据流取值范围无关,特别适用于周期较长数据范围广的数据挖掘。分析和实验验证了该算法的可行性和有效性。

Abstract: As one of the most important problems in data stream mining,the frequent patterns mining with a sliding window is widely researched and used in many fields.Exiting algorithms need process all elements in the data stream,whereas users only focus on several aspects of things.So inspired by the MFI-TransSW algorithm,a new algorithm based on transaction-sensitive sliding window is proposed in this paper,in which a sequence of bits is used to implement the sliding window operation.In addition,a mechanism of filtering frequent items,which decreases the memory usage and improve the efficiency of processing,because of the reduction of items retained in memory.Furthermore as space complexity is independent to the size of sliding window and the value range of elements,this method is specially applicable to discovery of data with a wide range of values in a long period.The analysis and experiments show the feasibility and effectiveness of the algorithm.

中图分类号: