Affiliations: Mathematical and Computer Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia, {talha.amin, igor.chikalov, mikhail.moshkov, beata.zielosko}@kaust.edu.sa
Note: [] Address for correspondence: Mathematical and Computer Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia Also works: Institute of Computer Science, University of Silesia, 39, Będzińska St., Sosnowiec 41-200, Poland
Abstract: 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.
