論文の概要: Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

• arxiv url: http://arxiv.org/abs/2609.06384v1
• Date: Sun, 06 Sep 2026 04:49:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.23259
• Title: Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering
• Title（参考訳）: ユークリッドフェア$k$-Centerクラスタリングのためのパラメータ化およびストリーミングアルゴリズム
• Authors: Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen,
• Abstract要約: ユークリッド空間を用いた公平な$k$-centerクラスタリングのための近似アルゴリズムを開発した。 本手法はクラスタリング精度の点で最先端の手法よりも優れている。
• 参考スコア（独自算出の注目度）: 7.186850020419764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.
• Abstract（参考訳）: 機械学習における公平性の重要性の高まりに動機付けられて、$k$-centerクラスタリングは、根本的な問題としてかなりの研究の注目を集めている。 この問題では、データセットを$m$不整合グループに分割し、その目的は、各グループから選択された中心数に対する上限値である$k$のデータポイントをセンターとして選択することであり、任意のデータポイントとその割り当てられた中心間の最大距離を最小化することを目的としている。 機械学習アプリケーションでユビキタスなユークリッド空間に着目し、まず、近似比が2.732$のユークリッドフェア$k$-centerのパラメータ化近似アルゴリズムを開発した。 このアルゴリズムを後処理の段階として大規模データのための1パスストリーミングフレームワークに組み込むことで、近似比が4.464$となる。 これらの比率は、それぞれ2.414$と3.828$に改善できる。 多項式時間の複雑性を保証するため、近似比が4.732$のワンパスストリーミングアルゴリズムをさらに設計し、さらに4.42$に改善し、最先端比を上回った。 最後に,我々の手法はクラスタリングの精度において,最先端の手法よりも優れていることを示す。

関連論文リスト

• A Sub-4 Approximation for Fair $k$-Means [18.61347737579578]
  ユークリッド空間における公平な$k$-meansクラスタリングについて検討し、各クラスタにおける保護群の割合は、指定された下限と上限内にある必要がある。 本稿では,線形プログラミング緩和と入力の幾何学変換を組み合わせた近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-09-07T20:54:36Z)
• 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)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• 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)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)

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

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