論文の概要: Generalization Performance of Ensemble Clustering: From Theory to Algorithm

• arxiv url: http://arxiv.org/abs/2506.02053v1
• Date: Sun, 01 Jun 2025 09:34:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:34.880155
• Title: Generalization Performance of Ensemble Clustering: From Theory to Algorithm
• Title（参考訳）: アンサンブルクラスタリングの一般化性能:理論からアルゴリズムへ
• Authors: Xu Zhang, Haoye Qiu, Weixuan Liang, Hui Liu, Junhui Hou, Yuheng Jia,
• Abstract要約: 本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
• 参考スコア（独自算出の注目度）: 57.176040163699554
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ensemble clustering has demonstrated great success in practice; however, its theoretical foundations remain underexplored. This paper examines the generalization performance of ensemble clustering, focusing on generalization error, excess risk and consistency. We derive a convergence rate of generalization error bound and excess risk bound both of $\mathcal{O}(\sqrt{\frac{\log n}{m}}+\frac{1}{\sqrt{n}})$, with $n$ and $m$ being the numbers of samples and base clusterings. Based on this, we prove that when $m$ and $n$ approach infinity and $m$ is significantly larger than log $n$, i.e., $m,n\to \infty, m\gg \log n$, ensemble clustering is consistent. Furthermore, recognizing that $n$ and $m$ are finite in practice, the generalization error cannot be reduced to zero. Thus, by assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation. From this, we theoretically demonstrate that to achieve better clustering performance, we should minimize the deviation (bias) of base clustering from its expectation and maximize the differences (diversity) among various base clusterings. Additionally, we derive that maximizing diversity is nearly equivalent to a robust (min-max) optimization model. Finally, we instantiate our theory to develop a new ensemble clustering algorithm. Compared with SOTA methods, our approach achieves average improvements of 6.1%, 7.3%, and 6.0% on 10 datasets w.r.t. NMI, ARI, and Purity. The code is available at https://github.com/xuz2019/GPEC.
• Abstract（参考訳）: アンサンブルクラスタリングは実際に大きな成功を収めてきたが、その理論的基礎は未解明のままである。 本稿では,アンサンブルクラスタリングの一般化性能について検討し,一般化誤差,過剰リスク,一貫性に着目した。 一般化誤差境界と余剰リスク境界の収束率を$\mathcal{O}(\sqrt {\frac {\log n}{m}}+\frac{1}{\sqrt{n}})$で導き、$n$と$m$はサンプルと基底クラスタリングの数である。 これに基づいて、$m$と$n$アプローチ無限大と$m$がlog $n$よりもはるかに大きいとき、すなわち$m,n\to \infty, m\gg \log n$, アンサンブルクラスタリングは一貫したものであることを証明した。 さらに、実際に$n$ と $m$ が有限であることを認識すると、一般化誤差は 0 に還元できない。 したがって、異なる重みを有限クラスタリングに割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 このことから, より優れたクラスタリング性能を実現するためには, 期待するベースクラスタリングの偏差(バイアス)を最小化し, 様々なベースクラスタリングの違い(多様性)を最大化する必要がある。 さらに、多様性の最大化は、ロバストな(最小限の)最適化モデルとほぼ同値である。 最後に、我々の理論をインスタンス化し、新しいアンサンブルクラスタリングアルゴリズムを開発する。 SOTA法と比較すると,NMI,ARI,Purityの10データセットに対して平均6.1%,7.3%,6.0%の改善が達成されている。 コードはhttps://github.com/xuz2019/GPECで公開されている。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle [9.578056676899203]
  オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。 我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T08:51:19Z)
• 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)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  我々は、$k$-means問題に対する急激な局所解の構造について検討する。 分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
  論文  参考訳（メタデータ） (2020-02-16T22:15:03Z)

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

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