Finding Relevant Points for Nearest-Neighbor Classification

• URL: http://arxiv.org/abs/2110.06163v1
• Date: Tue, 12 Oct 2021 16:58:29 GMT
• Title: Finding Relevant Points for Nearest-Neighbor Classification
• Authors: David Eppstein
• Abstract summary: In nearest-neighbor classification problems, a set of $d$-dimensional training points are given, each with a known classification, and are used to infer unknown classifications of other points. A training point is relevant if its omission from the training set would change the outcome of these inferences.
• Score: 0.456877715768796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In nearest-neighbor classification problems, a set of $d$-dimensional training points are given, each with a known classification, and are used to infer unknown classifications of other points by using the same classification as the nearest training point. A training point is relevant if its omission from the training set would change the outcome of some of these inferences. We provide a simple algorithm for thinning a training set down to its subset of relevant points, using as subroutines algorithms for finding the minimum spanning tree of a set of points and for finding the extreme points (convex hull vertices) of a set of points. The time bounds for our algorithm, in any constant dimension $d\ge 3$, improve on a previous algorithm for the same problem by Clarkson (FOCS 1994).

Related papers

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Reducing Nearest Neighbor Training Sets Optimally and Exactly [0.0]
  In nearest-neighbor classification, a training set $P$ of points in $mathbbRd$ with given classification is used to classify every point in $mathbbRd$ We show that the set of relevant points is such a minimum cardinality reduced training set if $P$ is in general position.
  arXiv  Detail & Related papers  (2023-02-04T08:48:59Z)
• Improved Search of Relevant Points for Nearest-Neighbor Classification [91.3755431537592]
  We say a training point is relevant if its omission from the training set could induce the misclassification of some query point in $mathbbRd$. An output-sensitive algorithm was proposed to find the set of border points of $P$ in $O( n2 + nk2 )$ time, where $k$ is the size of such set. In this paper, we improve this algorithm to have time complexity equal to $O( nk2 )$ by proving that the first steps of their algorithm, which require $O( n2
  arXiv  Detail & Related papers  (2022-03-07T18:10:27Z)
• DeepBBS: Deep Best Buddies for Point Cloud Registration [55.12101890792121]
  DeepBBS is a novel method for learning a representation that takes into account the best buddy distance between points during training. Our experiments show improved performance compared to previous methods.
  arXiv  Detail & Related papers  (2021-10-06T19:00:07Z)
• Quantum K-nearest neighbor classification algorithm based on Hamming distance [3.4501155479285326]
  We propose a quantum K-nearest neighbor classification algorithm with Hamming distance. It is shown that the proposed algorithm can achieve a quadratical speedup by analyzing its time complexity briefly.
  arXiv  Detail & Related papers  (2021-03-07T04:08:21Z)
• Social Distancing is Good for Points too! [91.3755431537592]
  We show that FCNN can behave poorly when points are too close to each other. We then successfully modify the algorithm to avoid such cases. This modification is sufficient to prove useful upper-bounds, along with approximation guarantees for the algorithm.
  arXiv  Detail & Related papers  (2020-06-28T16:49:59Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Coresets for the Nearest-Neighbor Rule [78.15296214629433]
  Nearest-neighbor condensation deals with finding a subset $R subseteq P$. This paper introduces the concept of coresets for nearest-neighbor classification. We propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets.
  arXiv  Detail & Related papers  (2020-02-16T19:00:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.