Dynamic programming approach for partial decision rule optimization

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

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


This paper is devoted to the study of an extension of dynamic programming approach which allows optimization of partial decision rules relative to the length or coverage. We introduce an uncertainty measure J(T) which is the difference between number of rows in a decision table T and number of rows with the most common decision for T. For a nonnegative real number γ, we consider γ-decision rules (partial decision rules) that localize rows in subtables of T with uncertainty at most γ. Presented 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 optimize such set of rules according to length or coverage. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository.
Original languageEnglish (US)
Pages (from-to)233-248
Number of pages16
JournalFundamenta Informaticae
Issue number3-4
StatePublished - Oct 4 2012

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Algebra and Number Theory
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'Dynamic programming approach for partial decision rule optimization'. Together they form a unique fingerprint.

Cite this