Tractable reasoning problems with fully-characterized association rules
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 achi...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2012
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 08210caa a22007457a 4500 | ||
|---|---|---|---|
| 001 | PAPER-9238 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203908.0 | ||
| 008 | 190411s2012 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84867688301 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Minuto Espil, M. | |
| 245 | 1 | 0 | |a Tractable reasoning problems with fully-characterized association rules |
| 260 | |c 2012 | ||
| 270 | 1 | 0 | |m Minuto Espil, M.; FCEyN, Universidad de Buenos AiresArgentina |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Agrawal, R., Srikant, R., Fast Algorithms for Mining Association Rules Proc. of the 20th International Conference on Very Large Databases (1994) | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Dyer, M.E., Linear Time Algorithms for Two- and Three-Variable Linear Programs (1984) SIAM Journal of Computing, 13 (1), pp. 31-45 | ||
| 504 | |a Calders, T., Computational Complexity of Itemset Frequency Satisfiability (2004) 23th ACM Symposium on Principles of Database Systems PODS Proceedings, pp. 143-154. , ACM | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Kacprzyk, J., Zadrozny, S., Fuzzy linguistic summaries via association rules (2001) Data Mining and Computational Intelligence, pp. 115-139. , Springer, Physica | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Lenstra Jr., H., Integer Programming with a Fixed Number of Variables (1983) Mathematics of Operations Research, 8 (4), pp. 538-548 | ||
| 504 | |a Luxemburger, M., Implications Partielles dans un Contexte, Mathematique (1991) Informatique et Sciences Humaines, 29 (113), pp. 35-55 | ||
| 504 | |a Minuto Espil, M., RDF Semantics for Web Association Rules (2011) LNCS, 6902, pp. 269-274. , Rudolph, S., Gutierrez, C. (eds.) RR 2011. Springer, Heidelberg | ||
| 504 | |a Megiddo, N., Linear-Time Algorithms for Linear Programming in R3 and Related Problems (1983) SIAM Journal of Computing, 12 (4), pp. 759-776 | ||
| 504 | |a Megiddo, N., Linear Programming in Linear Time When the Dimension Is Fixed (1984) Journal of ACM, 31 (1), pp. 114-127 | ||
| 504 | |a Morzy, M., Efficient Mining of Dissociation Rules (2006) LNCS, 4081, pp. 228-237. , Tjoa, A.M., Trujillo, J. (eds.) DaWaK 2006. Springer, Heidelberg | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Srikant, R., Agrawal, R., Mining Generalized Association Rules Proc. of the 21st International Conference on Very Large Databases (1995) | ||
| 504 | |a 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 | ||
| 504 | |a Zaki, M., Mining Non-Redundant Association Rules (2004) Data Mining and Knowledge Discovery, 9 (3), pp. 223-248 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a FCEyN, Universidad de Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMPLETE PROBLEMS |
| 690 | 1 | 0 | |a COMPLEXITY RESULTS |
| 690 | 1 | 0 | |a ITEM SETS |
| 690 | 1 | 0 | |a ITEMSET |
| 690 | 1 | 0 | |a SATISFIABILITY |
| 690 | 1 | 0 | |a SUPPORT AND CONFIDENCE |
| 690 | 1 | 0 | |a TRACTABLE REASONING |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a INFORMATION SYSTEMS |
| 690 | 1 | 0 | |a ASSOCIATION RULES |
| 711 | 2 | |c Poznan |d 18 September 2012 through 21 September 2012 |g Código de la conferencia: 93239 | |
| 773 | 0 | |d 2012 |g v. 7503 LNCS |h pp. 282-295 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 9783642330735 |t 16th East European Conference on Advances in Databases and Information Systems, ADBIS 2012 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84867688301&doi=10.1007%2f978-3-642-33074-2_21&partnerID=40&md5=141df90e83d7d94aea7de97940325e04 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-642-33074-2_21 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v7503LNCS_n_p282_MinutoEspil |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7503LNCS_n_p282_MinutoEspil |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v7503LNCS_n_p282_MinutoEspil |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 70191 | ||