基于广度优先的序列模式挖掘算法  

Sequential Pattern Mining Algorithm Based on Breadth- first

作　　者：张先飞[1] 李弼程[1] 

机构地区：[1]解放军信息工程大学信息工程学院,郑州450002

出　　处：《计算机工程与应用》2005年第32期172-177,216,共7页Computer Engineering and Applications

摘　　要：序列模式挖掘的典型算法-GSP算法及其之后的许多相关算法的重点都是放在寻找所有的序列模式上面。CloSpan算法首先提出搜索封闭集合的思想。封闭集合比全集合更精简有效,并且和全集合有着相同的表达能力。文章的ERIC算法同样用于搜索封闭集合。然而不同于之前算法多采用深度优先的策略,ERIC算法是基于广度优先的。它利用列表来保存序列的位置数据,通过利用序列的有序性,以及基于后向超模式与等位置数据的两个修剪技巧来提高算法的搜索效率。为了确保储存最终结果列表的简洁,ERIC算法对一些特殊情况进行了分析。从最终的试验结果可以看出,ERIC算法在较小支持度的情况下对中大型数据库有很好的搜索效率。The typical sequential pattern mining algorithm-the GSP algorithm and many interrelated methods mostly focuss on mining all of sets of sequential patterns.The CloSpan algorithm first suggests that the closed set of sequential patterns is more compact and has the same expressive power with respect to the full sets.The algorithm-ERIC also mine closed patterns.However,instead of depth-first searching uses in many previous methods,it adopts a breadth-first approach.It also uses a list which reserves the information of item ordering. , and two main pruning techniques,- backward super-pattern condition and same positional data condition to improve algorithm＇s efficiency.To ensure the final list＇s compact,ERIC also manipulates some special conditions.From the experimental results,ERIC has a perfect efficiency in the cases of large datasets and low support threshold.

关 键 词：广度优先 序列模式 封闭集合 超模式 修剪技巧 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]