Abstract
The paper describes an algorithm that constructs approximate decision trees (alpha-decision trees), which are optimal relatively to one of the following complexity measures: depth, total path length or number of nodes. The algorithm uses dynamic programming and extends methods described in [4] to constructing approximate decision trees. Adjustable approximation rate allows controlling algorithm complexity. The algorithm is applied to build optimal alpha-decision trees for two data sets from UCI Machine Learning Repository [1].