NDLI: Bias of Nearest Neighbor Error Estimates

Content Provider	IEEE Xplore Digital Library
Author	Fukunaga, Keinosuke Hummels, Donald M.
Copyright Year	1979
Abstract	The bias of the finite-sample nearest neighbor (NN) error from its asymptotic value is examined. Expressions are obtained which relate the bias of the NN and 2-NN errors to sample size, dimensionality, metric, and distributions. These expressions isolate the effect of sample size from that of the distributions, giving an explicit relation showing how the bias changes as the sample size is increased. Experimental results are given which suggest that the expressions accurately predict the bias. It is shown that when the dimensionality of the data is high, it may not be possible to estimate the asymptotic error simply by increasing the sample size. A new procedure is suggested to alleviate this problem. This procedure involves measuring the mean NN errors at several sample sizes and using our derived relationship between the bias and the sample size to extrapolate an estimate of the asymptotic NN error. The results are extended to the multiclass problem. The choice of an optimal metric to minimize the bias is also discussed.
Sponsorship	IEEE Computer Society
Starting Page	103
Ending Page	112
Page Count	10
File Size	2064380
File Format	PDF
ISSN	01628828
Volume Number	PAMI-9
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1987-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Nearest neighbor searches Neural networks Convergence Error analysis Size measurement Density functional theory sample size Bayes error estimation bias convergence finite sample k-NN nearest neighbor
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence Computational Theory and Mathematics Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bayes Error Estimation Using Parzen and k-NN Procedures

Classification Bias of the k-Nearest Neighbor Algorithm

An Optimal Global Nearest Neighbor Metric

The Nearest Neighbor and the Bayes Error Rates

The 2-NN Rule for More Accurate NN Risk Estimation

Any Discrimination Rule Can Have an Arbitrarily Bad Probability of Error for Finite Sample Size

On the reduction of the nearest-neighbor variation for more accurate classification and error estimates

Bootstrap Techniques for Error Estimation

Nonparametric Estimation of the Bayes Error of Feature Extractors Using Ordered Nearest Neighbor Sets

Bias of Nearest Neighbor Error Estimates

Similar Documents

Bayes Error Estimation Using Parzen and k-NN Procedures

Classification Bias of the k-Nearest Neighbor Algorithm

An Optimal Global Nearest Neighbor Metric

The Nearest Neighbor and the Bayes Error Rates

The 2-NN Rule for More Accurate NN Risk Estimation

Any Discrimination Rule Can Have an Arbitrarily Bad Probability of Error for Finite Sample Size

On the reduction of the nearest-neighbor variation for more accurate classification and error estimates

Bootstrap Techniques for Error Estimation

Nonparametric Estimation of the Bayes Error of Feature Extractors Using Ordered Nearest Neighbor Sets

Bias of Nearest Neighbor Error Estimates