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

Authors: Sarah Madi; Ahmed Riadh Baba-Ali

Addresses: Faculty of Electronics and Computer Science, University of Science and Technology Houari Boumedienne, BP 32 El Alia, Bab Ezzouar Algiers, 16111, Algeria ' Faculty of Electronics and Computer Science, University of Science and Technology Houari Boumedienne, BP 32 El Alia, Bab Ezzouar Algiers, 16111, Algeria

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.

Keywords: machine learning; instance selection; K nearest neighbours; KNN classification; genetic algorithm; wall following.

DOI: 10.1504/IJMHEUR.2022.127832

International Journal of Metaheuristics, 2022 Vol.8 No.1, pp.79 - 96

Accepted: 29 Mar 2022
Published online: 19 Dec 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article