Asymptotic Properties of Nearest Neighbor Rules Using Edited Data

IEEE Transactions on Systems Man and CyberneticsPublished 1 July 1972

Dennis L. Wilson

DOI10.1109/tsmc.1972.4309137

Citations2,050

TL;DR

The convergence properties of a nearest neighbor rule that uses an editing procedure to reduce the number of preclassified samples and to improve the performance of the rule are developed.

Abstract

The convergence properties of a nearest neighbor rule that uses an editing procedure to reduce the number of preclassified samples and to improve the performance of the rule are developed. Editing of the preclassified samples using the three-nearest neighbor rule followed by classification using the single-nearest neighbor rule with the remaining preclassified samples appears to produce a decision procedure whose risk approaches the Bayes' risk quite closely in many problems with only a few preclassified samples. The asymptotic risk of the nearest neighbor rules and the nearest neighbor rules using edited preclassified samples is calculated for several problems.

Keywords

Computer Science

IEEE Transactions on Information TheoryNearest neighbor pattern classification

16,134 Citations1967Thomas M. Cover, Peter E. Hart

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.

CERN Document Server (European Organization for Nuclear Research)Principles of Communication Engineering

1,920 Citations1965I. M. Jacobs, John M. Wozencraft

Textbook on communication engineering emphasizing random processes, information and detection theory, statistical communication theory, applications, etc.

Proceedings of the IEEEState of the art in pattern recognition

294 Citations1968George Nagy

This paper reviews statistical, adaptive, and heuristic techniques used in laboratory investigations of pattern recognition problems and includes correlation methods, discriminant analysis, maximum likelihood decisions minimax techniques, perceptron-like algorithms, feature extraction, preprocessing, clustering and nonsupervised learning.

Information and ControlA generalized k-nearest neighbor rule

192 Citations1970Edward A. Patrick, F.P. Fischer

A family of supervised, nonparametric decision rules, based on tolerance regions, is described which includes the k -Nearest Neighbor decision rules when there are two classes.

Elsevier eBooksLEARNING IN PATTERN RECOGNITION

77 Citations1969Thomas M. Cover

A discussion is made of some nonparametric approaches to the problem of the classification of an unknown pattern when the only information on the underlying distributions associated with the various categories is that which can be obtained from a finite number of samples.

The Annals of Mathematical StatisticsOn a General Concept of "In Probability"

39 Citations1959John W. Pratt

View PDF

IEEE Transactions on Automatic ControlOn pattern classification algorithms--Introduction and survey

39 Citations1968Yu‐Chi Ho, Ashok K. Agrawala

It is shown that these algorithms can be classified according to the type of input information required and that the techniques of estimation, decision, and optimization theory can be used effectively to derive known as well as new results.

SciencePattern Classification by Adaptive Machines

27 Citations1967C. A. Rosen

A number of different machine organizations and training rules have been developed and are being applied successfully to numerous classification problems, some of which require the aid of the digital computer programmed to supplement the functions of the adaptive classifier.