Guarantees on nearest-neighbor condensation heuristics

DOI10.1016/J.COMGEO.2020.101732MaRDI QIDQ1984597zbMATH OpenOpenAlexFDO

Authors Alejandro Flores-Velazco, David M. Mount

Publication date 16 September 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.12142

zbMATH Keywords

machine learningnearest-neighbor classificationtraining set reduction

Mathematics Subject Classification ID

Order statistics; empirical distribution functions (62G30) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The problem of nearest-neighbor (NN) condensation aims to reduce the size of a training set of a nearest-neighbor classifier while maintaining its classification accuracy. Although many condensation techniques have been proposed, few bounds have been proved on the amount of reduction achieved. In this paper, we present one of the first theoretical results for practical NN condensation algorithms. We propose two condensation algorithms, called RSS and VSS, along with provable upper-bounds on the size of their selected subsets. Additionally, we shed light on the selection size of two other state-of-the-art algorithms, called MSS and FCNN, and compare them to the new algorithms.

Recommendations

• scientific article; zbMATH DE number 1759570
• ROC curves and near neighbours, a proposal of a new condensation algorithm
• scientific article; zbMATH DE number 2101282
• NEAREST NEIGHBOR PROBLEMS
• Advances in Intelligent Data Analysis VI

Cites work

• An algorithm for a selective nearest neighbor decision rule (Corresp.)
• Artificial Intelligence and Soft Computing - ICAISC 2004
• Consistent nonparametric regression. Discussion
• Consistent subset problem with two labels
• Coresets for the Nearest-Neighbor Rule
• Nearest neighbor pattern classification
• On the Inequality of Cover and Hart in Nearest Neighbor Discrimination
• On the minimum consistent subset problem
• Open problems in geometric methods for instance-based learning
• Output-sensitive algorithms for computing nearest-neighbour decision boundaries.

Cited in

(7)

• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• NEAREST NEIGHBOR PROBLEMS
• scientific article; zbMATH DE number 1759570 (Why is no real title available?)
• scientific article; zbMATH DE number 2101282 (Why is no real title available?)
• ROC curves and near neighbours, a proposal of a new condensation algorithm
• Advances in Intelligent Data Analysis VI
• A class boundary preserving algorithm for data condensation

This page was built for publication: Guarantees on nearest-neighbor condensation heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1984597)