A novel gray-based reduced NN classification method

In pattern recognition, instance-based learning (also known as nearest neighbor rule) has become increasingly popular and can yield excellent performance. In instance-based learning, however, the storage of training set rises along with the number of training instances. Moreover, in such a case, a new, unseen instance takes a long time to classify because all training instances have to be considered when determining the ‘nearness’ or ‘similarity’ among instances. This study presents a novel reduced classification method for instance-based learning based on the gray relational structure. Here, only some training instances in the original training set are adopted for the pattern classification tasks. The relationships among instances are first determined according to the gray relational structure. In the relational structure, the inward edges of each training instance, indicating how many times each instance is considered as the nearest neighbor or neighbors in determining the class labels of other instances can be obtained. This method excludes training instances with no or few inward edges for the pattern classification tasks. By using the proposed instance pruning approach, new instances can be classified with a few training instances. Nine data sets are adopted to demonstrate the performance of the proposed learning approach. Experimental results indicate that the classification accuracy can be maintained when most of the training instances are pruned before learning. Additionally, the number of remained training instances in the proposal presented here is comparable to that of other existing instance pruning techniques.