Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

kNN Is Close to Optimal

  • Cover and Hart (1967)

  • Asymptotically, the error rate of 1-nearest-neighbor classification is less than twice the Bayes rate [error rate of classifier knowing model that generated data]

  • In particular, asymptotic error rate is 0 if Bayes rate is 0.

  • Assume: query point coincides with a training point.

  • Both query point and training point contribute error → 2 times Bayes rate

Speaker notes:

Content Tools


There are currently no sources for this slide.