Adaptive edited natural neighbor algorithm

Reduction techniques can reduce prohibitive computational costs and the storage requirements for classifying patterns while maintaining classification accuracy. The edited nearest neighbor rule is one of the most popular reduction technique, which removes noisy patterns that are not correctly classified by their k-nearest neighbors. However, selection of neighborhood parameters is an unsolved problem for the traditional neighborhood construction algorithms such as k-nearest neighbor and ε-neighborhood. To solve the problem, we present a novel editing algorithm called adaptive Edited Natural Neighbor algorithm (ENaN). ENaN aims to eliminate the noisy patterns based on the concept of natural neighbor which are obtained adaptively by the search algorithm of natural neighbor. The main advantages are that ENaN does not need any parameters and can degrade the effect of noisy patterns. The adaptive ENaN algorithm can be easily applied into other reduction algorithms as a noisy filter. Experiments show that the proposed approach effectively removes the noisy patterns while keeping more reasonable class boundaries and improves the performance of two condensation methods in terms of both accuracy and reduction rate greatly.