EUVIMEDEUVIMED entdecken
Crossref

Highly-Efficient Large-Scale k -means with Individual Fairness

Shengkun Zhu, Jinshan Zeng, Yuan Sun, Sheng Wang, Yiming Wang, Yushuai Ji, Feiping Nie, Xiaodong Li, Zhiyong Peng

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →