本文主要考虑聚类算法在实际应用中保证群体公平性的问题,并提出了相应的算法。在该算法中,决策者运行聚类算法,检查每个簇的中心并为其相应的簇分配一个适当的结果。
May, 2022
在机器学习中,我们提出了一个新的公理,即比例表示公平(PRF),并设计了高效的算法来实现公平聚类,这一概念以一种更有说服力的方式实现了现有概念的存在原因。
Apr, 2023
本文提出了针对多个保护类的公平聚类方法,并且提出了一种松散的公平概念,在这种概念下,可以对所有经典聚类目标进行双标准常数因子近似,这是通过将任意现有不公平的(整数)解和公平的(分数)线性规划解结合起来实现的。
Nov, 2018
本文研究数据汇总的公平性约束下的原型选择问题,提出了一种运行时间线性的近似算法,该算法对于少数人群,只会带来常数因子的开销。
Jan, 2019
我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平($p$, $k$)- 聚类问题。我们设计了首个快速局部搜索算法,具有~$O (nk^2)$ 的运行时间,并获得了(O (1), 6)的二对象近似解,然后我们通过实验证明了我们的算法不仅比以前的工作快得多,而且产生了更低成本的解决方案。
Feb, 2024
我们研究了陈等人的比例聚类问题,并将其与计算社会选择中的多胜者投票领域相关联。我们展示了任何满足 Brill 和 Peters 的弱比例概念的聚类同时获得陈等人比例公平概念、个体公平和 “核心” 的最佳已知拟合度。事实上,我们证明了任何对比例公平的近似也是对个体公平的近似,反之亦然。最后,我们还研究了比例代表性更强的概念,在这些概念中,偏差不仅发生在单个候选中心,还发生在多个候选中心,并且展示了 Brill 和 Peters 的更强比例概念对这些更严格的保证的拟合度。
Oct, 2023
运用线性规划和局部搜索算法解决在数据聚类问题中,$\ell_p$-range 目标下的个体公平问题。通过修改 LP 理论和结合局部搜索算法实践,实现更优算法,并在实验中展现了出众的表现。
Jun, 2021
本文研究了如何在保护隐私的前提下实现公平聚类,提出了公平小集(fairlets)的概念,并基于最小代价流设计出高效的近似算法,在实际数据集中验证了公平聚类的价值。
Feb, 2018
本文研究了公平聚类的结构、计算及近似算法,并提出了群组代表性聚类的思想,旨在解决公平聚类与聚类代表性之间的矛盾问题。
Jun, 2020
本研究提出了一种实用的近似公平分解算法,几乎在线性时间内运行,可对结果聚类的平衡性进行更精细的控制。
Feb, 2019