KNN Classification with One-step Computation
- URL: http://arxiv.org/abs/2012.06047v1
- Date: Wed, 9 Dec 2020 13:34:42 GMT
- Title: KNN Classification with One-step Computation
- Authors: Shichao Zhang and Jiaye Li
- Abstract summary: A one-step computation is proposed to replace the lazy part of KNN classification.
The proposed approach is experimentally evaluated, and demonstrated that the one-step KNN classification is efficient and promising.
- Score: 10.381276986079865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: KNN classification is a query triggered yet improvisational learning mode, in
which they are carried out only when a test data is predicted that set a
suitable K value and search the K nearest neighbors from the whole training
sample space, referred them to the lazy part of KNN classification. This lazy
part has been the bottleneck problem of applying KNN classification. In this
paper, a one-step computation is proposed to replace the lazy part of KNN
classification. The one-step computation actually transforms the lazy part to a
matrix computation as follows. Given a test data, training samples are first
applied to fit the test data with the least squares loss function. And then, a
relationship matrix is generated by weighting all training samples according to
their influence on the test data. Finally, a group lasso is employed to perform
sparse learning of the relationship matrix. In this way, setting K value and
searching K nearest neighbors are both integrated to a unified computation. In
addition, a new classification rule is proposed for improving the performance
of one-step KNN classification. The proposed approach is experimentally
evaluated, and demonstrated that the one-step KNN classification is efficient
and promising.
Related papers
- Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size.
Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
arXiv Detail & Related papers (2024-09-08T13:08:45Z) - Flexible K Nearest Neighbors Classifier: Derivation and Application for
Ion-mobility Spectrometry-based Indoor Localization [0.0]
The K Nearest Neighbors (KNN) is widely used in many fields such as fingerprint-based localization or medicine.
In this paper a KNN-variant is discussed which ensures that the K nearest neighbors are indeed close to the unlabelled sample.
It achieves a higher classification accuracy than the KNN in the tests, while having the same computational demand.
arXiv Detail & Related papers (2023-04-20T08:23:58Z) - A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor
Algorithms" [18.65808473565554]
Jia et al. showed that for K-Nearest Neighbors (KNN) models, the algorithm of Data Shapley is surprisingly simple and efficient.
We propose a more natural and interpretable utility function that better reflects the performance of KNN models.
Our new approach, dubbed soft-label KNNSV, achieves the same time as the original method.
arXiv Detail & Related papers (2023-04-09T15:31:53Z) - Nearest Neighbor Zero-Shot Inference [68.56747574377215]
kNN-Prompt is a technique to use k-nearest neighbor (kNN) retrieval augmentation for zero-shot inference with language models (LMs)
fuzzy verbalizers leverage the sparse kNN distribution for downstream tasks by automatically associating each classification label with a set of natural language tokens.
Experiments show that kNN-Prompt is effective for domain adaptation with no further training, and that the benefits of retrieval increase with the size of the model used for kNN retrieval.
arXiv Detail & Related papers (2022-05-27T07:00:59Z) - Do We Really Need a Learnable Classifier at the End of Deep Neural
Network? [118.18554882199676]
We study the potential of learning a neural network for classification with the classifier randomly as an ETF and fixed during training.
Our experimental results show that our method is able to achieve similar performances on image classification for balanced datasets.
arXiv Detail & Related papers (2022-03-17T04:34:28Z) - Rethinking Nearest Neighbors for Visual Classification [56.00783095670361]
k-NN is a lazy learning method that aggregates the distance between the test image and top-k neighbors in a training set.
We adopt k-NN with pre-trained visual representations produced by either supervised or self-supervised methods in two steps.
Via extensive experiments on a wide range of classification tasks, our study reveals the generality and flexibility of k-NN integration.
arXiv Detail & Related papers (2021-12-15T20:15:01Z) - KNN-BERT: Fine-Tuning Pre-Trained Models with KNN Classifier [61.063988689601416]
Pre-trained models are widely used in fine-tuning downstream tasks with linear classifiers optimized by the cross-entropy loss.
These problems can be improved by learning representations that focus on similarities in the same class and contradictions when making predictions.
We introduce the KNearest Neighbors in pre-trained model fine-tuning tasks in this paper.
arXiv Detail & Related papers (2021-10-06T06:17:05Z) - Adaptive Nearest Neighbor Machine Translation [60.97183408140499]
kNN-MT combines pre-trained neural machine translation with token-level k-nearest-neighbor retrieval.
Traditional kNN algorithm simply retrieves a same number of nearest neighbors for each target token.
We propose Adaptive kNN-MT to dynamically determine the number of k for each target token.
arXiv Detail & Related papers (2021-05-27T09:27:42Z) - A new hashing based nearest neighbors selection technique for big
datasets [14.962398031252063]
This paper proposes a new technique that enables the selection of nearest neighbors directly in the neighborhood of a given observation.
The proposed approach consists of dividing the data space into subcells of a virtual grid built on top of data space.
Our algorithm outperforms the original KNN in time efficiency with a prediction quality as good as that of KNN.
arXiv Detail & Related papers (2020-04-05T19:36:00Z) - Missing Data Imputation for Classification Problems [1.52292571922932]
Imputation of missing data is a common application in various classification problems where the feature training matrix has missingness.
In this paper, we propose a novel iterative kNN imputation technique based on class weighted grey distance.
This ensures that the imputation of the training data is directed towards improving classification performance.
arXiv Detail & Related papers (2020-02-25T07:48:45Z)
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.