\( \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML01.3 · k-nearest neighbors

A free, illustrated module of 4 lessons and one interactive in ML01 Machine Learning Foundations: Classify by your nearest neighbour; k neighbours and a vote; Distance and feature scaling; Regression, cost and many dimensions.

ML01.3 L1 · Core 4 lessons · about 100 min Live · in review

Part of ML01 Machine Learning Foundations in the Machine Learning track.

The simplest way to predict is to find the stored examples most like the new one and copy what they say. These four lessons build that idea into a working method. You will classify a fruit by its single nearest neighbour, then let k neighbours vote and choose k with a validation set, then see why the units of a feature can decide the answer and how standardising fixes it, and last use neighbours to predict a number, count what a prediction costs, and watch “near” lose its meaning as features are added.

What you need first. Features, labels and what a model is (ML01.1), and training, validation and test sets (ML01.2). Coordinates on a plane and Pythagoras’ theorem (M01.2). A little NumPy helps for the code.

Lessons

1. Classify by your nearest neighbour ML01.3.1 25 min

   The nearest-neighbour rule labels a new example by copying the label of the most similar example it has stored. Work it by hand with Euclidean distance on eight fruit, code it in NumPy and scikit-learn, and see the decision regions it draws.

2. k neighbours and a vote ML01.3.2 25 min

   One odd example should not decide a prediction. The k-nearest-neighbour classifier asks the k closest stored examples and takes a majority vote. See how a small k follows noise and a large k blurs the boundary, choose k with a validation set, and deal with ties.

3. Distance and feature scaling ML01.3.3 25 min

   A feature measured in large units dominates a distance, so k-nearest neighbours can end up ignoring every other feature. Standardise each feature with the training mean and standard deviation, watch the nearest neighbour change, and meet Manhattan distance.

4. Regression, cost and many dimensions ML01.3.4 25 min

   Neighbours can predict a number as well as a label: average the targets of the k nearest. Then count what a prediction costs when the model is the data itself, and see by simulation why neighbours stop being near when there are many features.

The interactive

ML01.3-X1 · Neighbour explorer. Place a query among labelled points, choose k and the distance, and see which neighbours vote and how the decision regions redraw. Stretch one feature’s units to watch the neighbourhood flatten and the answer change. It lives in k neighbours and a vote.