Dynamic programming approach to optimization of approximate decision rules

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

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

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
Volume221
DOIs
StatePublished - Feb 2013

ASJC Scopus subject areas

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

Fingerprint

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

Cite this