Abstract
Standard k-means clustering often prioritizes global utility at the expense of individual fairness, leading to a "Matthew Effect" where outliers in sparse regions are underserved. This paper introduces Tilted k-means (TKM), a novel algorithm that leverages exponential tilting to achieve individual fairness with linear time complexity. By incorporating a tunable hyperparameter $t$, TKM allows practitioners to weight outliers more heavily, ensuring a more equitable distribution of distances. We demonstrate that TKM scales to millions of data points, outperforming existing fair clustering methods in both speed and flexibility.
Introduction: The Fairness Gap in Clustering
Clustering is a fundamental tool for resource allocation, such as determining the locations of public facilities. However, vanilla k-means minimizes the total sum of squared errors (SSE), which naturally favors dense urban centers. This results in residents of sparsely populated areas being significantly further from centroids than those in dense areas.
Existing "individually fair" clustering solutions attempt to address this by ensuring no single point is unfairly distant. However, these methods typically rely on computationally expensive linear programming or $O(kn^4)$ local searches, making them impractical for large-scale datasets where $n$ can reach the millions.
Methodology: Tilted k-means (TKM)
TKM addresses the scalability bottleneck by replacing the standard SSE objective with a Tilted SSE function, inspired by Tilted Empirical Risk Minimization (TERM). The objective is controlled by a hyperparameter $t$: as $t \to 0$, the algorithm behaves like standard k-means; as $t$ increases, the objective function places exponentially more weight on points far from their centroids.
Optimization Workflow
Unlike previous methods that require complex solvers or $n \times n$ distance matrices, TKM utilizes an efficient optimization pipeline:
- Initialization: Employs k-means++ to select initial centroids.
- Assignment: Uses Coordinate Descent (CD) to assign points to clusters.
- Refinement: Updates centroids using Stochastic Gradient Descent (SGD) to minimize the tilted objective.
This approach maintains a linear time complexity of $O(n)$, allowing TKM to scale to datasets with millions of points while providing a "fairness knob" to tune the trade-off between global utility and individual equity.
Key Insights and Results
The authors evaluated TKM across diverse real-world and large-scale datasets, including the Census1990 (~2.4M points) and HMDA (~6M points) datasets.
- Scalability: TKM processed 5 million points in approximately 30 minutes, whereas traditional fair clustering baselines often failed due to memory constraints on datasets larger than 20,000 points.
- Fairness vs. Utility: TKM consistently achieved lower maximum distances and reduced distance variance compared to standard k-means. While this leads to a marginal increase in total SSE, the trade-off is highly controllable via the parameter $t$.
- Centroid Flexibility: By allowing centroids to be any point in the continuous space rather than restricting them to existing data points (exemplars), TKM achieves superior clustering utility compared to many fair baselines.
Conclusion
Tilted k-means (TKM) provides a scalable and theoretically grounded solution to the individual fairness problem in clustering. By utilizing exponential tilting and SGD-based optimization, it bridges the gap between the computational efficiency of vanilla k-means and the ethical requirements of fair resource allocation. Future work includes extending TKM to federated learning environments to address data privacy concerns in distributed settings.
Summary updated