論文の概要: Fair Minimum Representation Clustering
- arxiv url: http://arxiv.org/abs/2302.03151v1
- Date: Mon, 6 Feb 2023 23:16:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 18:04:38.282174
- Title: Fair Minimum Representation Clustering
- Title（参考訳）: 公正な最小表現クラスタリング
- Authors: Connor Lawless, Oktay Gunluk
- Abstract要約: クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。
一般的な$k$-meansアルゴリズムであるロイドのアルゴリズムが不公平な結果をもたらすことを示す。
フェアネス制約を直接組み込む、ミニReLと呼ばれるロイドのアルゴリズムの変種を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is an unsupervised learning task that aims to partition data into
a set of clusters. In many applications, these clusters correspond to
real-world constructs (e.g. electoral districts) whose benefit can only be
attained by groups when they reach a minimum level of representation (e.g. 50\%
to elect their desired candidate). This paper considers the problem of
performing k-means clustering while ensuring groups (e.g. demographic groups)
have that minimum level of representation in a specified number of clusters. We
show that the popular $k$-means algorithm, Lloyd's algorithm, can result in
unfair outcomes where certain groups lack sufficient representation past the
minimum threshold in a proportional number of clusters. We formulate the
problem through a mixed-integer optimization framework and present a variant of
Lloyd's algorithm, called MiniReL, that directly incorporates the fairness
constraints. We show that incorporating the fairness criteria leads to a
NP-Hard sub-problem within Lloyd's algorithm, but we provide computational
approaches that make the problem tractable for even large datasets. Numerical
results show that the approach is able to create fairer clusters with
practically no increase in the k-means clustering cost across standard
benchmark datasets.
- Abstract（参考訳）: クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。
多くの応用において、これらのクラスターは、最小の表現レベル(例えば、望ましい候補を選ぶために50\%)に達するとグループによってのみ得られる実世界の構成(例えば、選挙区)に対応している。
本稿では、グループ(例えば人口統計群)が指定されたクラスタ数の最小表現レベルを持つことを保証しながら、k平均クラスタリングを行うことの問題点を考察する。
人気の$k$-meansアルゴリズムであるロイドのアルゴリズムは、あるグループが比例数で最小のしきい値を超える十分な表現を欠くような不公平な結果をもたらす可能性がある。
混合整数最適化フレームワークを用いて問題を定式化し、フェアネス制約を直接組み込んだLloydのアルゴリズムであるMiniReLを提案する。
公平性基準を組み込むことで、LydのアルゴリズムにNP-Hardのサブプロブレムが生じることを示すが、大きなデータセットでも問題を引き出すことができる計算手法を提案する。
数値的な結果は、標準的なベンチマークデータセット間でk平均クラスタリングコストを実質的に増加させることなく、より公平なクラスタを作成することができることを示している。
関連論文リスト
- Fair Minimum Representation Clustering via Integer Programming [0.6906005491572401]
クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。
本稿では,各群が最小表現レベルを持つ必要があるという制約を伴って,k平均とkメダニアンのクラスタリング問題を考察する。
フェアネス制約を直接組み込んだ,MiniReLと呼ばれる交代最小化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-04T00:13:40Z) - 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) - Cluster-level Group Representativity Fairness in $k$-means Clustering [3.420467786581458]
クラスタリングアルゴリズムは、異なるグループが異なるクラスタ内で不利になるようにクラスタを生成することができる。
我々は,古典的アルゴリズムに先駆けて,セントロイドクラスタリングパラダイムに基づくクラスタリングアルゴリズムを開発した。
本手法はクラスタレベルの表現性フェアネスを,クラスタのコヒーレンスに低い影響で向上させるのに有効であることを示す。
論文 参考訳（メタデータ） (2022-12-29T22:02:28Z) - 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) - 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) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Socially Fair k-Means Clustering [3.3409719900340256]
我々は、異なるグループに対して公平なコストを提供するクラスタセンターを選択するための、公平なk平均目標とアルゴリズムを提案する。
このアルゴリズムであるFair-Lloydは、ロイドのk平均に対する修正であり、その単純さ、効率、安定性を継承している。
論文 参考訳（メタデータ） (2020-06-17T18:05:17Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。