LEVEL-WISE CONSTRUCTION OF DECISION TREES FOR CLASSIFICATION
Yan Zhao, Yiyu Y. Yao, JingTao Yao · International Journal of Software Engineering and Knowledge Engineering · 2006
A partition-based framework is presented for a formal study of classification problems. An information table is used as a knowledge representation, in which all basic notions are precisely defined by using a language known as the decision logic language. Solutions to, and solution space of, classification problems are formulated in terms of partitions. Algorithms for finding solutions are modelled as searching in a space of partitions under the refinement order relation. We focus on a particular type of solutions called conjunctively definable partitions. Two level-wise methods for decision tree construction are investigated, which are related to two different strategies: local optimization and global optimization. They are not in competition with, but are complementary to each other. Experimental results are reported to evaluate the two methods.