DISCRIMINANT ADAPTIVE NEAREST-NEIGHBOR CLASSIFICATION

Nearest neighbor classification expects the class conditional probabil ities to be locally constant, and suffers from bias in high dimensions . We propose a locally adaptive form of nearest neighbor classificatio n to try to ameliorate this curse of dimensionality. We use a local li near discriminant analysis to estimate an effective metric for computi ng neighborhoods. We determine the local decision boundaries from cent roid information, and then shrink neighborhoods in directions orthogon al to these local decision boundaries, and elongate them parallel to t he boundaries. Thereafter, any neighborhood-based classifier can be em ployed, using the modified neighborhoods. The posterior probabilities tend to be more homogeneous in the modified neighborhoods. We also pro pose a method for global dimension reduction, that combines local dime nsion information. In a number of examples, the methods demonstrate th e potential for substantial improvements over nearest neighbor classif ication.