論文の概要: Generalized Reductions: Making any Hierarchical Clustering Fair and
Balanced with Low Cost
- arxiv url: http://arxiv.org/abs/2205.14198v1
- Date: Fri, 27 May 2022 19:04:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 17:53:13.669330
- Title: Generalized Reductions: Making any Hierarchical Clustering Fair and
Balanced with Low Cost
- Title（参考訳）: 一般化された削減:階層的クラスタリングを公平にし、低コストでバランスをとる
- Authors: Marina Knittel, John P. Dickerson, MohammadTaghi Hajiaghayi
- Abstract要約: 私たちは階層的クラスタリングの文脈で公平性を研究する最初の人です。
階層内の任意のレベルにわたって、公平性とクラスタバランスを保証するために、既存の階層的なクラスタリングを変更する方法を示す。
- 参考スコア（独自算出の注目度）: 34.633719851428054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental building block of modern statistical analysis
pipelines. Fair clustering has seen much attention from the machine learning
community in recent years. We are some of the first to study fairness in the
context of hierarchical clustering, after the results of Ahmadian et al. from
NeurIPS in 2020. We evaluate our results using Dasgupta's cost function,
perhaps one of the most prevalent theoretical metrics for hierarchical
clustering evaluation. Our work vastly improves the previous
$O(n^{5/6}poly\log(n))$ fair approximation for cost to a near polylogarithmic
$O(n^\delta poly\log(n))$ fair approximation for any constant $\delta\in(0,1)$.
This result establishes a cost-fairness tradeoff and extends to broader
fairness constraints than the previous work. We also show how to alter existing
hierarchical clusterings to guarantee fairness and cluster balance across any
level in the hierarchy.
- Abstract（参考訳）: クラスタリングは、最新の統計分析パイプラインの基本構成要素である。
公正なクラスタリングは、近年、機械学習コミュニティから多くの注目を集めている。
私たちは、2020年にNeurIPSからAhmadianらによって得られた結果に続いて、階層的クラスタリングの文脈でフェアネスを研究した最初の人です。
dasguptaのコスト関数(おそらく最も一般的な階層的クラスタリング評価の理論的指標の1つ)を用いて結果を評価した。
我々の研究は、これまでの$o(n^{5/6}poly\log(n))$フェア近似を、任意の定数$\delta\in(0,1)$に対してほぼ多対数な$o(n^\delta poly\log(n))$フェア近似に大幅に改善した。
この結果は、コストフェアネスのトレードオフを確立し、以前の作業よりも広い公正性の制約にまで拡張します。
また,既存の階層的クラスタリングを変更する方法を示し,階層内の任意のレベルにわたって公平性とクラスタバランスを保証する。
関連論文リスト
- Fair Polylog-Approximate Low-Cost Hierarchical Clustering [14.088810363740208]
公正な機械学習、特にクラスタリングの研究は、現代のインテリジェントシステムが提起した多くの倫理的論争から、近年重要になっている。
そこで,本研究では,真に多元論的に近似した低コストな階層クラスタリングを提案する。
論文 参考訳（メタデータ） (2023-11-21T10:20:34Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。
本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
論文 参考訳（メタデータ） (2021-08-13T03:03:56Z) - A New Notion of Individually Fair Clustering: $\alpha$-Equitable
$k$-Center [31.936733991407134]
本稿では,クラスタリング問題に対する公平性の新たな定義を提案する。
我々のモデルでは、各点$j$ は他の点の集合 $mathcalS_j$ を持ち、それ自身と似ていると知覚する。
我々は、$k$-centerの目的に対して、効率的かつ容易に実装可能な近似アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-09T22:52:00Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - KFC: A Scalable Approximation Algorithm for $k$-center Fair Clustering [6.09170287691728]
フェアクラスタリングの問題を$k-$centerの目的に基づいて検討する。
公平なクラスタリングでは、入力は$N$ポイントであり、それぞれが$l$保護されたグループの少なくとも1つに属している。
提案アルゴリズムは,過剰表現や低表現を伴わない優れたクラスタを見つけるのに有効である。
論文 参考訳（メタデータ） (2020-10-26T23:33:34Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。