一种top-K序列模式挖掘算法  

Algorithm on Mining Top-K Sequential Patterns

作　　者：李涛[1] 张庭玉 陆正邦 郁美辰 LI Tao;ZHANG Ting - yu;LU Zheng - bang;YU Mei - chen(School of Electronic ＆ Information Engineering, Nanjing University of Information Science and Technology, Nanjing Jiangsu 210044, China)

机构地区：[1]南京信息工程大学电子与信息工程学院,江苏南京210044

出　　处：《计算机仿真》2018年第4期240-245,共6页Computer Simulation

基　　金：公益性行业(气象)科研专项项目(GYHY201306070);江苏省大学生实践创新训练计划项目(201610300031#);江苏高校品牌专业建设工程资助项目(PPZY2015B134)

摘　　要：序列模式挖掘是数据挖掘中的一个重要研究课题。序列模式挖掘算法通常需要用户设定最小支持度阈值minsup,然而这需要具备较深的领域知识或进行大量的实验。为了解决上述问题,研究者们逐渐将挖掘序列模式转变为挖掘top-K序列模式的研究。提出了一种top-K序列模式挖掘(top-K Sequential Patterns Mining,KSPM)算法。它采用OPUS的搜索方式对所有可能的候选序列进行遍历,并利用位图作为数据存储结构来缩小存储空间。此外,还使用了有效的剪枝策略提高算法执行效率。最后,通过web点击流序列、手语表达序列等数据集验证了提出的算法的有效性。Sequential pattern mining is an important research subject of data mining. Sequential pattern mining algorithms require the user to define the threshold minsup, but this usually needs in - depth domain knowledge or a lot of experiments. To solve this problem, researchers gradually transform sequential patterns mining into top -K se- quential patterns. This paper presents an efficient algorithm for mining top - K sequential patterns, the top - K Se- quential Patterns Mining（KSPM）. We used OPUS search method to traverse all the possible candidate sequences, and utilized a bitmap as data structure to reduce storage space. In addition, effective pruning rules were designed to improve the efficiency of the algorithm. Finally, experiments on web click stream sequences, sign language utterance sequences and other sequential datasets confirmed the effectiveness of the proposed algorithm.

关 键 词：数据挖掘 序列模式 位图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]