論文の概要: Diversity-aware clustering: Computational Complexity and Approximation Algorithms

• arxiv url: http://arxiv.org/abs/2401.05502v1
• Date: Wed, 10 Jan 2024 19:01:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-13 02:22:22.128729
• Title: Diversity-aware clustering: Computational Complexity and Approximation Algorithms
• Title（参考訳）: 多様性を考慮したクラスタリング:計算複雑性と近似アルゴリズム
• Authors: Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, Aristides Gionis
• Abstract要約: 本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。 クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。 近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 19.67390261007849
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study diversity-aware clustering problems where the data points are associated with multiple attributes resulting in intersecting groups. A clustering solution need to ensure that a minimum number of cluster centers are chosen from each group while simultaneously minimizing the clustering objective, which can be either $k$-median, $k$-means or $k$-supplier. We present parameterized approximation algorithms with approximation ratios $1+ \frac{2}{e}$, $1+\frac{8}{e}$ and $3$ for diversity-aware $k$-median, diversity-aware $k$-means and diversity-aware $k$-supplier, respectively. The approximation ratios are tight assuming Gap-ETH and FPT $\neq$ W[2]. For fair $k$-median and fair $k$-means with disjoint faicility groups, we present parameterized approximation algorithm with approximation ratios $1+\frac{2}{e}$ and $1+\frac{8}{e}$, respectively. For fair $k$-supplier with disjoint facility groups, we present a polynomial-time approximation algorithm with factor $3$, improving the previous best known approximation ratio of factor $5$.
• Abstract（参考訳）: 本研究では,データポイントが複数の属性に関連付けられ,相互に交わるグループとなる,多様性を考慮したクラスタリング問題について検討する。 クラスタリングソリューションでは、各グループから最小数のクラスタセンターを選択すると同時に、クラスタリングの目標を最小化する必要があります。 パラメータ化近似アルゴリズムは,それぞれ1+ \frac{2}{e}$, $1+\frac{8}{e}$, $3$ for diversity-aware $k$-median, diversity-aware $k$-means, diversity-aware $k$-supplierを示す。 近似比は Gap-ETH と FPT $\neq$ W[2] を強く仮定する。 弱気性群を持つ公正な$k$-median と公正な$k$-means に対して,近似比が 1+\frac{2}{e}$ と 1+\frac{8}{e}$ のパラメータ化近似アルゴリズムを提案する。 不連続な機能群を持つ公正な$k$-supplierに対して、多項式時間近似アルゴリズムを3ドルで示し、これまでの最もよく知られた5ドル近似比を改善した。

関連論文リスト

• 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)
• 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)
• Are Easy Data Easy (for K-Means) [0.0]
  本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。 シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
  論文  参考訳（メタデータ） (2023-08-02T09:40:19Z)
• 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)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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