論文の概要: Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model

• arxiv url: http://arxiv.org/abs/2306.12968v1
• Date: Sun, 18 Jun 2023 08:46:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-23 14:07:00.701984
• Title: Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Title（参考訳）: ラベル付き確率ブロックモデルにおけるインスタンス最適クラスタリカバリ
• Authors: Kaito Ariu, Alexandre Proutiere, Se-Young Yun
• Abstract要約: 観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
• 参考スコア（独自算出の注目度）: 79.46465138631592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of recovering hidden communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters, where cluster sizes grow linearly with the total number $n$ of items. In the LSBM, a label is (independently) observed for each pair of items. Our objective is to devise an efficient algorithm that recovers clusters using the observed labels. To this end, we revisit instance-specific lower bounds on the expected number of misclassified items satisfied by any clustering algorithm. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability. IAC consists of a one-time spectral clustering algorithm followed by an iterative likelihood-based cluster assignment improvement. This approach is based on the instance-specific lower bound and does not require any model parameters, including the number of clusters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of $\mathcal{O}(n \text{polylog}(n))$. We illustrate the effectiveness of our approach through numerical experiments.
• Abstract（参考訳）: 我々は,有限個のクラスタを持つラベル付き確率ブロックモデル (lsbm) において隠れたコミュニティを回復する問題を考える。 LSBMでは、ラベルは(独立して)各アイテムに対して観測される。 我々の目的は、観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案することである。 この目的のために、任意のクラスタリングアルゴリズムで満たされる誤分類項目の期待数について、インスタンス固有の下限を再検討する。 本稿では,これらの下位境界を期待値と高い確率で一致させる最初のアルゴリズムであるIACを提案する。 iacは1回のスペクトルクラスタリングアルゴリズムと反復的確率に基づくクラスタ割り当て改善からなる。 このアプローチはインスタンス固有の低境界に基づいており、クラスタ数を含むモデルパラメータは一切必要としない。 スペクトルクラスタリングを一度だけ実行することで、IACは$\mathcal{O}(n \text{polylog}(n))$の全体的な計算複雑性を維持する。 本手法の有効性を数値実験により示す。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• A Computational Theory and Semi-Supervised Algorithm for Clustering [0.0]
  半教師付きクラスタリングアルゴリズムを提案する。 クラスタリング法のカーネルは、Mohammadの異常検出アルゴリズムである。 結果は、合成および実世界のデータセットで示される。
  論文  参考訳（メタデータ） (2023-06-12T09:15:58Z)
• Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering [1.0589208420411012]
  本稿では,クラスタ融合と高効率更新方式を用いた反復アルゴリズムCCMMによる凸クラスタリングを提案する。 現在のデスクトップコンピュータでは、CCMMは、7次元空間に100万以上のオブジェクトを含む凸クラスタリング問題を効率的に解決する。
  論文  参考訳（メタデータ） (2022-11-03T15:07:51Z)
• 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)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• You Never Cluster Alone [150.94921340034688]
  我々は、主流のコントラスト学習パラダイムをクラスタレベルのスキームに拡張し、同じクラスタに属するすべてのデータが統一された表現に寄与する。 分類変数の集合をクラスタ化代入信頼度として定義し、インスタンスレベルの学習トラックとクラスタレベルの学習トラックを関連付ける。 代入変数を再パラメータ化することで、TCCはエンドツーエンドでトレーニングされる。
  論文  参考訳（メタデータ） (2021-06-03T14:59:59Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
  半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。 我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
  論文  参考訳（メタデータ） (2020-06-08T15:27:58Z)
• Bi-objective Optimization of Biclustering with Binary Data [0.0]
  クラスタリングは、いくつかの類似性基準に従って、データオブジェクトをクラスタと呼ばれるサブセットに分割する。 本稿では,クラスタの重複を許容する準クラスタリングについて論じる。 ビクラスタリングは、オブジェクトとフィーチャーを同時にグループ化し、特定のオブジェクトのグループに特別な機能のグループがあるようにします。
  論文  参考訳（メタデータ） (2020-02-09T21:49:26Z)

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

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