License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.54
URN: urn:nbn:de:0030-drops-169922
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16992/
Go to the corresponding LIPIcs Volume Portal

Flores-Velazco, Alejandro

Improved Search of Relevant Points for Nearest-Neighbor Classification

pdf-format:
LIPIcs-ESA-2022-54.pdf (0.8 MB)

Abstract

Given a training set P ⊂ ℝ^d, the nearest-neighbor classifier assigns any query point q ∈ ℝ^d to the class of its closest point in P. To answer these classification queries, some training points are more relevant than others. We say a training point is relevant if its omission from the training set could induce the misclassification of some query point in ℝ^d. These relevant points are commonly known as border points, as they define the boundaries of the Voronoi diagram of P that separate points of different classes. Being able to compute this set of points efficiently is crucial to reduce the size of the training set without affecting the accuracy of the nearest-neighbor classifier.
Improving over a decades-long result by Clarkson (FOCS'94), Eppstein (SOSA’22) recently proposed an output-sensitive algorithm to find the set of border points of P in ?(n² + nk²) time, where k is the size of such set. In this paper, we improve this algorithm to have time complexity equal to ?(nk²) by proving that the first phase of their algorithm, which requires ?(n²) time, are unnecessary.

BibTeX - Entry

@InProceedings{floresvelazco:LIPIcs.ESA.2022.54,
  author =	{Flores-Velazco, Alejandro},
  title =	{{Improved Search of Relevant Points for Nearest-Neighbor Classification}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{54:1--54:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16992},
  URN =		{urn:nbn:de:0030-drops-169922},
  doi =		{10.4230/LIPIcs.ESA.2022.54},
  annote =	{Keywords: nearest-neighbor classification, nearest-neighbor rule, decision boundaries, border points, relevant points}
}

Keywords: nearest-neighbor classification, nearest-neighbor rule, decision boundaries, border points, relevant points
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

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