论文标题
$ k $ - 集群的个人公平性
Individual Fairness for $k$-Clustering
论文作者
论文摘要
我们从个人公平的角度给出了$ K $ -Median和$ k $ -Means的本地搜索算法（$ k $ -Median和$ k $ -Means（更一般而言）以$ \ ell_p $ norm COST函数功能）。更确切地说，对于点$ x $的点$ x $，$ n $的$ p $，让$ r（x）$为最小半径，以使中心为$ x $的半径$ r（x）$至少具有$ n/k $点的$ n/k $点。直观地，如果从$ p $作为中心选择一组$ k $随机点，则每个点$ x \ in P $中的每个点都希望在Radius $ r（x）$中具有一个中心。一个单独的公平聚类为p $中的每个点$ x \提供了这样的保证。这种公平概念是在[Jung等人，2019年]中引入的，他们展示了如何在这种公平条件下获得大约可行的$ k $ cluster。 在这项工作中，我们展示了如何获得公平$ k $ coltustring的两尺度近似：$ k $ -Median（$ k $ -means）的解决方案成本在不变的成本范围内，是最佳公平$ k $ coltustring的成本，而我们的解决方案大约满足公平性条件（也满足公平因素（也在恒定的因素）。此外，我们通过经验评估来补充理论界限。
We give a local search based algorithm for $k$-median and $k$-means (and more generally for any $k$-clustering with $\ell_p$ norm cost function) from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. An individually fair clustering provides such a guarantee for every point $x\in P$. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible $k$-clustering with respect to this fairness condition. In this work, we show how to get a bicriteria approximation for fair $k$-clustering: The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor). Further, we complement our theoretical bounds with empirical evaluation.
