K-Means (Unsupervised Learning)
How an algorithm finds groups without anyone telling it what to look for.
What is K-Means Clustering?
Imagine you're organizing a large party and want to optimally group guests around standing tables. K-Means works like an intelligent party planner.
You know the number of tables (K), but not where the tables should be placed. Dr. Elana Vasquiz, our genome researcher, faces a similar problem: she has many genome samples and wants to organize them into meaningful groups.
The K-Means algorithm works as follows:
- Randomly place tables (initialize centroids)
- Each guest goes to the nearest table (assign data points)
- Move tables to the center of their guest groups (recalculate centroids)
- Repeat until everyone is satisfied (reach convergence)
In the end, you have perfectly distributed groups - just like Elana finds her genome clusters!
Analogy:
Imagine you're organizing a large party and want to optimally group guests around standing tables. K-Means works like an intelligent party planner.
You know the number of tables (K), but not where the tables should be placed. Dr. Elana Vasquiz, our genome researcher, faces a similar problem: she has many genome samples and wants to organize them into meaningful groups.
The K-Means algorithm works as follows:
- Randomly place tables (initialize centroids)
- Each guest goes to the nearest table (assign data points)
- Move tables to the center of their guest groups (recalculate centroids)
- Repeat until everyone is satisfied (reach convergence)
In the end, you have perfectly distributed groups - just like Elana finds her genome clusters!
Definition:
K-Means is an unsupervised learning algorithm for partitioning data into k clusters by minimizing the Within-Cluster Sum of Squares (WCSS).
Objective Function: Minimize Σ(||xi - μj||²) for all data points xi and cluster centroids μj
Algorithm: Lloyd's algorithm with iterative centroid reassignment and data partitioning
Convergence: Guaranteed for finite datasets, typically O(tkdn) time complexity, where t=iterations, k=clusters, d=dimensions, n=datapoints
The global optimization problem (minimal WCSS worldwide) is NP-hard. However, Lloyd's algorithm efficiently finds a local optimum, making K-Means tractable.
How does this demo work?
This interactive demonstration shows the K-Means algorithm in action. Dr. Elana Vasquiz guides you through genome analysis and explains every step.
Interaction with the Demo
- Mouse click to add:Click on the black field to add new genome samples
- Set K parameter:Use the slider to change the number of desired clusters
- Control algorithm:Start, stop, or reset the K-Means algorithm as desired
Visualization Elements
The demo shows various aspects of the algorithm in real-time:
- Blue circles:Represent genome samples to be grouped
- Large colored circles:Cluster centers that move until they find optimal positions
- Colored regions:Show mathematical boundaries between clusters (Voronoi diagram)
- Elbow diagram:Helps determine the optimal number of clusters
K-Means Clustering Demo
What happens on the field
This demo sorts points into groups — with no labels given, only by how close they lie to each other. Here is what you see on screen.
- What you see
- A dark field with points scattered evenly across it. Once the clustering runs, the points take on several group colours, and each group gets a larger centre marker as its middle.
- What happens
- On every step the centre markers slide to the middle of their coloured group. Then single points switch colour whenever a different centre suddenly sits closer. The borders between the colour patches shift step by step, until nothing moves any more.
- What you can do
- Click on the field to place your own points, or have points scattered for you. Set the number of groups, then run the process automatically or walk through it step by step.
- What to watch for
- Nobody tells the AI where the groups are. It finds them entirely on its own — purely from how close the points sit to each other.
🧬 Interactive Genome Analysis
Welcome to my lab! Let's analyze these genomes.
Clustering Controls
Data Management
Elbow Method
Determine the optimal number of clusters automatically
Updates automatically...
The elbow method helps determine the optimal number of clusters (K).
It measures inertia (sum of squared distances) for different K values and looks for the 'elbow' - the point where improvement slows down.
The elbow shows the best balance between clustering quality and complexity.
K-Means Explained
The K-Means Algorithm in Detail
K-Means is an iterative algorithm that partitions data into k clusters. The goal is to group data points such that the variance within each cluster is minimal. Here are the four main steps:
- Initialization: Choose k random points as initial cluster centroids (or use K-Means++ for better results). These starting points significantly influence the final result.
- Assignment: Assign each data point to the nearest centroid (based on Euclidean distance). This is done by calculating the Euclidean distance to each centroid.
- Update: Calculate new centroids as the mean of all assigned data points for each cluster. The centroids move to the center of mass of their group.
- Repetition: Repeat steps 2-3 until centroids no longer move (convergence reached) or only move minimally.
The algorithm guarantees convergence to a local optimum, but not necessarily to the global optimum. Therefore, it is often run multiple times with different initializations.
Understanding the Elbow Method
The elbow method is a heuristic for determining the optimal number of clusters in a dataset. It is based on analyzing the inertia (Within-Cluster Sum of Squares).
It calculates the Within-Cluster Sum of Squares (WCSS) for different k values and looks for the 'elbow' - the point where the rate of WCSS reduction dramatically slows. This point represents a good balance between model complexity and explanatory power.
Limitations and Constraints of K-Means
- Spherical Clusters: Works best with spherical, similarly sized clusters. With complex shapes (e.g., half-moons, nested circles), K-Means often fails.
- K Must Be Chosen in Advance: The choice of k must be made in advance. This requires domain knowledge or methods like Elbow or Silhouette analysis.
- Depends on Initialization: Results can vary depending on initialization. K-Means++ improves this, but the problem persists.
- Sensitivity to Outliers: Sensitive to outliers and noise in the data, as they can strongly influence the centroids. Median-based variants (K-Medians) can be more robust.
Practical Applications
- Customer Segmentation: Grouping customers based on purchasing behavior and demographics for targeted marketing.
- Bioinformatics: Classification of genes or proteins based on expression patterns or structural properties.
- Image Processing: Color quantization (palette reduction) and image segmentation (division into regions).
- Data Mining: Exploratory data analysis and pattern recognition in large datasets.
Try the demo! Experiment with different k values and initializations. Observe how the centroids move and the clusters form.
1
# K-Means Clustering Algorithm
2
function k_means(data, k):
3
# Main function: Divides data into k groups
4
X = load_data_points() # Unlabeled data
5
X = normalize(X) # Scale to 0-1
6
7
# Choose initial centroids
8
centroids = randomly_select(X, k_points)
9
max_iterations = 300, converged = false
10
11
while not converged:
12
# One iteration of K-Means
13
14
# Step 1: Assign points to clusters
15
for each point in X:
16
distances = calculate_distance(point, all_centroids)
17
nearest = find_minimum(distances)
18
cluster[point] = nearest
19
20
# Step 2: Recalculate centroids
21
for each cluster_id in k:
22
cluster_points = get_points(cluster_id)
23
new_center = mean(cluster_points)
24
centroids[cluster_id] = new_center
25
26
# Step 3: Check convergence
27
movement = distance(old_centroids, new_centroids)
28
if movement < 0.001:
29
converged = true
30
31
# Calculate quality
32
inertia = sum_squared_distances(points, centroids)
33
return cluster_assignments, centroids, inertia
📊 Load Data
Load unlabeled data and normalize it. Scale all features to same range (0-1) so no dimension dominates.
X = load_data_points() # Unlabeled data
X = normalize(X) # Scale to 0-1
🚀 Initialization
Choose starting points: K random centroids. Or better: K-Means++ for smarter starting points with maximum distance.
🎯 Assignment Phase
Each data point finds its nearest centroid. Voronoi diagram emerges: regions around each center.
📐 Update Phase
Centroids move to the center of mass of their clusters. Minimizes variance within each cluster.
🔍 Convergence
Repeat assignment and update until stable. Guarantees local optimum, not necessarily global.
📊 Result
K clusters with minimal intra-cluster variance. Elbow method helps find optimal k.
K-Means Understanding Quiz
What is the first step in the K-Means algorithm?
1. What is the first step in the K-Means algorithm?
- ☐ A) Assign all data points to the first cluster
- ☐ B) Choose k random points as initial centroids
- ☐ C) Calculate the optimal number of clusters
- ☐ D) Remove outliers from the data
2. What is the elbow method used for?
- ☐ A) To identify outliers
- ☐ B) To improve algorithm speed
- ☐ C) To determine the optimal number of clusters
- ☐ D) To initialize centroids
3. When does the K-Means algorithm converge?
- ☐ A) When centroids no longer move
- ☐ B) After a fixed number of iterations
- ☐ C) When all clusters are the same size
- ☐ D) When data points are evenly distributed
4. What limitation does K-Means have?
- ☐ A) It can only work with two-dimensional data
- ☐ B) It works best with spherical, similarly sized clusters
- ☐ C) It cannot handle outliers
- ☐ D) It requires pre-labeled data
Related Content
Article
Algorithmic Complexity
The lesson that an elegant algorithm beats any supercomputer — provided n is large enough.
Measures of Central Tendency: Where Is the Middle?
Three ways to find the "center" of data — and the entertaining question of which one is being dishonest right now.
The Raw Material: Data Engineering for Machine Learning
Before AI can become smart, the data needs to behave. How that's done.
Distributions: The Shape of Data
The shape of data explained — and why a bell curve is rarer than you think.
Embeddings & Latent Space
The mathematical space where similar words are neighbors — without anyone telling them.
The Machine's Knobs — Parameters vs. Hyperparameters
The fine line between "learned by the machine" and "guessed by you".
Programming vs. Training
How programming changed when people stopped writing every rule themselves.
How Good Is Your Model? Metrics That Actually Matter
Evaluating models without self-deception — metrics that do more than just look good.
Supervised Learning — Learning with a Teacher
Supervised Learning: the ML paradigm where someone diligently labeled things beforehand.
Unsupervised Learning
Learning without an answer key — the more demanding but often more practical variant of machine learning.
Spaces and Directions (Vectors)
Why AI constantly works with arrows in n-dimensional space.
Demo
Perceptron (Neural Networks)
Discover the first artificial neuron - the Big Bang of machine learning from 1957.
Supervised Learning
Join Sharlock Helmes in his cleverest case: learning to distinguish between genuine clues and Moriarty's sophisticated red herrings. Elementary, my dear algorithm!