最小表現制約付き公平クラスタリング
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2409.02963v2 発表種別：差し替え
要旨：クラスタリングは、データ点を複数のクラスタに分割することを目的とした、よく研究されている教師なし学習タスクである。多くの応用において、これらのクラスタは現実世界の構成要素（例えば、選挙区、プレイリスト、テレビチャンネル）に対応し、ある集団（例えば、社会集団または人口統計学的集団）は、クラスタ内における最小限の代表レベル（例えば、候補者を当選させるための50％）に達した場合にのみ恩恵を受ける。本論文では、各集団が少なくとも指定された数のクラスタにおいて最小限の代表レベルを達成するという追加の公平性制約の下でのk-meansとk-mediansクラスタリング問題を研究する。この問題を混合整数（非線形）最適化問題として定式化し、それを解くための交互最小化アルゴリズムであるMiniReLを提案する。公平性制約を組み込むとMiniReLアルゴリズム内でNP困難な割当問題が生じるが、大規模データセットに対してもアプローチを実用的にするいくつかのヒューリスティック戦略を示す。数値結果は、標準的なベンチマークデータセット全体でクラスタリングコストを増やすことなく、本手法が公平なクラスタを生成することを示している。
原文（英語）を表示
Title (EN): Fair Clustering with Minimum Representation Constraints
arXiv:2409.02963v2 Announce Type: replace-cross
Abstract: 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.
Published: 2025-09-24 19:00 UTC