Summary of Efficient K-means with Individual Fairness Via Exponential Tilting, by Shengkun Zhu et al.
Efficient k-means with Individual Fairness via Exponential Tilting
by Shengkun Zhu, Jinshan Zeng, Yuan Sun, Sheng Wang, Xiaodong Li, Zhiyong Peng
First submitted to arxiv on: 24 Jun 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Computers and Society (cs.CY)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper introduces a novel algorithm called Tilted k-means (TKM) for achieving individual fairness in clustering, which is particularly useful in location-based resource allocation scenarios. The proposed approach integrates exponential tilting into the sum of squared errors (SSE) to formulate a tilted SSE objective function, enabling optimization using coordinate descent and first-order gradient methods. A novel fairness metric, variance of distances within each cluster, is introduced to alleviate the Matthew Effect caused by existing metrics. Theoretical analysis demonstrates that TKM converges under mild conditions and exhibits linear time complexity with dataset size. Empirical results show that TKM outperforms state-of-the-art methods in terms of effectiveness, fairness, and efficiency. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary TKM is a new way to group people or things together based on location, making sure everyone gets treated fairly. This is important because we want to make sure all points are equal. The team behind TKM found a clever way to adjust an old method called k-means++ to make it more fair. They also created a new way to measure fairness that helps fix some problems with older methods. Their math shows that TKM works well and is fast, even when dealing with big datasets. |
Keywords
* Artificial intelligence * Clustering * K means * Objective function * Optimization
