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

经典的频繁情节挖掘算法NONEPI及其改进算法NONEPI+存在时空复杂度高、"重复计算"等问题,基于最小且非重叠发生的支持度定义,提出一个基于前缀共享树的频繁情节挖掘算法PST_NONEPI,该算法采用深度优先搜索策略,将发现的频繁情节压缩到前缀共享树中,通过动态维护前缀共享树来发现所有的频繁情节。该算法只需扫描事件序列一次,大大提高了频繁情节挖掘的效率。实验证明,PST_NONEPI算法能有效地挖掘频繁情节。

Algorithm for Mining Frequent Episodes Based on the Prefix Shared Tree

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 algorithm 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.