論文の概要: The Fairness-Quality Trade-off in Clustering

• arxiv url: http://arxiv.org/abs/2408.10002v1
• Date: Mon, 19 Aug 2024 13:57:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-20 16:03:38.477805
• Title: The Fairness-Quality Trade-off in Clustering
• Title（参考訳）: クラスタリングにおける公正-品質トレードオフ
• Authors: Rashida Hakim, Ana-Andreea Stoica, Christos H. Papadimitriou, Mihalis Yannakakis,
• Abstract要約: クラスタリング問題における品質と公平性の完全なトレードオフ曲線をトレースする新しいアルゴリズムを提案する。 本研究は, 先行研究における特例のほとんどを包含する2つの一般クラスにおいて, 公平性と品質に関するすべての目的を取り扱う。 また、各クラスタ内の2つのグループ間の不均衡の和を最小化する。
• 参考スコア（独自算出の注目度）: 2.797813058568041
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Fairness in clustering has been considered extensively in the past; however, the trade-off between the two objectives -- e.g., can we sacrifice just a little in the quality of the clustering to significantly increase fairness, or vice-versa? -- has rarely been addressed. We introduce novel algorithms for tracing the complete trade-off curve, or Pareto front, between quality and fairness in clustering problems; that is, computing all clusterings that are not dominated in both objectives by other clusterings. Unlike previous work that deals with specific objectives for quality and fairness, we deal with all objectives for fairness and quality in two general classes encompassing most of the special cases addressed in previous work. Our algorithm must take exponential time in the worst case as the Pareto front itself can be exponential. Even when the Pareto front is polynomial, our algorithm may take exponential time, and we prove that this is inevitable unless P = NP. However, we also present a new polynomial-time algorithm for computing the entire Pareto front when the cluster centers are fixed, and for perhaps the most natural fairness objective: minimizing the sum, over all clusters, of the imbalance between the two groups in each cluster.
• Abstract（参考訳）: クラスタリングの公平性は過去にも広く考慮されてきたが、この2つの目標のトレードオフ — 例えば、クラスタリングの品質をわずかに犠牲にして、公正性を著しく向上させることができるのか、あるいはその逆なのか? 対策はめったに行われていない。 我々は、クラスタリング問題における品質と公平性、すなわち、他のクラスタリングによって両目的に支配されない全てのクラスタリングの計算の間に、完全なトレードオフ曲線(Paretofront)をトレースする新しいアルゴリズムを導入する。 品質と公平性に関する特定の目的を取り扱う以前の研究とは異なり、我々は、以前の研究で対処された特別な事例のほとんどを含む2つの一般的なクラスにおいて、公正性と品質に関するすべての目的を扱う。 私たちのアルゴリズムは、パレートフロント自体が指数関数となるため、最悪の場合指数関数的な時間を要する。 パレートフロントが多項式である場合でも、我々のアルゴリズムは指数関数的な時間を要し、P = NP でない限りこれは避けられないことを証明している。 しかし、クラスタセンターが固定されたときにパレートフロント全体を計算するための新しい多項式時間アルゴリズムや、おそらく最も自然なフェアネスの目的として、各クラスタ内の2つのグループ間の不均衡の和を最小化することを提案する。

関連論文リスト

• Doubly Constrained Fair Clustering [11.11449872883085]
  Group Fairness (GF) と Diversity in Center Selection (DS) は、クラスタリングにおける最も顕著な人口統計学的表現フェアネスの概念である。 1つの制約 (GF または DS のみ) に対して定数近似アルゴリズムが与えられた場合、両方の制約を同時に満たす定数近似解が得られることを示す。 GF と DS は、他の距離に基づくフェアネスの概念の集合と相容れないことを示す。
  論文  参考訳（メタデータ） (2023-05-31T01:04:55Z)
• Proportionally Representative Clustering [17.5359577544947]
  本稿では,クラスタリング問題を対象とした新しい公理比例代表フェアネス(PRF)を提案する。 我々のフェアネスの概念は、既存のフェアクラスタリングアルゴリズムで満たされていない。 制約のない設定に対する我々のアルゴリズムは、よく研究されたプロポーショナルフェアネス(PF)の公理に対する最初の既知時間近似アルゴリズムでもある。
  論文  参考訳（メタデータ） (2023-04-27T02:01:24Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Feature-based Individual Fairness in k-Clustering [14.847868952138795]
  公平性の制約を確保しつつ一組の点をクラスタリングする問題を考察する。 我々は、必ずしもクラスタリングに使用されない特徴に基づいて、kクラスタリングにおける個別の公平性という新しい概念を導入する。
  論文  参考訳（メタデータ） (2021-09-09T20:42:02Z)
• Efficient Algorithms For Fair Clustering with a New Fairness Notion [5.21410307583181]
  我々は、Chierichettiらによって最初に導入されたフェアクラスタリングの問題を再考する。 既存のクラスタリングのソリューションはスケーラビリティが低いか、クラスタリングの目的と公平性のトレードオフを最適に達成できないかのいずれかです。 バランス特性を厳密に一般化し、細粒度効率とフェアネストレードオフを可能にする、$tau$-fair Fairnessと呼ばれる新しいフェアネスの概念を提案する。
  論文  参考訳（メタデータ） (2021-09-02T04:52:49Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。 本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
  論文  参考訳（メタデータ） (2021-08-10T14:46:17Z)
• You Never Cluster Alone [150.94921340034688]
  我々は、主流のコントラスト学習パラダイムをクラスタレベルのスキームに拡張し、同じクラスタに属するすべてのデータが統一された表現に寄与する。 分類変数の集合をクラスタ化代入信頼度として定義し、インスタンスレベルの学習トラックとクラスタレベルの学習トラックを関連付ける。 代入変数を再パラメータ化することで、TCCはエンドツーエンドでトレーニングされる。
  論文  参考訳（メタデータ） (2021-06-03T14:59:59Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• A Pairwise Fair and Community-preserving Approach to k-Center Clustering [34.386585230600716]
  クラスタリングは多くのアプリケーションで機械学習の基本的な問題である。 クラスタリング設定,ペアワイズフェアネス,コミュニティ保存の2つの新しいフェアネスを定義した。
  論文  参考訳（メタデータ） (2020-07-14T22:32:27Z)
• Fair Hierarchical Clustering [92.03780518164108]
  従来のクラスタリングにおける過剰表現を緩和する公平性の概念を定義する。 我々のアルゴリズムは、目的に対して無視できない損失しか持たない、公平な階層的なクラスタリングを見つけることができることを示す。
  論文  参考訳（メタデータ） (2020-06-18T01:05:11Z)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。 提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
  論文  参考訳（メタデータ） (2020-04-01T13:39:37Z)

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

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