On the Robustness of Nearest Neighbor with Noisy Data.

Nearest neighbor has always been one of the most appealing non-parametric approaches in machine learning, pattern recognition, computer vision, etc. Previous empirical studies partially demonstrate that nearest neighbor is resistant to noise, yet there is a lack of deep analysis. This work presents a full understanding on the robustness of nearest neighbor in the random noise setting.

We provide finite-sample, distribution-dependent bounds on the consistency of nearest neighbor. The theoretical results show that, for asymmetric noises, k-nearest neighbor is robust enough to classify most data correctly, except for a handful of examples, whose labels are totally misled by random noises. For symmetric noises, however, k-nearest neighbor achieves the same consistent rate as that of noise-free setting, which verifies the robustness of $k$-nearest neighbor. Motivated by theoretical analysis, we propose the Robust k-Nearest Neighbor (RNN) approach to deal with noisy labels. The basic idea is to make unilateral corrections to examples, whose labels are totally misled by random noises, and classify the others directly by utilizing the robustness of k-nearest neighbor. Extensive experiments show the effectiveness and robustness of the proposed algorithm.