K-means Clustering Path - Python Machine Learning

📚 What You'll Learn

By the end of this lesson, you will be able to:

Describe the K-means objective — minimizing the within-cluster sum of squares (inertia)
Walk through Lloyd's algorithm: the repeated "assign points, then move centroids" loop
Implement K-means from scratch in NumPy, including initialization and a convergence check
Use scikit-learn's KMeans and interpret labels_, cluster_centers_, and inertia_
Recognize K-means' assumptions and limitations (spherical, similar-sized clusters; sensitivity to initialization)

⏱️ Estimated Time: 45–60 minutes

🎯 Project: Implement K-means from scratch and confirm it matches scikit-learn's KMeans on the same dataset.

Discover Hidden Patterns in Your Data! 🎯

K-means clustering is one of the most popular unsupervised learning algorithms, used to automatically group similar data points without labeled examples. From customer segmentation to image compression, K-means helps uncover natural groupings in data. Master this fundamental algorithm including initialization strategies, optimal K selection, and advanced variants.

K-means Algorithm Overview

graph TD A[K-means Clustering] --> B[Algorithm Steps] A --> C[Key Concepts] A --> D[Applications] B --> E[1. Initialize K centroids] B --> F[2. Assign points to nearest centroid] B --> G[3. Update centroids] B --> H[4. Repeat until convergence] C --> I[Centroids] C --> J[Inertia/SSE] C --> K[Euclidean Distance] C --> L[Convergence] D --> M[Customer Segmentation] D --> N[Image Compression] D --> O[Document Clustering] D --> P[Anomaly Detection] style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#bbf,stroke:#333,stroke-width:2px style C fill:#fbf,stroke:#333,stroke-width:2px style D fill:#bfb,stroke:#333,stroke-width:2px

K-means Implementation from Scratch

Understanding the Algorithm

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import make_blobs, make_circles, make_moons
from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score, silhouette_samples, calinski_harabasz_score
from sklearn.metrics import davies_bouldin_score, adjusted_rand_score, adjusted_mutual_info_score
import warnings
warnings.filterwarnings('ignore')

# Set style
plt.style.use('seaborn-v0_8-darkgrid')
sns.set_palette("husl")

# Generate sample data
np.random.seed(42)
X, y_true = make_blobs(n_samples=300, centers=4, n_features=2,
                       center_box=(-10.0, 10.0), cluster_std=1.5,
                       random_state=42)

class KMeansFromScratch:
    """K-means clustering implementation from scratch"""
    
    def __init__(self, n_clusters=3, max_iters=100, random_state=None):
        self.n_clusters = n_clusters
        self.max_iters = max_iters
        self.random_state = random_state
        self.centroids = None
        self.labels = None
        self.inertia_ = None
        self.n_iter_ = 0
        self.history = {'centroids': [], 'labels': [], 'inertia': []}
        
    def euclidean_distance(self, X, centroids):
        """Calculate Euclidean distance between points and centroids"""
        distances = np.zeros((X.shape[0], len(centroids)))
        for k, centroid in enumerate(centroids):
            distances[:, k] = np.linalg.norm(X - centroid, axis=1)
        return distances
    
    def initialize_centroids(self, X, method='random'):
        """Initialize centroids using different methods"""
        np.random.seed(self.random_state)
        n_samples = X.shape[0]
        
        if method == 'random':
            # Random initialization
            idx = np.random.choice(n_samples, self.n_clusters, replace=False)
            centroids = X[idx]
            
        elif method == 'kmeans++':
            # K-means++ initialization
            centroids = []
            
            # Choose first centroid randomly
            first_idx = np.random.randint(n_samples)
            centroids.append(X[first_idx])
            
            for _ in range(1, self.n_clusters):
                # Calculate distances to nearest centroid
                distances = np.array([min([np.linalg.norm(x - c)**2 for c in centroids]) 
                                     for x in X])
                
                # Choose next centroid with probability proportional to squared distance
                probabilities = distances / distances.sum()
                cumprobs = probabilities.cumsum()
                r = np.random.rand()
                
                for j, p in enumerate(cumprobs):
                    if r < p:
                        centroids.append(X[j])
                        break
            
            centroids = np.array(centroids)
            
        return centroids
    
    def fit(self, X, init_method='kmeans++'):
        """Fit K-means clustering"""
        # Initialize centroids
        self.centroids = self.initialize_centroids(X, method=init_method)
        
        for iteration in range(self.max_iters):
            # Store history
            self.history['centroids'].append(self.centroids.copy())
            
            # Assign clusters
            distances = self.euclidean_distance(X, self.centroids)
            self.labels = np.argmin(distances, axis=1)
            self.history['labels'].append(self.labels.copy())
            
            # Calculate inertia
            self.inertia_ = 0
            for k in range(self.n_clusters):
                cluster_points = X[self.labels == k]
                if len(cluster_points) > 0:
                    self.inertia_ += np.sum((cluster_points - self.centroids[k])**2)
            self.history['inertia'].append(self.inertia_)
            
            # Update centroids
            new_centroids = np.zeros((self.n_clusters, X.shape[1]))
            for k in range(self.n_clusters):
                cluster_points = X[self.labels == k]
                if len(cluster_points) > 0:
                    new_centroids[k] = np.mean(cluster_points, axis=0)
            
            # Check convergence
            if np.allclose(self.centroids, new_centroids):
                self.n_iter_ = iteration + 1
                break
            
            self.centroids = new_centroids
        
        return self
    
    def predict(self, X):
        """Predict cluster labels for new data"""
        distances = self.euclidean_distance(X, self.centroids)
        return np.argmin(distances, axis=1)

# Implement K-means from scratch
print("="*60)
print("K-MEANS FROM SCRATCH")
print("="*60)

kmeans_scratch = KMeansFromScratch(n_clusters=4, max_iters=100, random_state=42)
kmeans_scratch.fit(X, init_method='kmeans++')

print(f"\nConverged in {kmeans_scratch.n_iter_} iterations")
print(f"Final inertia: {kmeans_scratch.inertia_:.2f}")
print(f"Cluster centers:\n{kmeans_scratch.centroids}")

# Compare with scikit-learn
kmeans_sklearn = KMeans(n_clusters=4, random_state=42, n_init=10)
kmeans_sklearn.fit(X)

print(f"\nScikit-learn inertia: {kmeans_sklearn.inertia_:.2f}")
print(f"ARI (scratch vs sklearn): {adjusted_rand_score(kmeans_scratch.labels, kmeans_sklearn.labels_):.3f}")

Key Takeaways

🎯 K-means partitions data into K spherical clusters
📏 Always scale features before clustering
🎲 Use k-means++ for better initialization
📊 Elbow method and silhouette score help choose K
⚡ Mini-batch K-means for large datasets
🔍 Sensitive to outliers - preprocess accordingly
🔄 Multiple runs with different seeds improve stability
📈 Monitor inertia to check convergence
🎨 Works well for image compression and segmentation
⚠️ Assumes spherical clusters of similar size

Further Resources

📓 Learning Journal

Keep a learning journal — digital or physical. After this lesson, take a few minutes to write down:

Key concepts you learned
Techniques that clicked for you
Questions or confusion points to revisit
Ideas you want to try
Your progress and feelings about learning this

✍️ This lesson's prompt: K-means alternates between two simple steps — assign points, then move centroids — yet it uncovers real structure. Where else have you seen a simple repeated rule produce surprisingly complex behavior?

📝 Lesson Summary

🎓 Key Takeaways

K-means partitions data into k clusters by minimizing the total squared distance from points to their assigned centroid.
It alternates two steps until convergence: assign each point to the nearest centroid, then recompute each centroid as the mean of its points.
Results depend on initialization and the chosen k; multiple restarts (n_init) and k-means++ improve reliability.
K-means assumes roughly spherical, similarly sized clusters and can struggle with other shapes.

🎉 What You've Accomplished

You understand K-means from the inside out — you can implement its core loop yourself and use the library version with confidence, knowing exactly what happens under the hood.

❓ Common Questions at This Stage

Why does K-means sometimes give different results on the same data?

The initial centroid positions are partly random, and the algorithm converges to a local optimum. Running it several times with different seeds (n_init) and keeping the lowest-inertia result mitigates this; k-means++ initialization also helps.

What is inertia?

Inertia is the sum of squared distances from each point to its assigned centroid — the quantity K-means minimizes. Lower is tighter, but it always decreases as k grows, so it can't alone tell you the best k.

Does K-means guarantee the best possible clustering?

No. It finds a local optimum, not the global one. That's exactly why initialization strategy and multiple restarts matter.

🔭 Looking Ahead

Now that you know how K-means works, the next questions are practical: how to choose the number of clusters and how to make the algorithm faster and more robust.

✅ Before the Next Lesson

Run your from-scratch K-means and scikit-learn's KMeans on make_blobs data and compare the centroids.
Change the initialization and number of restarts and watch how the final inertia varies.
Write your Learning Journal entry for this lesson

🌟 Encouragement for the Journey

You just built a real machine-learning algorithm from nothing but arithmetic and loops. That's a milestone — the "magic" of unsupervised learning is now something you can write yourself.