article

NP-completeness of the problem of prototype selection in the nearest neighbor method

Author:

A. V. ZukhbaAuthors Info & Claims

Pattern Recognition and Image Analysis, Volume 20, Issue 4

Pages 484 - 494

https://doi.org/10.1134/S1054661810040097

Published: 01 December 2010 Publication History

Abstract

The problem of selecting of prototypes is to select a subset in the learning sample for which the set of minimum cardinality would provide the optimum of a given learning quality functional. In this article the problem of classification is considered in two classes, the method of classification by nearest neighbor, and three functional characteristics: the frequency of errors on the entire sample, a cross validation with one separated object, and a complete cross validation with k separated objects. It is shown that the problem of selection of prototypes in all three cases is NP-complete, which justifies the use of well-known heuristic methods for the prototype search.

References

[1]

S. A. Aivazyan, V. M. Bukhshtaber, I. S. Enyukov, and L. D. Meshalkin, Applied Statistics: Classification and Dimension Reduction (Finansy i Statistika, Moscow, 1989) {in Russian}.

Google Scholar

[2]

I. A. Borisova, V. V. Dyubanov, N. G. Zagoruiko, and O. A. Kutnenko, "Similarity and Compactness," in Proc. All-Russian Conf. Mathematical Methods for Pattern Recognition-14(Maks Press, Moscow, 2009), pp. 89-92.

Google Scholar

[3]

K. V. Vorontsov, "Combinatory Approach to Quality Estimation of Tutorial Algorithms," in Mathematical Problems of Cybernetics, Ed. by O. B. Lupanov (Fizmatlit, Moscow, 2004), Vol. 13, pp. 5-36 {in Russian}.

Google Scholar

[4]

K. V. Vorontsov and A. O. Koloskov, "Compactness Profiles and Prototype Object Selection in Metric Classification Algorithms," Iskusstv. Intellekt, No. 2, 30-33 (2006).

Google Scholar

[5]

N. G. Zagoruiko, Applied Methods for Data and Knowledge Analysis (IM SO RAN, Novosibirsk, 1999) {in Russian}.

Google Scholar

[6]

M. N. Ivanov and K. V. Vorontsov, "Prototypes Selection Based on Minimization of Complete Follow Control Functional," in Proc. All-Russian Conf. Mathematical Methods for Pattern Recognition-14 (Maks Press, Moscow, 2009), pp. 119-122.

Google Scholar

[7]

S. Bermejo and J. Cabestany, "Learning with Nearest Neighbor Classifiers," Neural Proc. Lett. 13(2), 159- 181 (2001).

Crossref

Google Scholar

[8]

C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition," Data Mining Knowl. Discov. 2(2), 121-167 (1998).

Crossref

Google Scholar

[9]

W. S. Cleveland, "Robust Locally Weighted Regression and Smoothing Scatter Plots," J. Am. Stat. Assoc. 74 (368), 829-836 (1979).

Crossref

Google Scholar

[10]

M. Mullin and R. Sukthankar, "Complete Cross-Validation for Nearest Neighbor Classifiers," in Proc. Int. Conf. on Machine Learning (Stanford. Univ., 2000), pp. 639-646.

Crossref

Google Scholar

[11]

M. Tipping, "The Relevance Vector Machine," in Advances in Neural Information Processing Systems (Morgan Kaufmann, San Mateo, CA, 2000).

Google Scholar

Cited By

View all

Gottlieb LSharabi TWeiss RSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Weighted distance nearest neighbor condensingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692713(16153-16166)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692713
Tavallali PTavallali PKhosravi MSinghal M(2022)An EM-based optimization of synthetic reduced nearest neighbor model towards multiple modalities representation with human interpretabilityMultimedia Tools and Applications10.1007/s11042-021-11241-z81:29(41697-41710)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11042-021-11241-z
Gottlieb LKontorovich ANisnevitch P(2014)Near-optimal sample compression for nearest neighborsProceedings of the 28th International Conference on Neural Information Processing Systems - Volume 110.5555/2968826.2968868(370-378)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.5555/2968826.2968868
Show More Cited By

NP-completeness of the problem of prototype selection in the nearest neighbor method
1. Theory of computation

Recommendations

Prototype sample selection based on minimization of the complete cross validation functional

A method of prototype sample selection from a training set for a classifier of K nearest neighbors (KNN), based on minimization of the complete cross validation functional, is proposed. The optimization leads to reduction of the training set to the ...
Prototype Selection for Composite Nearest Neighbor Classifiers
A new two-layer nearest neighbor selection method for kNN classifier
Abstract
The k-nearest neighbor (kNN) classifier is a classical classification algorithm that has been applied in many fields. However, the performance of the kNN classifier is limited by a simple neighbor selection method, called nearest ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Pattern Recognition and Image Analysis

Pattern Recognition and Image Analysis Volume 20, Issue 4

December 2010

158 pages

ISSN:1054-6618

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gottlieb LSharabi TWeiss RSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Weighted distance nearest neighbor condensingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692713(16153-16166)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692713
Tavallali PTavallali PKhosravi MSinghal M(2022)An EM-based optimization of synthetic reduced nearest neighbor model towards multiple modalities representation with human interpretabilityMultimedia Tools and Applications10.1007/s11042-021-11241-z81:29(41697-41710)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11042-021-11241-z
Gottlieb LKontorovich ANisnevitch P(2014)Near-optimal sample compression for nearest neighborsProceedings of the 28th International Conference on Neural Information Processing Systems - Volume 110.5555/2968826.2968868(370-378)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.5555/2968826.2968868
Impedovo SMangini FBarbuzzi D(2014)A novel prototype generation technique for handwriting digit recognitionPattern Recognition10.1016/j.patcog.2013.04.01647:3(1002-1010)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1016/j.patcog.2013.04.016
Miloud-Aouidate ABaba-Ali A(2013)An Efficient Ant Colony Instance Selection Algorithm for KNN ClassificationInternational Journal of Applied Metaheuristic Computing10.4018/ijamc.20130701044:3(47-64)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.4018/ijamc.2013070104
Miloud-Aouidate ABaba-Ali A(2013)IDS false alarm reduction using an instance selection KNN-memetic algorithmInternational Journal of Metaheuristics10.1504/IJMHEUR.2013.0584732:4(333-352)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1504/IJMHEUR.2013.058473

Abstract

References

Cited By

Recommendations

Prototype sample selection based on minimization of the complete cross validation functional

Prototype Selection for Composite Nearest Neighbor Classifiers

A new two-layer nearest neighbor selection method for kNN classifier

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations