License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.47
URN: urn:nbn:de:0030-drops-129138
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12913/
Go to the corresponding LIPIcs Volume Portal

Flores-Velazco, Alejandro ; Mount, David M.

Coresets for the Nearest-Neighbor Rule

pdf-format:
LIPIcs-ESA-2020-47.pdf (5 MB)

Abstract

Given a training set P of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset R āŠ† P such that for every point p āˆˆ P, pā€™s nearest-neighbor in R has the same label as p. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set.
This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.

BibTeX - Entry

@InProceedings{floresvelazco_et_al:LIPIcs:2020:12913,
  author =	{Alejandro Flores-Velazco and David M. Mount},
  title =	{{Coresets for the Nearest-Neighbor Rule}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{47:1--47:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12913},
  URN =		{urn:nbn:de:0030-drops-129138},
  doi =		{10.4230/LIPIcs.ESA.2020.47},
  annote =	{Keywords: coresets, nearest-neighbor rule, classification, nearest-neighbor condensation, training-set reduction, approximate nearest-neighbor, approximation algorithms}
}

Keywords: coresets, nearest-neighbor rule, classification, nearest-neighbor condensation, training-set reduction, approximate nearest-neighbor, approximation algorithms
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: Source code is available at https://github.com/afloresv/nnc.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI