›› 2016, Vol. 31 ›› Issue (4): 776-786.doi: 10.1007/s11390-016-1662-2

Special Issue: Data Management and Data Mining

• Special Section on Data Management and Data Mining 2016 • Previous Articles     Next Articles

HUITWU: An Efficient Algorithm for High-Utility Itemset Mining in Transaction Databases

Shi-Ming Guo, and Hong Gao, Member, CCF   

  1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
  • Received:2016-02-29 Revised:2016-06-06 Online:2016-07-05 Published:2016-07-05
  • About author:Shi-Ming Guo received his B.S. degree in software engineering from Harbin Institute of Technology, Harbin, in 2004. He is currently a Ph.D. candidate in the School of Computer Science and Technology at Harbin Institute of Technology, Harbin. His current research interests include high-utility pattern mining and massive data management.
  • Supported by:

    This work is partly supported by the National Basic Research 973 Program of China under Grant No. 2012CB316200 and the National Natural Science Foundation of China under Grant Nos. 61190115 and 61173022.

Mining high-utility itemsets (HUIs) from a transaction database refers to the discovery of itemsets with high utilities like profits. Most of existing studies discover HUIs from a transaction database in two phases. In phase 1, different overestimation methods are applied to calculate the upper bounds of the utilities of itemsets. Since the overestimated utilities of itemsets are adopted, the itemsets whose overestimated utilities are no less than a user-specified threshold are selected as candidate HUIs, and they are verified by scanning the database one more time in phase 2. However, a large number of candidate HUIs incur two problems:1) it requires excessive memory to store these candidates; 2) it needs a large amount of running time to calculate their exact utilities. Vertical data format has been applied to mine HUIs recently. However this kind of method cannot deal with transactions with the same items effectively so that the size of database cannot be reduced sufficiently. The overall performance of algorithms is degraded consequently. Thus an algorithm HUITWU is proposed in this paper for mining HUIs. A novel data structure HUITWU-Tree is adopted to efficiently calculate the utilities of itemsets in a database. Extensive studies with both sparse and dense datasets have demonstrated that our proposed algorithm is more than an order of magnitude faster and consumes less memory than the state-of-the-art algorithms.

[1] Yao H, Hamilton H J, Butz C J. A foundational approach to mining itemset utilities from databases. In Proc. the 4th SIAM Int. Conf. Data Min., April 2004, pp.482-486.

[2] Ahmed C F, Tanbeer S K, Jeong B S et al. Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans. Knowl. Data Eng., 2009, 21(12):1708-1721.

[3] Tseng V A, Shie B E, Wu C W, Yu P S. Efficient algorithms for mining high utility itemsets from transactional databases. IEEE Trans. Knowl. Data Eng., 2013, 25(8):1772-1786.

[4] Pei J, Han J, Lakshmanan L V S. Mining frequent itemsets with convertible constraints. In Proc. the 17th Int. Conf. Data Eng., April 2001, pp.433-442.

[5] Li Y X, Yeh J S, Chang C C. Isolated items discarding strategy for discovering high utility itemsets. Data Knowl. Eng., 2008, 64(1):198-217.

[6] Liu Y, Liao W, Choudhary A. A two-phase algorithm for fast discovery of high utility of itemsets. In Proc. the 9th Pacific-Asia Conf. Knowl. Discov. Data Min., May 2005, pp.689-695.

[7] Liu M, Qu J. Mining high utility itemsets without candidate generation. In Proc. the 21st ACM Int. Conf. Inf. Knowl. Man., October 29-November 2, 2012, pp.55-64.

[8] Fournier-Viger P, Wu C W, Zida S, Tseng V S. FHM:Faster high-utility itemset mining using estimated utility co-occurrence pruning. In Proc. the 21th Int. Symp. Meth. Intel. Sys., June 2014, pp.83-92.

[9] Han J, Pei J, Yin Y, Mao R. Mining frequent patterns without candidate generation:A frequent-pattern tree approach. Data Min. Knowl. Discov., 2004, 8(1):53-87.

[10] Wang J, Han J, Pei J. CLOSET+:Searching for the best strategies for mining frequent closed itemsets. In Proc. the 9th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., August 2003, pp.236-245.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[5] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[6] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[7] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[8] Lu Xuemiao;. On the Complexity of Induction of Structural Descriptions[J]. , 1987, 2(1): 12 -21 .
[9] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[10] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved