Affiliations: [a] Department of Computer Engineering, Sejong University, Seoul, Korea | [b] Department of Computer Science, Chungbuk National University, Cheongju, Korea
Correspondence:
[*]
Corresponding author: Unil Yun, Department of Computer Engineering, Sejong University, Seoul, Korea. E-mail:[email protected]
Abstract: In frequent pattern mining, items are considered as having the same
importance in a database and their occurrence are represented as binary
values in transactions. In real-world databases, however, items not only
have relative importance but also are represented as non-binary values in
transactions. High utility pattern mining is one of the most essential
issues in the pattern mining field, which recently emerged to address the
limitation of frequent pattern mining. Meanwhile, tree construction with a
single database scan is significant since a database scan is a
time-consuming task. In utility mining, an additional database scan is
necessary to identify actual high utility patterns from candidates. In this
paper, we propose a novel tree structure, namely SIQ-Tree (Sum of Item
Quantities), which captures database information through a single-pass.
Moreover, a restructuring method is suggested with strategies for reducing
overestimated utilities. The proposed algorithm can construct the SIQ-Tree
with only a single scan and decrease the number of candidate patterns
effectively with the reduced overestimation utilities, through which mining
performance is improved. Experimental results show that our algorithm
outperforms a state-of-the-art one in terms of runtime and the number of
generated candidates with a similar memory usage.
Keywords: Data mining, high utility patterns, single-pass tree construction, tree restructuring, utility mining
