K-nearest neighbors algorithm: Difference between revisions

Revision as of 10:41, 1 October 2021

Revision as of 10:06, 10 October 2021

Line 120:

==Error rates==

There are many results on the error rate of the {{mvar|k}} nearest neighbour classifiers.<ref name = "PTPR">{{cite book |last1=Devroye |first1=Luc |last2=Gyorfi |first2=Laszlo |last3=Lugosi |first3=Gabor |year=1996 |title=A probabilistic theory of pattern recognition |publisher=Springer |isbn=978-0-3879-4618-4 }}</ref><ref>{{Cite journal|last1=Cabannes|first1=Vivien|last2=Rudi|first2=Alessandro|last3=Bach|first3=Francis|date=2021|title=Fast rates in Structured Prediction|journal=COLT|arxiv=2102.00760}}</ref> The {{mvar|k}}-nearest neighbour classifier is strongly (that is for any joint distribution on <math> (X, Y)</math>) [[Bayes classifier|consistent]] provided <math>k:=k_n</math> diverges and <math>k_n/n</math> converges to zero as <math>n \to \infty</math>.

Let <math> C_n^{knn} </math> denote the {{mvar|k}} nearest neighbour classifier based on a training set of size {{mvar|n}}. Under certain regularity conditions, the [[Bayes classifier|excess risk]] yields the following asymptotic expansion<ref name = "Samworth12">{{Cite journal |last=Samworth |first=Richard J.