一种基于频繁模式有向无环图的数据流频繁模式挖掘算法  

An algorithm based on frequent patterns directed acyclic graph for mining frequent patterns from data stream

作　　者：任家东[1] 王倩[1] 王蒙[2] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]泰山学院物理与电子工程学院,山东泰安271021

出　　处：《燕山大学学报》2011年第2期115-120,共6页Journal of Yanshan University

基　　金：河北省自然科学基金资助项目(F2008000888)

摘　　要：频繁模式挖掘中基于FP-growth的算法需要扫描两次事务数据库,预先给定支持度,且不支持时间敏感型数据。本文提出了一种基于频繁模式有向无环图的数据流频繁模式挖掘算法,它根据事务到来的时间给每个事务一个序号,每个事务中的数据项在存储前按数据项的顺序进行调整,频繁模式有向无环图的构建遵循这个顺序并用序号来记录事务与数据项的包含关系,模式增长过程只需要增加有向边上的序号。通过逆向遍历带有相同序号的有向边,产生条件模式基,根据动态定义的阈值抽取条件模式基信息,一次扫描数据库得到频繁模式。实验结果表明,本文算法的执行效率优于FP-growth算法,且存储节点的数目明显减少。The algorithms based on FP-growth for mining frequent patterns need to scan the transaction database twice and givethe threshold in advance, it also can not support time sensitive data stream. In this paper, an algorithm based on frequent patterndirected acyclic graph for mining frequent patterns from data stream is proposed. Each transaction is given a number according toits coming time. Items contained in a transaction are sorted by their order, and the directed acyclic graph follows that order. Afrequent pattern directed acyclic graph records the relation between transactions and items by its number. The process of patterngrowth is to increase the transaction number of the directed edges. The algorithm travels edges conversely by the same transactionnumber and products the conditional pattern bases, it can abstract the information of the conditional pattern bases according to dy-namic threshold and scan the database only once to gain frequent patterns. The experiment shows that the proposed algorithm isbetter than FP-growth in execute time and the number of the storaged node is significiantly reduced.

关 键 词：数据流 频繁模式 频繁模式有向无环图 

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