带间隔约束的Top-k对比序列模式挖掘

来源：软件学报杂志2015年第11期北京时间：

作者：杨皓,段磊,胡斌,邓松,王文韬,秦攀

单位：杨皓，四川大学 计算机学院, 四川 成都 61006511,段磊，四川大学 计算机学院, 四川 成都 610065;四川大学 华西公共卫生学院, 四川 成都 61004102,胡斌，国家电网 智能电网研究院, 江苏 南京 21000303,邓松，南京邮电大学 先进技术研究院, 江苏 南京 21000304,王文韬，四川大学 计算机学院, 四川 成都 61006505,秦攀，四川大学 计算机学院, 四川 成都 61006506

摘要：对比序列模式能够表达序列数据集合间的差异,在商品推荐、用户行为分析和电力供应预测等领域有广泛的应用.已有的对比序列模式挖掘算法需要用户设定正例支持度阈值和负例支持度阈值.在不具备足够先验知识的情况下,用户难以设定恰当的支持度阈值,从而可能错失一些对比显著的模式.为此,提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).kDSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了kDSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.

关键词：序列模式;top-k;对比挖掘

基金资助：国家自然科学基金(61103042); 中国博士后科学基金(2014M552371); 软件工程国家重点实验室开放研究基金(SKLSE2012-09-32)