
收稿日期:20120314;修回日期:20120424 基金项目:广西可信软件重点实验室开放基金资助项目;广西研究生科研创新资助项目
(2011105950812M22)
作者简介:缪裕青(1966),女,副教授,博士,主要研究方向为数据挖掘、生物数据挖掘(miaoyuqing@gueteducn);吴孔玲(1986),女,硕士,
主要研究方向为数据挖掘、序列模式挖掘;朱晓雁(1979),女,硕士,主要研究方向为管理学、营销管理;张锦杏(1986),男,硕士,主要研究方向为
数据挖掘、云计算.
基于二级索引结构无候选项闭合
序列模式挖掘算法
缪裕青,吴孔玲,朱晓雁,张锦杏
(桂林电子科技大学 计算机科学与工程学院,广西 桂林 541004)
摘 要:针对 CloSpan算法分两个阶段挖掘闭合序列模式中第一阶段需要保持候选序列且未充分利用项的位置
信息、存在对数据库重复扫描和计算大小的不足,提出了 posCloSpan算法。算法通过对二级索引结构进行检索
实现向前剪枝,避免数据库重复扫描以及对超序索引表、子序索引表的检测,实现非闭合序列的修剪,无须保存
候选序列。实验结果证明,算法在处理较长序列以及存在大量重复投影数据库的数据源时,有效降低了时间上
的开销。
关键词:数据挖掘;序列模式挖掘;闭合序列;CloSpan
中图分类号:TP391 文献标志码:A 文章编号:10013695(2012)10367205
doi:103969/jissn10013695201210018
Closedsequentialpatternminingalgorithmwithnocandidate
sequencebasedontwolevelindexstructure
MIAOYuqing,WUKongling,ZHUXiaoyan,ZHANGJinxing
(SchoolofComputerScience&Engineering,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)
Abstract:AimingatthedefectsofCloSpanalgorithmwhenminingclosedsequentialpatternthatitneedstomaintainthecan
didatesequencesinthefirststageanddonotmakefulluseofthelocationinformation,existsrepeatedlyscanningdatabasecal
culatingdatabasesize,thispaperputforwardposCloSpanalgorithm.Bydetectingthetwolevelindexstructure,thealgorithm
achievedforwardpruning
,avoidedrepeatedlyscanningdatabase.Atthesametime,ittrimednonclosedsequencesthrough
detectingsupsequenceindextableandsubsequenceindextable,withoutsavingcandidatesequence.Experimentalresult
showsthatthealgorithmcaneffectivelyreducethetimeconsumptionindealingwithlongersequenceandthedatasourcethat
hasalargenumberofduplicatedprojectdatabase.
Keywords:datamining;sequentialpatternmining;closedsequence;CloSpan
!
引言
序列模式挖掘算法 ApriorAll
[1]
、SPADE
[2]
、SPAM
[3]
、Pre
fixSpan
[4]
等都是在数据库中挖掘出所有满足最小支持度的频
繁序列,并且对由短序列组成的数据库取得了很好性能。但
是当支持度很低或挖掘长序列数据库时,频繁序列会呈指数
级增长,算法性能大大降低;同时大量的挖掘结果不仅导致
存储空间的巨大消耗,也降低了从挖掘结果中提取有用信息
的效率。如何压缩挖掘结果,降低存储空间成为研究热点,
于是提出了闭合序列模式挖掘。闭合序列模式是指在支持
度相同的条件下,不存在被其他任何包含的序列模式,它不
仅可以完全表达结果的完全集,有更精简的结果,而且不存
在信息的衰减,对它进行挖掘被认为是压缩挖掘结果的有效
途径。
Yan等人
[5]
提出的 CloSpan算法是第一个挖掘闭合序列
模式算法,它在 PrefixSpan
[4]
算法的基础上加入两种剪枝策略,
并用哈希算法优化搜索空间,可分为两个阶段:第一阶段产生
候选序列,并运用数据库大小哈希、子模式回溯、超模式回溯等
策略提前结束序列的增长;第二阶段运用支持度哈希,修剪非
闭合序列模式,从而得到全部闭合序列模式。实验证明,
CloS
pan
算法效率比 PrefixSpan算法有很大提高。
BIDE算法
[6]
克服了需要维护候选序列的不足,基于伪投
影,采用双向扩展闭合检测方法,通过向后扫描和跳跃扫描优
化技术剪枝搜索空间,比
CloSpan有更好的算法性能。该算法
主要应用于简单数据序列,即序列的一个元素为单个项,如蛋
白质序列、网络点击流序列等。随后金沙等人
[7]
提出的 PosD
算法利用支持度、约束策略和位置信息来减少搜索空间。而林
颖提出的
PosD
算法是在原 PosD算法中加入了时间约束,进
一步减小了搜索空间
[7]
。
通过研究发现,CloSpan算法在第一阶段需要维护候选序
列,且在模式增长过程中,未充分利用末项的位置信息,对每个
投影数据库都要进行扫描统计其大小,存在着重复扫描统计的
第 29卷第 10期
2012年 10月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol29No10
Oct2012