Welcome to the fascinating landscape of Unsupervised Learning and Clustering. In this course, we'll explore the popular k-Means clustering algorithm, a simple yet powerful form of clustering. Although clustering might seem technical, if you've ever sorted your clothes into piles based on their colors or types, you've unknowingly performed a form of "clustering" — grouping similar items into different categories or clusters. Intrigued? Let's get started!

Supervised learning is like learning with a teacher. In this type of machine learning, you provide the computer with labeled data, which means the algorithm is given the input data and the correct answers. The aim is to find a model that makes the best predictions based on the given examples.

Unsupervised learning, on the other hand, is like learning on your own. In this type, the algorithm is given data but no specific directions about what it should be looking for. The computer is expected to explore the data and find its own patterns or structures. It is called unsupervised because there are no correct answers and no teacher.

Algorithms for unsupervised learning, like clustering, aim to group objects so that objects in the same group (a cluster) are more similar to each other than to those in other groups.

Consider an example: you have a list of fruits with their corresponding weights and volumes and want to group them into two groups, but you don’t know what the fruits are. You can perform clustering to segment the data into two clusters. Although we don’t know what the fruits are, we could predict that data points in the same cluster are the same type of fruit.

Given data for a new piece of fruit, you could attempt to classify which group it belongs to by seeing which cluster center it is closest to.

This lesson will focus on the widely used k-Means clustering method.

The k-Means clustering algorithm aims to partition n observations into k clusters, where each observation belongs to the cluster with which it shares the most similarity. The steps involved are:

1. Initialization: Random initialization of k centroids.
2. Assignment: Allocation of each data point to the closest centroid.
3. Update: Updating each centroid by computing the mean of all points allocated to its cluster.

We repeat steps 2 and 3 until the centroids cease to change significantly. For now, we will manually set k, the number of clusters.

Now, let's implement the k-Means algorithm in C++. The algorithm will repeatedly assign each data point to the nearest centroid and then update the centroids to be the mean of the points in their clusters until the centroids stabilize.

First, we need a function to compute the mean (center) of a cluster:

// Compute the mean of points in a cluster
Point computeCenter(const vector<Point>& cluster) {
    double x = 0.0, y = 0.0;
    for (const auto& point : cluster) {
        x += point.first;
        y += point.second;
    }
    return {x / cluster.size(), y / cluster.size()};
}

Now, let's put the k-Means algorithm together. Note that we use tuple as the return type, and you can use structured bindings (C++17 and above) to unpack the result:

#include <tuple>

// k-Means clustering algorithm
tuple<vector<vector<Point>>, vector<Point>> kMeans(
    const vector<Point>& data,
    vector<Point> centers,
    int k,
    double tolerance = 1e-4
) {
    vector<vector<Point>> clusters(k);
    while (true) {
        // Reset clusters
        for (auto& cluster : clusters) cluster.clear();

        // Assign points to nearest center
        for (const auto& point : data) {
            int nearest = 0;
            double min_dist = numeric_limits<double>::max();
            for (int i = 0; i < k; ++i) {
                double d = distance(point, centers[i]);
                if (d < min_dist) {
                    min_dist = d;
                    nearest = i;
                }
            }
            clusters[nearest].push_back(point);
        }

        // Update centers
        vector<Point> new_centers;
        for (const auto& cluster : clusters) {
            new_centers.push_back(computeCenter(cluster));
        }

        // Check convergence
        double max_shift = 0.0;
        for (int i = 0; i < k; ++i) {
            double shift = distance(centers[i], new_centers[i]);
            if (shift > max_shift)
                max_shift = shift;
        }
        if (max_shift < tolerance) break;

        centers = new_centers;
    }
    return {clusters, centers};
}

In this function, we repeatedly assign each data point to the nearest centroid, then update each centroid to be the mean of its assigned points. The process repeats until the centroids do not move significantly (as measured by the tolerance parameter).

Now, let's run our k-Means clustering algorithm, print the results, and visualize the clusters and their centers using matplotlibcpp.

int main() {
    vector<Point> data = {
        {2, 3}, {5, 3.4}, {1.3, 1}, {3, 4}, {2, 3.5}, {7, 5}
    };
    int k = 2;
    vector<Point> centers = {data[0], data[3]}; // Initial centers

    auto [clusters, final_centers] = kMeans(data, centers, k);

    // Print the cluster centers
    cout << fixed << setprecision(2);
    for (int i = 0; i < k; ++i) {
        cout << "Cluster" << (i + 1) << " center is : ("
             << final_centers[i].first << ", " << final_centers[i].second << ")\n";
    }

    // Print the clusters
    for (int i = 0; i < k; ++i) {
        cout << "Cluster" << (i + 1) << " points are : [";
        for (size_t j = 0; j < clusters[i].size(); ++j) {
            cout << "(" << clusters[i][j].first << ", " << clusters[i][j].second << ")";
            if (j != clusters[i].size() - 1) cout << ", ";
        }
        cout << "]\n";
    }

    // Plotting
    vector<string> colors = {"r", "g", "b", "y", "c", "m"};
    for (int i = 0; i < k; ++i) {
        vector<double> x, y;
        for (const auto& point : clusters[i]) {
            x.push_back(point.first);
            y.push_back(point.second);
        }
        plt::scatter(x, y, 50.0, {{"color", colors[i % colors.size()]}});
    }

    // Plot centers
    for (const auto& center : final_centers) {
        plt::scatter(vector<double>{center.first}, vector<double>{center.second}, 100.0, {{"marker", "x"}, {"color", "black"}});
    }

    plt::title("Clusters and their centers");
    plt::save("static/images/plot.png");

    return 0;
}

Sample Output:

Cluster1 center is : (2.66, 2.98)
Cluster2 center is : (7.00, 5.00)
Cluster1 points are : [(2, 3), (5, 3.4), (1.3, 1), (3, 4), (2, 3.5)]
Cluster2 points are : [(7, 5)]

This output consists of cluster centers and clusters. Cluster centers, or means, are centroids representing the central point of each cluster. Each point in our dataset is assigned to the cluster closest to it. The code also generates a plot of the clusters and their centers, saved as static/images/plot.png. While versatile, k-Means performs optimally when cluster densities are approximately equal.

Plot:

Congratulations on successfully navigating the core aspects of clustering and implementing the k-Means algorithm in C++! Moving forward, practice exercises are available to help solidify these concepts. I look forward to seeing you in the next lesson!