Criteria for selecting a variable in the construction of efficient decision trees

Two variable selection criteria are proposed for converting a decision table to a near-optimum decision tree in the sense of minimal average cost of testing. A criterion, Q, is introduced that is based on the potential of a decision table. The previously known criterion 'loss' and Q are combined into a third criterion O. The performance of the three criteria is examined both theoretically and experimentally. Of most importance is that Q and O do not select a nonessential variable, while 'loss' may do so. It is also shown that the performance of the three criteria is not worse than that of any other known heuristics, at least for a particular example. The algorithm requires at most O(L/sup 2/2/sup L/) operations, where L is the arity of an input table.>