K-Means Clustering Algorithm

K-Means Clustering Algorithm is a center-based, iterative machine learning algorithm that partitions unlabeled (unsupervised) data points into K clusters based on their similarity. Each data point belongs to exactly one cluster; in this regard, it is a "hard" clustering technique. Unlike supervised learning, the K-Means algorithm does not require class labels and aims to discover the natural structure within the data.

The K-Means algorithm forms clusters around a predefined number of centroids. Each data point is assigned to the nearest centroid. The cluster centers are then updated by computing the mean of all data points assigned to each cluster. This process continues until the centroids stabilize (convergence) or a maximum number of iterations is reached.

1. Initialization: The number of clusters K is determined, and K initial cluster centroids are selected (randomly or using specialized methods such as k-means++).
2. Assignment Step (Expectation): Each data point is assigned to the nearest centroid, typically using Euclidean distance.
3. Update Step (Maximization): For each cluster, a new centroid is calculated as the mean of all data points assigned to that cluster.
4. Iteration: The assignment and update steps are repeated until the centroids no longer change significantly.

K-Means seeks to minimize the total sum of squared errors (SSE), which is the sum of the squared distances between each data point and the centroid of its assigned cluster:

SSE = $\sum _{i=1}^k\sum _{x\in C_i}\left|\right|x-{\mu }_i|{|}^2$

Where:

• k: The number of clusters
• i: An index ranging from 1 to k, used to perform separate operations for each cluster
• $C_i$: The i-th cluster, containing multiple data points
• $x\in C_i$: A data point belonging to cluster i; each x can be multidimensional (e.g., a vector)
• ${\mu }_i$: The centroid of the i-th cluster; it is the mean of all data points x in that cluster
• $\left|\right|x-{\mu }_i|{|}^2$: The squared Euclidean distance between data point x and its cluster centroid ${\mu }_i$. This distance indicates how well the point fits within its cluster.

^{K-Means Algorithm Illustration (generated by artificial intelligence.)}

• Simple and interpretable: Easy to implement and understand
• Fast: Delivers high performance, especially on large datasets
• Scalable: Can handle high-dimensional data

• Sensitivity to initialization: Random starting centroids may lead to different results
• K must be specified in advance: The number of clusters must be known beforehand
• Sensitive to outliers: Since it uses means, extreme values can distort cluster centers
• Limitations on cluster shape and density: Performs best with spherical, evenly sized clusters

• Elbow Method: SSE is computed for each value of K. The optimal K is identified at the "elbow" point on the plot, where the rate of decrease in SSE slows significantly.
• Silhouette Analysis: Evaluates cluster quality by measuring the difference between the average similarity of a point to its own cluster and its similarity to the nearest other cluster.

• k-means++: Improves stability and quality by selecting initial centroids with probability proportional to their squared distance from existing centroids, ensuring better spread.

• Inertia: The sum of squared distances within clusters. Lower inertia indicates more compact clusters.
• Dunn Index: The ratio of the minimum distance between clusters to the maximum distance within any cluster. Higher values indicate better-separated clusters.

• Customer Segmentation: Grouping customers with similar behaviors for targeted marketing strategies
• Document Clustering: Categorizing news articles or research papers by topic
• Image Segmentation: Partitioning images into regions, such as analyzing tissue types in medical imaging
• Recommendation Systems: Analyzing user preferences to suggest relevant content or products
• Data Compression: Representing image data with fewer dimensions by clustering similar pixels

• Gaussian Mixture Models (GMM): A probabilistic clustering method that allows each data point to belong to multiple clusters with varying probabilities
• Hierarchical Clustering: Builds a tree-like structure to represent nested groupings of data
• DBSCAN: A density-based clustering algorithm that is more robust to outliers and can discover clusters of arbitrary shape