Today’s Roadmap

Introduction to Clustering

K-Means Clustering

Minimizing Inertia

Agglomerative Clustering

Picking K

1

Based on Data 100, Berkeley

Review: Taxonomy of Machine Learning

2

Labeled Data

Supervised Learning

Regression

Classification

Categorical Response

Quantitative Response

Unlabeled Data

Unsupervised Learning

Clustering

Dimensionality Reduction

Data 8: Nearest Neighbors

Earlier: Logistic Regression

Tuesday: Decision Trees

Today: KMeans Clustering

Agglomerative Clustering

Review: Taxonomy of Machine Learning

In “Supervised Learning”:

• Goal is to create a function that maps inputs to outputs.
• Model is learned from example input/output pairs. Each pair consists of:
• Input vector.
• Output value (label).
• Regression: Output value is quantitative.
• Classification: Output value is categorical.

3

Labeled Data

Supervised Learning

Regression

Classification

Categorical Response

Quantitative Response

Review: Taxonomy of Machine Learning

In “Unsupervised Learning”:

• Goal is to identify patterns in unlabeled data.
• We do not have input/output pairs.
• Note: Sometimes we may have labels, but we’re just choosing to ignore them (e.g. PCA on labeled data).

​

Problem: Dimensionality Reduction.

• Solution: PCA.

​

Problem: Clustering.

4

Unlabeled Data

Unsupervised Learning

Clustering

Dimensionality Reduction

Clustering Example

Consider the figure shown from Fall 2019 Midterm 2.

• Each point represents the 1st and 2nd principal component of how much time patrons spent at 8 different zoo exhibits.
• Original dataset was 8 dimensions.
• PCA reduces it to 2.

​

Goal of clustering: Assign each point to a cluster.

​

This is an unsupervised task.

• We don’t have labels for each visitor.
• Want to infer pattern even without labels.

5

Clustering Example

Consider the figure shown from Fall 2019 Midterm 2.

• Each point represents the 1st and 2nd principal component of how much time patrons spent at 8 different zoo exhibits.
• Original dataset was 8 dimensions.
• PCA reduces it to 2.

​

Goal of clustering: Assign each point to a cluster.

​

This is an unsupervised task.

• We don’t have labels for each visitor.
• Want to infer pattern even without labels.

6

Clustering Example 1: Netflix

Suppose you’re Netflix and have information on customer viewing habits.

• Can use clustering to assign each person or show to a “cluster”.
• Don’t have to define clusters in advance.

​

Clustering is different from classification.

• With classification, you have to decide on labels in advance.
• Clustering discovers groups automatically.

​

7

Clustering Example 1: Netflix

8

Note: I’m not certain that Netflix actually uses ML clustering to identify these categories, but they could in principle.

Clustering Example 2: Clustering Students

In 2018, as a tiny part of a project working to understand factors that affect 61B student success, we tried clustering students based on:

• Time and number of posts on Piazza.
• Time and number of submissions to Gradescope.
• Time and number of submissions to GitHub (basically whenever students saved work).

​

Clustering algorithm automatically identified procrastinating students.

​

This result wasn’t particularly useful, but it was somewhat interesting.

9

Clustering Example 3: Reverse Engineering Biology

In plot to the right:

• Rows are conditions (e.g. a row might be: “poured acid on the cells”).
• Columns are genes.

​

Green indicates that the gene was ~off.

• The ~9 genes on the left all got turned off by the 6 experiments at the top.

​

Clustering brings similar observations together.

10

Note: There is also red in this image indicating genes which were especially “on”. Sorry if you can’t differentiate red from green by eye! Blame the 1990s bioinformatics community.

Before and After Clustering

11

From: Cluster analysis and display of genome-wide expression patterns by Michael Eisen, et. al

​

(Recolored by me)

12

K-Means Clustering

Lecture 24, Data 100 Spring 2022

Introduction to Clustering

K-Means Clustering

Minimizing Inertia

Agglomerative Clustering

Picking K

13

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

​

14

Raw data →

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

​

15

Initial random placement of two centers

Iteration: 0

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

​

16

Data colored by closest center

Iteration: 0

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center
• Move center for each color to center of points with that color.

​

​

17

Where should the centers go next?

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

18

Centers moved to their new homes

Iteration: 1

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

19

Data colored by closest center (in new position)

Iteration: 1

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center
• Move center for each color to center of points with that color.

​

20

Centers moved to new position

Iteration: 2

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

21

Data colored by closest center (in new position)

Iteration: 3

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center
• Move center for each color to center of points with that color.

​

​

22

Centers moved to new position

Iteration: 4

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

​

23

Data colored by closest center (in new position)

Iteration: 4

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center
• Move center for each color to center of points with that color.

​

​

​

24

Centers moved to new position

Iteration: 5

K-Means Clustering

Most popular clustering approach. The algorithm:

• Pick an arbitrary k, and randomly place k “centers”, each a different color.
• Repeat until convergence:
• Color points according to the closest center.
• Move center for each color to center of points with that color.

​

​

​

25

Data colored by closest center (in new position)

Iteration: 5

K-Means Clustering

Above we see the results after iteration 4 and 5:

• Centers moved slightly between iteration 4 and 5.
• But no points changed color.
• Are we done?

26

Iteration: 5

Iteration: 4

K-Means Clustering

Above we see the results after iteration 4 and 5:

• Centers moved slightly between iteration 4 and 5.
• But no points changed color.
• Are we done?
• Yes! If we tried iteration 6, we’d see that �centers don’t move at all

27

Iteration: 5

Iteration: 4

K-Means vs. K-Nearest Neighbors

Quick note: K-Means is a totally different algorithm than “K-Nearest Neighbors”.

• K-Means: For clustering:
• Assigns each point to one of K clusters.
• K-Nearest Neighbors: For Classification (or less often, Regression):
• Prediction is the most common class among the k-nearest data points in the training set.
• Covered in Data 8.

​

The names may be similar, but there isn’t really anything in common.

28

Minimizing Inertia

Introduction to Clustering

K-Means Clustering

Minimizing Inertia

Agglomerative Clustering

Picking K

29

K-Means Clustering for K = 4

Below is an example of an output for K=4:

​

30

K-Means Clustering for K = 4

Each time you run K-Means, you get a different output, depending on where centers started.

� random.seed(25) random.seed(29) random.seed(40)

Which is best?

• One approach: Define some sort of loss function.

31

K-Means Clustering for K = 4

Each time you run K-Means, you get a different output, depending on where centers started.

� random.seed(25) random.seed(29) random.seed(40)

​

Which is best?

• One approach: Define some sort of loss function.

​

Goal: Come up with a loss function for clustering.

• What is “good” about the leftmost clustering, but “bad” about the right clustering?

32

K-Means Clustering for K = 4 (Your Ideas for a Clustering Loss Function)

Each time you run K-Means, you get a different output. Define a loss to decide which is best.

� random.seed(25) random.seed(29) random.seed(40)

Come up with a loss function for clustering -- your ideas:

• Clusters being too close to each other seems bad: My thought, should include data as well.
• Minimize average distance between data points and their centers.

33

K-Means Clustering for K = 4

To evaluate different clustering results, we need a loss function

Two common loss functions:

• Inertia: Sum of squared distances from each data point to its center.
• Distortion: Weighted sum of squared distances from each data point to its center.

34

Example:

• Inertia: 0.47² + 0.19² + 0.34² + 0.25² + 0.58² + 0.36² + 0.44²
• Distortion: (0.47² + 0.19² + 0.34²)/3 + (0.25² + 0.58² + 0.36² + 0.44²)/4

K-Means Clustering for K = 4

Each time you run K-Means, you get a different output:

​

random.seed(25) random.seed(29) random.seed(40)

​

Among these three choices, our inertia loss function says that the leftmost clustering is best (inertia: 44.96) and rightmost clustering (inertia: 54.35) is worst.

35

Inertia: 44.96

Inertia: 45.95

Inertia: 54.35

K-Means and Inertia

It turns out that the function K-Means is trying to minimize is inertia…

​

… but often fails to find global optimum. Why? Sketch below

​

Can think of K-means as a pair of optimizers that take turns:

• First optimizer:
• Holds center positions constant.
• Optimizes data colors.
• Second optimizer:
• Holds data colors constant.
• Optimizes center positions.
• Neither gets total control!

36

Optimizing Inertia

Hard problem: Give an algorithm that optimizes inertia FOR A GIVEN K. K is picked in advance.

• Your algorithm should return the EXACT best centers and colors.
• Don’t worry about runtime.

​

This is a bit of a CS61B/CS70/CS170 problem. It may be far too hard for some of you

37

Optimizing Inertia

Hard problem: Give an algorithm that optimizes inertia FOR A GIVEN K. K is picked in advance.

• Your algorithm should return the EXACT best centers and colors.
• Don’t worry about runtime.

​

Algorithm:

• For all possible kⁿ colorings:
• Compute the k centers for that coloring.
• Compute the inertia for the k centers.
• If current inertia is better than best known, write down the current centers and coloring and call that the new best known.

​

No better algorithm has been found for solving the problem of minimizing exactly.

38

A “coloring” is just a choice of color for every point, e.g. point 1 = red, point 2 = green, point 3 = orange, point 4 = blue

For those who know what this means: � K-Means is known to be an NP-hard problem

Agglomerative Clustering

Introduction to Clustering

K-Means Clustering

Minimizing Inertia

Agglomerative Clustering

Picking K

39

K-Means

Which clustering result do you like better?

40

K-Means

Which clustering result do you like better?

K-Means likes the one on the right better. It has lower inertia.

• Why is the inertia on the right lower?
• Is clustering on the right “wrong”?

41

Inertia: 94.41

Inertia: 87.28

K-Means

Which clustering result do you like better?

K-Means likes the one on the right better because it has lower inertia: sum of squared distances from each data point to its center.

• Why is the inertia lower? K-Means optimizes for distance, not “blobbiness”.
• Is clustering on the right “wrong”? Good question!

42

Inertia: 94.41

Inertia: 87.28

Agglomerative Clustering

As with regression and classification, there are many ways to do clustering.

​

So far we’ve seen K-Means, which attempts to minimize inertia.

• Results not guaranteed to optimize inertia.
• Even global optimum may not match our intuition of the best result.

​

Let’s discuss an alternate idea known as agglomerative clustering.

Basic idea:

• Every data point starts out as its own cluster.
• Join clusters with neighbors until we have only K clusters left.

​

Let’s see an example for K = 2.

43

Agglomerative Clustering Example

When the algorithm starts, every data point is in its own cluster.

• Below, 12 data points, so 12 clusters.
• Closest clusters are 10 and 11, so merge them.

44

Agglomerative Clustering Example

When the algorithm starts, every data point is in its own cluster.

• Below, 12 data points, so 12 clusters.
• Closest clusters are 10 and 11, so merge them.

45

Two points in the same cluster

Agglomerative Clustering Example

Next two closest are 0 and 4, so merge them.

46

Two points in the same cluster

Agglomerative Clustering Example

Next two closest are 0 and 4, so merge them

47

Merged

Agglomerative Clustering Example

At this point we have 10 clusters:

• 8 with a single point {1, 2, 3, 5, 6, 7, 8, 9}
• 2 with two points {0/0, 10/10}

48

Agglomerative Clustering Example

Tricky question:

• What is the distance between clusters 0 and 3?

49

Agglomerative Clustering Example

Tricky question:

• What is the distance between clusters 0 and 3?
• There is no right answer. Common choice, use the max.

50

Would be perfectly reasonable to do something else, e.g. average or minimum.

Agglomerative Clustering Example

Next two closest clusters are 1 and 5.

51

Agglomerative Clustering Example

Next two closest clusters are 1 and 5.

52

Merged

Agglomerative Clustering Example

Next two closest clusters are 7 and 9.

• Note: Might not look that way, but axes are not on the same scale! �Y-axis goes only up to 2.5, and x axis goes up to more than 7.

​

​

​

53

Agglomerative Clustering Example

Next two closest clusters are 7 and 9.

• Note: If you think some other choice looks better, note that axes are not on the same scale! �Y-axis goes only up to 2.5, and x axis goes up to more than 7.

​

​

​

​

54

Merged

1

1

Agglomerative Clustering Example

Next closest are 6 and 8.

55

Agglomerative Clustering Example

Next closest are 6 and 8.

56

Merged

Agglomerative Clustering Example

Now 0 and 3 are closest. Merge them next.

57

Merged

Agglomerative Clustering Example

Now 0 and 3 are closest. Merge them next.

​

58

Merged

Agglomerative Clustering Example

Next up are 1 and 10.

​

​

59

Merged

Agglomerative Clustering Example

Next up are 1 and 10.

​

​

​

60

Merged

Agglomerative Clustering Example

Next up are 0 and 7. Why?

• Max line between any member of 0 and 6 is longer than max line between any member of 0 and 7.

​

​

​

61

Blue line is shorter than gold line.

​

Note: Doesn’t look visually shorter due to different scales for x and y axes.

• x-axis is ~from 1 to 7
• y-axis is ~from 0 to 2.5

Agglomerative Clustering Example

Next up are 0 and 7. Why?

• Max line between any member of 0 and 6 is longer than max line between any member of 0 and 7.

62

Merged

Agglomerative Clustering Example

Next up are 0 and 6.

​

​

63

Agglomerative Clustering Example

Next up are 0 and 6.

64

Merged

Agglomerative Clustering Example

Next up are 0 and 2.

65

Agglomerative Clustering Example

Next up are 0 and 2.

• At this point, we are done, because we only have two clusters left!
• Reminder: We arbitrarily chosen two clusters at the start.

66

Merged

Agglomerative Clustering Example

On the full dataset, our agglomerative clustering algorithm gets the “correct” output.

67

Clustering and Dendrograms

Agglomerative clustering is one form of “hierarchical clustering.”

• Can keep track of when two clusters got merged.
• Each cluster is a tree.
• Can visualize merging hierarchy, resulting in a “dendrogram.”
• Won’t discuss any further, but you might see these in the wild.

68

Clustering Algorithms: Many More We Haven’t Seen

69

https://scikit-learn.org/stable/_images/sphx_glr_plot_cluster_comparison_001.png

K Means

Agglomerative

Quick Sidetrack: Grading

Some professors (not me) use agglomerative clustering for grading bins.

• If there is a big gap between two people, draw a grading threshold there.
• The idea: Grade clustering should be more like left figure, not right.

70

Inertia: 87.28

Inertia: 94.41

Picking K

Lecture 24, Data 100 Spring 2022

Introduction to Clustering

K-Means Clustering

Minimizing Inertia

Agglomerative Clustering

Picking K

71

Picking K

The algorithms we’ve discussed today require us to pick a K before we start.

• But how do we pick K?

​

Often, best K is subjective:

• Example: State plot.
• How many clusters are there here?

72

Picking K: Elbow Method

For K-Means, one approach is to plot inertia versus many different K values.

• Pick the K in the “elbow”, where we get diminishing returns afterwards.
• Note: Big complicated data often lacks an elbow.

73

Silhouette Scores

To evaluate how “well clustered” a specific data point is, we can use the “silhouette score”, a.k.a. the “silhouette width”.

• High score: Near the other points in its X’s cluster.
• Low score: Far from the other points in its cluster.

74

Low score point

High score point

For a data point X, score S is:

• A = avg distance to other points in cluster.
• B = avg distance to points in closest cluster.
• S = (B - A) / max(A, B)

Silhouette Scores

For a data point X:

• A = average distance to other points in X’s cluster.
• B = average distance to points in closest cluster.
• S = (B - A) / max(A, B).

​

75

What is the highest possible S?

• How can this happen?

Low score point

High score point

Silhouette Scores

For a data point X:

• A = average distance to other points in X’s cluster.
• B = average distance to points in closest cluster.
• S = (B - A) / max(A, B).

​

​

76

What is the highest possible S?

• How can this happen?

​

Highest possible S is 1.

• This happens if every point in X’s cluster is right on top of X.
• Average distance to other points in X’s cluster is 0 (all equal to zero!), so A = 0.
• B / max(0, B) = B / B = 1

Low score point

High score point

Silhouette Scores

For a data point X:

• A = average distance to other points in X’s cluster.
• B = average distance to points in closest cluster (other than X).
• So if you have 100 clusters, it’d be the distance from X to pts in closest neighboring cluster.
• S = (B - A) / max(A, B).

​

​

77

Can S be negative?

Low score point

High score point

Silhouette Scores

For a data point X:

• A = average distance to other points in X’s cluster.
• B = average distance to points in closest cluster.
• S = (B - A) / max(A, B).

​

​

78

Can S be negative?

• Yes. If the average distance to X’s clustermates is larger than distance to the closest cluster.

Low score point

High score point

Silhouette Scores

For a data point X:

• A = average distance to other points in X’s cluster.
• B = average distance to points in closest cluster.
• S = (B - A) / max(A, B).

​

​

79

Can S be negative?

• Yes. If the average distance to X’s clustermates is larger than distance to the closest cluster.
• Example: The “low score” point on the right has S = -0.13

Low score point

High score point

Silhouette Plot

We can plot the Silhouette Scores for all of our data points.

• Points with large silhouette widths are deeply embedded in their cluster.
• Red dotted line shows the average.

80

Low score point

High score point

Low score point

High score point

Blue Cluster

Orange Cluster

Silhouette Scores, K = 2 vs. K = 3

81

Average silhouette score is lower.

Blue

Orange

Green

Blue Cluster

Orange Cluster

Picking K: Real World Metrics (Example via Andrew Ng)

Sometimes you can rely on real world metrics to guide your choice of K.

​

Perform 2 clusterings:

• Cluster heights and weights of customers with K = 3 to design Small, Medium, and Large shirts.
• Cluster heights and weights of customers with K = 5 to design XS, S, M, L, and XL shirts.

​

To pick K:

• Consider projected costs and sales for the 2 different Ks.
• Pick the one that maximizes profit.

82

Summary

Today we discussed a new machine learning goal: Clustering

​

Saw two solutions:

• K-Means
• Tries to optimize a loss function called inertia -- no known algorithm to find the optimal answer in an efficient manner.
• Agglomerative

​

Our version of these algorithms required a hyperparameter k.

• 4 ways to pick k: Intuitively, elbow method, silhouette scores, Harnessing real world metrics.

​

​

83

Bigger Picture Summary

There are many Machine Learning problems.

• Each can be addressed by many different solution techniques.
• Each has many metrics for evaluating success / loss.

�

Many solution technique can be used for multiple problem types.

• Example: Linear models can be used for regression and classification.

�

We’ve only scratched the surface. Haven’t discussed many important ideas.

• One hugely important solution technique: Neural Networks / Deep Learning.
• See other courses in CS and Data Science for more.
• Will provide some specific course recommendations in the last lecture.

​

84

Taxonomy of Machine Learning

85

Labeled Data

Supervised Learning

Regression

Classification

Categorical Response

Quantitative Response

Unlabeled Data

Unsupervised Learning

Clustering

Dimensionality Reduction

Reward

Reinforcement Learning