Overview

K-Means is one of the most widely used clustering algorithms in machine learning and data analysis. It fals under the category of unsupervised learning algorithms, meaning it discovers natural groupings in data without pre-defined labels. The algorithm partitions a dataset into K distinct clusters based on feature similarity, where similarity is measured using distance metrics.

The Algorithm

K-Means operates through an iterative refinement process:

1. Initialization: Select K initial centroids (cluster centers) from the dataset. These can be chosen randomly or through more sophisticated methods.

2. Assignment: For each data point, calculate its distance to all K centroids. Assign the point to the nearest centroid's cluster.

3. Update: Recalculate each centroid by computing the mean of all data points assigned to its cluster.

4. Convergence Check: If centroid positions remain relatively stable (below a threshold) or maximum iterations are reached, terminate. Otherwise, return to step 2.

The algorithm minimizes within-cluster variance, measured as the sum of squared distances between points and their respective centroids.

Worked Example

Consider six two-dimensional data points that visually appear to form two natural clusters:

Iteration 1: Using P1 and P4 as initial centroids, calculate distances:

• P2 distence to P1: √5 ≈ 2.24
• P2 distance to P4: √157 ≈ 12.53 → Assign to P1
• P3 distance to P1: √10 ≈ 3.16
• P3 distance to P4: √85 ≈ 9.22 → Assign to P1
• P5 distance to P1: √245 ≈ 15.65
• P5 distance to P4: √5 ≈ 2.24 → Assign to P4
• P6 distance to P4: √9 = 3 → Assign to P4

Cluster assignments after iteration 1:

• Cluster A: P1, P2, P3
• Cluster B: P4, P5, P6

Iteration 2: Compute new centroids:

• Centroid A: (1.33, 1)
• Centroid B: (9, 8.33)

Reassign points based on new centroids. Distances remain unchanged, indicating convergence. The algorithm successfully identified the two natural groupings.

Distance Metrics

Euclidean Distance

The most common metric, calculating the straight-line distance between two points in Euclidean space:

Distance = √[(x₁-x₂)² + (y₁-y₂)²]

This metric works well with continuous numerical features and assumes spherical cluster shapes.

Cosine Similarity

Measures the angle between two vectors rather than their magnitude:

cosine = (A · B) / (||A|| × ||B||)

Useful when dealing with text data or when cluster shape varies significantly. Less sensitive to magnitude differences.

Paramter Selection

Choosing K Value

No universal method exists for optimal K selection. Common approaches include:

• Elbow Method: Plot within-cluster sum of squares (WCSS) against K. Look for the "elbow" point where diminishing returns begin.

• Domain Knowledge: Based on business requirements or analytical objectives.

• Cross-Validation: Test multiple K values and evaluate cluster quality metrics.

Initial Centroid Selection

Poor initialization can lead to suboptimal results. Strategies include:

• Multiple Runs: Execute algorithm multiple times with different initializations.

• K-Means++: intelligently select initial centroids to maximize separation.

• Hierarchical Clustering Pre-step: Use hierarchical results to identify good starting points.

Data Preprocessing

Feature Scaling

K-Means is sensitive to feature scales. Without normalization:

• Features with larger ranges dominate distance calculations
• Features with smaller ranges have minimal influence

Normalization Methods

Min-Max Scaling: Transforms data to [0, 1] range:

X' = (X - min) / (max - min)

Z-Score Standardization: Rescales to zero mean and unit variance:

X' = (X - μ) / σ

Choose based on data distribution and algorithm requirements.

Practical Considerations

Handling Outliers

Outlierscan significantly distort centroid positions. Options:

• Remove extreme values before clustering
• Use modified algorithms like K-Medians
• Consider analyzing outliers as separate groups

Interpreting Results

After clustering, analyze cluster characteristics:

• Profile each cluster's feature distributions
• Use statistical tests (ANOVA) to identify significant differentiating features
• Validate results against domain knowledge

Algorithm Limitations

• Assumes spherical, equally-sized clusters
• Sensitive to initialization
• Requires pre-specification of K
• Poor performance with categorical data

For non-spherical clusters, consider algorithms like DBSCAN or Gaussian Mixture Models.