A divide-and-conquer approach to the Pairwise Opposite Class-Nearest Neighbor (POC-NN) algorithm for classification and regression problems

Abstract

This paper presents a new method based on divide-and-conquer approach to the selection of a set of prototypes from the training data by the nearest neighbor rule. The method aims at reducing computational time and memory space as well as sensitivity of the order and noise of the training data. A reduced prototype set contains Pairwise Opposite Class-Nearest Neighbor (POC-NN) prototypes, which are close to the decision boundary and used instead of the training patterns. POC-NN prototypes are obtained by recursively analysis and iterative separation of the training data into two regions until each region is correctly grouped and classied. The separability is determined by the POC-NN prototypes essential to dene the locations of all separating hyperplanes. Our method is fast and order independent. The number of prototypes and the overtting of the model can be reduced by the user. This method can be used to solve not only classication but also regressionproblems. The experimental results signify the effectiveness of this technique and its performance in both accuracy and prototype rate as well as in training time over those obtained by classical nearest neighbor techniques.