論文の概要: Linear Programming based Approximation to Individually Fair k-Clustering with Outliers

• arxiv url: http://arxiv.org/abs/2412.10923v1
• Date: Sat, 14 Dec 2024 18:16:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:59:49.218912
• Title: Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
• Title（参考訳）: 線形プログラミングに基づく外接点をもつ個別に公平なkクラスタリングへの近似
• Authors: Binita Maity, Shrutimoy Das, Anirban Dasgupta,
• Abstract要約: 我々は、外れ値を含むデータセットに対して、個別に公平な$k$-meansクラスタリングアルゴリズムを開発する。 アウトリーでない各点に対して、与えられた点の最も近い近傍に$fracnk$の中心が存在する必要がある。 我々は,本手法が正半径とクラスタリングコストの保証された近似につながることを理論的に保証する。
• 参考スコア（独自算出の注目度）: 1.4460482276563802
• License:
• Abstract: Individual fairness guarantees are often desirable properties to have, but they become hard to formalize when the dataset contains outliers. Here, we investigate the problem of developing an individually fair $k$-means clustering algorithm for datasets that contain outliers. That is, given $n$ points and $k$ centers, we want that for each point which is not an outlier, there must be a center within the $\frac{n}{k}$ nearest neighbours of the given point. While a few of the recent works have looked into individually fair clustering, this is the first work that explores this problem in the presence of outliers for $k$-means clustering. For this purpose, we define and solve a linear program (LP) that helps us identify the outliers. We exclude these outliers from the dataset and apply a rounding algorithm that computes the $k$ centers, such that the fairness constraint of the remaining points is satisfied. We also provide theoretical guarantees that our method leads to a guaranteed approximation of the fair radius as well as the clustering cost. We also demonstrate our techniques empirically on real-world datasets.
• Abstract（参考訳）: 個々の公正性を保証することは、しばしば望ましい性質を持つが、データセットが外れ値を含むと、形式化が困難になる。 本稿では,外れ値を含むデータセットに対して,個別に公平な$k$-meansクラスタリングアルゴリズムを開発する際の問題点について検討する。 つまり、$n$点と$k$中心が与えられた場合、アウトリーでない各点に対して、与えられた点の近傍に$\frac{n}{k}$中心が存在する必要がある。 最近の研究のいくつかは、個別に公正なクラスタリングを調査しているが、これは、$k$-meansクラスタリングのアウトリーチの存在下でこの問題を探求する最初の研究である。 この目的のために、我々は、外れ値を特定するのに役立つ線形プログラム(LP)を定義し、解決する。 我々はこれらの外れ値をデータセットから除外し、残りの点の公正性制約を満たすように、$k$センターを計算するラウンドアルゴリズムを適用する。 また,本手法が正半径の近似とクラスタリングコストを保証できるという理論的保証も提供する。 また、実世界のデータセット上で実証的な手法を実証した。

関連論文リスト

• 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)
• A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
  我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。 私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。 ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
  論文  参考訳（メタデータ） (2024-02-02T10:44:42Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds [17.226362076527764]
  k-means、k-medoids、k-centersといったCentroidベースのクラスタリング手法は、探索データ解析においてゴーツーツールとして強く応用されている。 多くの場合、これらの手法はデータセットの視覚化や要約のためにデータ多様体の代表的なセントロイドを得るのに使用される。 本研究では, 遠心円周波によって形成されるクラスターに最大半径制約$r$を導入することにより, このようなシナリオを緩和することを提案する。
  論文  参考訳（メタデータ） (2022-03-04T18:59:02Z)
• Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
  一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
  論文  参考訳（メタデータ） (2022-02-16T16:24:31Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Robust Trimmed k-means [70.88503833248159]
  本稿では,外乱点とクラスタポイントを同時に識別するRobust Trimmed k-means (RTKM)を提案する。 RTKMは他の方法と競合することを示す。
  論文  参考訳（メタデータ） (2021-08-16T15:49:40Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  我々は、$k$-means問題に対する急激な局所解の構造について検討する。 分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
  論文  参考訳（メタデータ） (2020-02-16T22:15:03Z)

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

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