K-means Clustering: A Study in Iterative Optimization

This repository provides a Python-based implementation and visualization of the K-means clustering algorithm. The project frames the algorithm not merely as a clustering technique, but as a case study in iterative optimization, demonstrating the convergence of an unsupervised learning system towards a local minimum.

Abstract

The primary objective of this work is to visualize the mechanics of high-dimensional data clustering through the lens of an iterative optimization algorithm. By animating the process of centroid convergence, we can empirically observe the behavior of Lloyd’s Algorithm in real-time. This diagnostic approach provides insight into how the system stabilizes and reaches a solution, making abstract mathematical concepts tangible.

Mathematical Process: The K-means Algorithm

K-means is an unsupervised learning algorithm that partitions a dataset into 'k' distinct, non-overlapping clusters. It operates on the principles of Expectation-Maximization (EM) to find a locally optimal solution. The process is iterative and can be broken down into the following steps:

1. Centroid Initialization: The algorithm begins by selecting 'k' initial centroids. This implementation uses a random selection strategy, where 'k' data points from the dataset are chosen to serve as the initial cluster centers.

2. Expectation (Assignment Step): Each data point in the set is assigned to the nearest centroid. The proximity is determined by calculating the Euclidean Distance between the point and every centroid. A point x_i is assigned to cluster C_j if the distance to its centroid μ_j is minimal.

3. Maximization (Update Step): After all points have been assigned to clusters, the centroids are re-computed. The new centroid for each cluster is the mean (or barycenter) of all data points assigned to it. This step aims to move the centroid to a more central position within its newly formed cluster.

These two steps, Expectation and Maximization, are repeated until the system reaches convergence.

Optimization Logic: Convergence

The K-means algorithm is fundamentally an optimization process that seeks to minimize an objective function known as Inertia, or the Within-Cluster Sum of Squares (WCSS). This is defined as the sum of squared distances between each data point and its assigned centroid:

WCSS = Σ_{j=1}^{k} Σ_{x_i ∈ C_j} ||x_i - μ_j||^2

The algorithm has converged when the cluster assignments of the data points no longer change between iterations. At this point, the WCSS has reached a local minimum, and the positions of the centroids stabilize. The visualization provided in this project makes this state of equilibrium visually apparent.

Performance and Complexity

The time complexity of the standard K-means algorithm (Lloyd's Algorithm) is:

O(n * k * i * d)

Where:

• n: The number of samples in the dataset.

• k: The number of clusters.

• i: The number of iterations required for convergence.

• d: The number of dimensions (features) of each sample.

The performance is linear with respect to each of these parameters, making it efficient for many practical applications, but potentially slow for datasets with a very large number of samples, clusters, or dimensions.

Technical Stack

• Python: The core programming language.

• NumPy: Utilized for efficient vectorized computations, particularly for distance calculations and mean computations.

• Matplotlib: Used to generate the real-time animation of the clustering process, serving as a diagnostic tool for observing convergence.

Installation

Use the package manager pip to install the required dependencies.

pip install -r requirements.txt

Usage

To run the visualization, execute the main script from the command line.

python main.py

Future Research

While this project provides a solid foundation, further research could explore more advanced techniques:

• K-means++ Initialization: To improve the quality of the final clusters and reduce the likelihood of converging to a poor local minimum, the K-means++ initialization heuristic could be implemented. This method selects initial centroids with a weighted probability based on their distance from other centroids.

• The Elbow Method: To programmatically determine the optimal value of 'k', the Elbow Method could be implemented. This involves running the K-means algorithm for a range of 'k' values and plotting the WCSS for each. The "elbow" of the resulting curve represents a point of diminishing returns, suggesting the optimal 'k'.