1 of 50

KNN, ML Vocabulary, and K-Means

Lecture 2

Our first models, supervised and unsupervised

EECS 189/289, Fall 2025 @ UC Berkeley

Joseph E. Gonzalez and Narges Norouzi

EECS 189/289, Fall 2025 @ UC Berkeley

Joseph E. Gonzalez and Narges Norouzi

EECS 189/289, Fall 2026 @ UC Berkeley

Joseph E. Gonzalez and Narges Norouzi

2 of 50

Roadmap

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

3 of 50

Data Tools Overview

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

4 of 50

Look at the Data First

  •  

The Data

Labels

(Optional)

Features

 

 

7824889

5 of 50

Today's Question

A field researcher hands you two measurements from a penguin: the length of its bill and the length of its flipper.

​

Can you tell them what species it is?

​

And before you answer: how would you know whether your answer is any good?

7824889

6 of 50

Demo

Palmer Penguins�Review:

    • pandas,
    • numpy, and
    • plotting

7824889

7 of 50

The Simplest Model

We want to predict a penguin's species from two numbers.

​

Similar penguins should have similar species.

​

To label a new penguin, find the most similar penguin we have seen, and copy its label.

7824889

8 of 50

K-Nearest Neighbors (KNN)

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

9 of 50

K-Nearest Neighbors, with k = 1

Given a new point, find the nearest point in the training data and copy its label.

​

  • Similarity = Euclidean distance in feature space.

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=1)

knn.fit(X_train, y_train)

​

7824889

10 of 50

Training vs Inference

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

11 of 50

Training vs Inference

Training is the process of building the model from data.

Inference is the process of using the model to make a prediction.

​

​

​

​

​

​

​

​

​

​

​

  • For KNN, training does almost nothing: it stores the data.
  • All the work happens at inference, when we compute distances to every stored point.

7824889

12 of 50

Parametric vs Non-Parametric

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

13 of 50

Parametric vs. Non-Parametric Models

  •  

Voronoi

Diagram

https://en.wikipedia.org/wiki/Voronoi_diagram

 

Training Data

7824889

14 of 50

Demo

KNN with k = 1�How accurate is it?

7824889

15 of 50

Our k=1 model just scored 100% accuracy on the penguin data. What is the most likely explanation?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

7824889

16 of 50

100% Accuracy

Our dumbest possible model just classified every penguin correctly.

​

Something is wrong. What?

​

  • The nearest neighbour of every training point is itself, at distance zero.
  • We asked the model questions it had already been given the answers to.

​

Accuracy on data the model has already seen tells us nothing about whether it has learned anything.

7824889

17 of 50

Generalization

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

18 of 50

Generalization

Generalization in machine learning is the ability of a model to perform well on new, unseen data sampled from the same distribution as its training data.

​

To evaluate generalization,�we need a method to evaluate�the model’s performance on �new data not used for �training.

Training Data

New, Unseen Data

Probably a better model?

7824889

19 of 50

Train/Validation/Test

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

20 of 50

How will we evaluate the model?

We are about to train a model using data.

How will we know if the model has “learned” from our data?

  • Could we measure how well our model fits the data?

​

​

​

​

​

Why is memorizing the data (exam) not good?

​

The Exam Analogy:

What would happen if we gave everyone access to the exam and solutions (the data) to study (train) for the exam?

  • Would everyone do well?
  • Does this mean they learned the material in the class?

7824889

21 of 50

Evaluating generalization using the�Train-Test Split

The train-test split is the standard technique we use to evaluate generalization in machine learning:

  1. Shuffle the training data
  2. Split into two parts:
    • Larger Training Part (~80%): used to �develop and train the model.
    • Smaller Testing Part (~20%): used to �evaluate generalization performance.

Data

Test

Train

Train - Test

Split

You should only use the test dataset once �after developing and training the model.

Why?

If you use the test data to tune the model,�the test data no longer measures generalization.

7824889

22 of 50

Evaluating generalization using the�Train-Test Split

The train-test split is the standard technique we use to evaluate generalization in machine learning:

  1. Shuffle the training data
  2. Split into two parts:
    • Larger Training Part (~80%): used to �develop and train the model.
    • Smaller Testing Part (~20%): used to �evaluate generalization performance.

Data

Test

Train

Train - Test

Split

You should only use the test dataset once �after developing and training the model.

Why?

If you use the test data to tune the model�the test data no longer measures generalization.

But what if I want to peek at the test data�to tune for better generalization?

7824889

23 of 50

The Validation Split

The validation dataset is used to evaluate generalization performance during the model development process.

Data

Test

Train

Train - Test

Split

Train - Val.

Split

Train

Val.

Fit (train) the model using the training data.

Tune the model design using the validation data.

7824889

24 of 50

The Train-Validation-Test Split Analogy

You can think of the train, validation, and test splits as how you might study for an exam.

Test

Train

Val.

Practice question and answer pairs that you use to study for the exam. (Go to discussion!)

Practice exam evaluates if your studying process is working (or if you need to study more).

The exam is how we evaluate if you should pass the class.

7824889

25 of 50

You train a model, then try 30 different settings and pick the one with the best test accuracy. What have you actually measured?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

7824889

26 of 50

Demo

Train/test split�and the effect of k

7824889

27 of 50

Overfitting vs Underfitting

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

28 of 50

What k Controls

Let the k nearest neighbours vote, instead of just one.

  • Small k: The boundary tries to capture every training point, including the unusual ones. This is overfitting.
  • Large k: The boundary smooths until the model barely responds to the data at all. This is underfitting.

7824889

29 of 50

Choosing k Without Eyeballing It

Fit the model for every k and score it on the validation set.

  • Left side (Overfitting): Training accuracy is perfect, validation accuracy is not.
  • Right side (Underfitting): Both fall together.
  • The peak of the validation curve is the k we choose.

On our data the best k is 3, and the final test accuracy is 97%.

7824889

30 of 50

Hyperparameters

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

31 of 50

Hyperparameters

  •  

for hp1 in [0.1, 1, 10]:

for hp2 in [0.1, 1, 10]:

model = MyModel(hp1=hp1, hp2=hp2)

model.fit(X_train, y_train)

error[hp1, hp2] = error(y_val, model.predict(X_val))

hp1_best, hp2_best = arg_min(error)

​

0.1

1

10

0.1

0.8

0.7

0.7

1

0.4

0.2

0.3

10

0.5

0.6

0.6

7824889

32 of 50

Parameters vs Hyperparameters

A parameter is learned from the data during training.

A hyperparameter is chosen by us, before training.

​

  • k in KNN is a hyperparameter.
  • KNN has no parameters at all, which is unusual.

​

7824889

33 of 50

Feature Engineering

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

34 of 50

Example of Feature Engineering: Standardization

Feature engineering is a process of preparing your data and its features for effective modeling.

​

KNN is built entirely on distance, so it inherits whatever the units happen to be.

  • Flipper length spans roughly 172 to 231 mm.
  • Bill length spans roughly 32 to 60 mm.
  • Flipper length therefore dominates the distance, purely because its numbers are bigger.

​

Standardization rescales every feature to mean 0 and standard deviation 1, so features contribute on equal terms.

7824889

35 of 50

KNN for Regression

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

36 of 50

The Other Kind of Prediction

So far we predicted a category: which species.

That is classification.

​

What if we want to predict a number, like body mass in grams?

That is regression.

​

Does our algorithm still work?

7824889

37 of 50

KNN Regression

Find the k nearest neighbours, then average their values instead of taking a majority vote.

​

  • k = 1: a jagged step function chasing every point.
  • k = 200: nearly a flat line.

​

We see the same overfitting and underfitting issues.

7824889

38 of 50

Demo

KNN for regression�Predicting body mass from flipper length

7824889

39 of 50

K-Means Clustering

  • Data Tools Overview
  • K-Nearest Neighbors (KNN)
  • Vocabulary
    • Training vs Inference,
    • Parametric vs Non-Parametric,
    • Generalization
    • Train/Validation/Test,
    • Overfitting vs Underfitting
    • Hyperparameters
    • Feature Engineering
  • KNN for Regression
  • K-Means Clustering

7824889

40 of 50

What If There Were No Labels?

Everything so far was supervised: every penguin arrived with its species attached.

​

Now suppose the researcher hands you the same measurements with no labels at all, and asks: are there natural groups in here?

​

This is unsupervised learning, and specifically clustering.

7824889

41 of 50

K-Means Clustering

  •  

 

7824889

42 of 50

K-Means Cluster (Lloyd’s) Algorithm

  •  

Why is this the mean of each cluster?

7824889

43 of 50

Updating the Cluster Centers

  •  

Sum over clusters

Sum over points in cluster k

 

7824889

44 of 50

Convergence of K-Means

Lloyd's algorithm always converges, but only to a local optimum.

​

  • Each step can only decrease the objective, and there are finitely many assignments.
  • Different random initializations can give different final clusterings.
  • This is why scikit-learn runs it several times and keeps the best: n_init=10.

7824889

45 of 50

Demo

K-means on the penguins�Animated Lloyd's algorithm

7824889

46 of 50

Choosing the Number of Clusters

  •  

The “Elbow”

 

7824889

47 of 50

Clusters Are Not Labels

K-means rediscovered the species without ever seeing a label.

But it found penguins that sit close together in bill and flipper measurements. In this dataset those groups happen to line up with species.

Change the features and the clusters change.

7824889

48 of 50

Interpreting the Clusters

We used k-means to compute a cluster assignment for each penguin.

  • Which species is each cluster?
    • We do not know. We would have to ask for some labels.
  • Does each cluster represent a species?
    • Maybe.
  • Use caution when interpreting clusters.

7824889

49 of 50

K-means found three clusters that line up closely with the three penguin species. What does this tell us?

The Slido app must be installed on every computer you’re presenting from

Do not edit�How to change the design

7824889

50 of 50

KNN, ML Vocabulary, and K-Means

Lecture 2

Credit: Joseph E. Gonzalez and Narges Norouzi

Reference Book Chapters: Chapter 1 (up to the end of 1.2), Chapter 15.1 (K-Means)