可扩展的公平聚类
本文提出了针对多个保护类的公平聚类方法,并且提出了一种松散的公平概念,在这种概念下,可以对所有经典聚类目标进行双标准常数因子近似,这是通过将任意现有不公平的(整数)解和公平的(分数)线性规划解结合起来实现的。
Nov, 2018
我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平($p$, $k$)- 聚类问题。我们设计了首个快速局部搜索算法,具有~$O (nk^2)$ 的运行时间,并获得了(O (1), 6)的二对象近似解,然后我们通过实验证明了我们的算法不仅比以前的工作快得多,而且产生了更低成本的解决方案。
Feb, 2024
本文提出了一种基于局部搜索的算法,用于实现 $k$-median 和 $k$-means(以及任何使用 $\ell_p$ 范数的 $k$- 聚类),并从个体公平性的角度来考虑。我们的算法提供了一个逼近可行的 $k$- 聚类,其 $k$-median ($k$-means) 的成本与最优的 $k$- 聚类成本相比呈常数比例,并且我们的解决方案大约满足公平条件 (也在常数因子之内)。此外,我们还通过实证评估来补充我们的理论界限。
Feb, 2020
本文研究如何在数据中找到低成本的公平聚类问题,针对数据点可能属于多个受保护群体的情况,通过允许用户指定定义公平表示的参数、在任何 Lp 范数目标上工作的聚类算法以及允许个体属于多个保护群体的算法,将任何普通聚类解转换为公平聚类解,实验表明,在实践中算法的表现比理论结果更好。
Jan, 2019
探讨了关于 $k-$center 目标函数的公平聚类问题,使用保护组的概念确保每个簇的公平性,提出了一种新的随机化 $3-$ 近似算法,对比之前的算法在效率和公平性方面获得了优化。
Oct, 2020
本研究探讨了在公平约束下的相关性聚类,通过引入新的组合优化问题,在多种公正性约束条件下,获得了公平相关聚类的近似算法。同时,通过对真实图形的算法进行深入分析,表明与现有的不公平算法相比,可以在有限的成本增加下获得相关聚类的公平解决方案。
Feb, 2020
此论文介绍了一种可行的算法,用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题,并对相应指标(如 bicriteria)进行了优化;同时,提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法,并将借鉴此算法,将个体公平聚类转化为更一般如群体公平聚类的解法。
Jun, 2021