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: | SER |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v7503LNCS_n_p282_MinutoEspil |
| Aporte de: |
| Sumario: | 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. |
|---|