Three Criteria for Selecting Variables in the Construction of Near-Optimal Decision Trees
Masahiro Miyakawa, Nobuyuki Otsu · Institutional Repositories DataBase (IRDB) · 1990
For converting a decision table to a near-optimal deci- sion tree in the sense of the minimal number of nodes of the tree, we propose three criteria for variable selec- tion: $\Gamma_{A},$ $\Gamma_{H}$ and $\Gamma_{D}$ from three different standpoints of combinatorial, entropy and discriminant analyses.First we examine "static" behaviors of the criteria, e.g.rejection of nonessential variables (nev-free), se- lection of a totally essential variable (tev-bound) and selection of a quasi-decisive variable (qdv-bound).It is shown that $\Gamma_{A}$ is nev-free, tev-bound but not $qdv-$ bound, while $\Gamma_{H}$ and $\Gamma_{D}$ have the complemental properties.An experiment to evaluate the performance of the criteria shows that each of the criteria gives good near-optimum trees, indicating that $\Gamma_{D}$ and $\Gamma_{H}$ are practically comparative and $\Gamma_{A}$ is slightly better.All the criteria require at most $O(L^{2}2^{L})$ operations with $O(L2^{L})$ storage, where $L$ is the number of variables of the input table.