Efficient k-means with Individual Fairness via Exponential Tilting

Shengkun Zhu, Jinshan Zeng, Yuan Sun, Sheng Wang, Xiaodong Li, Zhiyong PengarXiv 2024 · DOI · arXiv

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.

Comparison of standard k-means and individually fair k-means, highlighting how fairness adjustments reduce extreme distances for outliers.

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:

  1. Initialization: Employs k-means++ to select initial centroids.
  2. Assignment: Uses Coordinate Descent (CD) to assign points to clusters.
  3. Refinement: Updates centroids using Stochastic Gradient Descent (SGD) to minimize the tilted objective.
The TKM optimization workflow, showing k-means++ initialization followed by iterative coordinate descent and SGD-based refinement.

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

Abstract

In location-based resource allocation scenarios, the distances between each individual and the facility are desired to be approximately equal, thereby ensuring fairness. Individually fair clustering is often employed to achieve the principle of treating all points equally, which can be applied in these scenarios. This paper proposes a novel algorithm, tilted k-means (TKM), aiming to achieve individual fairness in clustering. We integrate the exponential tilting into the sum of squared errors (SSE) to formulate a novel objective function called tilted SSE. We demonstrate that the tilted SSE can generalize to SSE and employ the coordinate descent and first-order gradient method for optimization. We propose a novel fairness metric, the variance of the distances within each cluster, which can alleviate the Matthew Effect typically caused by existing fairness metrics. Our theoretical analysis demonstrates that the well-known k-means++ incurs a multiplicative error of O(k log k), and we establish the convergence of TKM under mild conditions. In terms of fairness, we prove that the variance generated by TKM decreases with a scaled hyperparameter. In terms of efficiency, we demonstrate the time complexity is linear with the dataset size. Our experiments demonstrate that TKM outperforms state-of-the-art methods in effectiveness, fairness, and efficiency.
BibTeX
@misc{zhu2024efficient,
  author = {Shengkun Zhu and Jinshan Zeng and Yuan Sun and Sheng Wang and Xiaodong Li and Zhiyong Peng},
  title = {{Efficient k-means with Individual Fairness via Exponential Tilting}},
  year = {2024},
  eprint = {2406.16557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.16557},
}
Figure