EncodKNN: Augmenting KNN with Autoencoder for Computational Cost Reduction

Abstract

The K Nearest Neighbor (kNN) is a classification method that's easy to understand a nd commonly used in statistical data mining. Typically, kNN operates by analyzing the nearest instances to a given data point, relying on a distance metric for comparison. However, its efficacy diminishes notably i n high-dimensional spaces as the number of input features increases. Consequently, the computational cost of the algorithm becomes prohibitively high, posing a significant challenge in practical applications. To tackle this challenge, this paper proposes an unsupervised learning approach that integrates a deep autoencoder for dimensionality reduction. This method involves embedding the training data into lower-dimensional latent feature spaces, effectively reducing computational complexity while retaining essential information for accurate classification. Furthermore, the paper proposes a differential evolution optimization technique to determine the best embedding dimension of latent space of the autoencoder. Experimental findings a cross diverse d atasets demonstrate that this approach significantly reduces computational overheads while maintaining performance levels comparable to standard kNN. Additionally, the optimization method reduces feature dimensions ranging from 69.2% to 84.2%.