数据挖掘的一个基础研究方向就是频繁项集挖掘。频繁项集挖掘指从交易数据库中挖掘出频繁出现的项集,从而为下一步关联规则挖掘或序列挖掘提供支持。传统的频繁项集的挖掘的一个局限是它假定所有的项都是同样重要,并且最多出现一次。为解决这一局限,一些学者提出了高效用项集挖掘,它允许不同的项有不同的效用（重要程度）,同时在一次交易中各项也可以出现超过一次。高效用项集挖掘极大地拓展了频繁项集挖掘的应用范围,并能为各种决策提供更有效的支持。高效用项集挖掘的一个局限在于它忽略了每个交易产生的时间,由此可能会失去一些有用信息。项集的效用分布可能会随时间变化,传统高效用项集挖掘会找出在整个数据库中产生高效用的项集,而这会偏向那些在所有时间段都出现的项集,会忽略在局部时间段产生非常高效用的项集。例如,在超市的数据库中,可能{面包、牛奶}这一项集会是高效用项集,因为它在一年中的每个时间段都有销售,而{月饼}这一项集可能不会是高效用项集,可是它在中秋节前后这一时间段却可能产生很高的效用。基于此,本研究提出一个新的问题局部高效用项集。这将是一个新的项集衡量标准,在市场营销、网络点击分析等方面将会有广泛的应用场景。既然项集的效用会随时间变化,那么找到项集能产生显著高于平常的效用的时间段则对决策有益。例如商场经营者不仅想知道什么项集能产生高利润,他们也会想知道这些项集在哪些时间段能产生较高的利润从而更合理的安排采购与销售。为解决这一问题,本研究提出了另一个新模式峰值高效用项集。高效用项集挖掘扩展了传统的频繁项集挖掘。效用挖掘就是在频繁项集挖掘的基础上允许每次交易中单个项出现多次,同时每个项能产生不同的效用。频繁项集挖掘可以看成特殊的高效用项集挖掘。更准确的定义如下:在正文所示的交易数据库中,每个TID标识了一次交易,items记录了该交易所包含的项以及其对应的数量。第二个表是利润表,记录了每个项所产生的利润。在确定了阈值minutil后,问题的要求是找到所有产生效用高于minutil的项集。高效用挖掘被广泛承认比频繁项集挖掘更有挑战性。关键的一点在于,在频繁项集挖掘中被用来减少搜索空间的反单调性（非频繁项集的超集一定不是频繁项集）不再成立。也就是说一个项集的超集可能产生高于或低于其本身的效用。所以,大多数频繁项集挖掘算法不能直接应用在高效用项集挖掘上。目前针对这一问题,已经出现了很多高效的算法像Two-Phase,UP-Growth,FHM,EFIM等。本研究考虑到项集的效用会随时间变化而变化,并由此提出两个新问题使I={i₁,i₂,...,i_n}表示所有项的集合.一个交易T是被用户购买的项的集合（T?I）。交易数据库是一个交易的集合D={T₁,T₂,...,T_m},其中每个交易T_tid（1≤tid≤m）都有一个标识符tid。此外,用t（T）表示交易T发生的时间。每个交易中的项i∈I都有一个与之对应的效用值u（i）,表示了其产生的效用或重要程度。考虑数据库正文数据库示例表所示（后面将用它举例说明相关概念）,数据库中共有8条交易（T₁,T₂,...,T₈）5个项（a,b,c,d,e）,每个项旁边的括号表示了其的效用（注意这里定义是正文中的简化版本）。例如,交易T₁中项b,c,e的效用（利润）分别为4,2,3。另外,交易T₁,T₂...T₈后跟了一个时间戳d₁,d₃,...d₁₀,代表了发生的时间（d_i=第i天）,这里时间单位是天,但是其他单位像秒、分钟等在一定场景下也是允许的。而且,虽然这里举例用的超市的数据,但高效用挖掘在其他领域也有着广泛的应用。如果一个项集X的效用u（X）不低于用户设定的阈值minutil≥0,即u（X）≥minutil,则该项集X被称为儎?亯?。例如在上述数据库中,如果设定minutil=60,则共有7个高效用项集{a,c,e},{b,c,d},{b,c,d,e},{b,d},{b,e},{b,d,e},和{b,c,e},它们分别产生效用62、73、85、66、62、78和74。高效用项集挖掘是经典的频繁项集挖掘的一个泛华,也比之更有挑战性,主要原因在于项集的效用不是反单调性的,由此,频繁项集挖掘的剪枝策略便不能直接应用在高效用项集挖掘上。很多算法通过找满足反单调性的效用的上界来剪枝,最经典的是TWU,一个项集的TWU为其所在交易的效用总和,显然其是反单调性的,可以用来缩小搜索空间。尽管高效用项集挖掘有着广泛的应用,它忽略了时间维度,由此不能捕捉效用随时间的变化。为了解决这一局限,本研究提出局部高效用项集和分值高效用项集,随后进一步提出去冗余峰值高效用项集。在上述数据库中,当minutil=60,项集{a,c,e}是一个高效用项集,因为u（{a,c,e}）=62>60,{d,e}不是一个高效用项集,因为u（{d,e}）=463到d₅这一时间段内,{d,e}产生的效用是{a,c,e}的两倍（两者分别为46和18）。所以在这一时间段内{d,e}比{a,c,e}更重要,但却被传统高效用项集挖掘所忽略。而局部高效用项集就是为了解决这一局限,定义为:如果一个项集存在某个长度为minLength的时间窗,在其中产生效用高于设定好的阈值l Minutil,则称之为局部高效用项集,这里minLength和l Minutil为用户设定的两个参数。例如,如果minLength=5,l Minutil=30,则{a,b,c}为一个局部高效用项集,因为其在窗口d₂,d₆中的效用为32,大于阈值。可以证明,在参数设定合适的情况下,所有高效用项集都是局部高效用项集,也就是说新的模式不会损失任何信息。既然项集的效用会随着时间变化而变化,那么找出项集产生较高效用的时间段就可以随之做有用的决策。第二个新的模式基于上述的局部高效用项集,旨在发现项集产生显著高于平常效用的时间段,新的模式称为峰值高效用项集。峰值高效用项集的定义利用了股票交易系统中的一个技术——移动平均交叉。移动平均是指用一小段时间内的平均值来代替某一点的值,这可以用来平缓波动,而一段时间的长短则代表了平缓程度的大小。移动平均交叉则指两个不同平缓程度的交叉点,这代表着上升或下降的趋势（在股票市场中表示买入或卖出点）。峰值高效用项集指短移动平均线在长移动平均线上面的时间段,这代表了该项集的峰值效用。在定义了峰值后,另一问题就是要找出哪些项集的峰值,显然找出所有项集的峰值是不可能同时也是不必要的。在这里我们的方案是找出所有局部高效用项集的峰值。实验结果发现通常挖掘出的峰值高效用项集都较多,不利于向用户展示。为了解决这一局限,本研究进一步提出其子模式去冗余峰值高效用项集。它基于的原理是如果一个项集的子项集不是峰值高效用项集,那么该项集不是峰值高效用项集。例如月饼在中秋节前后会有峰值,而面包在中秋节前后可能没有大的波动,但是面包,月饼合起来再中秋前后可能有峰值,但这一峰值产生的原因是因为月饼的峰值,所以没有什么意义。而去冗余峰值高效用项集可以排除这一冗余信息。在算法设计方面,本研究改进了HUI-Miner算法中的utility-list数据结构,在其中增加了高效用时期信息。每一个项集都有与之对应的utility-list,utility-list由一个三元组列表组成,每一个三元组形如(T_id,u(X,T_id),ru(X,T_id),分别表示了该项集出现交易的标识符,在该交易中的效用,在该交易中剩下的效用（注意这里对项进行排序,剩下的效用仅考虑出现在该项集后面的那些项）。这样,在探索高效用项集时就不用重复地扫描数据库,而仅探索utility-list。而添加的时期信息为该项集产生高效用的的时期,这样在后续探索utility-list时就不用考虑所有三元组,而仅考虑在这些时期中的元素。局部高效用项集和峰值高效用项集的搜索方法与HUI-Miner类似,也就是用深度优先搜索,并剪枝不可能的子树。至于局部信息和峰值时期信息,则可以用滑动窗口技术解决。对于去冗余峰值高效用项集,可以用后处理方法,去掉子项集不是峰值高效用项集的项集。为进一步提升算法的表现,本研究提出了三个优化策略。实验结果表明所提出的算法是高效的并且可以发现以前被传统高效用项集忽略的模式。