Navegar

Colección

Datos Estadísticas

Artículo

Minuto Espil, M. "Tractable reasoning problems with fully-characterized association rules" (2012) 16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012. 7503 LNCS:282-295
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The support and confidence of association rules are defined in terms of itemset frequencies. While deciding the satisfiability of a set of itemset frequencies is known to be an NPTIME complete problem when frequencies are specified through rational ranges, this complexity result is too wide. To achieve tractability, two simpler problems are studied, instead. Both receive a set of association rules as input, each rule provided with exact support and confidence values, and the decision is to be made, respectively on the consistency of the addition and on the implication of a goal rule. Both allow bounds for the support and confidence values of the goal to be specified, and only admit itemsets relevant to the rules to have non-empty extensions in a model. We show that the problems are tractable and efficient algorithms for them are presented. © 2012 Springer-Verlag.

Registro:

Documento: Artículo
Título:Tractable reasoning problems with fully-characterized association rules
Autor:Minuto Espil, M.
Ciudad:Poznan
Filiación:FCEyN, Universidad de Buenos Aires, Argentina
Palabras clave:Complete problems; Complexity results; Item sets; Itemset; Satisfiability; Support and confidence; Tractable reasoning; Algorithms; Information systems; Association rules
Año:2012
Volumen:7503 LNCS
Página de inicio:282
Página de fin:295
DOI: http://dx.doi.org/10.1007/978-3-642-33074-2_21
Título revista:16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7503LNCS_n_p282_MinutoEspil

Referencias:

  • Antonie, M.-L., Zaïane, O.R., Mining Positive and Negative Association Rules: An Approach for Confined Rules (2004) LNCS (LNAI), 3202, pp. 27-38. , Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. Springer, Heidelberg
  • Agrawal, R., Srikant, R., Fast Algorithms for Mining Association Rules Proc. of the 20th International Conference on Very Large Databases (1994)
  • Balcázar, J.L., Deduction Schemes for Association Rules (2008) LNCS (LNAI), 5255, pp. 124-135. , Boulicaut, J.-F., Berthold, M.R., Horváth, T. (eds.) DS 2008. Springer, Heidelberg
  • Balcázar, J.L., Minimum-Size Bases of Association Rules (2008) LNCS (LNAI), 5211, pp. 86-101. , Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008, Part I. Springer, Heidelberg
  • Dyer, M.E., Linear Time Algorithms for Two- and Three-Variable Linear Programs (1984) SIAM Journal of Computing, 13 (1), pp. 31-45
  • Calders, T., Computational Complexity of Itemset Frequency Satisfiability (2004) 23th ACM Symposium on Principles of Database Systems PODS Proceedings, pp. 143-154. , ACM
  • Calders, T., Rigotti, C., Boulicaut, J., A Survey on Condensed Representations for Frequent Sets (2006) LNCS (LNAI), 3848, pp. 64-80. , Boulicaut, J.-F., De Raedt, L., Mannila, H. (eds.) Constraint-Based Mining and Inductive Databases. Springer, Heidelberg
  • Casali, A., Cicchetti, R., Lakhal, L., Essential Patterns: A Perfect Cover of Frequent Patterns (2005) LNCS, 3589, pp. 428-437. , Tjoa, A.M., Trujillo, J. (eds.) DaWaK 2005. Springer, Heidelberg
  • Jzefowska, J., Lawrynowicz, A., Lukaszewski, T., The role of semantics in mining frequent patterns from knowledge bases in description logics with rules (2010) TPLP, 10 (3), pp. 251-289
  • Kacprzyk, J., Zadrozny, S., Fuzzy linguistic summaries via association rules (2001) Data Mining and Computational Intelligence, pp. 115-139. , Springer, Physica
  • Kryszkiewicz, M., Gajek, M., Concise Representation of Frequent Patterns Based on Generalized Disjunction-Free Generators (2002) LNCS (LNAI), 2336, pp. 159-171. , Chen, M.-S., Yu, P.S., Liu, B. (eds.) PAKDD 2002. Springer, Heidelberg
  • Kryszkiewicz, M., Rybiński, H., Cichoń, K., On Concise Representations of Frequent Patterns Admitting Negation (2010) SCI, 263, pp. 259-289. , Koronacki, J., Raś, Z.W., Wierzchoń, S.T., Kacprzyk, J. (eds.) Advances in Machine Learning II. Springer, Heidelberg
  • Lenstra Jr., H., Integer Programming with a Fixed Number of Variables (1983) Mathematics of Operations Research, 8 (4), pp. 538-548
  • Luxemburger, M., Implications Partielles dans un Contexte, Mathematique (1991) Informatique et Sciences Humaines, 29 (113), pp. 35-55
  • Minuto Espil, M., RDF Semantics for Web Association Rules (2011) LNCS, 6902, pp. 269-274. , Rudolph, S., Gutierrez, C. (eds.) RR 2011. Springer, Heidelberg
  • Megiddo, N., Linear-Time Algorithms for Linear Programming in R3 and Related Problems (1983) SIAM Journal of Computing, 12 (4), pp. 759-776
  • Megiddo, N., Linear Programming in Linear Time When the Dimension Is Fixed (1984) Journal of ACM, 31 (1), pp. 114-127
  • Morzy, M., Efficient Mining of Dissociation Rules (2006) LNCS, 4081, pp. 228-237. , Tjoa, A.M., Trujillo, J. (eds.) DaWaK 2006. Springer, Heidelberg
  • Ng, R.T., Semantics, Consistency and Query Processing of Empirical Deductive Databases (1993) 10th International Conference on Logic Programming ICLP Proceedings, pp. 812-826. , MIT Press
  • Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L., Efficient Mining of Association Rules Using Closed Itemset Lattices (1999) Information Systems, 24 (1), pp. 25-46
  • Pasquier, N., Taouil, R., Bastide, Y., Stumme, G., Lakhal, L., Generating a Condensed Representation for Association Rules (2005) Journal on Intelligent Information Systems, 24 (1), pp. 29-60
  • Savasere, A., Omiecinski, A., Navathe, S., Mining for Strong Negative Associations in a Large Database of Customer Transactions (1998) 14th International Conference on Data Engineering, ICDE 1998, pp. 494-502. , IEEE CS
  • Srikant, R., Agrawal, R., Mining Generalized Association Rules Proc. of the 21st International Conference on Very Large Databases (1995)
  • Wu, X., Zhang, C., Zhang, C., Efficient mining of both positive and negative association rules (2004) ACM Transaction on Information Systems, 22 (3), pp. 381-405
  • Zaki, M., Mining Non-Redundant Association Rules (2004) Data Mining and Knowledge Discovery, 9 (3), pp. 223-248
  • Zaki, M., Ogihara, M., Theoretical Foundations of Association Rules (1998) 3rd ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 71-78
  • Zaki, M., Parthasarathy, S., Ogihara, M., Li, W., New Algorithms for Fast Discovery of Association Rules (1997) 3rd International Conference on Knowledge Discovery and Data Mining, pp. 283-286A4 - Allegro Group; City of Poznan; IBM; Roche; Microsoft

Citas:

---------- APA ----------
(2012) . Tractable reasoning problems with fully-characterized association rules. 16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012, 7503 LNCS, 282-295.
http://dx.doi.org/10.1007/978-3-642-33074-2_21
---------- CHICAGO ----------
Minuto Espil, M. "Tractable reasoning problems with fully-characterized association rules" . 16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012 7503 LNCS (2012) : 282-295.
http://dx.doi.org/10.1007/978-3-642-33074-2_21
---------- MLA ----------
Minuto Espil, M. "Tractable reasoning problems with fully-characterized association rules" . 16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012, vol. 7503 LNCS, 2012, pp. 282-295.
http://dx.doi.org/10.1007/978-3-642-33074-2_21
---------- VANCOUVER ----------
Minuto Espil, M. Tractable reasoning problems with fully-characterized association rules. Lect. Notes Comput. Sci. 2012;7503 LNCS:282-295.
http://dx.doi.org/10.1007/978-3-642-33074-2_21