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:
- Utility ($J_U$): Minimizing the traditional sum of squared distances.
- Fairness ($J_F$): A Rawlsian objective that seeks to minimize the distance of the most disadvantaged group within each cluster.
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.
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