Distributed and Joint Evidential K-Nearest Neighbor Classification
Chaoyu Gong, Jim Demmel, Yang You · IEEE Transactions on Knowledge and Data Engineering · 2023
The performance ofK-nearest neighbor (K-NN) classification depends significantly on the searched neighborhoods of test samples, namely, the neighborhood sizeKand the used distance metric. For these two issues, many methods either to acquire the adaptiveKor to learn a variant metric have been proposed and yielded appropriate performances. However, most of the existing methods ignore the fact that these two factors can be jointly learned. In this paper, we propose a Joint Evidential K-NN algorithm (JEKNN), which learns the adaptiveKof each sample and distance metric jointly based on the feedback of error function. To break the computational bottleneck of handling large datasets, a distributed version of JEKNN (JEKNN$_{\mathrm{{dis}}}$) is implemented under Apache Spark, i.e., an optimization algorithm based on distributed gradient descent and data parallelism is proposed to accelerate the training stage. Ablation and comparison experiments on small-scale datasets shows the performance improvement from the joint learning and the state-of-the-art accuracy of JEKNN, respectively. Compared to other KNN-based methods designed for Big Data, experimental results on big datasets demonstrate that JEKNN$_{\mathrm{{dis}}}$achieves better scaling efficiency without significant loss of accuracy. Besides, the generalization error bound of the proposed algorithm is also analyzed theoretically.