論文の概要: 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個の実データを用いた経験的研究を行い,本手法が実用的環境で非常にうまく機能することを示す。
関連論文リスト
- Group conditional validity via multi-group learning [5.797821810358083]
本研究では,分布自由な共形予測の問題と群条件妥当性の基準について考察する。
既存の方法は、制限的群化構造または分布的仮定の下でそのような保証を達成する。
マルチグループ学習と呼ばれる問題に対して,アルゴリズムを活用することにより,個人集団に対する妥当性保証を実現する問題に対する簡易な削減を提案する。
論文 参考訳(メタデータ) (2023-03-07T15:51:03Z) - 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) - Feature-based Individual Fairness in k-Clustering [14.847868952138795]
公平性の制約を確保しつつ一組の点をクラスタリングする問題を考察する。
我々は、必ずしもクラスタリングに使用されない特徴に基づいて、kクラスタリングにおける個別の公平性という新しい概念を導入する。
論文 参考訳(メタデータ) (2021-09-09T20:42:02Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - Group Collaborative Learning for Co-Salient Object Detection [152.67721740487937]
協調物体をリアルタイムで検出できる新しいグループ協調学習フレームワーク(GCoNet)を提案する(16ms)。
CoCA、CoSOD3k、Cosal2015の3つの挑戦的なベンチマークに関する大規模な実験は、我々の単純なGCoNetが10の最先端モデルより優れ、新しい最先端モデルを達成することを実証している。
論文 参考訳(メタデータ) (2021-03-15T13:16:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。