論文の概要: A Performance Guarantee for Spectral Clustering

• arxiv url: http://arxiv.org/abs/2007.05627v1
• Date: Fri, 10 Jul 2020 22:03:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-11 21:14:20.820357
• Title: A Performance Guarantee for Spectral Clustering
• Title（参考訳）: スペクトルクラスタリングにおける性能保証
• Authors: March Boedihardjo, Shaofeng Deng, Thomas Strohmer
• Abstract要約: スペクトルクラスタリングはいつ,最小比カット問題に対する大域的な解を見つけることができるのか? 我々は、グラフラプラシアンの不変部分空間に対して、$k$最小固有値に対応する決定論的2-無限ノルムを開発する。 これら2つの結果を組み合わせることで、スペクトルクラスタリングが保証され、大域的な解を最小比カット問題に出力する条件を与える。
• 参考スコア（独自算出の注目度）: 0.6445605125467572
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The two-step spectral clustering method, which consists of the Laplacian eigenmap and a rounding step, is a widely used method for graph partitioning. It can be seen as a natural relaxation to the NP-hard minimum ratio cut problem. In this paper we study the central question: when is spectral clustering able to find the global solution to the minimum ratio cut problem? First we provide a condition that naturally depends on the intra- and inter-cluster connectivities of a given partition under which we may certify that this partition is the solution to the minimum ratio cut problem. Then we develop a deterministic two-to-infinity norm perturbation bound for the the invariant subspace of the graph Laplacian that corresponds to the $k$ smallest eigenvalues. Finally by combining these two results we give a condition under which spectral clustering is guaranteed to output the global solution to the minimum ratio cut problem, which serves as a performance guarantee for spectral clustering.
• Abstract（参考訳）: 2段階のスペクトルクラスタリング法は、ラプラシアン固有写像と丸いステップからなるもので、グラフ分割に広く用いられる方法である。 NP-ハード最小比カット問題に対する自然な緩和と見なすことができる。 スペクトルクラスタリングはいつ,最小比カット問題に対する大域的な解を見つけることができるのか? まず、与えられたパーティションのクラスタ内およびクラスタ間コネクティビティに自然に依存する条件を提供し、この分割が最小比率カット問題の解であることを証明する。 次に、k$最小の固有値に対応するグラフラプラシアンの不変部分空間に対して束縛された決定論的2対無限ノルム摂動を開発する。 最後に、これら2つの結果を組み合わせることで、スペクトルクラスタリングが最小比カット問題に対してグローバルソリューションを出力することを保証し、スペクトルクラスタリングの性能保証となる条件を与える。

関連論文リスト

• Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
  任意のサイズ制約下でグラフを分割するグラフカットアルゴリズムを提案する。 我々は,大域収束を臨界点に保証する高速化された近位GDアルゴリズムを用いてこの問題を解決する。
  論文  参考訳（メタデータ） (2024-02-07T10:33:09Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。 我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。 本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
  論文  参考訳（メタデータ） (2023-12-07T06:19:39Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  正規化されたグラフ分割は、グラフ内のノードの集合を$k$ディスジョイントクラスタに分割して、任意のクラスタと他のクラスタ間の全エッジの分画を最小限にすることを目的としている。 本稿では,ノードが異なる階層群に属することを示す分類学的属性によって特徴付けられる分割問題の公平な変種について考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。
  論文  参考訳（メタデータ） (2023-07-22T12:20:46Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-07T09:14:44Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。 nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
  論文  参考訳（メタデータ） (2020-04-25T17:52:05Z)

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

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