A multi-stage genetic algorithm for instance selection dedicated to k nearest neighbours classification: application to robot wall following problem

Abstract

K nearest neighbours algorithm is a classic, well studied yet a promising classification technique with high accuracy and best learning time compared to other classification algorithms. The goal is to overcome its slow classification time using instance selection by eliminating redundant and erroneous data. The instance selection problem has been classified as a non-deterministic polynomial time hard problem. In this article, the aim is to keep up with real time applications such as robotics with limited memory, while maintaining the fast-learning speed and high classification accuracy. We introduce a new multistage genetic algorithm for instance selection consisting of successive genetic instance selection stages with iterative search space reduction. The results witnessed an extreme reduction in classification time, reaching 99% without any significant penalty in the accuracy. It has been tested successfully using real traces of robot wall following navigation datasets and favourably compared to other approaches using various datasets.