Clustering Algorithms from Scratch

Coursework implementations of k-means, k-means++ initialization, and bisecting k-means written directly in NumPy. The original Colab attribution remains in each source file.

Explore the implementations

File	What it does
kmeans.py	Random initialization, assignment/update iterations, and silhouette evaluation
kmeansplusplus.py	Distance-weighted centroid initialization followed by k-means iterations
bisectingkmeans.py	Repeatedly splits the cluster with the largest sum of squared errors
kmeanssynthetic (1).py	Generates Gaussian data from observed mean/covariance and evaluates it with a manual silhouette calculation

The repaired entry points validate finite, non-empty 2D data, positive integer iteration limits, and feasible integer cluster counts. They reseed empty clusters with distinct observations, retain those repaired centroids even at close numeric scales, and return labels for the final centroids. Bisecting k-means tracks row indices so duplicate points keep their membership. Initialization uses seed 42 reproducibly.

Setup and data

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

The repository includes CA2data (2).zip and an assignment document. Extract only the required dataset member from the archive:

unzip -p "CA2data (2).zip" dataset > dataset

Every loader treats the first token as a label and the remaining tokens as numeric features; each row needs at least two features.

Run an experiment

After preparing the expected data file, run one script from the repository directory:

python kmeans.py

Or choose another implementation:

python kmeansplusplus.py
python bisectingkmeans.py
python "kmeanssynthetic (1).py"

The scripts write distinct plot files named silhouette_scores_kmeans.png, silhouette_scores_kmeansplusplus.png, silhouette_scores_bisecting.png, and silhouette_scores_synthetic.png.

Run the regression suite headlessly:

MPLCONFIGDIR=/tmp/matplotlib MPLBACKEND=Agg python -m pytest -p no:cacheprovider --rootdir=. tests

Automated checks

GitHub Actions runs the regression suite with Python 3.11 and a headless Matplotlib backend on pushes and pull requests. The tests cover input validation, deterministic edge cases, command-line failure status, and loading and clustering a subset of the bundled dataset. They do not establish clustering quality or reproduce every full silhouette experiment.

Scope and limitations

• These remain educational NumPy implementations rather than optimized production clustering code.
• The synthetic experiment scales the observed covariance by 0.5. Its manual silhouette calculation follows the standard definition, excluding each point's self-distance and assigning singleton samples a score of zero.
• The manual score constructs a full pairwise distance matrix, which becomes expensive for large datasets.
• Silhouette calculations stop before the sample count and distinct-point count because the score is undefined outside that range.
• No benchmark score is claimed here.