論文の概要: Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications

• arxiv url: http://arxiv.org/abs/2511.11539v1
• Date: Fri, 14 Nov 2025 18:19:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.756172
• Title: Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications
• Title（参考訳）: フェアクラスタリングを複数グループに一般化するアルゴリズムと応用
• Authors: Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das, Tien-Long Nguyen,
• Abstract要約: 本研究は,グループ数(2以上)の任意の設定に対して,最良クラスタリング問題の研究を一般化する。 任意のサイズの複数グループを効率的に扱うニア線形時間近似アルゴリズムを提案する。 我々は,複数のグループ(2つ以上のグループ)を含むEmphfairコンセンサスクラスタリング問題に対して,近似アルゴリズムを初めて提供する。
• 参考スコア（独自算出の注目度）: 1.6398837165722515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is a fundamental task in machine learning and data analysis, but it frequently fails to provide fair representation for various marginalized communities defined by multiple protected attributes -- a shortcoming often caused by biases in the training data. As a result, there is a growing need to enhance the fairness of clustering outcomes, ideally by making minimal modifications, possibly as a post-processing step after conventional clustering. Recently, Chakraborty et al. [COLT'25] initiated the study of \emph{closest fair clustering}, though in a restricted scenario where data points belong to only two groups. In practice, however, data points are typically characterized by many groups, reflecting diverse protected attributes such as age, ethnicity, gender, etc. In this work, we generalize the study of the \emph{closest fair clustering} problem to settings with an arbitrary number (more than two) of groups. We begin by showing that the problem is NP-hard even when all groups are of equal size -- a stark contrast with the two-group case, for which an exact algorithm exists. Next, we propose near-linear time approximation algorithms that efficiently handle arbitrary-sized multiple groups, thereby answering an open question posed by Chakraborty et al. [COLT'25]. Leveraging our closest fair clustering algorithms, we further achieve improved approximation guarantees for the \emph{fair correlation clustering} problem, advancing the state-of-the-art results established by Ahmadian et al. [AISTATS'20] and Ahmadi et al. [2020]. Additionally, we are the first to provide approximation algorithms for the \emph{fair consensus clustering} problem involving multiple (more than two) groups, thus addressing another open direction highlighted by Chakraborty et al. [COLT'25].
• Abstract（参考訳）: クラスタリングは機械学習とデータ分析の基本的なタスクであるが、複数の保護された属性によって定義されたさまざまな辺境化コミュニティに対して公平な表現を提供することがしばしば失敗する。 結果として、クラスタリング結果の公平性を高める必要性が高まっている。理想的には、最小限の変更を行うことによって、おそらくは、従来のクラスタリングの後の処理ステップとして。 最近、Chakraborty et al [COLT'25] は、データポイントが2つのグループにしか属さない制限されたシナリオにおいて、 \emph{closest fair clustering} の研究を開始した。 しかし実際には、データポイントは多くのグループによって特徴づけられ、年齢、民族、性別などの多様な保護された属性を反映している。 本研究は,任意の数の群(2つ以上)で設定された設定に対して,emph{closest fair clustering}問題の研究を一般化する。 まず、すべての群が等しい大きさであってもNPハードであることが示され、これは正確なアルゴリズムが存在する二群の場合とは全く対照的である。 次に,Chakraborty et al [COLT'25] が提案するオープンな疑問に答えるため,任意のサイズの複数グループを効率的に扱うニア線形時間近似アルゴリズムを提案する。 Ahmadian et al [AISTATS'20] と Ahmadi et al [2020] によって確立された最先端の成果を推し進める。 さらに、我々は、複数の(2つ以上の)群を含む \emph{fair consensus clustering} 問題に対する近似アルゴリズムを初めて提供し、Chakraborty et al [COLT'25] によって強調された別の開放方向に対処する。

関連論文リスト

• Towards Fair Representation: Clustering and Consensus [1.7243216387069678]
  特定の保護された属性に関して、代表的であるだけでなく公平でもあるコンセンサスクラスタリングを見つけます。 調査の一環として,既存のクラスタリングを最小限に修正して公平性を実現する方法について検討した。 我々は,同値なグループ表現とニア線形時間定数係数近似アルゴリズムを用いたデータセットの最適アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-06-10T10:33:21Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Fair Algorithms for Hierarchical Agglomerative Clustering [17.66340013352806]
  Hierarchical Agglomerative Clustering (HAC)アルゴリズムは、現代のデータサイエンスで広く利用されている。 たとえデータセットが特定の保護されたグループに対するバイアスを含むとしても、これらのアルゴリズムが公平であることを保証することが不可欠である。 公平性制約を強制するHACを行うための公正アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-07T01:41:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。