Machine Learning › Unsupervised Learning › Day 183

Hands-on lab — Day 183: Clustering with k-means

← Back to the Day 183 lesson
Open the hands-on files on GitHub — clone or download them from the public labs repository
Local path in your clone: labs/sections/machine-learning/day-183-clustering-with-k-means/

Commands

Setup

pip install -r requirements/requirements.txt

Run

python3 examples/clustering_with_k_means_lib.py

Test

./tests/run_tests.sh

File tree

examples/clustering_with_k_means_lib.py
examples/test_clustering_with_k_means_lib.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/starter-run.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/clustering_with_k_means_lib.py
starter/test_clustering_with_k_means_lib.py
tests/run_tests.sh
tests/test_clustering_with_k_means_lib.py
troubleshooting.md

Lab README

Lab: Day 183 -- Clustering with k-means

Lesson

Day number: 183 of 365. Course: Course04-SS03 (Beyond Supervised Learning). Topic: K-Means Clustering, Lloyd's Coordinate Descent, and k-means++ Seeding.

Purpose

Build a complete, pure NumPy implementation of the K-Means clustering algorithm from scratch. You will implement k-means++ distance-squared probability initialization, the alternating expectation assignment step, the maximization centroid recalculation step, and compute the final WCSS inertia.

Learning objectives

Implement k-means++ distance-squared probability seeding.
Implement Lloyd's alternating expectation-maximization coordinate descent.
Calculate Within-Cluster Sum of Squares (WCSS / Inertia).
Assign unseen test points to their nearest cluster centroid in Euclidean metric space.

Prerequisites

Linear algebra: Matrix operations, Euclidean norm calculations.
Probability: Discrete probability sampling with np.random.choice.
Python 3.11+ with NumPy.

Supported operating systems

macOS (Apple Silicon / Intel)
Linux (Ubuntu, Debian, Fedora, Arch)
Windows 11 / WSL2

Hardware requirements

1+ CPU cores.
512 MB RAM.
50 MB disk space.

Required software

Python 3.11 or newer.
pip package manager.
virtualenv or venv module.

Free and open-source options

All tools used in this lab (Python, NumPy, pytest, scikit-learn) are free and open-source under BSD/MIT licenses.

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

starter/clustering_with_k_means_lib.py: Student scaffold file.
examples/clustering_with_k_means_lib.py: Complete reference implementation.
tests/test_clustering_with_k_means_lib.py: Pytest automated validation suite.
expected-output/: Verified output logs and baseline values.

How to run

Execute the reference demonstration script:

python3 examples/clustering_with_k_means_lib.py

What the commands do

Initializes 3 Gaussian blobs with 300 total points in 2D space.
Runs KMeansFromScratch with k-means++ initialization until centroid convergence.
Prints the final converged WCSS Inertia.

Expected output

K-Means converged with Inertia: 384.22

Validation steps

Check that _init_centroids selects well-dispersed points using D^2 probability.
Verify that fit() iterates until centroid movement is less than tol.
Verify that predict() returns integer cluster IDs [0, K-1].
Ensure all test cases pass.

Tests

Run the test runner script:

./tests/run_tests.sh

Cleanup

find . -type d -name "__pycache__" -exec rm -rf {} +
find . -type d -name ".pytest_cache" -exec rm -rf {} +

Troubleshooting

Empty Cluster Error: If a cluster has 0 assigned points during update, reassign its centroid to a randomly chosen sample point.
Slow Convergence: Ensure tolerance tol=1e-4 is checked against the Euclidean norm of centroid shifts.

Security notes

All computations run strictly on local CPU memory. No telemetry or network connections are initiated.

Extension exercises

Implement Mini-Batch K-Means using random sub-samples of size 64.
Implement Silhouette Score calculation in pure NumPy.

Lesson title: Clustering with k-means
Day number: 183 of 365
Lesson article: https://ai-roadmap-365.github.io/day-183-clustering-with-k-means
Lab files: everything you need is in this directory — follow “How to run” below.
Browse the course locally: from the repository root, this lab also appears in the course website at /labs/day-183-clustering-with-k-means when the site is running.

Expected output

FIELDS.md

# Expected Output Fields: Day 183

- `Inertia`: Float value representing Within-Cluster Sum of Squares (WCSS).
- `Cluster Centers`: NumPy float matrix of shape (K, D).
- `Labels`: NumPy integer vector of length N with values in [0, K-1].

examples-run.txt

K-Means converged with Inertia: 384.22

measured-values.txt

Inertia: 384.22
Cluster Centers Shape: (3, 2)
Number of Samples: 300

starter-run.txt

Starter scaffold executed. Ready for student implementation.

test-run.txt

============================= test session starts ==============================
collected 2 items

tests/test_clustering_with_k_means_lib.py::test_kmeans_convergence_and_inertia PASSED [ 50%]
tests/test_clustering_with_k_means_lib.py::test_kmeans_prediction_accuracy PASSED [100%]

============================== 2 passed in 0.08s ===============================

Source files

examples/clustering_with_k_means_lib.py (2855 bytes)

import numpy as np

class KMeansFromScratch:
    def __init__(self, n_clusters=3, max_iter=300, tol=1e-4, init='k-means++', random_state=42):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.tol = tol
        self.init = init
        self.random_state = random_state
        self.cluster_centers_ = None
        self.inertia_ = None

    def _init_centroids(self, X, rng):
        n_samples, n_features = X.shape
        if self.init == 'random':
            indices = rng.choice(n_samples, size=self.n_clusters, replace=False)
            return X[indices].copy()

        centers = np.empty((self.n_clusters, n_features))
        first_idx = rng.integers(0, n_samples)
        centers[0] = X[first_idx]

        for k in range(1, self.n_clusters):
            dists = np.min(np.linalg.norm(X[:, np.newaxis, :] - centers[:k, np.newaxis, :], axis=2)**2, axis=0)
            probs = dists / np.sum(dists)
            next_idx = rng.choice(n_samples, p=probs)
            centers[k] = X[next_idx]

        return centers

    def fit(self, X):
        rng = np.random.default_rng(self.random_state)
        self.cluster_centers_ = self._init_centroids(X, rng)

        for iteration in range(self.max_iter):
            dists = np.linalg.norm(X[:, np.newaxis, :] - self.cluster_centers_[np.newaxis, :, :], axis=2)
            labels = np.argmin(dists, axis=1)

            new_centers = np.zeros_like(self.cluster_centers_)
            for k in range(self.n_clusters):
                mask = labels == k
                if np.sum(mask) > 0:
                    new_centers[k] = np.mean(X[mask], axis=0)
                else:
                    new_centers[k] = X[rng.integers(0, len(X))]

            shift = np.linalg.norm(self.cluster_centers_ - new_centers)
            self.cluster_centers_ = new_centers
            if shift < self.tol:
                break

        dists = np.linalg.norm(X[:, np.newaxis, :] - self.cluster_centers_[np.newaxis, :, :], axis=2)
        labels = np.argmin(dists, axis=1)
        min_dists = np.min(dists, axis=1)
        self.inertia_ = float(np.sum(min_dists**2))
        return self

    def predict(self, X):
        dists = np.linalg.norm(X[:, np.newaxis, :] - self.cluster_centers_[np.newaxis, :, :], axis=2)
        return np.argmin(dists, axis=1)

def run_kmeans_demo():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-4.0, -4.0], scale=0.8, size=(100, 2))
    c2 = np.random.normal(loc=[4.0, 4.0], scale=0.8, size=(100, 2))
    c3 = np.random.normal(loc=[0.0, 5.0], scale=0.8, size=(100, 2))
    X = np.vstack([c1, c2, c3])

    kmeans = KMeansFromScratch(n_clusters=3, random_state=42).fit(X)
    labels = kmeans.predict(X)
    print(f"K-Means converged with Inertia: {kmeans.inertia_:.2f}")
    return kmeans, labels

if __name__ == "__main__":
    run_kmeans_demo()

examples/test_clustering_with_k_means_lib.py (946 bytes)

import pytest
import numpy as np
from examples.clustering_with_k_means_lib import KMeansFromScratch

def test_kmeans_convergence_and_inertia():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-5.0, 0.0], scale=0.5, size=(50, 2))
    c2 = np.random.normal(loc=[5.0, 0.0], scale=0.5, size=(50, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    assert kmeans.cluster_centers_.shape == (2, 2)
    assert kmeans.inertia_ > 0
    assert kmeans.inertia_ < 100.0

def test_kmeans_prediction_accuracy():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-10.0, -10.0], scale=0.2, size=(30, 2))
    c2 = np.random.normal(loc=[10.0, 10.0], scale=0.2, size=(30, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    p1 = kmeans.predict(np.array([[-10.0, -10.0]]))
    p2 = kmeans.predict(np.array([[10.0, 10.0]]))
    assert p1[0] != p2[0]

metadata.yml (436 bytes)

lesson_id: D183
day: 183
kind: lab
languages:
  - python
setup_commands:
  - 'pip install -r requirements/requirements.txt'
run_commands:
  - 'python3 examples/clustering_with_k_means_lib.py'
test_commands:
  - './tests/run_tests.sh'
cleanup_commands:
  - 'find . -type d -name "__pycache__" -exec rm -rf {} +'
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-29'
executed_on: 'macos-arm64'

requirements/requirements.txt (62 bytes)

numpy>=1.26.0
scikit-learn>=1.4.0
pytest>=8.0.0
scipy>=1.12.0

starter/clustering_with_k_means_lib.py (594 bytes)

import numpy as np

class KMeansFromScratch:
    def __init__(self, n_clusters=3, max_iter=300, tol=1e-4, init='k-means++', random_state=42):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.tol = tol
        self.init = init
        self.random_state = random_state
        self.cluster_centers_ = None
        self.inertia_ = None

    def fit(self, X):
        # TODO: Implement k-means++ initialization, Lloyd assignment and update steps
        pass

    def predict(self, X):
        # TODO: Return index of closest centroid for each sample
        pass

starter/test_clustering_with_k_means_lib.py (946 bytes)

import pytest
import numpy as np
from examples.clustering_with_k_means_lib import KMeansFromScratch

def test_kmeans_convergence_and_inertia():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-5.0, 0.0], scale=0.5, size=(50, 2))
    c2 = np.random.normal(loc=[5.0, 0.0], scale=0.5, size=(50, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    assert kmeans.cluster_centers_.shape == (2, 2)
    assert kmeans.inertia_ > 0
    assert kmeans.inertia_ < 100.0

def test_kmeans_prediction_accuracy():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-10.0, -10.0], scale=0.2, size=(30, 2))
    c2 = np.random.normal(loc=[10.0, 10.0], scale=0.2, size=(30, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    p1 = kmeans.predict(np.array([[-10.0, -10.0]]))
    p2 = kmeans.predict(np.array([[10.0, 10.0]]))
    assert p1[0] != p2[0]

tests/run_tests.sh (227 bytes)

#!/usr/bin/env bash
set -euo pipefail
echo "========================================"
echo "Running Day 183 Lab Test Suite"
echo "========================================"
pytest tests/ -v
echo "All tests passed successfully."

tests/test_clustering_with_k_means_lib.py (946 bytes)

import pytest
import numpy as np
from examples.clustering_with_k_means_lib import KMeansFromScratch

def test_kmeans_convergence_and_inertia():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-5.0, 0.0], scale=0.5, size=(50, 2))
    c2 = np.random.normal(loc=[5.0, 0.0], scale=0.5, size=(50, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    assert kmeans.cluster_centers_.shape == (2, 2)
    assert kmeans.inertia_ > 0
    assert kmeans.inertia_ < 100.0

def test_kmeans_prediction_accuracy():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-10.0, -10.0], scale=0.2, size=(30, 2))
    c2 = np.random.normal(loc=[10.0, 10.0], scale=0.2, size=(30, 2))
    X = np.vstack([c1, c2])

    kmeans = KMeansFromScratch(n_clusters=2, random_state=42).fit(X)
    p1 = kmeans.predict(np.array([[-10.0, -10.0]]))
    p2 = kmeans.predict(np.array([[10.0, 10.0]]))
    assert p1[0] != p2[0]

Troubleshooting

Troubleshooting: Day 183 - Clustering with k-means

Common Issues

Centroids Diverging / NaN Values:
- Cause: A cluster lost all assigned samples during the E-step, causing division by zero in mean calculation.
- Solution: In the maximization step, check if np.sum(mask) > 0: before taking np.mean. If zero, reset the centroid to a random point.

Security notes

Security & Privacy: Day 183 - Clustering with k-means

Security Guidance

All clustering calculations execute locally in user space without third-party network egress.

Hands-on lab — Day 183: Clustering with k-means

Commands

Setup

Run

Test

File tree

Lab README

Lab: Day 183 -- Clustering with k-means

Lesson

Purpose

Learning objectives

Prerequisites

Supported operating systems

Hardware requirements

Required software

Free and open-source options

Installation

File structure

How to run

What the commands do

Expected output

Validation steps

Tests

Cleanup

Troubleshooting

Security notes

Extension exercises

Navigation

Expected output

FIELDS.md

examples-run.txt

measured-values.txt

starter-run.txt

test-run.txt

Source files

Troubleshooting

Troubleshooting: Day 183 - Clustering with k-means

Common Issues

Security notes

Security & Privacy: Day 183 - Clustering with k-means

Security Guidance