Prototype sample selection based on minimization of the complete cross validation functional
Pages 427 - 437
Abstract
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 minimum sufficient number of prototypes, removal (censoring) of noise samples, and improvement of the generalization ability, simultaneously.
References
[1]
I. A. Borisova, V. V. Dyubanov, N. G. Zagoruiko, and O. A. Kutenko, "Similarity and Compactness," in Proc. All-Russian Conf. Mathematical Methods for Pattern Recognition MMPR-14 (Maks Press, Moscow, 2009).
[2]
S. Bermejo and J. Cabestany, "Learning with Nearest Neighbour Classifiers," Neural Process. Lett. 13, No. 2, 159-181 (2001).
[3]
S. Brin, "Near Neighbor Search in Large Metric Spaces," in Proc. 21th Int. Conf. on Very Large Data Bases (Zurich, 1995), pp. 574-584.
[4]
C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition," Data Min. Knowl. Discovery 2, No. 2, 121-167 (1998).
[5]
E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroqün, "Searching in Metric Spaces," ACM Comput. Surv. 33, No. 3, 273-321 (2001).
[6]
C. Cortes and V. Vapnik, "Support-Vector Networks," Mach. Learn. 20, No. 3, 273-297 (1995).
[7]
F. Chang, C.-C. Lin, and C.-J. Lu, "Adaptive Phototype Learning Algorithms: Theoretical and Experimental Studies," J. Mach. Learn. Res., No. 7, 2125-2148 (2006).
[8]
M. N. Ivanov and K. V. Vorontsov, "Standards Selection Based on Total Follow Control Minimization," in Proc. All-Russian Conf. Mathematical Methods for Pattern Recognition MMPR-14 (Maks Press, Moscow, 2009).
[9]
P. E. Hart, "The Condensed Nearest Neighbor Rule," IEEE Trans. Inf. Theory, No. 14, 515-516 (1968).
[10]
R. Kohavi, "A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection," in Proc. 14th Int. Joint Conf. on Artificial Intelligence (Quebec, 1995), pp. 1137-1145.
[11]
C.-L. Liu and M. Nakagawa, "Evaluation of Phototype Learning Algorithms for Nearest-Neighbor Classifier in Application to Handwritten Character Recognition," Pattern Recognit. 34, No. 3, 601-615 (2001).
[12]
M. Mullin and R. Shukhankar, "Complete Cross-Validation for Nearest Neighbor Classifiers," in Proc. Int. Conf. of Machine Learning (Stanford Univ., 2000), pp. 639-646.
[13]
M. Tipping, "The Relevance Vector Machine," in Advances in Neural Information Processing Systems (Morgan Kaufmann, San Mateo, CA, 2000).
[14]
K. V. Vorontsov, "Combinatorial Approach to Quality Estimation of Tutorial Algorithms," in Mathematical Problems of Cybernetics (Fizmatlit, Moscow, 2004), Vol. 13, pp. 5-36 {in Russian}.
[15]
K. V. Vorontsov and A. V. Koloskov, "Compactness Profiles and Reference Objects Selection in Metric Classification Algorithms," in Artificial Intelligence (Donetsk, 2006), pp. 30-33 {in Russian}.
[16]
D. Wilson, "Asymptotic Properties of Nearest Neighbor Rules Using Edited Data," IEEE Trans. Syst., Man, Cybernet., No. 2, 408-421 (1972).
[17]
N. G. Zagoruiko, Applied Methods for Data and Knowledge Analysis (IM SO RAN, Novosibirsk, 1999) {in Russian}.
- Prototype sample selection based on minimization of the complete cross validation functional
Recommendations
NP-completeness of the problem of prototype selection in the nearest neighbor method
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 ...
Positive Unlabeled Learning by Sample Selection and Prototype Refinement
Advanced Data Mining and ApplicationsAbstractPositive and Unlabeled learning (PU learning) learns a binary classifier on training data with only positive and unlabeled instances. Recent cost-sensitive methods tackled this problem by designing unbiased loss functions and achieved state-of-the-...
Active hashing with joint data example and tag selection
SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrievalSimilarity search is an important problem in many large scale applications such as image and text retrieval. Hashing method has become popular for similarity search due to its fast search speed and low storage cost. Recent research has shown that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2010 Pleiades Publishing, Ltd.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 December 2010
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Jan 2025