skip to main content
10.1145/1321440.1321549acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Generating concise association rules

Published: 06 November 2007 Publication History

Abstract

Association rule mining has made many achievements in the area of knowledge discovery. However, the quality of the extracted association rules is a big concern. One problem with the quality of the extracted association rules is the huge size of the extracted rule set. As a matter of fact, very often tens of thousands of association rules are extracted among which many are redundant thus useless. Mining non-redundant rules is a promising approach to solve this problem. The Min-max exact basis proposed by Pasquier et al [Pasquier05] has showed exciting results by generating only non-redundant rules. In this paper, we first propose a relaxing definition for redundancy under which the Min-max exact basis still contains redundant rules; then we propose a condensed representation called Reliable exact basis for exact association rules. The rules in the Reliable exact basis are not only non-redundant but also more succinct than the rules in Min-max exact basis. We prove that the redundancy eliminated by the Reliable exact basis does not reduce the belief to the Reliable exact basis. The size of the Reliable exact basis is much smaller than that of the Min-max exact basis. Moreover, we prove that all exact association rules can be deduced from the Reliable exact basis. Therefore the Reliable exact basis is a lossless representation of exact association rules. Experimental results show that the Reliable exact basis significantly reduces the number of non-redundant rules.

References

[1]
R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 207--216, 1993.
[2]
R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proceedings of the 20th International Conference on very large data bases, pages 487--499, 1994.
[3]
R. J. Bayardo. Efficiently mining long patterns from databases. In Proceedings of the 1998 ACM SIGMOD Conference, pages 85--93, 1998.
[4]
R. J. Bayardo, R. Agrawal, and D. Gunopulos. Constraint-based rule mining in large, dense databases. Data Mining and Knowledge Discovery, 4:217--240, 2000.
[5]
M. J. A. Berry and G. S. Linoff. Data Mining Techniques for Marketing, Sales and Customer Support. John Wiley and Sons, 1997.
[6]
S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In Proceedings of the 1997 ACM SIGMOD Conference, pages 255--264, 1997.
[7]
B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer-Verlag, 1999.
[8]
J. Han and Y. Fu. Mining multiple-level association rules in large databases. IEEE Transactions on Knowledge and Data Engineering, 11:798--804, 5 2000.
[9]
J. Han and J. Pei. Mining frequent patterns by pattern-growth: methodology and implications. ACM SIGKDD Explorations Newsletter, 2(2):14--20, 2000.
[10]
M. Kryszkiewicz, H. Rybinski, and M. Gajek. Dataless transitions between concise representations of frequent patterns. Journal of Intelligent Information Systems, 22(1):41--70, 2004.
[11]
K. Ng and B. Abramson. Uncertainty management in expert systems. IEEE Expert, 5(2):29--47, 1990.
[12]
R. T. Ng, V. Lakshmanan, J. Han, and A. Pang. Exploratory mining and pruning otimizations of constrained association rules. In Proceedings of the SIGMOD conference, pages 13--24, 1998.
[13]
N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequent closed itemsets for association rules. In Proceedings of the 7th ICDT conference, pages 398--416, 1999.
[14]
N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Efficient mining of association rultes using closed itemset lattices. Information Systems, 24(1):25--46, 1999.
[15]
N. Pasquier, R. Taouil, Y. Bastide, G. Stumme, and L. Lakhal. Generating a condensed representation for association rules. Journal of Intelligent Information Systems, 24(1):29--60, 2005.
[16]
J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In Proceedings of the DMKD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 21--30, 2000.
[17]
E. H. Shortliffe and B. G. Buchanan. A model of inexact reasoning in medicine. Mathematical Biosciences, 23(3/4):351--379, 1975.
[18]
R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In Proceedings of the KDD Conference, pages 67--73, 1997.
[19]
R. Wille. Restructuring lattices theory: An approach based on hierarchies of concepts. I. Rival (editor), Ordered sets. Dordrecht-Boston, 1982.
[20]
M. J. Zaki. Generating non-redundent association rules. In Proceedings of the KDD Conference, pages 34--43, 2000.
[21]
M. J. Zaki. Mining non-redundant association rules. Data Mining and Knowledge Discovery, 9:223--248, 2004.
[22]
M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In Proceedings of the 3rd KDD conference, pages 283--286, 1997.

Cited By

View all
  • (2021)GrAFCI+ A fast generator-based algorithm for mining frequent closed itemsetsKnowledge and Information Systems10.1007/s10115-021-01575-3Online publication date: 18-May-2021
  • (2016)Analytical Business Model for Sustainable Distributed Retail Enterprises in a Competitive MarketSustainability10.3390/su80201408:2(140)Online publication date: 4-Feb-2016
  • (2014)Feature Selection and Term WeightingProceedings of the 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) - Volume 0110.1109/WI-IAT.2014.53(336-339)Online publication date: 11-Aug-2014
  • Show More Cited By

Index Terms

  1. Generating concise association rules

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management
    November 2007
    1048 pages
    ISBN:9781595938039
    DOI:10.1145/1321440
    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: 06 November 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. closed itemsets
    2. generators
    3. redundant association rules

    Qualifiers

    • Research-article

    Conference

    CIKM07

    Acceptance Rates

    Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

    Upcoming Conference

    CIKM '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)GrAFCI+ A fast generator-based algorithm for mining frequent closed itemsetsKnowledge and Information Systems10.1007/s10115-021-01575-3Online publication date: 18-May-2021
    • (2016)Analytical Business Model for Sustainable Distributed Retail Enterprises in a Competitive MarketSustainability10.3390/su80201408:2(140)Online publication date: 4-Feb-2016
    • (2014)Feature Selection and Term WeightingProceedings of the 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) - Volume 0110.1109/WI-IAT.2014.53(336-339)Online publication date: 11-Aug-2014
    • (2014)Mining Positive Relevance Feedback to Determine User Information NeedsArabian Journal for Science and Engineering10.1007/s13369-014-1463-239:12(8765-8774)Online publication date: 12-Nov-2014
    • (2013)Mining Specific Features for Acquiring User Information NeedsAdvances in Knowledge Discovery and Data Mining10.1007/978-3-642-37453-1_44(532-543)Online publication date: 2013
    • (2013)Interestingness Measures for Multi-Level Association RulesInnovations in Intelligent Machines-410.1007/978-3-319-01866-9_2(47-74)Online publication date: 15-Nov-2013
    • (2012)Text mining in negative relevance feedbackWeb Intelligence and Agent Systems10.5555/2589968.258997010:2(151-163)Online publication date: 1-Apr-2012
    • (2010)A knowledge-based model using ontologies for personalized web information gatheringWeb Intelligence and Agent Systems10.5555/1839537.18395388:3(235-254)Online publication date: 1-Aug-2010
    • (2010)Mining positive and negative patterns for relevance feature discoveryProceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/1835804.1835900(753-762)Online publication date: 25-Jul-2010
    • (2010)A pattern mining approach for information filtering systemsInformation Retrieval10.1007/s10791-010-9154-414:3(237-256)Online publication date: 14-Dec-2010
    • Show More Cited By

    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