No Access

Closed-Set-Based Discovery of Representative Association Rules

Department of Mathematics, Statistics and Computation, Universidad de Cantabria, Av. de los Castros 48, Santander 39005, Spain

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

José L. Balcázar

Department of Computer Science, Universitat Politècnica de Catalunya, C. Jordi Girona 1-3, Omega 005, Barcelona 08034, Spain

E-mail Address: [email protected]

Search for more papers by this author

, and

Domingo Gómez-Pérez

Department of Mathematics, Statistics and Computation, Universidad de Cantabria, Av. de los Castros 48, Santander 39005, Spain

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0129054120400109Cited by:1 (Source: Crossref)

This article is part of the issue:

Special Issue — A Collection of Papers in Honour of the 60th Birthday of Victor Mitrana

Abstract

The output of an association rule miner is often huge in practice. This is why several concise lossless representations have been proposed, such as the “essential” or “representative” rules. A previously known algorithm for mining representative rules relies on an incorrect mathematical claim, and can be seen to miss part of its intended output; in previous work, two of the authors of the present paper have offered a complete but, often, somewhat slower alternative. Here, we extend this alternative to the case of closure-based redundancy. The empirical validation shows that, in this way, we can improve on the original time efficiency, without sacrificing completeness.

Communicated by Erzsébet Csuhaj-Varjú and Florin Manea

Keywords:

References

1. C. C. Aggarwal and P. S. Yu, A new approach to online generation of association rules, IEEE Transactions on Knowledge and Data Engineering 13(4) (2001) 527–540. Crossref, Web of Science, Google Scholar
2. A. Asuncion and D. Newman, UCI machine learning repository (2007). Google Scholar
3. J. L. Balcázar, Redundancy, deduction schemes, and minimum-size bases for association rules, Logical Methods in Computer Science 6(2:3) (2010) 1–33. Web of Science, Google Scholar
4. J. L. Balcázar and C. Tîrnăucă, Closed-set-based discovery of representative association rules revisited, Actes de Extraction et gestion des connaissances (EGC), eds. A. Khenchaf and P. Poncelet Revue des Nouvelles Technologies de l’Information RNTI-E-20 (Hermann-Éditions, 2011), pp. 635–646. Google Scholar
5. T. Brijs et al., Using association rules for product assortment decisions: A case study, Proc. of the fifth ACM SIGKDD international conference on Knowledge Discovery and Data Mining (1999), pp. 254–260. Crossref, Google Scholar
6. A. Ceglar and J. F. Roddick, Association mining, ACM Comput. Surv. 38 (2006). Crossref, Web of Science, Google Scholar
7. K. Geurts, Traffic accidents data set, http://fimi.ua.ac.be/data/accidents.pdf (2004). Google Scholar
8. B. Goethals, Frequent itemset mining implementations repository, http://fimi.ua.ac.be/ (2004). Google Scholar
9. J. Guigues and V. Duquenne, Familles minimales d’implications informatives résultant d’un tableau de données binaires, Mathématiques et Sciences Humaines 95 (1986) 5–18. Google Scholar
10. D. Gunopulos et al., Discovering all most specific sentences, ACM Trans. Database Syst. 28(2) (2003) 140–174. Crossref, Web of Science, Google Scholar
11. M. Kryszkiewicz, Fast discovery of representative association rules, Proc. of the 1st International Conference on Rough Sets and Current Trends in Computing (RSCTC), eds. L. Polkowski and A. Skowron, Lecture Notes in Computer Science, Vol. 1424 (Springer, 1998), pp. 214–221. Crossref, Google Scholar
12. M. Kryszkiewicz, Closed set based discovery of representative association rules, Proc. of the 4th International Symposium on Intelligent Data Analysis (IDA), eds. F. Hoffmann, D. J. Hand, N. M. Adams, D. H. Fisher and G. Guimarães, Lecture Notes in Computer Science, Vol. 2189 (Springer, 2001), pp. 350–359. Crossref, Google Scholar
13. M. Kryszkiewicz, Concise representations of association rules, Proc. of the ESF Exploratory Workshop on Pattern Detection and Discovery, eds. D. J. Hand, N. M. Adams and R. J. Bolton, Lecture Notes in Computer Science, Vol. 2447 (Springer, 2002), pp. 92–109. Crossref, Google Scholar
14. N. Pasquier et al., Generating a condensed representation for association rules, J. Intell. Inf. Syst. 24(1) (2005) 29–60. Crossref, Web of Science, Google Scholar
15. J. Saquer and J. S. Deogun, Using closed itemsets for discovering representative association rules, Proc. of the 12th International Symposium on Foundations of Intelligent Systems (ISMIS), eds. Z. W. Ras and S. Ohsuga, Lecture Notes in Computer Science, Vol. 1932 (Springer, 2000), pp. 495–504. Crossref, Google Scholar
16. P. Valtchev, R. Missaoui and R. Godin, Formal concept analysis for knowledge discovery and data mining: The new challenges, Concept Lattices, Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23–26, 2004, Proceedings, ed. P. W. Eklund, Lecture Notes in Computer Science, Vol. 2961 (Springer, 2004), pp. 352–371. Crossref, Google Scholar
17. M. J. Zaki, Mining non-redundant association rules, Data Min. Knowl. Discov. 9(3) (2004) 223–248. Crossref, Web of Science, Google Scholar