論文の概要: Fair Clustering with Minimum Representation Constraints

• arxiv url: http://arxiv.org/abs/2409.02963v2
• Date: Wed, 24 Sep 2025 17:47:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-25 20:53:19.454851
• Title: Fair Clustering with Minimum Representation Constraints
• Title（参考訳）: 最小表現制約による公正クラスタリング
• Authors: Connor Lawless, Oktay Gunluk,
• Abstract要約: 我々は、各群が少なくとも指定された数のクラスタにおいて、最小レベルの表現を達成しなければならないという追加の公平性制約の下で、k平均およびkメディアンクラスタリング問題について検討する。 大規模なデータセットであっても,このアプローチを実用的にするための戦略をいくつか提示する。
• 参考スコア（独自算出の注目度）: 2.707154152696381
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: クラスタリングは、データポイントを多数のクラスタに分割することを目的とした、よく研究された教師なしの学習タスクである。 多くのアプリケーションにおいて、これらのクラスタは実世界の構成(例えば、選挙地区、プレイリスト、テレビチャンネル)に対応しており、グループ(例えば、社会的または人口統計学的)がクラスタ内の最小レベルの表現(例えば、好まれる候補を選択するのに50%)に達すると、そのグループ(例えば、社会的または人口的)が恩恵を受ける。 本稿では,k平均とkメダニアンのクラスタリング問題を,各群が少なくとも指定された数のクラスタにおいて最小レベルの表現を達成しなければならないという追加の公平性制約の下で検討する。 我々はこの問題を混合整数(非線形)最適化問題として定式化し、MiniReLと呼ばれる交互最小化アルゴリズムを提案する。 公平性制約を組み込むと、MiniReLアルゴリズム内のNP-hard代入問題が発生するが、大規模なデータセットに対してもアプローチを実用的にするためのいくつかのヒューリスティック戦略を示す。 提案手法は,標準ベンチマークデータセット間のクラスタリングコストを増大させることなく,公平なクラスタを生成することを示す。

関連論文リスト

• Towards Fair Representation: Clustering and Consensus [1.7243216387069678]
  特定の保護された属性に関して、代表的であるだけでなく公平でもあるコンセンサスクラスタリングを見つけます。 調査の一環として,既存のクラスタリングを最小限に修正して公平性を実現する方法について検討した。 我々は,同値なグループ表現とニア線形時間定数係数近似アルゴリズムを用いたデータセットの最適アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-06-10T10:33:21Z)
• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  我々は,未知の地下構造クラスタリングを用いて,半教師付き環境で問題を研究する。 本稿では,クラスタリングアルゴリズムの精度向上のためのサイズ一般化の概念を提案する。 データセット全体においてどのアルゴリズムが最適かを特定するために、データの5%をサブサンプルとして使用しています。
  論文  参考訳（メタデータ） (2024-02-22T06:53:35Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Fair Minimum Representation Clustering [0.0]
  クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。 一般的な$k$-meansアルゴリズムであるロイドのアルゴリズムが不公平な結果をもたらすことを示す。 フェアネス制約を直接組み込む、ミニReLと呼ばれるロイドのアルゴリズムの変種を示す。
  論文  参考訳（メタデータ） (2023-02-06T23:16:38Z)
• Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
  センターベースのクラスタリングと線形サブスペースクラスタリングは、現実世界のデータを小さなクラスタに分割する一般的なテクニックである。 異なる敏感なグループに対する1点当たりのクラスタリングコストは、公平性に関連する害をもたらす可能性がある。 本稿では,社会的に公平なセンタベースのクラスタリングと線形サブスペースクラスタリングを解決するための統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-08-22T07:10:17Z)
• Fair Labeled Clustering [28.297893914525517]
  クラスタリングのダウンストリーム適用と,そのような設定に対してグループフェアネスをどのように確保するかを検討する。 このような問題に対するアルゴリズムを提供し、グループフェアクラスタリングにおけるNPハードのアルゴリズムとは対照的に、効率的な解が可能であることを示す。 また、距離空間における中心位置に関係なく、意思決定者が自由にクラスタにラベルを割り当てることができるような、モチベーションのよい代替設定についても検討する。
  論文  参考訳（メタデータ） (2022-05-28T07:07:12Z)
• Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints [0.0]
  均等なクラスタリングは、密度も期待されるクラスの数にも依存せず、相似性の閾値にも依存します。 このクラスタリング問題に対する様々な実践的ソリューション間のトレードオフを特定するために,適切なクラスタリングアルゴリズムをレビューし,評価する。
  論文  参考訳（メタデータ） (2021-09-28T12:02:18Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• You Never Cluster Alone [150.94921340034688]
  我々は、主流のコントラスト学習パラダイムをクラスタレベルのスキームに拡張し、同じクラスタに属するすべてのデータが統一された表現に寄与する。 分類変数の集合をクラスタ化代入信頼度として定義し、インスタンスレベルの学習トラックとクラスタレベルの学習トラックを関連付ける。 代入変数を再パラメータ化することで、TCCはエンドツーエンドでトレーニングされる。
  論文  参考訳（メタデータ） (2021-06-03T14:59:59Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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