論文の概要: On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their
Applications
- arxiv url: http://arxiv.org/abs/2007.10137v1
- Date: Mon, 20 Jul 2020 14:15:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 14:32:30.049919
- Title: On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their
Applications
- Title（参考訳）: 計量空間とユークリッド空間におけるフェアクラスタリングのためのコアセットとその応用について
- Authors: Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov
- Abstract要約: ランダムサンプリングに基づくフェアクラスタリングのための新しいコアセットの構築を提案する。
ユークリッド空間に対して、サイズが指数関数的に次元に依存しない最初のコアセットを得る。
新しいコアセット構成は、いくつかの新しい近似とストリーミングアルゴリズムの設計に役立つ。
- 参考スコア（独自算出の注目度）: 11.254051258449815
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fair clustering is a constrained variant of clustering where the goal is to
partition a set of colored points, such that the fraction of points of any
color in every cluster is more or less equal to the fraction of points of this
color in the dataset. This variant was recently introduced by Chierichetti et
al. [NeurIPS, 2017] in a seminal work and became widely popular in the
clustering literature. In this paper, we propose a new construction of coresets
for fair clustering based on random sampling. The new construction allows us to
obtain the first coreset for fair clustering in general metric spaces. For
Euclidean spaces, we obtain the first coreset whose size does not depend
exponentially on the dimension. Our coreset results solve open questions
proposed by Schmidt et al. [WAOA, 2019] and Huang et al. [NeurIPS, 2019]. The
new coreset construction helps to design several new approximation and
streaming algorithms. In particular, we obtain the first true
constant-approximation algorithm for metric fair clustering, whose running time
is fixed-parameter tractable (FPT). In the Euclidean case, we derive the first
$(1+\epsilon)$-approximation algorithm for fair clustering whose time
complexity is near-linear and does not depend exponentially on the dimension of
the space. Besides, our coreset construction scheme is fairly general and gives
rise to coresets for a wide range of constrained clustering problems. This
leads to improved constant-approximations for these problems in general metrics
and near-linear time $(1+\epsilon)$-approximations in the Euclidean metric.
- Abstract（参考訳）: フェアクラスタリング(fair clustering)は、クラスタ内の任意の色のポイントの割合が、データセット内のこの色のポイントの分数にほぼ等しいように、色付きポイントの集合を分割することを目的とした、クラスタリングの制約付き変種である。
この変種はChierichettiらによって最近導入された。
[NeurIPS, 2017]は叙述的な作品であり、クラスタリング文学で広く普及した。
本稿では,ランダムサンプリングに基づく公平なクラスタリングのためのコアセットの新規構築を提案する。
新しい構成により、一般計量空間における公正クラスタリングのための最初のコアセットが得られる。
ユークリッド空間に対して、サイズが指数関数的に次元に依存しない最初のコアセットを得る。
私たちのコアセットの結果はschmidtらによって提案されたオープンな質問を解決します。
[WAOA, 2019]とHuangら。
[NeurIPS, 2019]
新しいコアセット構成は、いくつかの新しい近似とストリーミングアルゴリズムの設計に役立つ。
特に,実行時間が固定パラメータトラクタブル(FPT)である計量フェアクラスタリングのための,最初の真の定数近似アルゴリズムを得る。
ユークリッドの場合、時間複雑性がほぼ直線であり、空間の次元に指数関数的に依存しないフェアクラスタリングのための最初の$(1+\epsilon)$-approximationアルゴリズムを導出する。
さらに、コアセットの構成スキームは比較的一般的であり、幅広い制約付きクラスタリング問題に対してコアセットが発生する。
これにより、一般の計量におけるこれらの問題に対する定数近似やユークリッド計量における近線形時間(1+\epsilon)$近似が改善される。
関連論文リスト
- Approximating Fair $k$-Min-Sum-Radii in Euclidean Space [1.6369404745833038]
定数$k$の場合の任意の次元のユークリッド空間における$k$-min-sum-radii問題を研究する。
定数$k$の場合の任意の次元のユークリッド空間における公平な$k$-min-sum-radii問題に対するPTASを提案する。
論文 参考訳（メタデータ） (2023-09-02T06:01:59Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - An enhanced method of initial cluster center selection for K-means
algorithm [0.0]
K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。
Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。
We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
論文 参考訳（メタデータ） (2022-10-18T00:58:50Z) - New Coresets for Projective Clustering and Applications [34.82221047030618]
点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。
我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
論文 参考訳（メタデータ） (2022-03-08T19:50:27Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。
我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
論文 参考訳（メタデータ） (2021-04-28T13:35:17Z) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳（メタデータ） (2020-09-10T05:21:20Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳（メタデータ） (2020-05-02T10:39:26Z) - Fair Correlation Clustering [18.00619071013106]
本稿では,各ノードが色を持つ相関クラスタリング問題に対して,公平性制約の2つのバリエーションを検討する。
本研究では,実世界のデータセットに対する実験的な評価により,公平なクラスタを生成するアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2020-02-10T02:59:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。