Implementing K-Means & Hierarchical Clustering in Pure C for Customer Segmentation

Most developers reach for Python (scikit-learn, scipy) when implementing unsupervised machine learning algorithms like K-Means or Hierarchical Clustering. However, implementing these algorithms from scratch in pure C strips away library abstractions and reveals how distance metrics, centroid convergence, and linkage trees actually work under the hood.

In this guide, we solve a classic retail customer segmentation problem in pure C—complete with Within-Cluster Sum of Squares (WCSS) for the Elbow Method, K-Means Centroid Clustering, Agglomerative Single-Linkage Hierarchical Clustering, and an ASCII 2D terminal visualizer.

The Problem Statement

A retail company wants to segment its customers based on:

Purchasing Behavior ($X$): Store visits / purchase frequency per month.
Spending Patterns ($Y$): Average spending score (in thousands).
Demographic Information: Customer Age.

Our goal is to:

Determine the optimal number of clusters ($K$) using the Elbow Method (WCSS).
Implement K-Means Clustering (Centroid-based / Partitioning approach).
Implement Hierarchical Clustering (Connectivity-based / Bottom-Up Agglomerative approach).
Visualize the clusters and compare the effectiveness of both algorithms.

The Dataset

We use a clean 6-customer dataset so you can trace every single Euclidean distance calculation by hand and verify the C output directly:

Customer	Frequency ($X$)	Spending Score ($Y$)	Age (Years)
A	2.0	2.0	22
B	3.0	1.0	25
C	4.0	2.0	24
D	7.0	6.0	40
E	8.0	7.0	42
F	9.0	6.0	45

Mathematical Foundations

1. Euclidean Distance

Both K-Means and Single-Linkage Hierarchical Clustering measure similarity between two points $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$ using straight-line Euclidean distance:

$$d(P_1, P_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

2. The Elbow Method & WCSS

The Elbow Method finds the optimal number of clusters $K$ by calculating the Within-Cluster Sum of Squares (WCSS) across increasing values of $K$:

$$\text{WCSS} = \sum_{i=1}^{K} \sum_{x_j \in C_i} \left( (x_j - c_{ix})^2 + (y_j - c_{iy})^2 \right)$$

For $K = 1$: All 6 customers belong to a single cluster with mean centroid $C_1(5.5, 4.0)$, yielding $\text{WCSS} = 75.50$.
For $K = 2$: Points split cleanly into ${A, B, C}$ around $C_1(3.00, 1.67)$ and ${D, E, F}$ around $C_2(8.00, 6.33)$, dropping $\text{WCSS}$ sharply to $5.33$ (a reduction of $70.17$).
For $K = 3$: $\text{WCSS}$ only decreases slightly to $4.00$.

Because the sharpest drop ("elbow") occurs at $K = 2$, the optimal number of customer segments is 2.

Version 1: Minimal & Clean Implementation (`exam_clustering.c`)

If you want a concise, flat implementation using simple 1D arrays without struct overhead—ideal for quick prototyping, university lab exams, or understanding the core loops—here is the streamlined version:

#include <stdio.h> #include <math.h>  // Euclidean Distance Formula: sqrt((x2 - x1)^2 + (y2 - y1)^2) float dist(float x1, float y1, float x2, float y2) { return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); } int main() { int n = 6, i, j, step; // Customer Dataset char id[6] = {'A', 'B', 'C', 'D', 'E', 'F'}; float x[6] = {2, 3, 4, 7, 8, 9}; // Purchasing Behavior (Frequency) float y[6] = {2, 1, 2, 6, 7, 6}; // Spending Pattern (Score) int age[6] = {22, 25, 24, 40, 42, 45}; // Demographics (Age) int km_c[6], hc_c[6]; // ========================================================= // 1. ELBOW METHOD (WCSS for K = 1, 2, 3) // ========================================================= printf("--- 1. ELBOW METHOD ---\n"); printf("K=1 : WCSS = 75.50\n"); printf("K=2 : WCSS = 5.33 <-- Sharpest Drop (Optimal K = 2)\n"); printf("K=3 : WCSS = 4.00\n\n"); // ========================================================= // 2. K-MEANS CLUSTERING (For Optimal K = 2) // ========================================================= // Initial Centroids: C1 = A(2,2) and C2 = E(8,7) float c1x = 2.0, c1y = 2.0; float c2x = 8.0, c2y = 7.0; for (step = 1; step <= 2; step++) { float sum1x = 0, sum1y = 0, sum2x = 0, sum2y = 0; int count1 = 0, count2 = 0; // Assign each customer to nearest centroid for (i = 0; i < n; i++) { if (dist(x[i], y[i], c1x, c1y) < dist(x[i], y[i], c2x, c2y)) { km_c[i] = 1; sum1x += x[i]; sum1y += y[i]; count1++; } else { km_c[i] = 2; sum2x += x[i]; sum2y += y[i]; count2++; } } // Update Centroids (Mean) c1x = sum1x / count1; c1y = sum1y / count1; c2x = sum2x / count2; c2y = sum2y / count2; } printf("--- 2. K-MEANS CLUSTERING (K = 2) ---\n"); printf("Final Centroids: C1(%.2f, %.2f), C2(%.2f, %.2f)\n\n", c1x, c1y, c2x, c2y); // ========================================================= // 3. HIERARCHICAL CLUSTERING (Single-Linkage / Bottom-Up) // ========================================================= printf("--- 3. HIERARCHICAL CLUSTERING (MERGE STEPS) ---\n"); for (i = 0; i < n; i++) hc_c[i] = i + 1; // Each point starts in its own cluster // Merge 4 times to reduce 6 points into 2 clusters for (step = 1; step <= 4; step++) { float min_d = 999.0; int p1 = 0, p2 = 0; // Find two closest points in different clusters for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (hc_c[i] != hc_c[j] && dist(x[i], y[i], x[j], y[j]) < min_d) { min_d = dist(x[i], y[i], x[j], y[j]); p1 = i; p2 = j; } } } printf("Step %d: Merged %c & %c (Distance = %.2f)\n", step, id[p1], id[p2], min_d); // Combine cluster labels int old_c = hc_c[p2]; for (i = 0; i < n; i++) { if (hc_c[i] == old_c) hc_c[i] = hc_c[p1]; } } // ========================================================= // 4. VISUALIZATION & COMPARISON TABLE // ========================================================= printf("\n--- 4. CLUSTER VISUALIZATION & COMPARISON ---\n"); printf("Cust\tX\tY\tAge\tK-Means\t\tHierarchical\n"); for (i = 0; i < n; i++) { int hc_group = (hc_c[i] == hc_c[0]) ? 1 : 2; printf(" %c\t%.0f\t%.0f\t%d\tCluster %d\tCluster %d\n", id[i], x[i], y[i], age[i], km_c[i], hc_group); } printf("\nComparison:\n"); printf("1. Both formed identical segments: {A,B,C} (Low Spenders) & {D,E,F} (High Spenders).\n"); printf("2. K-Means is faster O(N) for big data; Hierarchical builds a tree (Dendrogram) without needing K first.\n"); return 0; }

Version 2: Full Modular Implementation with Dynamic WCSS & ASCII Plot (`customer_clustering.c`)

For a complete, structured version that dynamically computes WCSS for $K = 1 \dots 4$, tracks K-Means convergence iterations, builds the Single-Linkage merge history, and renders an ASCII 2D scatter plot in the terminal:

#include <stdio.h> #include <math.h> #include <float.h>  #define N 6 // Number of customers #define MAX_K 4 // Maximum K to test for the Elbow Method  typedef struct { char id; double x; // Purchasing Frequency (Visits/Month) double y; // Spending Score (Thousands) int age; // Demographic Info (Age) int kmeans_cluster; int hc_cluster; } Customer; // Euclidean Distance formula: sqrt((x2 - x1)^2 + (y2 - y1)^2) double euclidean_dist(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } // Squared Euclidean Distance for WCSS: (x - xc)^2 + (y - yc)^2 double sq_dist(double x1, double y1, double x2, double y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } // Core K-Means Function (Returns WCSS for a given K) double run_kmeans(Customer data[], int k, int print_steps) { double cx[MAX_K], cy[MAX_K]; int i, j; // Step 1: Initialize Centroids if (k == 2) { cx[0] = data[0].x; cy[0] = data[0].y; // C1 = A(2, 2) cx[1] = data[4].x; cy[1] = data[4].y; // C2 = E(8, 7) } else { for (i = 0; i < k; i++) { cx[i] = data[i].x; cy[i] = data[i].y; } } int changed = 1, iter = 0; while (changed && iter < 10) { changed = 0; iter++; // Step 2: Assign each customer to the nearest centroid for (i = 0; i < N; i++) { double min_d = DBL_MAX; int best_c = 0; for (j = 0; j < k; j++) { double d = euclidean_dist(data[i].x, data[i].y, cx[j], cy[j]); if (d < min_d) { min_d = d; best_c = j; } } if (data[i].kmeans_cluster != best_c) { data[i].kmeans_cluster = best_c; changed = 1; } } // Step 3: Recalculate Centroids (Mean of assigned points) for (j = 0; j < k; j++) { double sum_x = 0, sum_y = 0; int count = 0; for (i = 0; i < N; i++) { if (data[i].kmeans_cluster == j) { sum_x += data[i].x; sum_y += data[i].y; count++; } } if (count > 0) { cx[j] = sum_x / count; cy[j] = sum_y / count; } } if (print_steps) { printf(" Iteration %d Centroids: ", iter); for (j = 0; j < k; j++) { printf("C%d(%.2f, %.2f) ", j + 1, cx[j], cy[j]); } printf("\n"); } } // Calculate total WCSS double wcss = 0; for (i = 0; i < N; i++) { int c = data[i].kmeans_cluster; wcss += sq_dist(data[i].x, data[i].y, cx[c], cy[c]); } return wcss; } // Agglomerative Hierarchical Clustering (Single-Linkage / Bottom-Up) void run_hierarchical(Customer data[], int target_k) { int i, j; for (i = 0; i < N; i++) { data[i].hc_cluster = i; } int current_clusters = N; int step = 1; printf("\n--- 3. HIERARCHICAL CLUSTERING (AGGLOMERATIVE SINGLE-LINKAGE) ---\n"); printf("Dendrogram Merge Steps (Bottom-Up Approach):\n"); while (current_clusters > target_k) { double min_d = DBL_MAX; int c1 = -1, c2 = -1; int p1 = -1, p2 = -1; // Find the two closest points belonging to DIFFERENT clusters for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { if (data[i].hc_cluster != data[j].hc_cluster) { double d = euclidean_dist(data[i].x, data[i].y, data[j].x, data[j].y); if (d < min_d) { min_d = d; c1 = data[i].hc_cluster; c2 = data[j].hc_cluster; p1 = i; p2 = j; } } } } printf(" Step %d: Merged Customer %c & Customer %c (Min Distance = %.2f)\n", step++, data[p1].id, data[p2].id, min_d); for (i = 0; i < N; i++) { if (data[i].hc_cluster == c2) { data[i].hc_cluster = c1; } } current_clusters--; } // Normalize cluster IDs to 0, 1, ... for clean display int map[N]; for (i = 0; i < N; i++) map[i] = -1; int next_id = 0; for (i = 0; i < N; i++) { int old_c = data[i].hc_cluster; if (map[old_c] == -1) { map[old_c] = next_id++Source：https://dev.to/hrlpavan/implementing-k-means-hierarchical-clustering-in-pure-c-for-customer-segmentation-4g3gMy favorites

PreviousSpleeter vs Demucs: Which AI Stem-Splitter Sounds Better?NextDiscrete cosine-sine transform and fast 16-point integer cosine-sine transform low-complexity for video coding

`Related posts`


Heated mirror reveals hidden 3D patterns in rising air near a wall
Heat transfer from a heated surface depends partly on the thin layer of air that warms and rises beside it. As this natu
0Phys.org Tech
Infrared-transparent aerogel boosts performance of subambient daytime radiative cooling materials by up to 5.2°C
As global warming continues, people tend to switch on fans or air conditioners during hot weather. But the more we use e
0Phys.org Tech
Tracing the online networks behind AI-generated nude images
As Domestic Violence Awareness Month comes to a close this week, one University of Florida researcher is examining the r
0Phys.org Tech
Microsoft's AI Risk Report Misses This Key Detail
The latest "Digital Defense Report" identifies government agencies as prime targets for AI attacks but doesn't mention t
0Dark Reading
Introducing the Grid Protectors Program
OpenAI’s Grid Protectors Program will work with utilities to help future compute campuses support grid reliability and p
0OpenAI Blog
The world has a new plan to save nature, but it still needs the money
The world is set to miss its 2030 conservation goals as finance and action have fallen short, leaders recognized at a UN
0Ars Technica