基于前缀树的数据流频繁模式挖掘算法  

Prefix tree-based algorithm for mining frequent patterns over data streams

作　　者：杨君锐[1] 黄威[1] 

机构地区：[1]西安科技大学计算机科学与技术学院,陕西西安710054

出　　处：《华中科技大学学报（自然科学版）》2010年第7期107-110,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：陕西省教育厅专项科研基金资助项目(06JK248)

摘　　要：针对数据流的无限性和流动性特点,提出了一种基于前缀树的数据流频繁模式挖掘算法(Prefix-stream).该算法将对数倾斜时间窗口划分为若干个子窗口,以子窗口为单位,利用提出的数据结构Prefix-tree进行挖掘,在整个数据流的频繁模式挖掘中,使得频繁模式挖掘和更新能在Prefix-tree中同时进行.该算法应用对数倾斜时间窗口逐步降低历史事务的权重,从而区分最近事务与历史事务.实验结果表明Prefix-stream具有较高的效率与较好的可扩展性.Finding frequent items is one of the most basic problems on mining in the data streams. The limitless and mobility of data streams make the traditional frequent pattern algorithms difficult to extend to data streams. A new Prefix-stream algorithm based on prefix tree for mining frequent patterns over data streams is proposed. A logarithmic tilted-time window was divided into several child windows and the child window was served as an updating unit,then a new data structure Prefix-tree that is proposed in the paper is used for mining frequent patterns. The algorithm for mining and updating frequent patterns over data streams was processed in Prefix-tree at the same time. Besides,the algorithm can differentiate the patterns of recently generating transactions from those of historic transactions with a logarithmic tilted-time window. The experimental results show that the proposed algorithm is efficient and scalable.

关 键 词：数据挖掘 数据流 频繁模式挖掘 频繁模式树 对数倾斜时间窗口 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]