Dynamic Programming Approach for Partial Decision Rule Optimization

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 gamma, we consider gamma-decision rules (partial decision rules) that localize rows in subtables of T with uncertainty at most gamma. Presented algorithm constructs a directed acyclic graph Delta(gamma)(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 gamma. The graph Delta(gamma)(T) allows us to describe the whole set of so-called irredundant gamma-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.