ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (7): 1452-1464.doi: 10.7544/issn1000-1239.2017.20160553

• 人工智能 • 上一篇    下一篇

基于Spark的Top-k对比序列模式挖掘

张鹏1,段磊1,2,秦攀1,左劼1,唐常杰1,元昌安3,彭舰1   

  1. 1(四川大学计算机学院 成都 610065);2(四川大学华西公共卫生学院 成都 610041);3(科学计算与智能信息处理广西高校重点实验室(广西师范学院) 南宁 530001) (zp_jy1993@163.com)
  • 出版日期: 2017-07-01
  • 基金资助: 
    国家自然科学基金项目(61572332,61363037);国家自然科学基金委员会-中国民用航空局民航联和研究基金项目(U1333113);中国博士后科学基金特别资助项目(2016T90850);中央高校基本科研业务费专项资金项目(2016SCU04A22);四川省科技支撑计划基金项目(2014GZ0111)

Mining Top-k Distinguishing Sequential Patterns Using Spark

Zhang Peng1, Duan Lei1,2, Qin Pan1, Zuo Jie1, Tang Changjie1, Yuan Chang’an3, Peng Jian1   

  1. 1(School of Computer Science, Sichuan University, Chengdu 610065);2(West China School of Public Health, Sichuan University, Chengdu 610041);3(Guangxi Higher Education Key Laboratory of Science Computing and Intelligent Information Processing (Guangxi Teachers Education University), Nanning 530001)
  • Online: 2017-07-01

摘要: 对比序列模式(distinguishing sequential pattern, DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如:构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSP-Miner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.

关键词: 并行计算, 序列模式, top-k, 对比挖掘, Spark

Abstract: DSP (distinguishing sequential pattern) is a kind of sequence such that it occurs frequently in the sequence set of target class, while infrequently in the sequence set of non-target class. Since distinguishing sequential patterns can describe the differences between two sets of sequences, mining of distinguishing sequential patterns has wide applications, such as building sequence classifiers, characterizing biological features of DNA sequences, and behavior analysis for specified group of people. Compared with mining distinguishing sequential patterns satisfying the predefined support thresholds, mining distinguishing sequential patterns with top-k contrast measure can avoid setting improper support thresholds by users. Thus, it is more user-friendly. However, the conventional algorithm for mining top-k DSPs cannot deal with the sequence data set with large-scale. To break this limitation, a parallel mining method using Spark, named SP-kDSP-Miner (Spark based top-k DSP miner), is designed for mining top-k distinguishing sequential patterns from large-scale sequence data set. Furthermore, in order to improve the efficiency of SP-kDSP-Miner, a novel candidate pattern generation strategy and several pruning strategies, as well as a parallel computing method for the contrast scores of candidate patterns are proposed considering the characteristics of Spark structure. Experiments on both real-world and synthetic data sets demonstrate that SP-kDSP-Miner is effective, efficient and scalable.

Key words: parallel computing, sequential pattern, top-k, contrast mining, Spark

中图分类号: