Research map / Learning theory and algorithms / Clustering

Towards Fairer Centroids in K-means Clustering

AAAI 2024 · Learning theory and algorithms › Clustering · approach: Fairness-constrained clustering · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes cluster-level centroid fairness (CCF), a metric for per-cluster group representativity disparity, and Fair-Centroid, a k-means variant that improves the worst-off group's representativity within each cluster.

Problem

Existing fair k-means objectives aggregate group representativity (distance to centroid) across clusters, letting poor representativity in one cluster be offset elsewhere and concealing intra-cluster unfairness across groups.

Approach

Define fairness at the cluster level: measure the variance of group representativities within each cluster after standardising distances per cluster, and optimise a k-means objective plus a log-sum-exp smoothed sum of each cluster's worst-off group representativity, using an EM-style greedy reassignment and gradient-based centroid updates.

Key results

• Fair-Centroid consistently and significantly reduces average cluster disparity relative to Lloyd's k-means across k=3 to 12 on Adult/sex, Adult/race and CreditCard/SEX, at a comparably small increase in the k-means objective.
• Fair-Lloyd (fair k-means) often performs worse than Lloyd on the cluster-level disparity metric, sometimes even worse than Lloyd.
• Fair-Centroid makes the overall worst-off group's representativity worse than Lloyd on the fair k-means objective, showing that cluster-level and dataset-level fairness can conflict.

Measured effects reported in the paper

Surprising findings

• Fair-Lloyd, which optimises the dataset-level fair k-means objective, can yield worse cluster-level disparity than plain Lloyd's k-means.
• Fair-Centroid increases the dataset-level worst-off group's representativity loss relative to Lloyd, indicating that optimising one fairness objective does not entail the other.

Limitations

• Fair-Centroid is slower than Lloyd and Fair-Lloyd, with greedy E-step yielding suboptimal assignments and more iterations.
• Only a single binary or categorical sensitive attribute per experiment; numeric sensitive attributes left to future work.
• Evaluated only on two datasets (Adult and CreditCard) with no baseline designed specifically for cluster-level fairness.

Experimental setup

Datasets: Adult CreditCard (default of credit card clients)

Benchmarks: Adult/sex Adult/race CreditCard/SEX

Metrics: average cluster disparity (variance of group representativit k-means objective fair centroid objective fair k-means objective

Baselines: Lloyd's k-means Fair-Lloyd

Builds on: k-means (Lloyd's heuristic) fair k-means (Ghadiri et al. 2021) representativity fairness (P and Abraham 2020)

Closest papers by meaning

• Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.92)
• Fair Clustering via Alignment (ICML 2025 · similarity 0.91)
• Unifying Proportional Fairness in Centroid and Non-Centroid Clustering (NeurIPS 2025 · similarity 0.90)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.89)
• The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.89)
• Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.89)