AN EXPERIMENTAL COMPARISON OF THE NEAREST-NEIGHBOR AND NEAREST-HYPERRECTANGLE ALGORITHMNS

Algorithms based on Nested Generalized Exemplar (NGE) theory (Salzberg , 1991) classify new data points by computing their distance to the ne arest ''generalized exemplar'' (i.e., either a point or an axis-parall el rectangle). They combine the distance-based character of nearest ne ighbor (NN) classifiers with the axis-parallel rectangle representatio n employed in many rule-learning systems. An implementation of NGE was compared to the k-nearest neighbor (kNN) algorithm in 11 domains and found to be significantly inferior to kNN in 9 of them Several modific ations of NGE were studied to understand the cause of its poor perform ance. These show that its performance can be substantially improved by preventing NGE from creating overlapping rectangles, while still allo wing complete nesting of rectangles. Performance can be further improv ed by modifying the distance metric to allow weights on each of the fe atures (Salzberg, 1991). Best results were obtained in this study when the weights were computed using mutual information between the featur es and the output class. The best version of NGE developed is a batch algorithm (BNGE FWMI) that has no user-tunable parameters. BNGE FWMI's performance is comparable to the first-nearest neighbor algorithm (al so incorporating feature weights). However, the k-nearest neighbor alg orithm is still significantly superior to BNGE FWMI in 7 of the 11 dom ains, and inferior to it in only 2. We conclude that, even with our im provements, the NGE approach is very sensitive to the shape of the dec ision boundaries in classification problems. in domains where the deci sion boundaries are axis-parallel, the NGE approach can produce excell ent generalization with interpretable hypotheses. In all domains teste d, NGE algorithms require much less memory to store generalized exempl ars than is required by NN algorithms.