关键词: 高效用, 模式挖掘, 树, 列表, 一阶段算法, 二阶段算法, 剪枝策略

Abstract:

High utility pattern mining is used to find serviceable information from the data for users. Due to the multiple existing algorithms of high utility pattern mining, how to choose the superior way and be in progress is the prevalent problem. To solve this problem, people consider the classification of high utility pattern mining algorithms firstly, and find out the corresponding algorithm according to these issues afterward. Multiple different kinds of algorithms can be divided, in the light of different perspectives, i.e. divided into tree-based and utility list-based methods from the types using data structures, divided into one-stage and two-stage methods from the implementation needs. In addition, the algorithms can be divided through the pruning strategy, such as projection, remain utility, minimum utility improvement, etc. This paper starts with analyzing one-stage and two-stage high utility methods, which aims at tree-based two-stage algorithm and list-based one-stage algorithm. And then, this paper explores the tree-based one from whether to generate candidates. Finally, this paper discusses the space reduction strategy of high utility mining, e.g., pruning strategy and projection technology. Through analysis, the one-stage algorithm is superior to the two-stage algorithm in terms of time and space, and the algorithm that does not produce candidate itemsets is superior to the algorithm that produces candidate itemsets in terms of time and space. Generally, the algorithm reduces the search space through a variety of pruning strategies.

Key words: high utility, pattern mining, tree, list, one-stage algorithm, two-stage algorithm, pruning strategy