Improving fair clustering methods to better balance group representation
A Sub-4 Approximation for Fair $k$-Means
Computational GeometryMachine Learning
Summary
Clustering is a way to group similar items together, but it's important to make sure different protected groups are fairly represented in each cluster. The authors developed a new method that improves the accuracy of fair clustering by better combining mathematical tools and geometry. Their approach provides results closer to the best possible solution while ensuring fair representation limits are met exactly. This method also works for related problems in data summarization. Overall, it offers a more effective way to create balanced groups in datasets.
k-means clusteringfairness constraintsapproximation algorithmlinear programming relaxationEuclidean spaceintegrality gapPTAS (Polynomial Time Approximation Scheme)fractional solutionrounding procedureWasserstein barycenter
Authors
Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding
Abstract
Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair $k$-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/Γ)ρ+O(ε)$ times the optimal integral fair cost, where $Γ\approx6.357$ is an upper bound on the integrality gap of the standard Euclidean $k$-means LP. With a PTAS as the subroutine, the approximation ratio becomes $3.8427+O(ε)$, improving the previous factor of $5+O(ε)$ to below $4$. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the $k$-sparse Wasserstein barycenter problem.