論文の概要: Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model
- arxiv url: http://arxiv.org/abs/2207.04600v1
- Date: Mon, 11 Jul 2022 03:16:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-13 02:41:38.349191
- Title: Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model
- Title（参考訳）: 低ランク混合モデルに対するロイドアルゴリズムによる最適クラスタリング
- Authors: Zhongyuan Lyu and Dong Xia
- Abstract要約: 行列値の観測を行うために低ランク混合モデル(LrMM)を提案する。
ロイドアルゴリズムと低ランク近似を統合して計算効率のよいクラスタリング法を設計する。
本手法は,実世界のデータセットにおける文献上の他者よりも優れる。
- 参考スコア（独自算出の注目度）: 12.868722327487752
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper investigates the computational and statistical limits in
clustering matrix-valued observations. We propose a low-rank mixture model
(LrMM), adapted from the classical Gaussian mixture model (GMM) to treat
matrix-valued observations, which assumes low-rankness for population center
matrices. A computationally efficient clustering method is designed by
integrating Lloyd algorithm and low-rank approximation. Once well-initialized,
the algorithm converges fast and achieves an exponential-type clustering error
rate that is minimax optimal. Meanwhile, we show that a tensor-based spectral
method delivers a good initial clustering. Comparable to GMM, the minimax
optimal clustering error rate is decided by the separation strength, i.e, the
minimal distance between population center matrices. By exploiting
low-rankness, the proposed algorithm is blessed with a weaker requirement on
separation strength. Unlike GMM, however, the statistical and computational
difficulty of LrMM is characterized by the signal strength, i.e, the smallest
non-zero singular values of population center matrices. Evidences are provided
showing that no polynomial-time algorithm is consistent if the signal strength
is not strong enough, even though the separation strength is strong. The
performance of our low-rank Lloyd algorithm is further demonstrated under
sub-Gaussian noise. Intriguing differences between estimation and clustering
under LrMM are discussed. The merits of low-rank Lloyd algorithm are confirmed
by comprehensive simulation experiments. Finally, our method outperforms others
in the literature on real-world datasets.
- Abstract（参考訳）: 本稿では,クラスタリング行列値観測における計算と統計の限界について検討する。
本稿では,従来のガウス混合モデル(GMM)を応用した低ランク混合モデル(LrMM)を提案する。
ロイドアルゴリズムと低ランク近似を統合して計算効率のよいクラスタリング法を設計する。
うまく初期化されるとアルゴリズムは高速に収束し、極小値の指数型クラスタリング誤差率を達成する。
一方,テンソルに基づくスペクトル法は良好な初期クラスタリングをもたらすことを示す。
GMMと比較して、最小マックス最適クラスタリング誤差率は、分離強度、すなわち人口中心行列間の最小距離によって決定される。
低ランク性を活用することで,提案手法は分離強度の弱さを享受できる。
しかし、GMMとは異なり、LrMMの統計的および計算的難易度は信号強度、すなわち人口中心行列の最小の非ゼロ特異値によって特徴づけられる。
分離強度が強いにもかかわらず、信号強度が十分強くなければ多項式時間アルゴリズムは整合性がないことを示す証拠が提供される。
低ランクロイドアルゴリズムの性能は、サブガウシアンノイズ下でさらに実証される。
LrMMにおける推定とクラスタリングの違いについて論じる。
低ランクロイドアルゴリズムの利点は包括的シミュレーション実験によって確かめられる。
最後に,本手法は実世界のデータセットの文献において,他の手法よりも優れている。
関連論文リスト
- Linear time Evidence Accumulation Clustering with KMeans [0.0]
この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。
分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。
k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
論文 参考訳（メタデータ） (2023-11-15T14:12:59Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - 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) - A Non-Parametric Bootstrap for Spectral Clustering [0.7673339435080445]
我々は,データ行列のスペクトル分解と非パラメトリックブートストラップサンプリング方式を組み合わせた2つの新しいアルゴリズムを開発した。
我々の手法は、有限混合モデルに適合する他のブートストラップアルゴリズムと比較して収束性においてより一貫性がある。
論文 参考訳（メタデータ） (2022-09-13T08:37:05Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Optimal Clustering in Anisotropic Gaussian Mixture Models [3.5590836605011047]
異方性ガウス混合モデルに基づくクラスタリング作業について検討する。
クラスタ中心における信号対雑音比の依存性を特徴づける。
論文 参考訳（メタデータ） (2021-01-14T00:31:52Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳（メタデータ） (2020-10-02T10:41:59Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。