論文の概要: Heteroskedastic Tensor Clustering
- arxiv url: http://arxiv.org/abs/2311.02306v1
- Date: Sat, 4 Nov 2023 02:50:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 18:21:25.007056
- Title: Heteroskedastic Tensor Clustering
- Title（参考訳）: Heteroskedastic Tensor Clustering
- Authors: Yuchen Zhou, Yuxin Chen
- Abstract要約: 我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。
まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。
我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
- 参考スコア（独自算出の注目度）: 20.979358557219953
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Tensor clustering, which seeks to extract underlying cluster structures from
noisy tensor observations, has gained increasing attention. One extensively
studied model for tensor clustering is the tensor block model, which postulates
the existence of clustering structures along each mode and has found broad
applications in areas like multi-tissue gene expression analysis and multilayer
network analysis. However, currently available computationally feasible methods
for tensor clustering either are limited to handling i.i.d. sub-Gaussian noise
or suffer from suboptimal statistical performance, which restrains their
utility in applications that have to deal with heteroskedastic data and/or low
signal-to-noise-ratio (SNR).
To overcome these challenges, we propose a two-stage method, named
$\mathsf{High\text{-}order~HeteroClustering}$ ($\mathsf{HHC}$), which starts by
performing tensor subspace estimation via a novel spectral algorithm called
$\mathsf{Thresholded~Deflated\text{-}HeteroPCA}$, followed by approximate
$k$-means to obtain cluster nodes. Encouragingly, our algorithm provably
achieves exact clustering as long as the SNR exceeds the computational limit
(ignoring logarithmic factors); here, the SNR refers to the ratio of the
pairwise disparity between nodes to the noise level, and the computational
limit indicates the lowest SNR that enables exact clustering with polynomial
runtime. Comprehensive simulation and real-data experiments suggest that our
algorithm outperforms existing algorithms across various settings, delivering
more reliable clustering performance.
- Abstract（参考訳）: ノイズの多いテンソル観測から基盤となるクラスタ構造を抽出しようとするテンソルクラスタリングが注目されている。
テンソルクラスタリングの広く研究されているモデルの一つはテンソルブロックモデルであり、各モードに沿ってクラスタリング構造が存在することを仮定し、多関節遺伝子発現解析や多層ネットワーク解析といった領域で広く応用されている。
しかし、現在利用可能なテンソルクラスタリングの計算可能な方法は、サブガウスノイズの処理に限られるか、あるいは準最適統計性能に悩まされているかのいずれかであり、ヘテロスケダスティックデータや低信号対雑音比(SNR)を扱う必要があるアプリケーションにおいて、それらの実用性を抑える。
これらの課題を克服するために,2段階の手法である$\mathsf{high\text{-}order~heteroclustering}$ (\mathsf{hhc}$) を提案する。
本稿では,SNRが計算限界を超える限り,精度の高いクラスタリングを確実に達成し(対数的要因を無視する),SNRはノード間の対等差と雑音レベルとの比を,計算限界は多項式ランタイムとの正確なクラスタリングを可能にする最下位のSNRを示す。
総合的なシミュレーションと実データ実験により,提案アルゴリズムが既存のアルゴリズムを様々な設定で上回り,より信頼性の高いクラスタリング性能を提供することが示唆された。
関連論文リスト
- Consistency of Lloyd's Algorithm Under Perturbations [11.56433365648479]
ロイドのアルゴリズムは最も広く使われているクラスタリングアルゴリズムの1つである。
準ガウス混合のサンプルに対するロイドのアルゴリズムの誤クラスタリング速度は、$O(log(n))$ iterationsの後に指数関数的に有界であることを示す。
論文 参考訳（メタデータ） (2023-09-01T16:45:52Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。
本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。
さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
論文 参考訳（メタデータ） (2023-03-29T14:54:19Z) - Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳（メタデータ） (2022-05-26T17:47:35Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Exact Clustering in Tensor Block Model: Statistical Optimality and
Computational Limit [10.8145995157397]
高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。
非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
論文 参考訳（メタデータ） (2020-12-18T00:48:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling [19.675277307158435]
本稿では,新しいサンプリング手法であるCentroid Minimum Sum of Squared similarities (CMS3)と,それをいつ使用するかを示す,スケーラブルなNystromベースのクラスタリングアルゴリズムを提案する。
我々のデータセットはデータセットの固有スペクトル形状に依存しており、他の最先端手法と比較して、テストにおいて競合する低ランク近似が得られる。
論文 参考訳（メタデータ） (2020-07-21T17:49:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。