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

1(四川大学计算机学院 成都 610065)2(四川大学华西公共卫生学院 成都 610041)3 (科学计算与智能信息处理广西高校重点实验室(广西师范学院) 南宁 530001)



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

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

1(四川大学计算机学院 成都 610065)2(四川大学华西公共卫生学院 成都 610041)3(科学计算与智能信息处理广西高校重点实验室(广西师范学院) 南宁 530001)

(zp_jy1993@163.com)

对比序列模式(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

序列模式挖掘作为一项重要的数据挖掘任务,受到学者的广泛关注,提出了频繁序列模式[1]、闭合序列模式[2]、对比序列模式[3]、周期序列模式[4]、偏序……