K Means Clustering

Overview

Definition

K Means clustering: unsupervised learning technique for partitioning dataset into K clusters by minimizing intra-cluster variance. Centroids represent cluster centers. Objective: minimize sum of squared distances between points and assigned centroids.

History

Origin: introduced by Stuart Lloyd (1957), formally published 1982. Popularized in pattern recognition, signal processing. Basis for many clustering algorithms.

Purpose

Purpose: data segmentation, pattern detection, feature learning. Used to discover latent groupings without labeled data.

Key Concepts

Centroid: mean vector of cluster points. Cluster assignment: nearest centroid. Objective function: sum of squared errors (SSE). Convergence: stable cluster assignments or max iterations.

"K-means clustering provides a simple yet powerful method for identifying underlying group structures in unlabeled data." -- J. MacQueen

Algorithm Details

Step-by-step Process

1. Initialize K centroids. 2. Assign each data point to nearest centroid. 3. Update centroids as mean of assigned points. 4. Repeat steps 2-3 until convergence.

Objective Function

Minimize within-cluster sum of squares (WCSS):

J = ∑_(i=1)^K ∑_(x ∈ C_i) || x - μ_i ||²Where: K = number of clusters C_i = points in cluster i μ_i = centroid of cluster i

Convergence Criteria

Converges when assignments no longer change or when change in centroids falls below threshold or max iterations reached.

Cluster Assignment

Each point assigned to cluster with nearest centroid using chosen distance metric (commonly Euclidean).

Initialization Methods

Random Initialization

Randomly select K points as initial centroids. Simple but can cause poor local minima convergence.

K Means++ Initialization

Probabilistic seeding to spread centroids. Reduces initialization variance. Improves convergence speed and quality.

Forgy Method

Randomly choose K data points as centroids. Equivalent to random initialization but defined distinctly.

Impact on Results

Initialization affects final clustering. Multiple runs with different seeds recommended.

Distance Metrics

Euclidean Distance

Default metric. Measures straight-line distance in feature space. Works well for continuous numeric data.

Manhattan Distance

Sum of absolute differences. Useful in high-dimensional or grid-like data.

Cosine Similarity

Measures angle between vectors. Used in text or sparse data with directional meaning.

Choosing Distance Metric

Metric choice depends on data type, scale, and problem domain. Can affect cluster shape and results.

Optimization Techniques

Iterative Refinement

Alternate between assignment and centroid update steps until convergence. Guaranteed to converge to local minimum.

Elkan’s Algorithm

Uses triangle inequality to reduce distance computations. Speeds up assignment step.

Mini-Batch K Means

Uses small random data batches to update centroids. Trade-off between speed and accuracy.

Accelerated Methods

Use data structures (k-d trees, ball trees) to speed nearest centroid search.

Applications

Image Segmentation

Clusters pixels by color/intensity to segment images into regions.

Market Segmentation

Groups customers based on purchasing behavior, demographics.

Document Clustering

Organizes large corpora by topic or similarity.

Anomaly Detection

Identifies outliers based on distance from cluster centroids.

Advantages and Limitations

Advantages

Simple to implement. Scalable to large datasets. Efficient convergence. Intuitive cluster representation.

Limitations

Requires pre-specified K. Sensitive to initialization. Assumes spherical clusters. Poor with noisy/outlier data.

Scalability Issues

High dimensionality degrades distance metric effectiveness. Large K increases computational cost.

Cluster Shape Constraints

Works best for convex, isotropic clusters. Cannot model complex shapes.

Computational Complexity

Per Iteration Complexity

O(n × K × d) where n = points, K = clusters, d = dimensions.

Overall Complexity

Depends on iterations until convergence, typically small in practice.

Memory Requirements

Stores dataset, centroids, and cluster assignments. Scales linearly with data size.

Parallelization

Assignment and update steps parallelizable, enabling use on distributed systems.

Evaluation Metrics

Inertia

Sum of squared distances within clusters. Lower inertia indicates tighter clusters.

Silhouette Score

Measures cluster separation and cohesion. Ranges from -1 to 1; higher is better.

Davies-Bouldin Index

Ratio of within-cluster scatter to between-cluster separation. Lower is preferable.

Elbow Method

Plots inertia vs. K to identify diminishing returns on cluster number.

Variants and Extensions

Fuzzy C Means

Soft clustering: points belong to clusters with membership weights.

Bisecting K Means

Hierarchical clustering using repeated bisection via K Means.

Kernel K Means

Projects data to higher dimension with kernel trick to find nonlinear clusters.

Constrained K Means

Incorporates must-link and cannot-link constraints to guide clustering.

Implementation Considerations

Choosing K

Use domain knowledge, Elbow method, silhouette analysis, or cross-validation to select K.

Preprocessing

Standardize or normalize features to prevent bias due to scale differences.

Handling Outliers

Outliers skew centroids. Consider preprocessing or robust variants.

Software Libraries

Widely available in scikit-learn, MATLAB, R, TensorFlow, etc., with customizable parameters.

# Example: Pseudocode for K Meansinitialize centroids randomlyrepeat for each point: assign to nearest centroid for each cluster: recompute centroid as mean of assigned pointsuntil convergence or max iterations

References

• MacQueen, J. "Some Methods for Classification and Analysis of Multivariate Observations," Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, 1967, pp. 281-297.
• Lloyd, S. "Least Squares Quantization in PCM," IEEE Transactions on Information Theory, vol. 28, no. 2, 1982, pp. 129–137.
• Arthur, D., and Vassilvitskii, S. "k-means++: The Advantages of Careful Seeding," Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1027-1035.
• Elkan, C. "Using the Triangle Inequality to Accelerate k-Means," Proceedings of the 20th International Conference on Machine Learning (ICML), 2003, pp. 147-153.
• Steinley, D. "K-means clustering: A half-century synthesis," British Journal of Mathematical and Statistical Psychology, vol. 59, no. 1, 2006, pp. 1–34.