論文の概要: Exact Clustering in Tensor Block Model: Statistical Optimality and
Computational Limit
- arxiv url: http://arxiv.org/abs/2012.09996v2
- Date: Sun, 14 Mar 2021 14:55:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-02 04:34:56.249942
- Title: Exact Clustering in Tensor Block Model: Statistical Optimality and
Computational Limit
- Title(参考訳): テンソルブロックモデルにおける厳密なクラスタリング:統計的最適性と計算限界
- Authors: Rungang Han, Yuetian Luo, Miaoyan Wang, and Anru R. Zhang
- Abstract要約: 高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。
非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
- 参考スコア(独自算出の注目度): 10.8145995157397
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: High-order clustering aims to identify heterogeneous substructure in multiway
dataset that arises commonly in neuroimaging, genomics, and social network
studies. The non-convex and discontinuous nature of the problem poses
significant challenges in both statistics and computation. In this paper, we
propose a tensor block model and the computationally efficient methods,
\emph{high-order Lloyd algorithm} (HLloyd) and \emph{high-order spectral
clustering} (HSC), for high-order clustering in tensor block model. The
convergence of the proposed procedure is established, and we show that our
method achieves exact clustering under reasonable assumptions. We also give the
complete characterization for the statistical-computational trade-off in
high-order clustering based on three different signal-to-noise ratio regimes.
Finally, we show the merits of the proposed procedures via extensive
experiments on both synthetic and real datasets.
- Abstract(参考訳): 高次クラスタリングは、神経画像、ゲノム、およびソーシャルネットワーク研究で一般的に発生するマルチウェイデータセットにおける不均一なサブ構造を特定することを目的としている。
この問題の非凸性と不連続性は、統計と計算の両方において大きな課題を生じさせる。
本稿では,テンソルブロックモデルにおける高次クラスタリングのためのテンソルブロックモデルと計算効率のよい方法である 'emph{high-order Lloyd algorithm} (HLloyd) と \emph{high-order spectrum clustering} (HSC) を提案する。
提案手法の収束が確立され,提案手法が妥当な仮定のもとに正確なクラスタリングを実現することを示す。
また、3つの異なる信号対雑音比に基づく高次クラスタリングにおける統計的計算的トレードオフの完全な特性を示す。
最後に,合成データと実データの両方について広範な実験を行い,提案手法のメリットを示す。
関連論文リスト
- GCC: Generative Calibration Clustering [55.44944397168619]
本稿では,特徴学習と拡張をクラスタリングに組み込む新しいGCC法を提案する。
まず,実検体と実検体間の固有関係を識別する識別的特徴アライメント機構を開発する。
第二に、より信頼性の高いクラスタ割り当てを生成するための自己教師付きメトリック学習を設計する。
論文 参考訳(メタデータ) (2024-04-14T01:51:11Z) - Maximum Likelihood Estimation on Stochastic Blockmodels for Directed Graph Clustering [22.421702511126373]
我々は、有向ブロックモデルにおいて、基盤となるコミュニティを推定するものとしてクラスタリングを定式化する。
本稿では,2つの効率的かつ解釈可能な有向クラスタリングアルゴリズム,スペクトルクラスタリングアルゴリズム,半定値プログラミングに基づくクラスタリングアルゴリズムを紹介する。
論文 参考訳(メタデータ) (2024-03-28T15:47:13Z) - Heteroskedastic Tensor Clustering [20.979358557219953]
我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。
まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。
我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
論文 参考訳(メタデータ) (2023-11-04T02:50:40Z) - 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) - High-dimensional variable clustering based on maxima of a weakly dependent random process [1.1999555634662633]
本稿では,Asymptotic Independent Block (AI-block)モデルと呼ばれる,変数クラスタリングのための新しいモデルのクラスを提案する。
このモデルのクラスは特定可能であり、つまり、分割の間に部分的な順序を持つ極大要素が存在し、統計的推測が可能であることを意味する。
また,変数のクラスタを列挙するチューニングパラメータに依存するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-02T08:24:26Z) - Unified Multi-View Orthonormal Non-Negative Graph Based Clustering
Framework [74.25493157757943]
我々は,非負の特徴特性を活用し,多視点情報を統合された共同学習フレームワークに組み込む,新しいクラスタリングモデルを定式化する。
また、深層機能に基づいたクラスタリングデータに対するマルチモデル非負グラフベースのアプローチを初めて検討する。
論文 参考訳(メタデータ) (2022-11-03T08:18:27Z) - Multiway Spherical Clustering via Degree-Corrected Tensor Block Models [8.147652597876862]
推定精度を保証した次数補正ブロックモデルを開発した。
特に,3次以上のテンソルに対してのみ,本質的な統計的-計算的ギャップが生じることを示す。
本手法の有効性を2つのデータアプリケーションを用いて実証した。
論文 参考訳(メタデータ) (2022-01-19T03:40:22Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z) - Tensor Clustering with Planted Structures: Statistical Optimality and
Computational Limits [9.427635404752936]
我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。
我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。
信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-21T15:53:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。