StatQuest: K-means clustering

Summary

In this episode of Stat Quest, Josh Starmer introduces k-means clustering, a method for organizing data points into distinct groups. The tutorial covers selecting the number of clusters (K), randomly choosing initial points, calculating distances to assign points to the nearest cluster, and iteratively updating cluster means until convergence. It also explores determining the optimal K value using an 'elbow plot' and discusses the difference between k-means and hierarchical clustering. The video concludes with examples of applying k-means to data on a number line, in two dimensions, and on a heatmap, illustrating the versatility of this clustering technique.

Takeaways

• 📚 The video is an educational tutorial on k-means clustering, a method used to group data points into clusters.
• 🔍 It explains how to identify the optimal number of clusters, 'K', for the data set, which is a crucial step in k-means clustering.
• 🎯 The process begins by randomly selecting 'K' distinct data points as initial clusters and then iteratively refining these clusters.
• 📏 The script describes how to calculate the distance of each data point from the centroids of the clusters to assign them to the nearest cluster.
• ⚖️ It discusses the importance of calculating the mean of each cluster to update the centroids and reassign points based on these new values.
• 🔄 The iterative process continues until the clusters no longer change, indicating that the clustering has converged to a stable solution.
• 📊 The quality of clustering can be assessed by measuring the total variation within each cluster, with lower variation indicating better clustering.
• 📈 The 'elbow method' is introduced as a way to determine the best value for 'K' by observing the point where the reduction in variance per additional cluster diminishes.
• 🤖 The video highlights that k-means clustering is different from hierarchical clustering in that it aims to partition data into a specified number of clusters.
• 📈 The script also covers how to apply k-means clustering to data that is not on a number line, using Euclidean distance in two or more dimensions.
• 🌡️ It mentions that k-means can be used with data represented as a heatmap, by treating the data points in a two-dimensional space and applying the same clustering principles.
• 🎶 The video ends with a call to action for viewers to subscribe for more content and support the channel by liking the video and considering purchasing the creator's songs.

Q & A

What is the main topic of the video?

The main topic of the video is k-means clustering, a method used to group data into clusters based on their similarities.

Who is the presenter of the video?

The presenter of the video is Josh Stormer.

What is the purpose of using k-means clustering in the video?

The purpose of using k-means clustering in the video is to identify clusters in data without relying on visual inspection, such as distinguishing between different types of tumors or cell types.

What is the 'K' in k-means clustering?

The 'K' in k-means clustering represents the number of clusters that the algorithm is instructed to identify in the data.

How does k-means clustering start the clustering process?

K-means clustering starts by randomly selecting 'K' distinct data points as the initial clusters.

What is the method used to assign data points to clusters in k-means clustering?

Data points are assigned to the nearest cluster based on the calculated distance between the point and the centroids of the clusters.

How does the k-means algorithm determine the best value for K?

The best value for K can be determined by trying different values and observing the total variation within the clusters, often using an elbow plot to identify the point where the reduction in variance decreases significantly.

What is an elbow plot in the context of k-means clustering?

An elbow plot is a graphical representation that shows the reduction in variance as the number of clusters increases, helping to identify the optimal number of clusters by finding the 'elbow' point where the decrease in variance slows down.

How does k-means clustering differ from hierarchical clustering?

K-means clustering aims to partition the data into a specified number of clusters, whereas hierarchical clustering builds a tree of clusters and does not require a predetermined number of clusters.

Can k-means clustering be applied to data that is not plotted on a number line?

Yes, k-means clustering can be applied to data in two or more dimensions using the Euclidean distance to measure the distance between points.

How is the Euclidean distance calculated for data with more than two dimensions?

The Euclidean distance for data with more than two dimensions is calculated as the square root of the sum of the squared differences between corresponding coordinates of points in the multidimensional space.

What is the significance of calculating the mean of each cluster in k-means clustering?

Calculating the mean of each cluster is important because it helps to reassign the data points to the nearest updated cluster center, which is essential for the iterative process of refining the clusters.

Outlines

00:00

📊 Introduction to K-Means Clustering

Josh Stormer introduces the concept of k-means clustering, a method for organizing data points into clusters based on their similarity. The video aims to demonstrate how to apply this technique to data that can be plotted on a line, an XY graph, or a heatmap. The process begins by selecting the number of clusters (K), choosing initial cluster centers, and iteratively refining the clusters by reassigning points to the nearest mean until no changes occur. The video also hints at a more sophisticated method for determining the optimal value of K.

05:01

🔍 Exploring K-Means Clustering Techniques and Cluster Quality Assessment

This paragraph delves deeper into the k-means clustering process, emphasizing the iterative nature of the algorithm and the importance of selecting the right value for K. It explains how to assess the quality of clustering by measuring the total variation within clusters. The video introduces the concept of an 'elbow plot' to help determine the optimal number of clusters by observing the rate of variance reduction. Additionally, it touches on the differences between k-means and hierarchical clustering, and how k-means can be applied to data in two or more dimensions using Euclidean distance. The summary concludes with a mention of how to handle heatmap data by treating it as a two-dimensional case for clustering.

Keywords

💡StatQuest

StatQuest is the name of the educational channel presented by Josh Starmer, which focuses on explaining statistical concepts in an accessible and engaging manner. In the context of the video, StatQuest serves as the platform through which the concept of k-means clustering is introduced and explained to the audience.

💡K-means Clustering

K-means clustering is a method of vector quantization, used to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. In the video, k-means clustering is the central theme, where Josh explains how to use this technique to group data points into clusters based on their similarities.

💡Cluster

A cluster in the context of k-means clustering refers to a grouping of data points that are similar to each other and dissimilar to points in other groups. The video script describes the process of assigning each data point to the nearest cluster based on calculated distances.

💡XY Graph

An XY graph, also known as a scatter plot, is a type of chart used to display data points on horizontal and vertical axes. In the video, the concept of plotting data points on an XY graph is used to visually represent the clusters that the k-means algorithm would identify.

💡Heat Map

A heat map is a graphical representation of data where individual values are represented as colors. In the script, Josh mentions the application of k-means clustering to a heat map, which could represent complex data with multiple dimensions.

💡K (in k-means)

The 'K' in k-means clustering refers to the number of clusters to be identified in the data set. The script explains that selecting the appropriate value for K is a crucial step in the clustering process, with Josh demonstrating how to choose K by using an elbow plot.

💡Euclidean Distance

Euclidean distance is the 'ordinary' straight-line distance between two points in Euclidean space. In the video, the Euclidean distance is used to measure the distance between data points and the centroids of the clusters during the k-means clustering process.

💡Centroid

The centroid is the central point of a shape, such as a triangle or a circle. In the context of clustering, the centroid is the mean point of all the data points in a cluster. The script describes how the mean (centroid) of each cluster is calculated and used to reassign data points in subsequent iterations of the k-means algorithm.

💡Iteration

In the context of the k-means algorithm, an iteration refers to a complete run through the process of assigning data points to clusters, recalculating centroids, and reassigning points based on the new centroids. The script mentions that the algorithm repeats this process until the clusters no longer change.

💡Elbow Plot

An elbow plot is a graphical tool used to determine the optimal number of clusters for k-means clustering. It plots the variance within the clusters against the number of clusters. In the script, Josh explains how to use an elbow plot to identify the point where adding more clusters does not significantly decrease the variance, indicating the optimal K.

💡Hierarchical Clustering

Hierarchical clustering is a clustering technique that builds a hierarchy of clusters. Unlike k-means, which requires the number of clusters to be specified in advance, hierarchical clustering does not require this specification and can provide a dendrogram to visualize the clustering structure. The script contrasts hierarchical clustering with k-means clustering.

Highlights

Introduction to k-means clustering and its application in grouping data on a line or an XY graph and even on a heatmap.

The necessity of choosing the best value for K in k-means clustering to identify the correct number of clusters.

Step-by-step explanation of the k-means clustering process starting from selecting the number of clusters.

The method of randomly selecting initial clusters and the importance of this step in the k-means algorithm.

Calculating the distance between data points and clusters to assign points to the nearest cluster.

The iterative process of recalculating the mean of each cluster and re-clustering based on the new means.

Assessing the quality of clustering by measuring the total variation within each cluster.

The concept of using multiple starting points to improve the reliability of k-means clustering results.

The use of an elbow plot to determine the optimal value for K by observing the reduction in variance.

Comparing k-means clustering with hierarchical clustering and their distinct approaches to data grouping.

Application of k-means clustering in two-dimensional space using Euclidean distance.

Explanation of how to handle data that is not plotted on a number line by using Euclidean distance in higher dimensions.

Approach to clustering heatmap data by renaming samples as x and y and plotting them on an XY graph.

The significance of calculating Euclidean distances for clustering data with more than two dimensions.

Encouragement for viewers to subscribe for more educational content on statistical methods.

Invitation for viewers to support the channel by liking the video and considering purchasing original songs.

Transcripts

statcast

[Music]

stat quest stat quest stat quest hello

I'm Josh stormer and welcome to stat

quest today we're going to be talking

about k-means clustering we're gonna

learn how to cluster samples that can be

put on a line on an XY graph and even on

a heat map and lastly we'll also talk

about how to pick the best value for K

imagine you had some data that you could

plot on a line and you knew you needed

to put it into three clusters maybe they

are measurements from three different

types of tumors or other cell types in

this case the data make three relatively

obvious clusters but rather than rely on

our eye let's see if we can get a

computer to identify the same three

clusters to do this we'll use k-means

clustering we'll start with raw data

that we haven't yet clustered step one

select the number of clusters you want

to identify in your data this is the K

in k-means clustering in this case we'll

select K equals three that is to say we

want to identify three clusters there is

a fancier way to select a value for K

but we'll talk about that later

step two randomly select three distinct

data points these are the initial

clusters

step 3 measure the distance between the

first point and the three initial

clusters this is the distance from the

first point to the blue cluster this is

the distance from the first point to the

green cluster

and this is the distance from the first

point to the orange cluster well it's

kind of yellow but we'll just call it

orange for now step 4 assign the first

point to the nearest cluster in this

case the nearest cluster is the blue

cluster now we do the same thing for the

next point we measure the distances and

then assign the point to the nearest

cluster now we figure out which cluster

the third point belongs to we measure

the distances and then assign the point

to the nearest cluster the rest of these

points are closest to the orange cluster

so they'll go in that one two now that

all the points are in clusters we go on

to step 5 calculate the mean of each

cluster then we repeat what we just did

measure and cluster using the mean

values

since the clustering did not change at

all during the last iteration were done

BAM the k-means clustering is pretty

terrible compared to what we did by eye

we can assess the quality of the

clustering by adding up the variation

within each cluster here's the total

variation within the clusters since

k-means clustering can't see the best

clustering it's only option is to keep

track of these clusters and their total

variance and do the whole thing over

again with different starting points so

here we are again back at the beginning

k-means clustering picks three initial

clusters and then clusters all the

remaining points calculates the mean of

each cluster and then re clusters based

on the new means it repeats until the

cluster is no longer change bit bit bit

of bit of boop boop boop now that the

data are clustered we sum the variation

within each cluster

and then we do it all again

at this point k-means clustering knows

that the second clustering is the best

clustering so far but it doesn't know if

it's the best overall so it will do a

few more clusters it does as many as you

tell it to do and then come back and

return that one if it is still the best

question how do you figure out what

value to use for K with this data it's

obvious that we should set K to three

but other times it is not so clear one

way to decide is to just try different

values for K

we'll start with k equals 1 k equals 1

is the worst case scenario we can

quantify its badness with the total

variation now try K equals 2 K equals 2

is better and we can quantify how much

better by comparing the total variation

within the two clusters to K equals 1

now try K equals 3 k equals 3 is even

better we can quantify how much better

by comparing the total variation within

the three clusters to k equals 2 now try

k equals 4 the total variation within

each cluster is less than when K equals

3 each time we add a new cluster the

total variation within each cluster is

smaller than before and when there is

only one point per cluster the variation

equals 0 however if we plot the

reduction in variance per value for K

there is a huge reduction in variation

with K equals three but after that the

variation doesn't go down as quickly

this is called an elbow plot and you can

pick K by finding the elbow in the plot

question how is k-means clustering

different from hierarchical clustering

k-means clustering specifically tries to

put the data into the number of clusters

you tell it to hierarchical clustering

just tells you pairwise what two things

are most similar question what if our

data isn't plotted on a number line just

like before you pick three random points

and we use the Euclidean distance in two

dimensions the Euclidean distance is the

same thing as the Pythagorean theorem

then just like before we assign the

point to the nearest cluster and just

like before we then calculate the center

of each cluster and re cluster BAM

although this looks good the computer

doesn't know that until it does the

clustering a few more times question

what if my data is a heatmap well if we

just have two samples we can rename them

x and y and we can then plot the data in

an XY graph then we can cluster just

like before note we don't actually need

to plot the data in order to cluster it

we just need to calculate the distances

between things when we have two samples

or two axes the Euclidean distance is

the square root of x squared plus y

squared when we have three samples or

three axes the Euclidean distance is the

square root of x squared plus y squared

plus Z squared and when we have four

samples or four axes the Euclidean

distance is the square root of x squared

plus y squared plus Z squared plus a

squared etc etc etc hooray

we've made it to the end of another

exciting stat quest if you like this

stat quest and want to see more please

subscribe and if you want to support

stack quest well click the like button

down below and consider buying one or

two of my original songs alright tune in

next time for another exciting stat

quest