杨克帅，武优西*，耿 萌，刘靖宇，李 艳

（1.河北工业大学 人工智能与数据科学学院，天津 300401；2.河北工业大学 经济管理学院，天津 300401）

0 引言

序列模式挖掘（Sequential Pattern Mining，SPM）作为数据挖掘领域中重要课题，旨在从序列数据库［1］发现支持度（在序列数据库中出现次数）满足用户最小支持度阈值的子序列，被广泛应用于多种实际场景，如DNA 序列检测［2］、用户购买行为分析［3］和网页点击流挖掘［4-5］等。

传统频繁序列模式挖掘只考虑模式是否在序列中出现，而忽略了它在序列的出现次数。为解决此问题，重复挖掘方法［6-12］应运而生，该方法通过模式匹配技术计算模式在一条序列的出现次数。例如：假定有两个消费者，他们的购买次序分别形成了两条消费序列S1={(1，ab)（2，a）（3，abc）｝和S2={(1，bd)(2，ab)(3，acd)(4，abc)(5，ac)(6，ac)（7，ab）（8，ad）（9，cd）｝。以S1为例，它表示消费者1，第1 次购买了a 和b 两样商品；第2 次仅购买了a 商品；第3 次购买了a、b 和c 共三样商品。易知模式（ab）（c）在S1和S2中均有出现。由于传统的序列模式挖掘方法不甄别模式在序列中的重复性，因此模式（ab）（c）在S1和S2中的支持度为2。而可重复序列模式挖掘则甄别模式在序列中的重复性，易知模式（ab）（c）在S2中的出现了3 次，出现位置为因此在可重复序列模式挖掘中，模式（ab）（c）在S1和S2中的支持度分别为1 和3，总支持度为4。由此可见，消费者2 比消费者1 在模式（ab）（c）上具有更大的兴趣。因此，可重复序列模式挖掘与传统序列模式挖掘方法显著不同。

此外，与一次性条件［12］不同，文献［12］在单项序列上进行挖掘，即序列是由若干单项构成的，此研究的对应S1序列是｛abaabc｝；而本文在通用性更强的项集序列上进行研究，问题更通用、更复杂。……