提出近最优聚类算法，解决多马尔可夫链轨迹的精准分组问题。
Near-Optimal Clustering in Mixture of Markov Chains
- 基于谱聚类与新嵌入方法，实现马尔可夫链轨迹高效分组
- 在合理轨迹数与长度下，聚类误差率接近理论下限
- 适用于复杂动态系统建模，适合有概率轨迹数据的研究者
研究由 K 个未知遍历马尔可夫链在大小为 S 的有限状态空间上生成的 T 条长度为 H 的轨迹聚类问题。我们推导出一个实例相关、高概率的聚类误差率下界，受转移核之间的平稳加权 KL 散度支配。随后提出两阶段算法：第一阶段通过一种新的可注入欧氏嵌入对遍历马尔可夫链进行谱聚类，该贡献独立具有价值，能实现紧致浓度结果；第二阶段通过单步似然重分配精炼聚类。证明在合理的 T 与 H 条件下，该算法能以高概率达到近最优聚类误差。初步实验支持该方法，最后讨论其局限性与扩展方向。
原文摘要 · Abstract (English)
We study the problem of clustering $T$ trajectories of length $H$, each generated by one of K unknown ergodic Markov chains over a finite state space of size $S$. We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the stationary-weighted KL divergence between transition kernels. We then propose a two-stage algorithm: Stage I applies spectral clustering via a new injective Euclidean embedding for ergodic Markov chains, a contribution of independent interest enabling sharp concentration results; Stage II refines clusters with a single likelihood-based reassignment step. We prove that our algorithm achieves near-optimal clustering error with high probability under reasonable requirements on $T$ and $H$. Preliminary experiments support our approach, and we conclude with discussions of its limitations and extensions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。