In this paper, we present results of experimental studies related to the existence of totally optimal decision trees (which are optimal relative to two or more cost functions simultaneously) for nine decision tables from the UCI Machine Learning Repository. Such trees can be useful when we consider decision trees as algorithms for problem solving or as a way for knowledge representation. For cost functions, we use depth, average depth, and number of nodes. We study not only exact but also approximate decision trees based on five uncertainty measures: entropy, Gini index, misclassification error, relative misclassification error, and number of unordered pairs of rows with different decisions. To investigate the existence of totally optimal trees, we use an extension of dynamic programming that allows us to make multi-stage optimization of decision trees relative to a sequence of cost functions. Experimental results show that totally optimal decision trees exist in many cases. The behavior of graphs that describe how the number of decision tables with totally optimal decision trees depends on their accuracy is mainly irregular. However, one can observe some trends, in particular, an upward trend when accuracy is decreasing.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper, seven greedy heuristics for construction of association rules are compared from the point of view of the length and coverage of constructed rules. The obtained rules are compared also with optimal ones constructed by dynamic programming algorithms. The average relative difference between length of rules constructed by the best heuristic and minimum length of rules is at most 4%. The same situation is with coverage.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.