Highly-Efficient Large-Scale k -means with Individual Fairness
Proceedings of the VLDB Endowment · 01.01.2026 · 19 (5) · 808-821
DOI: 10.14778/3796195.3796197 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 05.05.2026. Verfasst von Shengkun Zhu und 8 weiteren Autor:innen. Die Arbeit nennt 74 Literaturangaben.
Abstract (Originalsprache)
Traditional k -means minimizes the sum of squared error (SSE) but may treat data points unequally, as some are assigned to significantly distant centroids. This leads to unfair outcomes in downstream tasks such as facility location planning, where each cluster corresponds to a specific share of limited resources. To address this, we modify the objective of k -means via exponential tilting , which emphasizes the impact of distant data points and yields a new objective: the tilted SSE. We propose TKM, which optimizes via coordinate descent and stochastic gradient descent, and improves fairness by shifting centroids toward underrepresented groups. We adopt the within-cluster variance to quantify fairness among individuals within the same group, which provably reduces extreme disparities in outcomes. To improve efficiency, we propose FastTKM, which uses stochastic dynamics to estimate the tilted SSE with lower computational cost. We theoretically demonstrate that, under our proposed methods, the variance decreases with t , a scaling factor that controls the degree of centroid deviation. Furthermore, our methods exhibit time and space complexities comparable to the classical Lloyd's heuristic. Experimentally, our methods outperform six baselines in terms of clustering utility and fairness across twelve real-world datasets. In terms of efficiency, our methods achieve thousand-fold speedups in running time and reduction in memory usage, with this factor growing as the dataset size increases.
Zitieren
APA
Zhu, S., Zeng, J., Sun, Y., Wang, S., Wang, Y., Ji, Y., Nie, F., Li, X., & Peng, Z. (2026). Highly-Efficient Large-Scale k -means with Individual Fairness. Proceedings of the VLDB Endowment, 19(5), 808-821. https://doi.org/10.14778/3796195.3796197
Vancouver
Zhu S, Zeng J, Sun Y, Wang S, Wang Y, Ji Y, et al. Highly-Efficient Large-Scale k -means with Individual Fairness. Proceedings of the VLDB Endowment. 2026;19(5):808-821. doi:10.14778/3796195.3796197
BibTeX
@article{Zhu2026,
author = {Zhu, Shengkun and Zeng, Jinshan and Sun, Yuan and Wang, Sheng and Wang, Yiming and Ji, Yushuai and Nie, Feiping and Li, Xiaodong and Peng, Zhiyong},
title = {Highly-Efficient Large-Scale k -means with Individual Fairness},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {5},
pages = {808--821},
doi = {10.14778/3796195.3796197}
}
EUVIMED