論文の概要: A Scalable Algorithm for Individually Fair K-means Clustering
- arxiv url: http://arxiv.org/abs/2402.06730v1
- Date: Fri, 9 Feb 2024 19:01:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 19:29:48.159555
- Title: A Scalable Algorithm for Individually Fair K-means Clustering
- Title（参考訳）: 個別に公平なK平均クラスタリングのためのスケーラブルアルゴリズム
- Authors: MohammadHossein Bateni and Vincent Cohen-Addad and Alessandro Epasto
and Silvio Lattanzi
- Abstract要約: Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
- 参考スコア（独自算出の注目度）: 77.93955971520549
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a scalable algorithm for the individually fair ($p$,
$k$)-clustering problem introduced by Jung et al. and Mahabadi et al. Given $n$
points $P$ in a metric space, let $\delta(x)$ for $x\in P$ be the radius of the
smallest ball around $x$ containing at least $n / k$ points. A clustering is
then called individually fair if it has centers within distance $\delta(x)$ of
$x$ for each $x\in P$. While good approximation algorithms are known for this
problem no efficient practical algorithms with good theoretical guarantees have
been presented. We design the first fast local-search algorithm that runs in
~$O(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Then we
show empirically that not only is our algorithm much faster than prior work,
but it also produces lower-cost solutions.
- Abstract（参考訳）: Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
計量空間において$n$ポイント$P$を与えられたとき、$\delta(x)$ for $x\in P$を、少なくとも$n / k$ポイントを含む$x$の周りの最小球の半径とする。
クラスタリングは、各$x\in P$に対して$x$の距離$\delta(x)$の中心を持つ場合、個別にフェアと呼ばれる。
優れた近似アルゴリズムが知られているが、理論的な保証が良い効率的な実用的なアルゴリズムは提示されていない。
我々は ~$O(nk^2)$ 時間で動作し、bicriteria $(O(1), 6)$近似を得る最初の高速局所探索アルゴリズムを設計する。
そして、我々のアルゴリズムが以前の作業よりもはるかに高速であるだけでなく、低コストのソリューションを生み出すことを実証的に示す。
関連論文リスト
- Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Constant-Factor Approximation Algorithms for Socially Fair
$k$-Clustering [12.545909976356528]
社会的に公正な$(ell_p, k)$-clustering問題$m$groupに対する近似アルゴリズムについて検討する。
a-time $(5+2sqrt6)pimation at most $k+m$center (2) a $(5+2sqrt6)pimation with $k$center in time $n2O(p)cdot m2$, (3) a $ 15+6sqrt6)p$ approximation with $k$center in。
論文 参考訳（メタデータ） (2022-06-22T16:57:17Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Better Algorithms for Individually Fair $k$-Clustering [4.936817539835045]
Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
論文 参考訳（メタデータ） (2021-06-23T04:16:46Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。