論文の概要: KFC: A Scalable Approximation Algorithm for $k$-center Fair Clustering

• arxiv url: http://arxiv.org/abs/2010.13949v2
• Date: Sat, 7 Nov 2020 08:33:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 20:16:11.719347
• Title: KFC: A Scalable Approximation Algorithm for $k$-center Fair Clustering
• Title（参考訳）: KFC:$k$-center Fair Clusteringのためのスケーラブルな近似アルゴリズム
• Authors: Elfarouk Harb and Ho Shan Lam
• Abstract要約: フェアクラスタリングの問題を$k-$centerの目的に基づいて検討する。 公平なクラスタリングでは、入力は$N$ポイントであり、それぞれが$l$保護されたグループの少なくとも1つに属している。 提案アルゴリズムは,過剰表現や低表現を伴わない優れたクラスタを見つけるのに有効である。
• 参考スコア（独自算出の注目度）: 6.09170287691728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of fair clustering on the $k-$center objective. In fair clustering, the input is $N$ points, each belonging to at least one of $l$ protected groups, e.g. male, female, Asian, Hispanic. The objective is to cluster the $N$ points into $k$ clusters to minimize a classical clustering objective function. However, there is an additional constraint that each cluster needs to be fair, under some notion of fairness. This ensures that no group is either "over-represented" or "under-represented" in any cluster. Our work builds on the work of Chierichetti et al. (NIPS 2017), Bera et al. (NeurIPS 2019), Ahmadian et al. (KDD 2019), and Bercea et al. (APPROX 2019). We obtain a randomized $3-$approximation algorithm for the $k-$center objective function, beating the previous state of the art ($4-$approximation). We test our algorithm on real datasets, and show that our algorithm is effective in finding good clusters without over-representation or under-representation, surpassing the current state of the art in runtime speed, clustering cost, while achieving similar fairness violations.
• Abstract（参考訳）: 本稿では,$k-$center 目標における公平なクラスタリングの問題について検討する。 公平なクラスタリングでは、入力はn$ポイントであり、それぞれが男性、女性、アジア人、ヒスパニックなどの保護されたグループのうちの少なくとも1つに属している。 目的は、従来のクラスタリング目的関数を最小化するために、$n$ポイントを$k$クラスタにクラスタすることである。 しかし、公平性の概念の下では、各クラスタが公平である必要があるという追加の制約がある。 これにより、どのクラスタにおいても、どのグループも"過剰表現"または"アンダー表現"されないことが保証される。 我々の研究は、Chierichetti et al. (NIPS 2017)、Bella et al. (NeurIPS 2019)、Ahmadian et al. (KDD 2019)、Bercea et al. (APPROX 2019)の成果に基づいている。 我々は、k-$center の目的関数に対してランダム化された 3-$approximation アルゴリズムを取得し、以前の art ($4-$approximation) の状態を上回った。 実際のデータセット上でアルゴリズムをテストした結果、我々のアルゴリズムは過剰表現や過剰表現なしによいクラスタを見つけるのに効果的であり、実行時速度、クラスタリングコスト、および同様の公平性違反を実現できることを示した。

関連論文リスト

• Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
  与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。 中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
  論文  参考訳（メタデータ） (2024-10-31T16:33:40Z)
• 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)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Explainable k-means. Don't be greedy, plant bigger trees! [12.68470213641421]
  説明可能な$k$-meansクラスタリングのために,新しいbi-criteria $tildeO(log2 k)$の競合アルゴリズムを提供する。 説明可能な$k$-meansは、最近Dasgupta、Frost、Moshkovitz、Rashtchian(ICML 2020)によって導入された。
  論文  参考訳（メタデータ） (2021-11-04T23:15:17Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• K-expectiles clustering [0.0]
  本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。 固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
  論文  参考訳（メタデータ） (2021-03-16T21:14:56Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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