唐辉军 王乐 樊成立

序列模式挖掘作为数据挖掘领域的一项重要研究内容,在风险管理、生物信息学、基因分析等方面具有重要的应用[1−3].频繁序列模式挖掘作为其应用的典型代表,突出了序列数据集中的高频模式,传统数据集上的频繁项集闭包属性表明:任一个频繁项集的非空子集都是频繁项集,非频繁项集的任一个超集都不是频繁项集,基于上述闭包属性计算原则形成了序列集频繁模式挖掘算法[4−5].然而频繁模式没有考虑序列集中各项的效用值.例如在零售业,冰箱的销售要比牙刷卖的次数少的多,但其利润可能比牙刷高的多,因此在频繁序列模式的基础上,提出了高效用序列模式挖掘,即将内外效用值引入到序列项集中,目前,高效用序列模式已经成为数据挖掘领域的一个热门研究内容[6−8].2010年,Ahmed等[9]给出了高效用序列模式挖掘的完整定义和数学模型.其主要任务为在具有一定效用值的序列数据库中找出效用值不小于预先给定阈值的所有有序项集.在定义过程中,一个项集X的总效用值为X在该数据集中有包含项集X的事务t上的效用值U(X,t)的总和.而在单一事务t中可能存在多个相同序列集,文献选择其中较大效用值作为项集X在该事务中的效用.同时,该文献还提出两种挖掘算法UtilityLevel 和UtilitySpan,其中UtilityLevel通过事务中项集按水平次序组合生成候选项集,进而判断和识别其中高效用序列.UtilitySpan通过项集前缀垂直查找,搜索高效用项……