Making clusterings fairer by post-processing: algorithms, complexity results and experiments
Making clusterings fairer by post-processing: algorithms, complexity results and experiments
复制标题
DOI：
10.1007/s10618-022-00893-6
复制
发表时间：
2022-12
影响因子：
4.8
通讯作者：
I. Davidson;Zilong Bai;C. Tran;S. Ravi;T. Calders;Salvatore Ruggieri;Bodo Rosenhahn;Mykola Pechenizkiy;Eirini Ntoutsi
中科院分区：
文献类型：
--
作者：
I. Davidson;Zilong Bai;C. Tran;S. Ravi;T. Calders;Salvatore Ruggieri;Bodo Rosenhahn;Mykola Pechenizkiy;Eirini Ntoutsi
虽然现有的公平性工作通常集中在公平的设计算法，在这里，我们考虑使公平不知道算法的输出更公平。具体来说，我们探索该地区的公平性聚类修改现有算法产生的聚类，使他们更公平，同时保留其质量。我们制定了最小的聚类修改公平性（MCMF）问题，其中输入是一个给定的分区聚类，目标是最小限度地改变它，使聚类仍然是质量好，但更公平。我们表明，对于一个单一的二进制保护状态变量，问题是有效的解决（即，通过证明整数线性规划公式的约束矩阵是完全幺模的，从而证明了P）类中的整数线性规划公式的约束矩阵是完全幺模的。有趣的是，我们表明，即使对于单个受保护的变量，添加简单的成对聚类指导（即确保个体级别的公平性）也会使MCMF问题在计算上变得难以处理（即，NP-hard）。使用Twitter，人口普查和纽约时报数据集的实验结果表明，我们的方法可以在几分钟内修改现有的聚类数据集超过100，000个实例在笔记本电脑上，并找到公平的聚类，但比公平的设计聚类算法产生的质量更高。最后，我们探索了一个具有挑战性的实际问题，即进行历史聚类（即，邮政编码聚集到加州的国会选区）更公平使用一个新的多方面的基准数据集。
While existing fairness work typically focuses on fair-by-design algorithms, here we consider making a fairness-unaware algorithm’s output fairer. Specifically, we explore the area of fairness in clustering by modifying clusterings produced by existing algorithms to make them fairer whilst retaining their quality. We formulate the minimal cluster modification for fairness (MCMF) problem, where the input is a given partitional clustering and the goal is to minimally change it so that the clustering is still of good quality but fairer. We show that for a single binary protected status variable, the problem is efficiently solvable (i.e., in the classP) by proving that the constraint matrix for an integer linear programming formulation is totally unimodular. Interestingly, we show that even for a single protected variable, the addition of simple pairwise guidance for clustering (to say ensure individual-level fairness) makes the MCMF problem computationally intractable (i.e.,NP-hard). Experimental results using Twitter, Census and NYT data sets show that our methods can modify existing clusterings for data sets in excess of 100,000 instances within minutes on laptops and find clusterings that are as fair but are of higher quality than those produced by fair-by-design clustering algorithms. Finally, we explore a challenging practical problem of making a historical clustering (i.e., zipcodes clustered into California’s congressional districts) fairer using a new multi-faceted benchmark data set.