融合多种支持度定义的频繁情节挖掘算法

Frequent Episode Mining Algorithm Compatible with Various Support Definitions

事件序列中蕴藏的频繁情节刻画了用户或系统的行为规律.现有的频繁情节挖掘算法在各自支持度定义下具有较好的挖掘效果,但在支持度定义发生变化时却很难甚至无法直接挖掘频繁情节.针对用户多变的支持度定义需求,提出了一种频繁情节挖掘算法FEM-DFS(frequent episode mining-depth first search).该算法通过单遍扫描事件序列,以深度优先搜索方式来发现频繁情节,以共享前/后缀树来存储频繁情节,以单调性、前缀单调性或后缀单调性来压缩频繁情节的搜索空间.实验评估证实了所提出算法的有效性.

Frequent episodes hidden in an event sequence describe the behavioral regularities of users or systems.Existing algorithms yield good results for mining frequent episodes under their respective definitions of support,but each of them is difficult or impossible to directly mine frequent episodes when the definition of support is changed.To meet the needs of changeable support definitions of users,an algorithm called FEM-DFS(frequent episode mining-depth first search)is proposed to mine frequent episodes in this paper.After scanning the event sequence one pass,FEM-DFS finds frequent episodes in a depth first search fashion,stores frequent episodes in a shared prefix/suffix tree and compresses the search space of frequent episodes by utilizing monotonicity,prefix monotonicity or suffix monotonicity.Experimental evaluation demonstrates the effectiveness of the proposed algorithm.