For a given test point, find the k closest training points.
Take the label of the majority
Unlike most other algorithms, KNN doesn't require any training!
Trade-off: Relatively large test time
When k increases, decision boundary becomes smoother
What would your error be if you use the same dataset for training and testing, and set k=1?