03·k-NN and Naive Bayes — classification by similarity and probability

Introduction

Two fundamentally different classifiers: k-NN (Cover & Hart 1967) is "lazy" and non-parametric — it stores the whole training set and classifies by majority vote among k nearest neighbors. Naive Bayes (Bayes 1763, a 20th-century classifier) is probabilistic and naively assumes conditional feature independence, enabling fast P(y|x) computation. The lesson dissects: distance metrics, choice of k, the curse of dimensionality, Bayes' rule, NB variants (Gaussian, Multinomial, Bernoulli), Laplace smoothing, and why a "naive" model still works surprisingly well.