第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201702019 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20180417.1130.008.html 去冗余Top-k对比序列模式挖掘 江冰，谷飞洋，何增有 (大连理工大学软件学院，辽宁大连116621) 摘要：对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域， 对比序列模式有着广泛的应用。T©k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模 式。在Topk对比序列模式挖掘中，可能挖掘出冗余的序列模式。目前，虽然有Top-k对比序列模式发现算法 被提出，但这些算法并未考虑冗余序列模式的问题。为此，本文提出了基于广度优先生成树的去冗余T©p-k 对比序列模式挖掘算法BFM(breadth--first miner)。使用BFM算法可以有效地解决冗余问题，得到去冗余的Top-k 对比序列模式。在BFM算法的基础上，提出了性能更好的算法PBFM(pruning breadth--first miner)。通过在真实 数据集上的实验分析与对比，验证了本文算法的有效性。 关键词：对比序列模式：广度优先；冗余序列模式；模式挖掘：Topk 中图分类号：TP393文献标志码：A文章编号：1673-4785(2018)05-0680-07 中文引用格式：江冰，谷飞洋，何增有.去冗余Top-k对比序列模式挖掘J.智能系统学报，2018,13(5)：680-686. 英文引用格式：JIANG Bing,GU Feiyang,HE Zengyou.Mining Top-knon-redundant distinguishing sequential patterns.CAAI transactions on intelligent systems,2018,13(5):680-686. Mining Top-k non-redundant distinguishing sequential patterns JIANG Bing,GU Feiyang,HE Zengyou (Software School,Dalian University of Technology,Dalian 116621,China) Abstract:Distinct sequential patterns can be used to characterize different categories of datasets.In the field of bioin- formatics,logistics management,and e-commerce,the comparison of sequential pattern has a wide range of applica- tions.The goal of the Top-k distinguishing sequential pattern mining is to find k patterns with the highest contrast in a given data set.However,in the Top-k distinguishing sequential pattern mining,there is a redundancy problem with re- spect to the set of reported sequential patterns,which is not considered by the algorithm.Therefore,in this paper,a non- redundant Top-k distinguishing sequential pattern mining algorithm,breadth-first miner(BFM),is proposed based on breadth-first spanning tree.The redundancy problem is effectively solved using the BFM algorithm.Based on the BFM algorithm,a better algorithm,pruning breadth-first miner(PBFM),is proposed.Through the experimental analysis and comparison on the real data set,the validity of the algorithm is verified. Keywords:distinguishing sequential pattern;breadth-first,redundant sequential patterns;pattern mining;Top-k 至今已经有很多种序列模式被提出，包括周 据集中频繁出现，而在另一类数据集中很少出现 期模式山、偏序模式)、闭合模式倒、对比序列模 的序列模式。对比序列模式可以描述不同数据集 式、频繁序列模式阿等。对比序列模式挖掘作为 之间的差异，在很多领域有广泛应用。例如，对 数据挖掘中重要的一个问题，目前已经积累了大 比序列模式可以用于纳税人行为分析，患者的 量的研究成果6刀。对比序列模式是指在一类数 风险预测例等。在对比序列模式挖掘中，Top-k对 收稿日期：2017-02-26.网络出版日期：2018-04-18. 比序列模式挖掘是一种重要的挖掘策略。Top 基金项目：国家自然科学基金项目(61572094)：大学生创新创 业训练计划项日(2017101410901010382) k方法是指在给定的标准下挖掘出差异最大的 通信作者：何增有.E-mail:yhe@dut.edu.cn. k个模式的方法。该方法被广泛应用在关联规则、DOI: 10.11992/tis.201702019 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20180417.1130.008.html 去冗余 Top-k 对比序列模式挖掘 江冰，谷飞洋，何增有 （大连理工大学 软件学院，辽宁 大连 116621） 摘 要：对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域， 对比序列模式有着广泛的应用。Top-k 对比序列模式挖掘的目标是发现数据集中对比度最高的前 k 个序列模 式。在 Top-k 对比序列模式挖掘中，可能挖掘出冗余的序列模式。目前，虽然有 Top-k 对比序列模式发现算法 被提出，但这些算法并未考虑冗余序列模式的问题。为此，本文提出了基于广度优先生成树的去冗余 Top-k 对比序列模式挖掘算法 BFM(breadth-first miner)。使用 BFM 算法可以有效地解决冗余问题，得到去冗余的 Top-k 对比序列模式。在 BFM 算法的基础上，提出了性能更好的算法 PBFM(pruning breadth-first miner)。通过在真实 数据集上的实验分析与对比 ，验证了本文算法的有效性。 关键词：对比序列模式；广度优先；冗余序列模式；模式挖掘；Top-k 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2018)05−0680−07 中文引用格式：江冰, 谷飞洋, 何增有. 去冗余 Top-k 对比序列模式挖掘[J]. 智能系统学报, 2018, 13(5): 680–686. 英文引用格式：JIANG Bing, GU Feiyang, HE Zengyou. Mining Top-k non-redundant distinguishing sequential patterns[J]. CAAI transactions on intelligent systems, 2018, 13(5): 680–686. Mining Top-k non-redundant distinguishing sequential patterns JIANG Bing，GU Feiyang，HE Zengyou (Software School, Dalian University of Technology, Dalian 116621, China) Abstract: Distinct sequential patterns can be used to characterize different categories of datasets. In the field of bioin￾formatics, logistics management, and e-commerce, the comparison of sequential pattern has a wide range of applica￾tions. The goal of the Top-k distinguishing sequential pattern mining is to find k patterns with the highest contrast in a given data set. However, in the Top-k distinguishing sequential pattern mining, there is a redundancy problem with re￾spect to the set of reported sequential patterns, which is not considered by the algorithm. Therefore, in this paper, a non￾redundant Top-k distinguishing sequential pattern mining algorithm, breadth-first miner (BFM), is proposed based on breadth-first spanning tree. The redundancy problem is effectively solved using the BFM algorithm. Based on the BFM algorithm, a better algorithm, pruning breadth-first miner (PBFM), is proposed. Through the experimental analysis and comparison on the real data set, the validity of the algorithm is verified. Keywords: distinguishing sequential pattern; breadth-first; redundant sequential patterns; pattern mining; Top-k 至今已经有很多种序列模式被提出，包括周 期模式[1] 、偏序模式[2] 、闭合模式[3] 、对比序列模 式 [4] 、频繁序列模式[5]等。对比序列模式挖掘作为 数据挖掘中重要的一个问题，目前已经积累了大 量的研究成果[6-7]。对比序列模式是指在一类数 据集中频繁出现，而在另一类数据集中很少出现 的序列模式。对比序列模式可以描述不同数据集 之间的差异，在很多领域有广泛应用。例如，对 比序列模式可以用于纳税人行为分析[8] ，患者的 风险预测[9]等。在对比序列模式挖掘中，Top-k 对 比序列模式挖掘是一种重要的挖掘策略。 Top￾k 方法是指在给定的标准下挖掘出差异最大的 k 个模式的方法。该方法被广泛应用在关联规则[10] 、 收稿日期：2017−02−26. 网络出版日期：2018−04−18. 基金项目：国家自然科学基金项目 (61572094)；大学生创新创 业训练计划项目 (2017101410901010382). 通信作者：何增有. E-mail: zyhe@dlut.edu.cn. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018