随着互联网技术的发展,各行各业的数据呈现爆炸式增长。为了从这些数据中挖掘出有用的知识,越来越多的数据挖掘技术得到了广泛的研究。频繁项集挖掘就是其中一种流行的数据分析任务。其目标是识别交易数据库中那些经常出现的模式。如果模式的支持度（出现频率）小于最小支持度阈值,则称其为频繁模式。频繁模式挖掘有许多应用,而且也启发了许多其他数据挖掘任务,包括关联规则挖掘、序列模式挖掘、聚类和分类等等。虽然频繁模式很有用,但是只通过支持度的限制会经常性得到过多的频繁模式,并且其中许多对用户来说是无趣的。因此,用户分析频繁模式可能非常耗时。为了解决这个问题,有许多变种模式被提出并研究。它们是通过考虑用户各种感兴趣的约束来得到更小的模式集。周期模式便是最近的一个热门研究课题,它通过约束模式出现的周期性,即在两个连续出现时间点不超过最大距离的限制。周期模式在许多领域都有实际的应用,如分析股市数据以识别周期性的股市波动,分析网站点击来提高推荐系统的性能以及在DNA序列中发现频繁相关的基因。周期模式的另一个重要应用是通过发现定期购买的商品来研究顾客的购买行为,以达到营销和库存管理的目的。然而,传统的周期模式挖掘研究有两个主要的局限性。一个是大多数算法通过测量相同模式之间的记录数量来识别周期模式,而不依赖真实的时间戳。这样相隔一秒的记录数量与相隔几个小时的记录数量会被同等对待,这是不现实的。另一个局限性是在传统周期模式挖掘中周期模式必须在整个时间范围内都得保持周期性。这样会忽略在局部时间段具有周期性的模式。例如,荔枝主要在夏天销售,那么它可能只在特定的几个月内具有高周期性。如果利用传统的模式挖掘算法应用在近几年的交易数据库中,用户将无法得到重要的时间区间信息。基于此,本研究提出一个更加面向真实场景的新的问题局部周期模式。周期模式挖掘基于频繁模式挖掘。简单来说,周期模式挖掘就是在交易数据库中那些周期性出现的模式。周期模式挖掘就是在频繁模式挖掘的基础上限制了模式出现的间隔的大小。更加准确的定义如下:在如第三章的数据库中,每一个TID代表了一行记录的编号,它是满足自增长性的。每一行记录里包括了一次交易和该交易发生的时间戳。每一次交易包含一个或多个不同的项。传统的周期模式挖掘是通过考虑相同模式之间TID的差值作为衡量周期的方法,在确定差值需要满足的一个阈值后,问题的要求就是找到所有小于该阈值的项集。因为引入了周期性的概念,所以大多数频繁模式挖掘的算法不能直接应用在周期模式挖掘上。为了解决这个问题,很多高效的算法被提出来,像PF-tree,PFPM等。周期模式挖掘已经有很多学者做了充分的研究,本篇论文将重点研究基于传统模式挖掘的拓展上。具体的,传统的周期模式挖掘并没有考虑交易所对应的时间戳,而是基于自增正的TID来计算与衡量模式的周期性,这是不符合实际的。同时,传统的周期模式只能判断是否在整个数据库中具备周期性,而无法得到具体在哪些时间段具有周期性。所以很多有用的知识无法被充分挖掘,而本次研究就是基于此提出的一个新问题。本篇论文将利用交易对应的真实时间戳来计算模式的周期。因为TID的值是从1开始自增长,为了方便计算,传统的周期模式挖掘会给每一个模式增加一个额外的TID为0,来作为统一的起始点。而在本篇论文中,不会引入不存在的额外起始点。那么传统的周期模式挖掘基于TID来计算周期的数量将会比本篇论文基于真实时间戳计算周期的数量多1。在如第三章正文所示的交易数据库中,其中（a,b,c,d,e）表示该数据库中所有的项,每一行的记录的第一列代表其TID,第二列表示了该交易（用Tc表示,其中c表示对应的TID）中所涉及的项,第三列表示了该交易所对应的真实时间（用tc表示,其中c表示对应的TID）。项集{a,b}包含了{a}项集和{b}项集,它出现在T₁,T₂,T₃和T₉中。利用TID,传统模式挖掘将得到其周期（正文区分定义为gap）为{1-0,2-1,3-2,9-3,10-9}={1,1,1,6,1}。而利用真实时间戳,本篇论文将得到的周期（正文区分定义为per）为{ts₂-t s₁,t s₃-t s₂,t s₉-t s₃,t s₁₀-t s₉}={7-6,9-7,23-9,25-23}={1,2,14,2}。可以看出,这两种计算方式具有较大的差别。在传统模式挖掘中,通常使用周期的最大值来代表其周期性,如果其最大值小于用户所设定的阈值,那么我们就说该模式是周期模式。如果设定最大阈值为3,那么传统周期模式挖掘将会丢弃{a,b},因为其最大的周期是6。我们可以看到,其他值都是小于阈值的,该模式在一定范围内也是满足周期性的。而在局部周期模式中,那些满足周期性要求的区间将不会被丢弃。本篇论文提出了两个新的衡量方法去识别时间区间和评估模式在此区间的周期性,分别称为最大溢出周期和最小持续时长。最大溢出周期被用来识别可变长度的时间区间,在此区间中模式的行为可能会变化但具有周期性。最小持续时长用来确保这些时间区间满足最小的时长。为了更加高效地挖掘局部周期模式,本文提出了三个算法叫LPPMbr eadth,LPPM_depth和LPP-Growth。它们分别采用了深度优先,广度优先和模式增长地方法来通过拓展Apriori-TID,Eclat和FP-Growth算法到挖掘局部周期模式中。前两个算法采用了二进制数据库的表示方法,即每一项在每个交易中是否出现（是为1,否为0）,这样可以利用二进制的快速并运算来得到更大的候选项集的信息,使得算法更加高效。后一种算法采用了前缀树的数据结构来压缩数据库,将每一条交易中的项集排序后从根节点插入,其中时间信息只保存在尾节点上,换句话说任一节点的祖先节点都包含该节点的时间信息,这样极大的减小了内存的消耗。因为这三个算法都是从单项集开始,依据其不同的搜索方式进行扩张,且根据满足闭包性的属性进行剪枝,所以它们都能完整的发现全部满足条件的局部周期模式。这三个算法都具有三个相同的参数,分别是max Per,max So Per和min Dur。实验结果表明这三个参数都有助于筛选掉那些不满足条件的项集。在运行效率方面,LPP-Growth在稀疏型数据库中较LPPMbr eadth和LPPM_depth要快许多,而在稠密型数据库中则表现相反。因为在稠密型数据库中,模式往往具有较多或较长的周期区间,那么LPP-Growth将会花大量的时间去构造这些模式的条件树,而另两种不用构造树结构节省了很多时间。在模式数量方面,若三个算法使用相同大小的参数,那么它们将会得到相同的模式以及相等的数量,这些算法的正确性得以验证。同时,减小max So Per或max Per,或增大min Dur往往都会降低模式数量的发现。因为,这些参数影响了搜索空间的大小,而搜索空间的大小往往与模式的数量呈正相关性的。在内存消耗方面,LPP-Growth较其他两个算法内存消耗较小,主要得益于在构建树模型中,只有尾节点才保留时间信息,通过与祖先节点共享信息来减少内存的消耗。在模型表现方面,可以发现文本设计的算法可以很好的捕捉到局部周期模式以及它们具有周期性的时间区间。并能最大程度上捕捉到局部周期的信息,帮助用户做更加精准的决策。在算法的选择和使用上,用户可以根据数据库的具体特征来决定使用哪个算法,通过调节不同参数的大小来得到具有偏好的局部周期模式。综上所述,本文从近几年比较流行的周期模式出发,面向实际场景定义了一个新的问题,即在离散序列中挖掘局部周期模式。针对这个问题,提出了两个新的衡量方法用来识别局部周期模式以及其周期性时间区间。为了能高效挖掘该模式,设计了三个算法,并搭配基于闭包性的剪枝策略。在真实和生成数据上做了对照实验,结果表明这三个算法都有其自身的优势与劣势,且提出的模型能够发现数据中更加精准的有用信息。