論文の概要: Individual Fairness for $k$-Clustering

• arxiv url: http://arxiv.org/abs/2002.06742v2
• Date: Mon, 21 Sep 2020 18:31:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 12:26:33.468972
• Title: Individual Fairness for $k$-Clustering
• Title（参考訳）: $k$-clusteringのための個人フェアネス
• Authors: Sepideh Mahabadi and Ali Vakilian
• Abstract要約: ローカル検索に基づく$k$-medianと$k$-meansのアルゴリズム。 公平な$k$-clusteringのために、bicriteria近似の取得方法を示す。
• 参考スコア（独自算出の注目度）: 16.988236398003068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a local search based algorithm for $k$-median and $k$-means (and more generally for any $k$-clustering with $\ell_p$ norm cost function) from the perspective of individual fairness. More precisely, for a point $x$ in a point set $P$ of size $n$, let $r(x)$ be the minimum radius such that the ball of radius $r(x)$ centered at $x$ has at least $n/k$ points from $P$. Intuitively, if a set of $k$ random points are chosen from $P$ as centers, every point $x\in P$ expects to have a center within radius $r(x)$. An individually fair clustering provides such a guarantee for every point $x\in P$. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible $k$-clustering with respect to this fairness condition. In this work, we show how to get a bicriteria approximation for fair $k$-clustering: The $k$-median ($k$-means) cost of our solution is within a constant factor of the cost of an optimal fair $k$-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor). Further, we complement our theoretical bounds with empirical evaluation.
• Abstract（参考訳）: 局所的な検索ベースのアルゴリズムを$k$-medianと$k$-means(より一般的には$k$-clustering with $\ell_p$ norm cost function)に対して、個人の公正性の観点から与える。 より正確には、ある点集合の$x$ に対して$P$ of size $n$ とすると、$r(x)$ を半径 $r(x)$ の球が$x$ に集中する最小半径とし、$P$ から少なくとも$n/k$ の点を持つ。 直観的には、一組の$k$ランダムポイントが中心として$p$から選択されると、すべての点$x\in p$ は半径 $r(x)$ 内に中心を持つことを期待する。 個別に公平なクラスタリングは、すべてのポイント$x\in p$の保証を提供する。 このフェアネスの概念は[jung et al., 2019]で導入され、このフェアネス条件に関して、ほぼ実現可能な$k$-clusteringを得る方法を示した。 本研究では,fair $k$-clusteringに対するbicriteria近似の取得方法を示す。 私たちのソリューションの$k$-median(k$-means)コストは,最適なfair $k$-clusteringのコストの一定要素の範囲内にあり,我々のソリューションはフェアネス条件(また定数係数内)をほぼ満足する。 さらに,理論的な境界を経験的評価で補完する。

関連論文リスト

• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
  この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。 特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
  論文  参考訳（メタデータ） (2023-09-17T01:45:13Z)
• Approximation Algorithms for Fair Range Clustering [14.380145034918158]
  本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。 目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。 特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
  論文  参考訳（メタデータ） (2023-06-11T21:18:40Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Improved Approximation Algorithms for Individually Fair Clustering [9.914246432182873]
  16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost。 我々のアプローチは、Kleindessnerらによって提案されたグループフェアネス要件により、個別に公平なクラスタリングからクラスタリングに還元されることを示唆している。
  論文  参考訳（メタデータ） (2021-06-26T15:22:52Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• FPT Approximation for Socially Fair Clustering [0.38073142980733]
  距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。 社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。 本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-12T11:53:18Z)
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center [31.936733991407134]
  本稿では,クラスタリング問題に対する公平性の新たな定義を提案する。 我々のモデルでは、各点$j$ は他の点の集合 $mathcalS_j$ を持ち、それ自身と似ていると知覚する。 我々は、$k$-centerの目的に対して、効率的かつ容易に実装可能な近似アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-09T22:52:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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