Back to Evaluation, Leakage, and Unsupervised

Clustering and Dimensionality Reduction

Unsupervised: find structure without labels. The four most-used techniques. FIND_VIDEO: search 'k-means hierarchical PCA UMAP' — recommended channel: StatQuest. Aim for 11 min or under.

9 minutesVideo LessonPDF notes

Watch Clustering and Dimensionality Reduction on YouTube

🎯 Free Guest Mode: You are learning for free. Sign in to save your completion progress and quiz answers.

Ready to continue?

Mark this lesson as complete when you're ready to proceed.

Key moments

Introduction to K-means — K-means clustering is introduced as a method to group samples based on similarity.
Steps 1-2: Initialization — The process begins by selecting K (number of clusters) and randomly selecting K initial data points.
Steps 3-4: Assignment — Each point is assigned to the nearest cluster center by measuring the distance to all initial clusters.
Step 5: Recalculation — The mean of each newly formed cluster is calculated, and points are reassigned based on these new means.
Handling Suboptimal Runs — The algorithm repeats the clustering process with different starting points to find the lowest total variation.
Selecting K: Elbow Plot — The total variation is plotted against K values, and the optimal K is chosen at the 'elbow' where variance reduction slows.
K-means vs Hierarchical — K-means requires a specified number of clusters, unlike hierarchical clustering which focuses on pair-wise similarity.
Multi-Dimensional Data — K-means works in multiple dimensions by using Euclidean distance, which is equivalent to the Pythagorean theorem.
Clustering Heatmaps — Heatmap data can be clustered by treating samples as axes and calculating N-dimensional Euclidean distance between points.

PDF notes

Bottom line: You will be able to apply the K-means clustering algorithm to group data points based on similarity, whether on a line or in multi-dimensional space. You will also learn how to objectively select the optimal number of clusters (K) using the elbow plot method.

This lesson on Clustering and Dimensionality Reduction is hands-on and example-driven. You will be able to apply the K-means clustering algorithm to group data points based on similarity, whether on a line or in multi-dimensional space. You will also learn how to objectively select the optimal number of clusters (K) using the elbow plot method.

What You'll Be Able To Do

Define the purpose and steps of the K-means clustering algorithm.
Calculate the Euclidean distance between data points in multi-dimensional space.
Explain how K-means clustering handles different starting points (initial clusters).
Interpret an elbow plot to determine the optimal value for K.
Contrast K-means clustering with hierarchical clustering methods.

Topics Covered in Clustering and Dimensionality Reduction

Introduction to K-means (0:00 - 0:45) — K-means clustering is introduced as a method to group samples based on similarity.
Steps 1-2: Initialization (0:45 - 1:30) — The process begins by selecting K (number of clusters) and randomly selecting K initial data points.
Steps 3-4: Assignment (1:30 - 2:45) — Each point is assigned to the nearest cluster center by measuring the distance to all initial clusters.
Step 5: Recalculation (2:45 - 3:45) — The mean of each newly formed cluster is calculated, and points are reassigned based on these new means.
Handling Suboptimal Runs (3:45 - 4:45) — The algorithm repeats the clustering process with different starting points to find the lowest total variation.
Selecting K: Elbow Plot (4:45 - 6:30) — The total variation is plotted against K values, and the optimal K is chosen at the 'elbow' where variance reduction slows.
K-means vs Hierarchical (6:30 - 7:15) — K-means requires a specified number of clusters, unlike hierarchical clustering which focuses on pair-wise similarity.
Multi-Dimensional Data (7:15 - 8:30) — K-means works in multiple dimensions by using Euclidean distance, which is equivalent to the Pythagorean theorem.
Clustering Heatmaps (8:30 - 9:30) — Heatmap data can be clustered by treating samples as axes and calculating N-dimensional Euclidean distance between points.

SQL Cheat Sheet

K Means Clustering — Iteratively groups data points into K clusters based on proximity
```
SELECT data_point, cluster_id FROM clustered_data;
```
K Value — The predetermined number of clusters the algorithm must identify
- In practice: K = 3
Euclidean Distance — Measures the straight-line distance between two points in N dimensions
- In practice: sqrt(x^2 + y^2)
Total Variation — Sum of squared distances within each cluster; measures quality
Elbow Plot — Visualizes variance reduction versus K to help select optimal K
- In practice: Plot: Variance vs K
Iteration — Process of re-calculating means and re-assigning points until stable
- In practice: Repeat steps 3-5 until clusters stabilize.

Comparison Table

Feature	K-Means Clustering	Hierarchical Clustering
Goal	Put data into K specified clusters.	Identify most similar pair-wise items.
Input	Requires pre-selected K value.	Does not require pre-selected K.
Output	Final set of K distinct groups.	Tree structure showing similarity.
Method	Iterative mean calculation.	Pair-wise similarity calculation.

Common Pitfalls

Pitfall: {'Mistake': 'Relying on a single run of K-means for final results.', 'Avoid': 'Run the algorithm multiple times with different random starting points.'}
Pitfall: {'Mistake': 'Assuming the first clustering result is the best overall.', 'Avoid': 'Compare total variation across multiple runs and select the lowest variance result.'}
Pitfall: {'Mistake': 'Selecting K based only on visual inspection of the data.', 'Avoid': 'Use the elbow plot method to objectively quantify the reduction in variance.'}
Pitfall: {'Mistake': 'Using K=1 as a meaningful cluster result.', 'Avoid': 'K=1 is only used as the baseline for calculating the worst-case total variation.'}

FAQs

How do you figure out what value to use for K? Try different values for K and plot the reduction in total variation (the elbow plot). Select the K where the reduction in variation significantly slows down.
Why does K-means run multiple times? K-means starts with random initial clusters, which can lead to suboptimal results. Running it multiple times allows the algorithm to find the clustering with the lowest total variation.
How is K-means different from hierarchical clustering? K-means forces the data into a specific number (K) of clusters, while hierarchical clustering simply identifies which two things are most similar pair-wise.
Can K-means cluster data that isn't on a simple line or XY graph? Yes, K-means uses Euclidean distance, which can be calculated for any number of dimensions (samples or axes).

Common pitfalls

Relying on a single run of K-means for final results. — Run the algorithm multiple times with different random starting points.
Assuming the first clustering result is the best overall. — Compare total variation across multiple runs and select the lowest variance result.
Selecting K based only on visual inspection of the data. — Use the elbow plot method to objectively quantify the reduction in variance.
Using K=1 as a meaningful cluster result. — K=1 is only used as the baseline for calculating the worst-case total variation.

StatQuest StatQuest StatQuest StatQuest Hello. I'm Josh Starmer and welcome to StatQuest. Today we're going to be talking about K means clustering. We're going to 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 3. 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 three: 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 four: 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, too. Now that all the points are in clusters, we go on to step five: 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, we're 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, its 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 reclusters based on the new means. It repeats until the clusters no longer change. 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 3, 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 zero. However, if we plot the reduction in variance per value for K, there is a huge reduction in variation with K equals 3. 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, pair-wise, 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 recluster. 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 heat map? 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, etcetera, etcetera, etcetera. Hooray! We've made it to the end of another exciting StatQuest. If you like this StatQuest and want to see more, please subscribe. And if you want to support StatQuest, well, click the like button down below and consider buying one or two of my original songs. All right. Tune in next time for another exciting StatQuest.

Frequently asked questions

How do you figure out what value to use for K?

Try different values for K and plot the reduction in total variation (the elbow plot). Select the K where the reduction in variation significantly slows down.

Why does K-means run multiple times?

K-means starts with random initial clusters, which can lead to suboptimal results. Running it multiple times allows the algorithm to find the clustering with the lowest total variation.

How is K-means different from hierarchical clustering?

K-means forces the data into a specific number (K) of clusters, while hierarchical clustering simply identifies which two things are most similar pair-wise.

Can K-means cluster data that isn't on a simple line or XY graph?

Yes, K-means uses Euclidean distance, which can be calculated for any number of dimensions (samples or axes).