論文の概要: Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints

• arxiv url: http://arxiv.org/abs/2401.07091v1
• Date: Sat, 13 Jan 2024 14:59:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-17 19:42:01.297353
• Title: Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints
• Title（参考訳）: 最小サイズ制約付きクラスタリングのためのグループ間基準の最適化
• Authors: Eduardo S. Laber and Lucas Murtinho
• Abstract要約: クラスタリングの品質を評価するために使用される内部尺度は、通常、グループ内および/またはグループ間基準を考慮に入れます。 証明可能な近似保証付きアルゴリズムを提案し, 前者を最適化する。 10個の実際のデータセットを用いて実証的研究を行い、我々の手法が実用的な環境で非常にうまく機能することを示す。
• 参考スコア（独自算出の注目度）: 2.7195102129095003
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Internal measures that are used to assess the quality of a clustering usually take into account intra-group and/or inter-group criteria. There are many papers in the literature that propose algorithms with provable approximation guarantees for optimizing the former. However, the optimization of inter-group criteria is much less understood. Here, we contribute to the state-of-the-art of this literature by devising algorithms with provable guarantees for the maximization of two natural inter-group criteria, namely the minimum spacing and the minimum spanning tree spacing. The former is the minimum distance between points in different groups while the latter captures separability through the cost of the minimum spanning tree that connects all groups. We obtain results for both the unrestricted case, in which no constraint on the clusters is imposed, and for the constrained case where each group is required to have a minimum number of points. Our constraint is motivated by the fact that the popular Single Linkage, which optimizes both criteria in the unrestricted case, produces clusterings with many tiny groups. To complement our work, we present an empirical study with 10 real datasets, providing evidence that our methods work very well in practical settings.
• Abstract（参考訳）: クラスタリングの品質を評価するために使用される内部尺度は、通常、グループ内および/またはグループ間基準を考慮している。 前者を最適化するための証明可能な近似保証付きアルゴリズムを提案する論文は文献に多い。 しかし、グループ間基準の最適化はあまり理解されていない。 本稿では,2つの自然群間基準,すなわち最小間隔と最小スパンディングツリー間隔の最大化を保証可能なアルゴリズムを考案し,本論文の最先端に寄与する。 前者は異なるグループの点間の最小距離であり、後者は全ての群をつなぐ最小のスパンディングツリーのコストで分離性を獲得する。 クラスタに制約が課されない非制限ケースと、各グループに最小数のポイントが要求される制約ケースの両方について結果を得る。 我々の制約は、制約のないケースで両方の基準を最適化する人気のあるシングルリンクが、多数の小さなグループでクラスタリングを生成するという事実に動機づけられています。 本研究を補完するために,10個の実データを用いた経験的研究を行い,本手法が実用的環境で非常にうまく機能することを示す。

関連論文リスト

• Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
  一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。 そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
  論文  参考訳（メタデータ） (2024-10-16T18:00:19Z)
• Fair Minimum Representation Clustering via Integer Programming [0.6906005491572401]
  クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。 本稿では,各群が最小表現レベルを持つ必要があるという制約を伴って,k平均とkメダニアンのクラスタリング問題を考察する。 フェアネス制約を直接組み込んだ,MiniReLと呼ばれる交代最小化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-04T00:13:40Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Fair Minimum Representation Clustering [0.0]
  クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。 一般的な$k$-meansアルゴリズムであるロイドのアルゴリズムが不公平な結果をもたらすことを示す。 フェアネス制約を直接組み込む、ミニReLと呼ばれるロイドのアルゴリズムの変種を示す。
  論文  参考訳（メタデータ） (2023-02-06T23:16:38Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Max-Min Grouped Bandits [48.62520520818357]
  マルチアームバンディット問題であるmax-min grouped banditsを導入する。 ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。 この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
  論文  参考訳（メタデータ） (2021-11-17T01:59:15Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints [32.19047459493177]
  我々は,いくつかの本質的クラスタリングの目的に組み込んだ,新しいemphstochastic pairwise制約系を導入する。 これらの制約は,半教師付き学習における emphinvidual fairness や emphmust-link 制約など,興味をそそるアプリケーションの集合を簡潔にモデル化できることを示す。
  論文  参考訳（メタデータ） (2021-03-02T20:27:58Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Robust Optimization for Fairness with Noisy Protected Groups [85.13255550021495]
  ノイズが保護されたグループラベルに頼った結果について検討した。 頑健な最適化を用いた2つの新しいアプローチを提案する。 頑健なアプローチは、単純アプローチよりも真のグループ公平性を保証することが示される。
  論文  参考訳（メタデータ） (2020-02-21T14:58:37Z)

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

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