Inducing NNC-Trees Quickly

An NNC-tree is a decision tree (DT) with each non-terminal node containing a nearest neighbor classifier (NNC). Compared with the axis-parallel decision trees (APDTs), NNC-trees are more comprehensible for large problems, because the decision rules corresponding to the trees are simpler. Currently, the author has proposed an algorithm for inducing NNC-trees based on the R⁴-rule. However, compared with C4.5, which is a popular program for inducing APDTs, the computation of our algorithm is relatively expensive. This paper proposes two methods for reducing the computational cost. The efficiency of the proposed methods is verified through experiments on three public databases.