A Scalable Algorithm for Individually Fair K-means Clustering
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910328401428480 |
|---|---|
| author | Bateni, MohammadHossein Cohen-Addad, Vincent Epasto, Alessandro Lattanzi, Silvio |
| author_facet | Bateni, MohammadHossein Cohen-Addad, Vincent Epasto, Alessandro Lattanzi, Silvio |
| contents | We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. Given $n$ points $P$ in a metric space, let $δ(x)$ for $x\in P$ be the radius of the smallest ball around $x$ containing at least $n / k$ points. A clustering is then called individually fair if it has centers within distance $δ(x)$ of $x$ for each $x\in P$. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in ~$O(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06730 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Scalable Algorithm for Individually Fair K-means Clustering Bateni, MohammadHossein Cohen-Addad, Vincent Epasto, Alessandro Lattanzi, Silvio Data Structures and Algorithms Computers and Society Machine Learning We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. Given $n$ points $P$ in a metric space, let $δ(x)$ for $x\in P$ be the radius of the smallest ball around $x$ containing at least $n / k$ points. A clustering is then called individually fair if it has centers within distance $δ(x)$ of $x$ for each $x\in P$. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in ~$O(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions. |
| title | A Scalable Algorithm for Individually Fair K-means Clustering |
| topic | Data Structures and Algorithms Computers and Society Machine Learning |
| url | https://arxiv.org/abs/2402.06730 |