論文の概要: Estimating the number of clusters of a Block Markov Chain

• arxiv url: http://arxiv.org/abs/2407.18287v1
• Date: Thu, 25 Jul 2024 13:28:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-29 15:18:53.292758
• Title: Estimating the number of clusters of a Block Markov Chain
• Title（参考訳）: Block Markov Chainのクラスタ数の推定
• Authors: Thomas van Vuren, Thomas Cronk, Jaron Sanders,
• Abstract要約: ブロックマルコフ連鎖の軌跡である場合のクラスタ数を推定する手法を提案する。 カウント行列のエントリ間の依存関係や、カウント行列がスパースである場合でも、そのメソッドは一貫したものであることを示す。
• 参考スコア（独自算出の注目度）: 0.4374837991804086
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering algorithms frequently require the number of clusters to be chosen in advance, but it is usually not clear how to do this. To tackle this challenge when clustering within sequential data, we present a method for estimating the number of clusters when the data is a trajectory of a Block Markov Chain. Block Markov Chains are Markov Chains that exhibit a block structure in their transition matrix. The method considers a matrix that counts the number of transitions between different states within the trajectory, and transforms this into a spectral embedding whose dimension is set via singular value thresholding. The number of clusters is subsequently estimated via density-based clustering of this spectral embedding, an approach inspired by literature on the Stochastic Block Model. By leveraging and augmenting recent results on the spectral concentration of random matrices with Markovian dependence, we show that the method is asymptotically consistent - in spite of the dependencies between the count matrix's entries, and even when the count matrix is sparse. We also present a numerical evaluation of our method, and compare it to alternatives.
• Abstract（参考訳）: クラスタリングアルゴリズムは、事前に選択するクラスタの数を必要とすることが多いが、その方法は通常明確ではない。 この課題に対処するため,ブロックマルコフ連鎖の軌跡であるクラスタ数を推定する手法を提案する。 ブロックマルコフ連鎖は、その遷移行列にブロック構造を示すマルコフ連鎖である。 この方法は、軌道内の異なる状態間の遷移数をカウントする行列を考慮し、これを特異値しきい値によって次元が設定されたスペクトル埋め込みに変換する。 このスペクトル埋め込みの密度に基づくクラスタリング(Stochastic Block Modelの文献から着想を得たアプローチ)により、クラスタの数を推定する。 マルコフに依存したランダム行列のスペクトル濃度の最近の結果を活用して増大させることにより、この手法は漸近的に一貫性があることが示される。 また,本手法の数値評価を行い,代替手法と比較する。

関連論文リスト

• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Rank-one matrix estimation with groupwise heteroskedasticity [5.202966939338455]
  本研究では,異なるノイズレベル下で行列の異なるブロックが観測されるガウス観測からランク1行列を推定する問題について検討する。 行列と潜伏変数の両方を推定する際、最小平均二乗誤差の正確な公式を証明した。 我々は、近似メッセージパッシングアルゴリズムと勾配降下アルゴリズムを導出し、これらのアルゴリズムが特定の状況における情報理論的限界を達成することを実証的に示す。
  論文  参考訳（メタデータ） (2021-06-22T17:48:36Z)
• Unsupervised clustering of series using dynamic programming [0.0]
  各クラスタに存在するブロックが既知のモデルに対して整合的であるように、シリーズをセグメント化してクラスタ化したい。 データポイントがコヒーレントであるとは、同じパラメータを持つこのモデルを使って記述できる場合である。 我々は,クラスタ数,遷移数,ブロックの最小サイズに制約のある動的プログラミングに基づくアルゴリズムを設計した。
  論文  参考訳（メタデータ） (2021-01-23T14:35:35Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  本稿では,複数のクラスタリングを組み合わせ,個々のクラスタリングよりも優れたパフォーマンスを実現するクラスタリングアンサンブルの問題について検討する。 本稿では,この問題をグローバルな視点から解くために,新しい低ランクテンソル近似法を提案する。 7つのベンチマークデータセットを用いた実験の結果,提案手法は12の最先端手法と比較して,クラスタリング性能のブレークスルーを達成した。
  論文  参考訳（メタデータ） (2020-12-16T13:01:37Z)
• Kernel learning approaches for summarising and combining posterior similarity matrices [68.8204255655161]
  我々は,ベイズクラスタリングモデルに対するMCMCアルゴリズムの出力を要約するための新しいアプローチを提案するために,後部類似性行列(PSM)の概念を構築した。 我々の研究の重要な貢献は、PSMが正の半定値であり、したがって確率的に動機付けられたカーネル行列を定義するのに使用できることである。
  論文  参考訳（メタデータ） (2020-09-27T14:16:14Z)
• CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data [34.89460002735166]
  マルチスケールクラスタデータにスペクトルクラスタリングを適用する際の問題点について検討する。 マルチスケールデータの場合、スパースクラスタのオブジェクトが遠く離れているため、距離ベースの類似性は有効ではない。 係数行列を正規化するためにトレースラッソを適用するアルゴリズムCASTを提案する。
  論文  参考訳（メタデータ） (2020-06-08T09:46:35Z)
• Conjoined Dirichlet Process [63.89763375457853]
  我々はディリクレ過程に基づく新しい非パラメトリック確率的ビクラスタリング法を開発し、列と列の双方に強い共起を持つビクラスタを同定する。 本手法はテキストマイニングと遺伝子発現解析の2つの異なる応用に適用し,既存の手法に比べて多くの設定でビクラスタ抽出を改善することを示す。
  論文  参考訳（メタデータ） (2020-02-08T19:41:23Z)

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

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