K-nearest neighbor is considered in top machine learning algorithms because of its effectiveness in pattern classification and simple implementation. However, usage of KNN is limited due to its larger prediction time than model-based machine learning algorithms, its sensitivity to the existing outliers in the training dataset, and tuning parameter neighborhood size ( \(k\) ). Therefore, this research article proposes a new variant of the KNN to reduce the training and prediction time with improved performance. The prediction time of the KNN is reduced by making a binary search tree (BST) using the divide-and-conquer strategy, and prediction performance is improved using ensembling by injecting randomness such as bootstrap aggregation, random subspace, and random node splitting. The proposed KNN variant is parameter-free and, hence, not sensitive to the hyperparameter neighborhood size. Finally, three experiments have been performed based on 26 selected datasets to show the prediction time and prediction power superiority of the proposed KNN over random forest and six selected KNN variants. Results prove that the proposed KNN variant gives better prediction results with reduced prediction and training time.
