論文の概要: A Tighter Analysis of Spectral Clustering, and Beyond

• arxiv url: http://arxiv.org/abs/2208.01724v1
• Date: Tue, 2 Aug 2022 20:18:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-04 13:21:19.718675
• Title: A Tighter Analysis of Spectral Clustering, and Beyond
• Title（参考訳）: スペクトルクラスタリングのより厳密な分析
• Authors: Peter Macgregor and He Sun
• Abstract要約: この研究は、あるグラフ$G=(V_G, E_G)$の頂点を$k$固有ベクトルを使って$mathbbRk$に埋め込む古典的なスペクトルクラスタリングアルゴリズムを研究する。 最初の結果は、スペクトルクラスタリングの性能に関するより厳密な分析であり、なぜそれが文献で研究されているものよりもかなり弱い条件下で機能するのかを説明するものである。 2つ目の結果から、埋め込みを構築するために$k$eigenvectors未満を適用することで、スペクトルクラスタリングが多くの人にとってより良い出力を得られることを示す。
• 参考スコア（独自算出の注目度）: 9.759415650727892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work studies the classical spectral clustering algorithm which embeds the vertices of some graph $G=(V_G, E_G)$ into $\mathbb{R}^k$ using $k$ eigenvectors of some matrix of $G$, and applies $k$-means to partition $V_G$ into $k$ clusters. Our first result is a tighter analysis on the performance of spectral clustering, and explains why it works under some much weaker condition than the ones studied in the literature. For the second result, we show that, by applying fewer than $k$ eigenvectors to construct the embedding, spectral clustering is able to produce better output for many practical instances; this result is the first of its kind in spectral clustering. Besides its conceptual and theoretical significance, the practical impact of our work is demonstrated by the empirical analysis on both synthetic and real-world datasets, in which spectral clustering produces comparable or better results with fewer than $k$ eigenvectors.
• Abstract（参考訳）: この研究は、あるグラフ $G=(V_G, E_G)$ の頂点を $k$ eigenvectors of some matrix of $G$ を使って $k$ クラスタに埋め込む古典的なスペクトルクラスタリングアルゴリズムを研究し、$V_G$ を $k$ クラスタに分割するために $k$-means を適用する。 最初の結果は、スペクトルクラスタリングの性能に関するより厳密な分析であり、なぜ文献で研究されているものよりもかなり弱い状態で動作するのかを説明します。 2つ目の結果は、埋め込みを構成するのに$k$の固有ベクトルよりも少ない値を適用することで、スペクトルクラスタリングは多くの実例でより良い出力を得られることを示し、この結果はスペクトルクラスタリングにおける最初の例である。 その概念的および理論的重要性に加えて、我々の研究の実践的影響は、スペクトルクラスタリングが$k$固有ベクトル以下で同等またはより良い結果を生成する合成および実世界のデータセットの実証分析によって示される。

関連論文リスト

• Datacube segmentation via Deep Spectral Clustering [76.48544221010424]
  拡張ビジョン技術は、しばしばその解釈に挑戦する。 データ立方体スペクトルの巨大な次元性は、その統計的解釈において複雑なタスクを生じさせる。 本稿では,符号化空間における教師なしクラスタリング手法の適用の可能性について検討する。 統計的次元削減はアドホック訓練(可変)オートエンコーダで行い、クラスタリング処理は(学習可能な)反復K-Meansクラスタリングアルゴリズムで行う。
  論文  参考訳（メタデータ） (2024-01-31T09:31:28Z)
• Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
  スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。 電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。 合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
  論文  参考訳（メタデータ） (2023-10-17T02:31:57Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• On consistency of constrained spectral clustering under representation-aware stochastic block model [20.6072287343024]
  制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。 この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。 これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
  論文  参考訳（メタデータ） (2022-03-03T20:41:14Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• An $\ell_p$ theory of PCA and spectral clustering [23.90245234027558]
  主成分分析は統計と機械学習において強力なツールである。 本稿では、ヒルベルト空間におけるPCAの中空バージョンに対する$ell_p$理論を開発する。 文脈的コミュニティ検出のために、$ell_p$理論は、正確な回復のための情報しきい値を達成する単純なスペクトルアルゴリズムに導かれる。
  論文  参考訳（メタデータ） (2020-06-24T21:30:28Z)
• 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)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく 我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。 EGAEは1つのエンコーダと2つのデコーダで構成される。
  論文  参考訳（メタデータ） (2020-02-20T09:53:28Z)

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

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