基于模式增长的高效用序列模式挖掘算法

A New Algorithm for Mining High Utility Sequential Patterns Based on Pattern-growth

高效用序列模式挖掘是数据挖掘领域的一项重要内容,在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同,高效用序列模式挖掘不仅考虑项集的内外效用,更突出项集的时间序列含义,计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题,挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此,本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求,算法首先在去除无用项后建立全局树,进而采用模式增长方法从全局树上获取全部高效用序列模式,避免产生候选项集.在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比,实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式,并且在计算时间和空间使用效率两方面取得了较大的提高.

High utility sequential pattern mining is an important research topic in data mining.It plays an important role in many applications,such as bioinformatics and consumer behavior analysis.Different from traditional itemsets mining methods which take the appear numbers or the utility of the itemsets into account,high utility sequential pattern mining not only concerns the inner and outer utility but also the sequences of the items in the transactions,its computational complexity increases compared to the single frequent itemsets mining or high utility itemsets mining.Although a number of algorithms have been proposed to solve such problem,the efficiency of mining algorithms is still the main research topic in this field.In view of this,this paper proposes an efficient high utility sequential pattern mining algorithm named HUSP-FP based on pattern growth.Because the transaction utility value of the sequence itemset should satisfy the downward closure property,a global tree is established based on the sequential items in the transactions of the dataset after removing useless items.the HUSP-FP algorithm can efficiently extract sequential patterns from global tree without generating candidate itemsets.Comparing with the state-of-the-art high-utility sequential pattern mining algorithms of HUSP-Miner、USPAN and HUS-Span in our experiments,the proposed HUSP-FP out-performed its counterpart significantly.