論文の概要: Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects

• arxiv url: http://arxiv.org/abs/2006.14470v2
• Date: Sun, 31 Jan 2021 02:10:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 02:46:08.314621
• Title: Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects
• Title（参考訳）: Nystrom近似を用いたスケーラブルスペクトルクラスタリング:実用的および理論的側面
• Authors: Farhad Pourkamali-Anaraki
• Abstract要約: 本研究は、サンプリングされた点に関連付けられた類似度行列のスペクトル特性を利用して、精度と効率のトレードオフを制御したスペクトルクラスタリングアルゴリズムを提案する。 この研究の包括的な目標は、スペクトルクラスタリングを加速する将来の研究方向のための改善されたベースラインを提供することである。
• 参考スコア（独自算出の注目度）: 1.6752182911522515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral clustering techniques are valuable tools in signal processing and machine learning for partitioning complex data sets. The effectiveness of spectral clustering stems from constructing a non-linear embedding based on creating a similarity graph and computing the spectral decomposition of the Laplacian matrix. However, spectral clustering methods fail to scale to large data sets because of high computational cost and memory usage. A popular approach for addressing these problems utilizes the Nystrom method, an efficient sampling-based algorithm for computing low-rank approximations to large positive semi-definite matrices. This paper demonstrates how the previously popular approach of Nystrom-based spectral clustering has severe limitations. Existing time-efficient methods ignore critical information by prematurely reducing the rank of the similarity matrix associated with sampled points. Also, current understanding is limited regarding how utilizing the Nystrom approximation will affect the quality of spectral embedding approximations. To address the limitations, this work presents a principled spectral clustering algorithm that exploits spectral properties of the similarity matrix associated with sampled points to regulate accuracy-efficiency trade-offs. We provide theoretical results to reduce the current gap and present numerical experiments with real and synthetic data. Empirical results demonstrate the efficacy and efficiency of the proposed method compared to existing spectral clustering techniques based on the Nystrom method and other efficient methods. The overarching goal of this work is to provide an improved baseline for future research directions to accelerate spectral clustering.
• Abstract（参考訳）: スペクトルクラスタリング技術は、複雑なデータセットを分割するための信号処理や機械学習で有用なツールである。 スペクトルクラスタリングの有効性は、類似性グラフの作成とラプラシアン行列のスペクトル分解の計算に基づく非線形埋め込みの構築に起因している。 しかし、スペクトルクラスタリング法は計算コストとメモリ使用量が高いため、大規模なデータセットにスケールできない。 これらの問題に対処するための一般的なアプローチは、大きな正の半定値行列に対する低ランク近似を計算するための効率的なサンプリングベースアルゴリズムであるNystrom法を用いる。 本稿では,これまで広く用いられてきたナイストロム型スペクトルクラスタリングのアプローチに厳しい制限があることを示す。 既存の時間効率の手法では、サンプリングされた点に関連付けられた類似度行列のランクを早期に下げることで臨界情報を無視する。 また、Nystrom近似の利用がスペクトル埋め込み近似の品質にどのように影響するかについては、現在の理解が限られている。 この制限に対処するため,本研究では,サンプル点に付随する類似度行列のスペクトル特性を利用して精度・効率のトレードオフを制御した原理的スペクトルクラスタリングアルゴリズムを提案する。 そこで本研究では, 実データと合成データを用いた数値実験を行う。 実験により,Nystrom法および他の効率的な手法に基づく既存のスペクトルクラスタリング手法と比較して,提案手法の有効性と有効性を示す。 この研究の全体的な目標は、将来の研究方向のベースラインを改善し、スペクトルクラスタリングを加速することである。

関連論文リスト

• Toward Efficient and Incremental Spectral Clustering via Parametric Spectral Clustering [2.44755919161855]
  スペクトルクラスタリングは、非線形分離可能なデータを効果的にクラスタリングするための一般的な方法である。 本稿では、パラメトリックスペクトルクラスタリング(PSC)と呼ばれる新しい手法を提案する。 PSCは、ビッグデータとリアルタイムシナリオに関連する課題に対処する。
  論文  参考訳（メタデータ） (2023-11-14T01:26:20Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Spectral Decomposition Representation for Reinforcement Learning [100.0424588013549]
  本稿では, スペクトル分解表現法(SPEDER)を提案する。この手法は, データ収集ポリシーに急激な依存を生じさせることなく, ダイナミックスから状態-作用の抽象化を抽出する。 理論的解析により、オンライン設定とオフライン設定の両方において提案アルゴリズムのサンプル効率が確立される。 実験により、いくつかのベンチマークで現在の最先端アルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-08-19T19:01:30Z)
• Divide-and-conquer based Large-Scale Spectral Clustering [8.545202841051582]
  そこで本研究では,分散・分散型大規模スペクトルクラスタリング手法を提案し,効率と効率のバランスを良くする。 提案手法は,既存の大規模スペクトルクラスタリングよりも計算量が少ない。
  論文  参考訳（メタデータ） (2021-04-30T15:09:45Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Spectral Methods for Data Science: A Statistical Perspective [37.2486912080998]
  スペクトル法は、巨大でノイズの多い不完全なデータから情報を抽出するための単純で驚くほど効果的な手法として登場した。 この本は、現代の統計学的観点から、体系的で包括的でアクセスしやすいスペクトル法の導入を意図している。
  論文  参考訳（メタデータ） (2020-12-15T18:40:56Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• A boosted outlier detection method based on the spectrum of the Laplacian matrix of a graph [0.0]
  本稿では,グラフのラプラシア行列のスペクトルに基づく新しい外乱検出アルゴリズムを提案する。 ラプラシア行列の空間性は計算負担を著しく減少させる。
  論文  参考訳（メタデータ） (2020-08-07T08:37:56Z)
• Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling [19.675277307158435]
  本稿では,新しいサンプリング手法であるCentroid Minimum Sum of Squared similarities (CMS3)と,それをいつ使用するかを示す,スケーラブルなNystromベースのクラスタリングアルゴリズムを提案する。 我々のデータセットはデータセットの固有スペクトル形状に依存しており、他の最先端手法と比較して、テストにおいて競合する低ランク近似が得られる。
  論文  参考訳（メタデータ） (2020-07-21T17:49:03Z)

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

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