基于前缀共享树的频繁情节挖掘算法  

Algorithm for Mining Frequent Episodes Based on the Prefix Shared Tree

作　　者：丁勇[1] 朱辉生[2] 高广银[1] 

机构地区：[1]南京理工大学泰州科技学院 [2]泰州学院计算机科学与技术学院,泰州225300

出　　处：《科学技术与工程》2014年第28期231-234,246,共5页Science Technology and Engineering

基　　金：国家自然科学基金项目(61003001,61103009)资助

摘　　要：经典的频繁情节挖掘算法NONEPI及其改进算法NONEPI+存在时空复杂度高、"重复计算"等问题,基于最小且非重叠发生的支持度定义,提出一个基于前缀共享树的频繁情节挖掘算法PST_NONEPI,该算法采用深度优先搜索策略,将发现的频繁情节压缩到前缀共享树中,通过动态维护前缀共享树来发现所有的频繁情节。该算法只需扫描事件序列一次,大大提高了频繁情节挖掘的效率。实验证明,PST_NONEPI算法能有效地挖掘频繁情节。Algorithm NONEPI and its improved algorithm NONEPI ＋ to find non-overlapped frequent episodes exist some defects such as high complexity and ＂over computing＂ , etc. In this paper, support based on minimal and non-overlapped occurrence is definited, presents an algorithm called PST_NONEPI for mining frequent episodes based on the prefix shared tree, the algorithm uses a depth-first search strategy, compress frequent episodes have been found to the prefix shared tree, to discover all frequent episodes by maintaining the prefix shared tree. the al- gorithm only needs to scan the event sequences once, which improves the efficiency of mining frequent episodes. Experiments show that, PST_NONEPI algorithm can effectively mine frequent episodes.

关 键 词：事件序列 频繁情节 最小且非重叠发生 前缀共享树 

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