skip to main content
10.1145/1516241.1516357acmconferencesArticle/Chapter ViewAbstractPublication PagesicuimcConference Proceedingsconference-collections
research-article

Mining high utility patterns in incremental databases

Published: 15 February 2009 Publication History

Abstract

Frequent pattern mining techniques treat all items in the database equally by taking into consideration only the presence of an item within a transaction. However, the customer may purchase more than one of the same item, and the unit price may vary among items. High utility pattern mining approaches have been proposed to overcome this problem. As a result, it becomes a very important research issue in data mining and knowledge discovery. On the other hand, incremental and interactive data mining provides the ability to use previous data structures and mining results in order to reduce unnecessary calculations when the database is updated, or when the minimum threshold is changed. In this paper, we propose a tree structure, called IIUT (incremental and interactive utility tree), to solve these problems together. It uses a pattern growth mining approach to avoid the level-wise candidate set generation-and-test problem, and it can efficiently capture the incremental data without any restructuring operation. Moreover, IIUT has the "build once mine many" property and therefore it is highly suitable for interactive mining. Experimental results show that our tree structure is very efficient and scalable for incremental and interactive high utility pattern mining.

References

[1]
Agrawal, R., Imieliński, T., and Swami, A. Mining association rules between sets of items in large databases. In ACM SIGMOD Int. Conf. on Management of Data, pp. 207--216, 1993.
[2]
Agrawal, R., and Srikant, R. Fast Algorithms for Mining Association Rules. In 20th Int. Conf. on Very Large Data Bases, pp. 487--499, 1994.
[3]
Yun, U. Efficient Mining of weighted interesting patterns with a strong weight and/or support affinity. Information Sciences, vol. 177, pp. 3477--3499, 2007.
[4]
Yao, H., Hamilton, H. J., and C. J. Butz. A Foundational Approach to Mining Itemset Utilities from Databases, In Proceedings of the Third SIAM International Conference on Data Mining, pp. 482--486, 2004.
[5]
Yao, H., and Hamilton, H. J. Mining itemset utilities from transaction databases, Data & Knowledge Engineering, vol. 59, pp. 603--626, 2006.
[6]
Liu, Y., Liao, W.-K., and Choudhary, A. A Two Phase algorithm for fast discovery of High Utility of Itemsets, In Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'05), pp. 689--695. 2005.
[7]
Barber, B., and Hamilton, H. J. Extracting share frequent itemsets with infrequent subsets, Data Mining and Knowledge Discovery, vol. 7, pp. 153--185, 2003.
[8]
Chan, R., Yang, Q., and Shen, Y. D. Mining High Utility Itemsets, In Proceedings of the Third IEEE International Conference on Data Mining, pp. 19--26, 2003.
[9]
Tao, F. Weighted association rule mining using weighted support and significant framework. In 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 661--666, 2003.
[10]
Wang, W., Yang, J., and Yu, P. S. WAR: weighted association rules for item intensities. Knowledge Information and Systems, vol. 6, pp. 203--229, 2004.
[11]
Han, J., Pei, J., Yin, Y., and Mao, R. Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, vol. 8, pp. 53--87, 2004.
[12]
Grahne, G., and Zhu, J. Fast Algorithms for frequent itemset mining using FP-Trees. IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 10, pp. 1347--1362, 2005.
[13]
Han, J., Cheng, H., Xin, D., and Yan, X. Frequent pattern mining: current status and future directions. Data Mining and Knowledge Discovery, vol. 15, pp. 55--86, 2007.
[14]
Cheung, W., and Zaïane, O. R. Incremental Mining of Frequent Patterns Without Candidate Generation or Support Constraint, In Proceedings of the Seventh International Database Engineering and Applications Symposium (IDEAS'03), pp.111--116, 2003.
[15]
Koh, J.-L., Shieh, S.-F. An Efficient Approach for Maintaining Association Rules Based on Adjusting FP-tree Structures. In Proceedings of DASFAA 2004. LNCS, vol. 2973, pp. 417--424, 2004.
[16]
Li, X., Deng, Z. -H., and Tang, S. A fast algorithm for maintenance of association rules in incremental databases. Advanced Data Mining and Applications (ADMA), vol. 4093, pp. 56--63, 2006.
[17]
Lee, Y. -S., Yen, and S. -J. Incremental and interactive mining of web traversal patterns, Information Science, vol. 178, pp. 287--306, 2008.
[18]
Leung, C. K. -S., Khan, Q. I., Li, Z., and Hoque, T. CanTree: a canonical-order tree for incremental frequent-pattern mining. Knowledge and Information Systems, vol. 11, no. 3, pp. 287--311, 2007.
[19]
Yun, U. Mining lossless closed frequent patterns with weight constraints. Knowledge-Based Systems, vol. 210, pp. 86--97, 2007.
[20]
Erwin, A., Gopalan, R. P., and Achuthan, N. R. CTU-Mine: An Efficient High Utility Itemset Mining Algorithm Using the Pattern Growth Approach. In Proceedings of the Seventh IEEE International Conference on Computer and Information Technology (CIT'07), pp. 71--76, 2007.
[21]
Hu, J., and Mojsilovic, A. High Utility Pattern Mining: A method for discovery of high utility item sets, Pattern Recognition, vol. 40, pp. 3317--3324, 2007.
[22]
Zhang, S., Zhang, J., and Zhang, C. EDUA: An efficient algorithm for dynamic database mining, Information Sciences, vol. 177, pp. 2756--2767, 2007.
[23]
Li, Y. -C., Yeh, J. -S., and Chang, C. -C. Isolated items discarding strategy for discovering high utility itemsets, Data & Knowledge Engineering 64, pp. 198--217, 2008.
[24]
Tanbeer, S. K., Ahmed, C. F., Jeong, B. -S., Lee, Y. -K. CP-tree: A tree structure for single pass frequent pattern mining. In: 12th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD), pp. 1022--1027, 2008.

Cited By

View all
  • (2019)Efficient high average-utility itemset mining using novel vertical weak upper-boundsKnowledge-Based Systems10.1016/j.knosys.2019.07.018Online publication date: Jul-2019
  • (2012)EGDIMProceedings of the 6th International Conference on Ubiquitous Information Management and Communication10.1145/2184751.2184820(1-10)Online publication date: 20-Feb-2012

Index Terms

  1. Mining high utility patterns in incremental databases

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication
    February 2009
    704 pages
    ISBN:9781605584058
    DOI:10.1145/1516241
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 February 2009

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. data mining
    2. frequent pattern mining
    3. high utility pattern mining
    4. incremental mining
    5. interactive mining
    6. knowledge discovery

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    ICUIMC '09
    Sponsor:

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Efficient high average-utility itemset mining using novel vertical weak upper-boundsKnowledge-Based Systems10.1016/j.knosys.2019.07.018Online publication date: Jul-2019
    • (2012)EGDIMProceedings of the 6th International Conference on Ubiquitous Information Management and Communication10.1145/2184751.2184820(1-10)Online publication date: 20-Feb-2012

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media