Accession Number:

AD0806836

Title:

AN ASYMPTOTIC ANALYSIS OF THE NEAREST-NEIGHBOR DECISION RULE.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA STANFORD ELECTRONICS LABS

Personal Author(s):

• Hart, Peter E.

Report Date:

1966-05-01

Pagination or Media Count:

65.0

Abstract:

The nearest-neighbor decision rule NN rule assigns to an unclassified sample the classification of the nearest of n previously classified samples. In a large sample analysis it is shown, under very weak regularity conditions, that the risk incurred by this nonparametric rule is less than twice the Bayes risk. A variety of standard decision problems are treated, and in some cases the bounds given on the NN risk are the best possible. The natural extension of the NN rule to the decision rule that considers several nearby neighbors and takes a vote is also treated. Consideration is given to some of the implementation problems arising in connection with the NN rule. In particular, a method of optical computation is suggested to carry out the necessary calculations and a performance-feedback technique is proposed to determine sample-size requirements. Author

Descriptors:

• (*DECISION THEORY
• UNCERTAINTY)
• PATTERN RECOGNITION
• THEOREMS
• SAMPLING
• CLASSIFICATION
• OPTIMIZATION
• PROBABILITY
• ERRORS
• ASYMPTOTIC SERIES

Subject Categories:

• Statistics and Probability
• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE