Towards Fairer Centroids in K-means Clustering

Stanley Simoes, Deepak P, Muiris MacCarthaighAAAI 2024 · DOI

Abstract

Standard fair clustering techniques typically focus on global statistical parity, ensuring that protected groups are represented proportionally across an entire dataset. However, this macro-level focus often neglects how well specific groups are served by the individual cluster centers (centroids) to which they are assigned. We introduce Cluster-Level Centroid Fairness (CCF) and the Fair-Centroid algorithm. By optimizing for the representation of the "worst-off" group within every individual cluster, our approach ensures that fairness is a local reality rather than just a global average.

Introduction

In centroid-based clustering, such as $k$-means, the centroid serves as the representative point for all members of a cluster. In practical applications like facility location (e.g., placing health clinics or polling stations), the distance to a centroid directly dictates a user's access to essential services.

Existing "fair" $k$-means algorithms often suffer from compensatory effects. A demographic group might be well-served in one cluster but significantly disadvantaged in another; on a dataset-wide average, the treatment appears fair, but local inequality remains high. We argue that fairness must be evaluated and enforced at the cluster level to prevent these localized pockets of disadvantage.

Methodology

To address intra-cluster inequality, we propose a framework centered on Average Cluster Disparity, which quantifies unfairness by calculating the variance of mean distance-to-centroid among different groups within each cluster.

Our optimization objective, $J$, balances two primary goals:

  1. Utility ($J_U$): Minimizing the traditional sum of squared distances.
  2. Fairness ($J_F$): A Rawlsian objective that seeks to minimize the distance of the most disadvantaged group within each cluster.
Comparison of centroid placement for a single cluster (C1) across different algorithms. Fair-Centroid shifts the representative point to better balance the distances for the internal subgroups.

Because the "max" operator used to identify the worst-off group is non-differentiable, the Fair-Centroid algorithm employs a LogSumExp approximation. This allows for an Expectation-Maximization (EM) structure where the E-step reassigns objects to minimize the joint objective, and the M-step updates centroids via gradient descent to better serve disadvantaged subgroups.

Experimental Evaluation

We evaluated Fair-Centroid using the Adult (demographics) and CreditCard (client data) datasets, focusing on sensitive attributes such as sex and race. We compared our method against standard $k$-means (Lloyd's algorithm) and existing global fairness approaches (Fair-Lloyd).

Results and Discussion

Our results indicate that Fair-Centroid consistently achieves superior local fairness. Notably, we observed a "Fair-Lloyd Paradox": existing global fairness algorithms sometimes produced worse cluster-level fairness than standard $k$-means. This confirms that optimizing for global parity can inadvertently exacerbate local inequalities.

The fair centroid objective plotted against k for different datasets. Fair-Centroid (green) consistently achieves lower unfairness scores compared to Lloyd (blue) and Fair-Lloyd (orange).

Furthermore, the improvements in fairness come at a relatively low cost to traditional cluster utility. By tuning the trade-off hyperparameter $\lambda$, practitioners can significantly reduce group disparity while maintaining high cluster coherence.

Conclusion and Future Work

Fair-Centroid provides a robust mechanism for ensuring equitable representation at the local level. While the algorithm is computationally more intensive than standard $k$-means—taking significantly longer to converge on large datasets—it offers a necessary correction to the "veneer of fairness" provided by global metrics. Future research will focus on improving optimization efficiency through techniques like LP relaxation and extending the framework to accommodate continuous sensitive attributes.

Summary updated

BibTeX
@inproceedings{simoes2024towards,
  author = {Stanley Simoes and Deepak P and Muiris MacCarthaigh},
  title = {{Towards Fairer Centroids in K-means Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i19.30156},
}
Figure