|
In this paper, we present a novel data-mining algorithm, called LPS-Miner, to mine the complete frequent patterns in the transaction database. LPS-Miner algorithm bases the pattern growth principle and uses two new data structures, LPS-FP-Tree (Light Partial-Support FP-Tree) and LPS-Forest (Light Partial-Support FP-Tree Forest) to present the database. LPS-FP-Tree is a variation of FP-Tree with lighter and unidirectional nodes and mining process depends on partial-support of the patterns. The algorithm adopts partition and divide-and-conquer strategies in maximum, which decomposes the mining task into a set of smaller tasks. The light data structure and the efficient memory management mechanism keep the memory usage stable and efficient. Moreover, other implementation-based optimizations, such as pruning and outputting-optimization, make the algorithm achieve high efficiency. We test our c++ implementation of this algorithm versus several other algorithms on four datasets. The experimental results show that our algorithm has better space and time efficiency. |
|
Keywords:Data mining; Frequent pattern mining; FP-growth; FP-Tree |
|