Dynamic programming approach to optimization of approximate decision rules

Talha M. Amin, Igor Chikalov, Mikhail Moshkov, Beata Zielosko

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


This paper is devoted to the study of an extension of dynamic programming approach which allows sequential optimization of approximate decision rules relative to the length and coverage. We introduce an uncertainty measure R(T) which is the number of unordered pairs of rows with different decisions in the decision table T. For a nonnegative real number β, we consider β-decision rules that localize rows in subtables of T with uncertainty at most β. Our algorithm constructs a directed acyclic graph Δβ(T) which nodes are subtables of the decision table T given by systems of equations of the kind "attribute = value". This algorithm finishes the partitioning of a subtable when its uncertainty is at most β. The graph Δβ(T) allows us to describe the whole set of so-called irredundant β-decision rules. We can describe all irredundant β-decision rules with minimum length, and after that among these rules describe all rules with maximum coverage. We can also change the order of optimization. The consideration of irredundant rules only does not change the results of optimization. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository. © 2012 Elsevier Inc. All rights reserved.
Original languageEnglish (US)
Pages (from-to)403-418
Number of pages16
JournalInformation Sciences
StatePublished - Feb 2013

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This research was supported by King Abdullah University of Science and Technology in the frameworks of joint project with Nizhni Novgorod State University "Novel Algorithms in Machine Learning and Computer Vision, and their High Performance Implementations", Russian Federal Program "Research and Development in Prioritized Directions of Scientific-Technological Complex of Russia in 2007-2013".

ASJC Scopus subject areas

  • Artificial Intelligence
  • Theoretical Computer Science
  • Software
  • Information Systems and Management
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'Dynamic programming approach to optimization of approximate decision rules'. Together they form a unique fingerprint.

Cite this