Scalable Fair Clustering
Scalable Fair Clustering
复制标题
DOI：
--
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
A. Backurs;P. Indyk;Krzysztof Onak;B. Schieber;A. Vakilian;Tal Wagner
中科院分区：
文献类型：
--
作者：
A. Backurs;P. Indyk;Krzysztof Onak;B. Schieber;A. Vakilian;Tal Wagner
我们研究了Chierichetti等人引入的经典$ K $ -Median问题的公平变体。 [2017]。在标准的$ k $ -Median问题中，给定输入点集$ P $，目标是找到$ k $中心$ c $，并将每个输入点分配给$ c $的一个中心之一，以便平均距离的平均距离指向他们的集群中心的指向最小化。在$ k $ -Median的公平变体中，这些点是彩色的，目标是最大程度地降低相同的平均距离目标，同时确保所有簇都具有每种颜色的“大致相等”的点数。 Chierichetti等。提出了针对公平$ k $ clustering的两阶段算法。在第一步中，将点集分配为称为fairlets的子集，这些子集满足公平要求并大致保留$ k $ -Median目标。在第二步中，由现有的$ k $ -Median算法之一将Fairlet合并为$ K $簇。该算法的运行时间由第一步主导，这需要超级季度的时间。在本文中，我们提出了一种实用的近似Fairlet分解算法，该算法几乎在线性时间内运行。我们的算法还允许比原始工作更好地控制产生簇的平衡。我们通过经验评估来补充理论界限。
We study the fair variant of the classic $k$-median problem introduced by Chierichetti et al. [2017]. In the standard $k$-median problem, given an input pointset $P$, the goal is to find $k$ centers $C$ and assign each input point to one of the centers in $C$ such that the average distance of points to their cluster center is minimized. In the fair variant of $k$-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the $k$-median objective. In the second step, fairlets are merged into $k$ clusters by one of the existing $k$-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.