Feb, 2020

公平相关聚类

PDF
TL;DR本研究探讨了在公平约束下的相关性聚类，通过引入新的组合优化问题，在多种公正性约束条件下，获得了公平相关聚类的近似算法。同时，通过对真实图形的算法进行深入分析，表明与现有的不公平算法相比，可以在有限的成本增加下获得相关聚类的公平解决方案。
发现论文，激发创造
  • 公平分簇

    本文研究了如何在保护隐私的前提下实现公平聚类，提出了公平小集（fairlets）的概念，并基于最小代价流设计出高效的近似算法，在实际数据集中验证了公平聚类的价值。

    Feb, 2018

  • 可扩展的公平聚类

    本研究提出了一种实用的近似公平分解算法，几乎在线性时间内运行，可对结果聚类的平衡性进行更精细的控制。

    Feb, 2019

  • 论基本公平聚类的代价

    本文提出了针对多个保护类的公平聚类方法，并且提出了一种松散的公平概念，在这种概念下，可以对所有经典聚类目标进行双标准常数因子近似，这是通过将任意现有不公平的（整数）解和公平的（分数）线性规划解结合起来实现的。

    Nov, 2018

  • 数据汇总的公平 k-Center 聚类

    本文研究数据汇总的公平性约束下的原型选择问题，提出了一种运行时间线性的近似算法，该算法对于少数人群，只会带来常数因子的开销。

    Jan, 2019

  • 比例公平聚类

    本论文在度量空间中探讨了公平机器学习领域中比例质心聚类问题，定义了公平性并提出了计算、优化和审计聚类方案的算法，分析了比例方案与 K-Means 指标之间的权衡关系。

    May, 2019

  • 公平的聚类算法

    本文研究如何在数据中找到低成本的公平聚类问题，针对数据点可能属于多个受保护群体的情况，通过允许用户指定定义公平表示的参数、在任何 Lp 范数目标上工作的聚类算法以及允许个体属于多个保护群体的算法，将任何普通聚类解转换为公平聚类解，实验表明，在实践中算法的表现比理论结果更好。

    Jan, 2019

  • K - 聚类的个体公平性

    本文提出了一种基于局部搜索的算法，用于实现 $k$-median 和 $k$-means（以及任何使用 $\ell_p$ 范数的 $k$- 聚类），并从个体公平性的角度来考虑。我们的算法提供了一个逼近可行的 $k$- 聚类，其 $k$-median ($k$-means) 的成本与最优的 $k$- 聚类成本相比呈常数比例，并且我们的解决方案大约满足公平条件 (也在常数因子之内)。此外，我们还通过实证评估来补充我们的理论界限。

    Feb, 2020

  • 公平标注聚类

    本文主要考虑聚类算法在实际应用中保证群体公平性的问题，并提出了相应的算法。在该算法中，决策者运行聚类算法，检查每个簇的中心并为其相应的簇分配一个适当的结果。

    May, 2022

  • 个体公平聚类的改进近似算法

    此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

    Jun, 2021

  • KFC：$k$- 中心公平聚类的可扩展近似算法

    探讨了关于 $k-$center 目标函数的公平聚类问题，使用保护组的概念确保每个簇的公平性，提出了一种新的随机化 $3-$ 近似算法，对比之前的算法在效率和公平性方面获得了优化。

    Oct, 2020