論文の概要: Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
- arxiv url: http://arxiv.org/abs/2411.01115v1
- Date: Sat, 02 Nov 2024 02:50:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:49:49.688687
- Title: Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
- Title（参考訳）: Relax and Merge: 公平な$k$-Meansと$k$-sparse Wasserstein Barycenter問題を解決するためのシンプルで効果的なフレームワーク
- Authors: Shihong Song, Guanlin Mo, Qingyuan Yang, Hu Ding,
- Abstract要約: 複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
- 参考スコア（独自算出の注目度）: 8.74967598360817
- License:
- Abstract: The fairness of clustering algorithms has gained widespread attention across various areas, including machine learning, In this paper, we study fair $k$-means clustering in Euclidean space. Given a dataset comprising several groups, the fairness constraint requires that each cluster should contain a proportion of points from each group within specified lower and upper bounds. Due to these fairness constraints, determining the optimal locations of $k$ centers is a quite challenging task. We propose a novel ``Relax and Merge'' framework that returns a $(1+4\rho + O(\epsilon))$-approximate solution, where $\rho$ is the approximate ratio of an off-the-shelf vanilla $k$-means algorithm and $O(\epsilon)$ can be an arbitrarily small positive number. If equipped with a PTAS of $k$-means, our solution can achieve an approximation ratio of $(5+O(\epsilon))$ with only a slight violation of the fairness constraints, which improves the current state-of-the-art approximation guarantee. Furthermore, using our framework, we can also obtain a $(1+4\rho +O(\epsilon))$-approximate solution for the $k$-sparse Wasserstein Barycenter problem, which is a fundamental optimization problem in the field of optimal transport, and a $(2+6\rho)$-approximate solution for the strictly fair $k$-means clustering with no violation, both of which are better than the current state-of-the-art methods. In addition, the empirical results demonstrate that our proposed algorithm can significantly outperform baseline approaches in terms of clustering cost.
- Abstract（参考訳）: クラスタリングアルゴリズムの公正さは、機械学習を含む様々な分野において広く注目を集めており、本稿ではユークリッド空間におけるフェア$k$-meansクラスタリングについて検討する。
複数のグループからなるデータセットが与えられたとき、公正性制約は、各クラスタが指定された下限と上限内にある各グループからの点の割合を含む必要がある。
このような公正な制約のため、$k$ Centerの最適位置を決定することは、非常に難しい作業である。
1+4\rho + O(\epsilon))$-approximate solution, ここで、$\rho$はオフザシェルのvanilla $k$-meansアルゴリズムの近似比であり、$O(\epsilon)$は任意に小さな正数である。
PTASが$k$-meansである場合、我々のソリューションは、フェアネス制約をわずかに違反するだけで、現在の最先端の近似保証を改善することで、$(5+O(\epsilon))$の近似比を達成できる。
さらに、我々のフレームワークを用いて、最適輸送の分野における基本的な最適化問題である$k$スパース・ワッサーシュタイン・バリーセンター問題に対する$(1+4\rho +O(\epsilon))$-approximateソリューションと、厳密な公正な$k$-meansクラスタリングに対する$(2+6\rho)$-approximateソリューションも得られる。
さらに,提案アルゴリズムは,クラスタリングコストにおいて,ベースラインアプローチを著しく上回り得ることを示す。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - 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) - Diversity-aware clustering: Computational Complexity and Approximation
Algorithms [19.67390261007849]
本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。
クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。
近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-10T19:01:05Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - 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) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳（メタデータ） (2022-02-05T01:59:09Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳（メタデータ） (2020-02-16T22:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。