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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Minuto Espil, M.
Formato: SER
Materias:
Complete problems
Complexity results
Item sets
Itemset
Satisfiability
Support and confidence
Tractable reasoning
Algorithms
Information systems
Association rules
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v7503LNCS_n_p282_MinutoEspil
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v7503LNCS_n_p282_MinutoEspil
record_format dspace
spelling todo:paper_03029743_v7503LNCS_n_p282_MinutoEspil2023-10-03T15:19:30Z Tractable reasoning problems with fully-characterized association rules Minuto Espil, M. Complete problems Complexity results Item sets Itemset Satisfiability Support and confidence Tractable reasoning Algorithms Information systems 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 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v7503LNCS_n_p282_MinutoEspil
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Complete problems
Complexity results
Item sets
Itemset
Satisfiability
Support and confidence
Tractable reasoning
Algorithms
Information systems
Association rules
spellingShingle Complete problems
Complexity results
Item sets
Itemset
Satisfiability
Support and confidence
Tractable reasoning
Algorithms
Information systems
Association rules
Minuto Espil, M.
Tractable reasoning problems with fully-characterized association rules
topic_facet Complete problems
Complexity results
Item sets
Itemset
Satisfiability
Support and confidence
Tractable reasoning
Algorithms
Information systems
Association rules
description 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.
format SER
author Minuto Espil, M.
author_facet Minuto Espil, M.
author_sort Minuto Espil, M.
title Tractable reasoning problems with fully-characterized association rules
title_short Tractable reasoning problems with fully-characterized association rules
title_full Tractable reasoning problems with fully-characterized association rules
title_fullStr Tractable reasoning problems with fully-characterized association rules
title_full_unstemmed Tractable reasoning problems with fully-characterized association rules
title_sort tractable reasoning problems with fully-characterized association rules
url http://hdl.handle.net/20.500.12110/paper_03029743_v7503LNCS_n_p282_MinutoEspil
work_keys_str_mv AT minutoespilm tractablereasoningproblemswithfullycharacterizedassociationrules
_version_ 1807315203714449408

Ejemplares similares