Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints
Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints
复制标题
DOI：
10.1609/aaai.v35i8.16842
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Brian Brubach;D. Chakrabarti;John P. Dickerson;A. Srinivasan;Leonidas Tsepenekas
中科院分区：
文献类型：
--
作者：
Brian Brubach;D. Chakrabarti;John P. Dickerson;A. Srinivasan;Leonidas Tsepenekas
度量聚类是从组合优化和数据挖掘到机器学习和运筹学等领域的基础。然而，在各种情况下，我们可能有额外的要求或知识，不同于底层的度量，关于哪些点对应该聚集在一起。为了捕捉和分析这样的情况下，我们引入了一个新的家庭的随机成对约束，我们纳入几个基本的聚类目标（半径/中位数/手段）。此外，我们证明了这些约束可以简洁地模拟一个有趣的应用程序集合，包括聚类中的个体公平性和半监督学习中的必须链接约束。我们的主要结果包括一个一般的框架，产生近似算法与可证明的保证重要的聚类目标，而在同一时间产生的解决方案，尊重随机成对约束。此外，对于某些目标，我们设计改进的结果的情况下，必须链接的约束，这也是最好的可能从理论的角度来看。最后，我们提出了实验证据，验证了我们的算法的有效性。
Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms.