Social Distancing Is Good For Points Too!

Abstract

The nearest-neighbor rule is a well-known classification technique that, given a training set P of labeled points, classifies any unlabeled query point with the label of its closest point in P. The nearest-neighbor condensation problem aims to reduce the training set without harming the accuracy of the nearest-neighbor rule. FCNN is the most popular algorithm for condensation. It is heuristic in nature, and theoretical results for it are scarce. In this paper, we settle the question of whether reasonable upper-bounds can be proven for the size of the subset selected by FCNN. First, we show that the algorithm can behave poorly when points are too close to each other, forcing it to select many more points than necessary. We then successfully modify the algorithm to avoid such cases, thus imposing that selected points should "keep some distance". This modification is sufficient to prove useful upper-bounds, along with approximation guarantees for the algorithm.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfloresvelazco2020social

Related papers

• Reducing Nearest Neighbor Training Sets Optimally And Exactly (2023)0.00
• Finding Relevant Points For Nearest-neighbor Classification (2021)4.52
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• Explaining The Success Of Nearest Neighbor Methods In Prediction (2025)18.63
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00