Experimental Study of Totally Optimal Decision Rules

摘要

In this paper, we experimentally study the existence of totally optimal decision rules which are optimal relative to the length and coverage simultaneously for nine decision tables from the UCI Machine Learning Repository. Totally optimal rules can be useful when we consider decision rules as a way for knowledge representation. We study not only exact but also approximate decision rules based on the three uncertainty measures: entropy, Gini index, and misclassification error. To investigate the existence of totally optimal rules, we use an extension of dynamic programming that allows us to make multi-stage optimization of decision rules relative to the length and coverage. Experimental results show that totally optimal decision rules exist in many cases. However, the behavior of graphs describing how the number of rows of decision tables with totally optimal decision rules depends on the accuracy of rules is irregular.