A depth-based nearest neighbor algorithm for high-dimensional data classification

Abstract

Nearest neighbor algorithms like k-nearest neighbors (kNN) are fundamental supervised learning techniquesto classify a query instance based on class labels of its neighbors. However, quite often, huge volumes of datasets arenot fully labeled and the unknown probability distribution of the instances may be uneven. Moreover, kNN suffers fromchallenges like curse of dimensionality, setting the optimal number of neighbors, and scalability for high-dimensionaldata. To overcome these challenges, we propose an improvised approach of classification via depth representation ofsubspace clusters formed from high-dimensional data. We offer a consistent and principled approach to dynamicallychoose the nearest neighbors for classification of a query point by i) identifying structures and distributions of data; ii)extracting relevant features, and iii) deriving an optimum value of k depending on the structure of data by representingdata using data depth function. We propose an improvised classification algorithm using a depth-based representationof clusters, to improve performance in terms of execution time and accuracy. Experimentation on real-world datasetsreveals that proposed approach is at least two orders of magnitude faster for high-dimensional dataset and is at least asaccurate as traditional kNN.