让聚类结果公平地代表每个群体，且不增加成本。
Fair Clustering with Minimum Representation Constraints
- 设计最小代表约束下的聚类优化模型，保证每类至少在部分簇中达到最低比例。
- 提出MiniReL算法，在标准数据集上保持原聚类成本的同时实现公平性。
- 适合需要公平分组的应用，如选区划分、内容推荐等场景。
聚类是经典的无监督学习任务，旨在将数据点划分为若干簇。在许多实际应用中（如选区划分、播放列表生成），这些簇对应真实世界结构，其中某一社会或人口群体只有在簇中达到最低代表性水平（例如50%）时才能获益。本文研究在额外公平性约束下，即每个群体必须在至少指定数量的簇中达到最小代表比例的k-means与k-medians聚类问题。我们将该问题建模为混合整数非线性优化问题，并提出一种交替优化算法MiniReL求解。尽管引入公平性约束导致算法内部分配问题为NP难，但本文提出多种启发式策略，使方法在大规模数据上仍具实用性。数值实验表明，所提方法可在标准基准数据集上实现公平聚类，且未增加原始聚类成本。
原文摘要 · Abstract (English)
Clustering is a well-studied unsupervised learning task that aims to partition data points into a number of clusters. In many applications, these clusters correspond to real-world constructs (e.g., electoral districts, playlists, TV channels), where a group (e.g., social or demographic) benefits only if it reaches a minimum level of representation in the cluster (e.g., 50% to elect their preferred candidate). In this paper, we study the k-means and k-medians clustering problems under the additional fairness constraint that each group must attain a minimum level of representation in at least a specified number of clusters. We formulate this problem as a mixed-integer (nonlinear) optimization problem and propose an alternating minimization algorithm, called MiniReL, to solve it. Although incorporating fairness constraints results in an NP-hard assignment problem within the MiniReL algorithm, we present several heuristic strategies that make the approach practical even for large datasets. Numerical results demonstrate that our method yields fair clusters without increasing clustering cost across standard benchmark datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。