論文の概要: Can Evolutionary Clustering Have Theoretical Guarantees?
- arxiv url: http://arxiv.org/abs/2212.01771v2
- Date: Sat, 22 Jul 2023 04:12:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 00:20:36.728693
- Title: Can Evolutionary Clustering Have Theoretical Guarantees?
- Title（参考訳）: 進化的クラスタリングは理論的保証を持つか?
- Authors: Chao Qian
- Abstract要約: 進化的クラスタリングは多くの成功例を見出したが、すべての結果は実証的であり、理論的な支持が欠如している。
本稿では,GSEMOの近似性能を理論的に保証できることを証明して,このギャップを埋める。
- 参考スコア（独自算出の注目度）: 21.343803954998915
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental problem in many areas, which aims to partition a
given data set into groups based on some distance measure, such that the data
points in the same group are similar while that in different groups are
dissimilar. Due to its importance and NP-hardness, a lot of methods have been
proposed, among which evolutionary algorithms are a class of popular ones.
Evolutionary clustering has found many successful applications, but all the
results are empirical, lacking theoretical support. This paper fills this gap
by proving that the approximation performance of the GSEMO (a simple
multi-objective evolutionary algorithm) for solving four formulations of
clustering, i.e., $k$-tMM, $k$-center, discrete $k$-median and $k$-means, can
be theoretically guaranteed. Furthermore, we consider clustering under
fairness, which tries to avoid algorithmic bias, and has recently been an
important research topic in machine learning. We prove that for discrete
$k$-median clustering under individual fairness, the approximation performance
of the GSEMO can be theoretically guaranteed with respect to both the objective
function and the fairness constraint.
- Abstract（参考訳）: クラスタリングは多くの領域において基本的な問題であり、ある距離測度に基づいて与えられたデータセットをグループに分割することを目的としている。
その重要性とnpの難しさから、進化アルゴリズムが一般的なアルゴリズムのクラスである多くの手法が提案されている。
進化的クラスタリングは多くの応用が成功したが、全ての結果は経験的であり、理論的サポートが欠如している。
本稿では,gsemo (単純な多目的進化アルゴリズム) によるクラスタリングの4つの定式化,すなわち$k$-tmm, $k$-center, discrete $k$-median, $k$-means の近似性能を理論的に保証できることを証明し,このギャップを埋める。
さらに,アルゴリズムバイアスを回避しようとするフェアネス下でのクラスタリングも検討し,近年,機械学習における重要な研究課題となっている。
個別の公正度の下での離散的な$k$-medianクラスタリングに対して、GSEMOの近似性能は、目的関数と公正度制約の両方に関して理論的に保証できることを示す。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - Asymptotics for The $k$-means [0.6091702876917281]
k$-meansは統計学と計算機科学において最も重要な教師なし学習手法の1つである。
提案したクラスタリング整合性は,クラスタリング手法の以前の基準整合性よりも適切である。
提案した$k$-means法はクラスタリングエラー率を低くし,小さなクラスタやアウトレイアに対してより堅牢であることがわかった。
論文 参考訳（メタデータ） (2022-11-18T03:36:58Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。
このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。
このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
論文 参考訳（メタデータ） (2022-09-27T19:04:36Z) - A One-shot Framework for Distributed Clustered Learning in Heterogeneous
Environments [54.172993875654015]
異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。
ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。
厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
論文 参考訳（メタデータ） (2022-09-22T09:04:10Z) - Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
センターベースのクラスタリングと線形サブスペースクラスタリングは、現実世界のデータを小さなクラスタに分割する一般的なテクニックである。
異なる敏感なグループに対する1点当たりのクラスタリングコストは、公平性に関連する害をもたらす可能性がある。
本稿では,社会的に公平なセンタベースのクラスタリングと線形サブスペースクラスタリングを解決するための統一的なフレームワークを提案する。
論文 参考訳（メタデータ） (2022-08-22T07:10:17Z) - 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) - Deep Fair Discriminative Clustering [24.237000220172906]
2値および多状態保護状態変数(PSV)に対するグループレベルの公正性の一般概念について検討する。
本稿では,クラスタリング目標とフェアネス目標とを組み合わせて,フェアクラスタを適応的に学習する改良学習アルゴリズムを提案する。
本フレームワークは, フレキシブルフェアネス制約, マルチステートPSV, 予測クラスタリングなど, 新規なクラスタリングタスクに対して有望な結果を示す。
論文 参考訳（メタデータ） (2021-05-28T23:50:48Z) - Protecting Individual Interests across Clusters: Spectral Clustering
with Guarantees [20.350342151402963]
我々は、各クラスタが各クラスタに接続された適切なメンバー数を含む必要があるグラフ $mathcalg$ をクラスタリングするための個別フェアネス基準を提案する。
与えられた表現グラフの下で公正なクラスタを見つけるためのスペクトルクラスタリングアルゴリズムを考案する。
論文 参考訳（メタデータ） (2021-05-08T15:03:25Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Fair Hierarchical Clustering [92.03780518164108]
従来のクラスタリングにおける過剰表現を緩和する公平性の概念を定義する。
我々のアルゴリズムは、目的に対して無視できない損失しか持たない、公平な階層的なクラスタリングを見つけることができることを示す。
論文 参考訳（メタデータ） (2020-06-18T01:05:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。