論文の概要: Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
- arxiv url: http://arxiv.org/abs/2410.12913v1
- Date: Wed, 16 Oct 2024 18:00:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-18 13:23:09.623183
- Title: Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
- Title（参考訳）: データ要約のための公正クラスタリング: 近似アルゴリズムの改善と複雑度インサイト
- Authors: Ameet Gadekar, Aristides Gionis, Suhas Thejaswi,
- Abstract要約: 一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
- 参考スコア（独自算出の注目度）: 16.120911591795295
- License:
- Abstract: Data summarization tasks are often modeled as $k$-clustering problems, where the goal is to choose $k$ data points, called cluster centers, that best represent the dataset by minimizing a clustering objective. A popular objective is to minimize the maximum distance between any data point and its nearest center, which is formalized as the $k$-center problem. While in some applications all data points can be chosen as centers, in the general setting, centers must be chosen from a predefined subset of points, referred as facilities or suppliers; this is known as the $k$-supplier problem. In this work, we focus on fair data summarization modeled as the fair $k$-supplier problem, where data consists of several groups, and a minimum number of centers must be selected from each group while minimizing the $k$-supplier objective. The groups can be disjoint or overlapping, leading to two distinct problem variants each with different computational complexity. We present $3$-approximation algorithms for both variants, improving the previously known factor of $5$. For disjoint groups, our algorithm runs in polynomial time, while for overlapping groups, we present a fixed-parameter tractable algorithm, where the exponential runtime depends only on the number of groups and centers. We show that these approximation factors match the theoretical lower bounds, assuming standard complexity theory conjectures. Finally, using an open-source implementation, we demonstrate the scalability of our algorithms on large synthetic datasets and assess the price of fairness on real-world data, comparing solution quality with and without fairness constraints.
- Abstract（参考訳）: データ要約タスクは、しばしば$k$クラスタリング問題としてモデル化され、クラスタセンターと呼ばれる、クラスタリングの目的を最小化することでデータセットを最も多く表現する、$k$データポイントを選択することが目標である。
一般的な目的は、任意のデータポイントと最も近い中心の間の最大距離を最小化することであり、これは$k$-center問題として形式化されている。
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤと呼ばれる、予め定義されたポイントのサブセットからセンタを選択する必要がある。
本研究では,複数のグループから構成される公平な$k$-supplier問題としてモデル化された公平なデータ要約に着目し,各グループから最小限のセンターを選択するとともに,$k$-supplierの目的を最小化する。
群は解離あるいは重複し、それぞれ異なる計算複雑性を持つ2つの異なる問題変種をもたらす。
両変種に対して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 Minimum Representation Clustering via Integer Programming [0.6906005491572401]
クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。
本稿では,各群が最小表現レベルを持つ必要があるという制約を伴って,k平均とkメダニアンのクラスタリング問題を考察する。
フェアネス制約を直接組み込んだ,MiniReLと呼ばれる交代最小化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-04T00:13:40Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
センターベースのクラスタリングと線形サブスペースクラスタリングは、現実世界のデータを小さなクラスタに分割する一般的なテクニックである。
異なる敏感なグループに対する1点当たりのクラスタリングコストは、公平性に関連する害をもたらす可能性がある。
本稿では,社会的に公平なセンタベースのクラスタリングと線形サブスペースクラスタリングを解決するための統一的なフレームワークを提案する。
論文 参考訳（メタデータ） (2022-08-22T07:10:17Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳（メタデータ） (2022-02-01T19:31:15Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering [0.0]
ローン申請や広告などの人間中心の意思決定システムへのデータクラスタリングの適用において、クラスタリングの結果は異なる人口集団の人々に対して差別される可能性がある。
そこで我々は,$k$-meansの更新とグループスワップ更新を併用した,新たな交代バランス型$k$-means (SAKM) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-29T01:47:15Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳（メタデータ） (2020-02-16T22:15:03Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。