DWM, Snippets

Implementation of K-Means Algorithm in C++

11 Comments

The K-Means algorithm is one of the most widely used unsupervised machine learning algorithms. It partitions a dataset into K clusters such that each data point belongs to the cluster whose mean (centroid) it is closest to. Unlike KNN, K-Means does not use labelled data — it discovers natural groupings entirely on its own through iteration.

In this post we walk through a well-commented C++ implementation of K-Means that clusters 10 integer values into 2 groups. We cover the algorithm, explain each line of code, trace through the iterative process, and analyse the output in detail.

What is the K-Means Algorithm?

K-Means works by alternating between two steps until the cluster centres stop changing:

  1. Assignment step: Assign each data point to the cluster whose mean it is closest to.
  2. Update step: Recalculate the mean of each cluster based on its current members.

The algorithm converges when the means no longer change between iterations — meaning the clusters have stabilised. In this implementation:

  • K = 2 (two clusters)
  • Distance metric: absolute difference (1D Manhattan distance)
  • Dataset: 10 integers entered by the user
  • Initial means: provided by the user

C++ Program: K-Means Algorithm

#include <iostream>
using namespace std;

int main() {
    int dataIdx, cluster1Count, cluster2Count, loopIdx;

    // data holds the original 10 data points
    int data[10];

    // cluster1 and cluster2 are the two clusters built each iteration
    int cluster1[10];   // cluster 1 (closer to mean1)
    int cluster2[10];   // cluster 2 (closer to mean2)

    // ----------------------------------------------------------------
    // Input: read 10 integer data points
    // ----------------------------------------------------------------
    cout << "\nEnter 10 numbers:\n";
    for (dataIdx = 0; dataIdx < 10; dataIdx++) {
        cin >> data[dataIdx];
    }

    // ----------------------------------------------------------------
    // Input: read the two initial cluster means (centroids)
    // ----------------------------------------------------------------
    int mean1, mean2;
    cout << "\nEnter initial mean 1: ";
    cin  >> mean1;
    cout << "Enter initial mean 2: ";
    cin  >> mean2;

    int oldMean1, oldMean2;   // old means (used to detect convergence)
    int iteration = 0;

    // ================================================================
    // Main K-Means loop: repeats until means stop changing
    // ================================================================
    do {
        iteration++;
        cout << "\n--- Iteration " << iteration << " ---";

        // Save the current means before recalculating
        oldMean1 = mean1;
        oldMean2 = mean2;

        // ------------------------------------------------------------
        // Assignment step: assign each data point to the nearest cluster
        // cluster1Count tracks how many points are in cluster1
        // cluster2Count tracks how many points are in cluster2
        // ------------------------------------------------------------
        cluster1Count = 0;
        cluster2Count = 0;

        for (dataIdx = 0; dataIdx < 10; dataIdx++) {
            // Calculate distance from data[dataIdx] to each mean
            int dist1 = data[dataIdx] - mean1;
            if (dist1 < 0) dist1 = -dist1;   // |data[dataIdx] - mean1|

            int dist2 = data[dataIdx] - mean2;
            if (dist2 < 0) dist2 = -dist2;   // |data[dataIdx] - mean2|

            if (dist1 <= dist2) {
                // Closer to mean1 (or equidistant: goes to cluster1)
                cluster1[cluster1Count] = data[dataIdx];
                cluster1Count++;
            } else {
                // Closer to mean2
                cluster2[cluster2Count] = data[dataIdx];
                cluster2Count++;
            }
        }

        // ------------------------------------------------------------
        // Update step: recalculate the mean of each cluster
        // New mean = sum of cluster members / number of members
        // ------------------------------------------------------------

        // Recalculate mean1 (mean of cluster1)
        int sum = 0;
        for (loopIdx = 0; loopIdx < cluster1Count; loopIdx++) {
            sum += cluster1[loopIdx];
        }
        mean1 = sum / cluster1Count;   // integer division

        // Recalculate mean2 (mean of cluster2)
        sum = 0;
        for (loopIdx = 0; loopIdx < cluster2Count; loopIdx++) {
            sum += cluster2[loopIdx];
        }
        mean2 = sum / cluster2Count;   // integer division

        // ------------------------------------------------------------
        // Print the clusters and their new means for this iteration
        // ------------------------------------------------------------
        cout << "\nCluster 1: ";
        for (loopIdx = 0; loopIdx < cluster1Count; loopIdx++) {
            cout << cluster1[loopIdx] << " ";
        }
        cout << "  (new mean1 = " << mean1 << ")";

        cout << "\nCluster 2: ";
        for (loopIdx = 0; loopIdx < cluster2Count; loopIdx++) {
            cout << cluster2[loopIdx] << " ";
        }
        cout << "  (new mean2 = " << mean2 << ")";

    // ----------------------------------------------------------------
    // Convergence condition: stop when BOTH means are unchanged
    // ----------------------------------------------------------------
    } while (mean1 != oldMean1 || mean2 != oldMean2);
    //              ^^                   ^^
    //   Continue looping if EITHER mean changed.
    //   Stop only when NEITHER has changed (clusters have stabilised).

    cout << "\n\nClusters have converged after " << iteration << " iteration(s).";
    cout << "\nFinal Cluster 1: ";
    for (loopIdx = 0; loopIdx < cluster1Count; loopIdx++) cout << cluster1[loopIdx] << " ";
    cout << "  Mean = " << mean1;
    cout << "\nFinal Cluster 2: ";
    for (loopIdx = 0; loopIdx < cluster2Count; loopIdx++) cout << cluster2[loopIdx] << " ";
    cout << "  Mean = " << mean2 << "\n";

    return 0;
}

How the Code Works — Step by Step

Step 1 — Read Data and Initial Means

The user enters 10 integers (the dataset) and two initial mean values (the starting centroids for the two clusters). The choice of initial means can affect which clusters the algorithm converges to, though for simple 1D integer datasets it usually converges to the same result regardless.

Step 2 — Assignment Step

For each data point data[dataIdx], the program computes the absolute distance to both mean1 and mean2. The point is assigned to whichever cluster’s mean it is closer to. Equidistant points are assigned to cluster 1 (the dist1 <= dist2 condition).

Step 3 — Update Step

After all points have been assigned, the mean of each cluster is recalculated as the integer average of its current members. The old means are saved before this step so that convergence can be detected.

Step 4 — Convergence Check

The loop repeats as long as mean1 != oldMean1 || mean2 != oldMean2 — i.e., as long as at least one mean has changed. When both means are identical to what they were at the start of the iteration, the clusters have stabilised and the algorithm terminates.

Program Output

Enter 10 numbers:
2 4 10 12 3 20 30 11 25 23

Enter initial mean 1: 2
Enter initial mean 2: 16

--- Iteration 1 ---
Cluster 1: 2 4 3   (new mean1 = 3)
Cluster 2: 10 12 20 30 11 25 23   (new mean2 = 18)

--- Iteration 2 ---
Cluster 1: 2 4 10 3   (new mean1 = 4)
Cluster 2: 12 20 30 11 25 23   (new mean2 = 20)

--- Iteration 3 ---
Cluster 1: 2 4 10 3 11   (new mean1 = 6)
Cluster 2: 12 20 30 25 23   (new mean2 = 22)

--- Iteration 4 ---
Cluster 1: 2 4 10 12 3 11   (new mean1 = 7)
Cluster 2: 20 30 25 23   (new mean2 = 24)

--- Iteration 5 ---
Cluster 1: 2 4 10 12 3 11   (new mean1 = 7)
Cluster 2: 20 30 25 23   (new mean2 = 24)

Clusters have converged after 5 iteration(s).
Final Cluster 1: 2 4 10 12 3 11   Mean = 7
Final Cluster 2: 20 30 25 23   Mean = 24

Output Explanation — Iteration Trace

Let’s trace through each iteration with the dataset {2, 4, 10, 12, 3, 20, 30, 11, 25, 23} and initial means mean1=2, mean2=16:

IterationCluster 1New mean1Cluster 2New mean2
12, 4, 3310, 12, 20, 30, 11, 25, 2318
22, 4, 10, 3412, 20, 30, 11, 25, 2320
32, 4, 10, 3, 11612, 20, 30, 25, 2322
42, 4, 10, 12, 3, 11720, 30, 25, 2324
5 (final)2, 4, 10, 12, 3, 11720, 30, 25, 2324

In iteration 5, the means (mean1=7 and mean2=24) are identical to what they were at the end of iteration 4 — neither mean changed. The convergence condition is satisfied and the loop exits.

The final clusters make intuitive sense:

  • Cluster 1: {2, 3, 4, 10, 11, 12} — the smaller values, centred around 7.
  • Cluster 2: {20, 23, 25, 30} — the larger values, centred around 24.

The algorithm correctly discovered the natural split in the data between the low-value group (2–12) and the high-value group (20–30).

Why the Convergence Condition Matters

A common mistake is writing while(mean1!=oldMean1 && mean2!=oldMean2) — the logical AND. This means the loop stops as soon as either mean stabilises, even if the other is still changing. This is a bug: if by some coincidence mean1 stopped changing before mean2, the loop would exit prematurely with incorrect clusters.

The correct condition while(mean1!=oldMean1 || mean2!=oldMean2) uses logical OR, meaning the loop only exits when both means are simultaneously stable. This guarantees full convergence.

Key Concepts Recap

ConceptDetails in This Program
Algorithm typeUnsupervised clustering
Number of clusters (K)2
Distance metricAbsolute difference (1D Manhattan distance)
Mean calculationInteger average of cluster members
Convergence conditionBoth means unchanged after an iteration
Dataset10 integers entered by the user

Conclusion

The K-Means algorithm beautifully demonstrates how unsupervised learning works: starting from arbitrary initial centroids, it iteratively refines cluster assignments and recalculates means until the clusters stabilise. This C++ implementation covers all the essential mechanics — distance computation, cluster assignment, mean recalculation, and convergence detection — in a compact and readable form.

The most important detail to remember is the convergence condition (|| instead of &&), which ensures the algorithm always runs to true convergence rather than stopping early. Understanding this subtle logical difference is key to implementing iterative algorithms correctly.

Also explore the related DWM programs:

11 thoughts on “Implementation of K-Means Algorithm in C++”

  1. Thank you! i’ve been searching for this for a long time.
    I have one question, what is the use of the k-means ? is it important !?

    Reply

    1. It is one of the most widely used machine learning algorithms in use today. There are different variations of it for data of different sizes, formats, etc.

      Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.