Nearest neighbor has always been one of the most appealing non-parametric
approaches in machine learning, pattern recognition, computer vision, etc.
Previous empirical studies partly shows that nearest neighbor is resistant to
noise, yet there is a lack of deep analysis. This work presents the
finite-sample and distribution-dependent bounds on the consistency of nearest
neighbor in the random noise setting. 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
resistance of k-nearest neighbor to random noisy labels. Motivated by the
theoretical analysis, we propose the Robust k-Nearest Neighbor (RkNN) 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. We verify
the effectiveness of the proposed algorithm both theoretically and empirically.

通过研究在随机噪声情况下的 k - 最近邻（k-NN）一致性，提出了一种鲁棒的 k-NN 方法 (RkNN)，在处理噪声标签时具有一定的纠错和分类能力。