Abstract
High utility mining is a fundamental topic in association rule mining, which aims to discover all itemsets with high utility from transaction database. The previous studies are mainly based on fixed databases, which are not applicable for incremental databases. Although incremental high utility pattern (IHUP) mining has been proposed, its tree structure IHUP-Tree is redundant and thus IHUP algorithm has relative low efficiency. To address this issue, we propose an incremental compressed high utility mining algorithm called iCHUM. The iCHUM algorithm utilizes items of high transaction weighted utilization (TWU) to construct its tree structure, namely iCHUM-Tree. The iCHUM algorithm updates iCHUM-Tree when new database is appended to the original database. The information of high utility itemsets is maintained in the iCHUM-Tree such that candidate itemsets can be generated through mining procedure. Performance analysis shows that our algorithm is more efficient than baseline approaches in incremental databases.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agrawal, R., Imieliński, T., Swami, A.: Mining association rules between sets of items in large databases. ACM SIGMOD Record 22(2), 207–216 (1993)
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules. In: Proceedings of the 20th International Conference on Very Large Data Bases, pp. 487–499 (1994)
Ahmed, C.F., Tanbeer, S.K., Jeong, B.S., Lee, Y.K.: Efficient tree structures for high utility pattern mining in incremental databases. IEEE Transactions on Knowledge and Data Engineering 21(12), 1708–1721 (2009)
Erwin, A., Gopalan, R.P., Achuthan, N.: Ctu-mine: an efficient high utility itemset mining algorithm using the pattern growth approach. In: 2007 7th IEEE International Conference on Computer and Information Technology, pp. 71–76 (2007)
Grahne, G., Zhu, J.: Fast algorithms for frequent itemset mining using fp-trees. IEEE Transactions on Knowledge and Data Engineering 17(10), 1347–1362 (2005)
Han, J., Pei, J., Yin, Y.: Mining frequent patterns without candidate generation. ACM SIGMOD Record 29(2), 1–12 (2000)
Koh, J.-L., Shieh, S.-F.: An efficient approach for maintaining association rules based on adjusting fp-tree structures. In: Lee, Y.J., Whang, K.-Y., Li, J., Lee, D. (eds.) DASFAA 2004. LNCS, vol. 2973, pp. 417–424. Springer, Heidelberg (2004)
Li, Y.C., Yeh, J.S., Chang, C.C.: Efficient algorithms for mining share-frequent itemsets. In: Proceedings of the 11th International Fuzzy Systems Association World Congress, pp. 534–539 (2005)
Li, Y.C., Yeh, J.S., Chang, C.C.: Isolated items discarding strategy for discovering high utility itemsets. Data & Knowledge Engineering 64(1), 198–217 (2008)
Lin, C.W., Hong, T.P., Lu, W.H.: Maintaining high utility pattern trees in dynamic databases. In: 2010 2nd International Conference on Computer Engineering and Applications, pp. 304–308 (2010)
Lin, C.W., Hong, T.P., Lu, W.H.: An effective tree structure for mining high utility itemsets. Expert Systems with Applications 38(6), 7419–7424 (2011)
Lin, C.W., Lan, G.C., Hong, T.P.: An incremental mining algorithm for high utility itemsets. Expert Systems with Applications 39(8), 7173–7180 (2012)
Liu, Y., Liao, W.K., Choudhary, A.: A fast high utility itemsets mining algorithm. In: Proceedings of the 1st International Workshop on Utility-based Data Mining, pp. 90–99 (2005)
Liu, Y., Liao, W., Choudhary, A.K.: A two-phase algorithm for fast discovery of high utility itemsets. In: Cheung, D., Ho, T.-B., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol. 3518, pp. 689–695. Springer, Heidelberg (2005)
Tseng, V.S., Wu, C.W., Shie, B.E., Yu, P.S.: Up-growth: an efficient algorithm for high utility itemset mining. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 253–262 (2010)
Wu, C.W., Shie, B.E., Tseng, V.S., Yu, P.S.: Mining top-k high utility itemsets. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 78–86 (2012)
Yeh, J.S., Chang, C.Y., Wang, Y.T.: Efficient algorithms for incremental utility mining. In: Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication, pp. 212–217 (2008)
Yun, U.: Efficient mining of weighted interesting patterns with a strong weight and/or support affinity. Information Sciences 177(17), 3477–3499 (2007)
Yun, U., Leggett, J.J.: Wfim: weighted frequent itemset mining with a weight range and a minimum weight. In: Proceedings of the 2005 SIAM International Conference on Data Mining, pp. 636–640 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zheng, HT., Li, Z. (2015). iCHUM: An Efficient Algorithm for High Utility Mining in Incremental Databases. In: Zhang, S., Wirsing, M., Zhang, Z. (eds) Knowledge Science, Engineering and Management. KSEM 2015. Lecture Notes in Computer Science(), vol 9403. Springer, Cham. https://doi.org/10.1007/978-3-319-25159-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-25159-2_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25158-5
Online ISBN: 978-3-319-25159-2
eBook Packages: Computer ScienceComputer Science (R0)