聚类编码计算大提速！从多项式到线性，聚类数秒出结果！
Stochastic complexity of vectors containing cluster structure
📖 AI 总结
本文研究含聚类结构向量的随机复杂度计算问题，基于归一化最大似然（NML）模型求解最短编码长度。该问题在最小描述长度（MDL）原则下的数据聚类中具有重要理论与实用价值，可用于估计最优聚类数量和聚类结构。传统上，基于NML模型直接计算含聚类结构向量的最短编码长度，其时间复杂度随向量规模和聚类数量呈多项式增长。作者通过引入递归公式高效计算NML模型中的归一化常数，将时间复杂度从多项式降至线性，从而证明该问题具有可解性。这一改进显著提升了聚类结构评估的计算效率，为大规模数据聚类分析提供了更优的理论基础。
🔑 关键词速览
| Normalized Maximum Likelihood (NML) | 一种用于最小描述长度原理的模型，通过归一化似然函数来计算随机复杂度。 |
| Minimum Description Length (MDL) | 一种模型选择原则，选择能最短描述数据的模型，平衡拟合度和复杂度。 |
| Stochastic complexity | 在给定模型类下，数据的最短编码长度，用于衡量数据的随机性。 |
| Cluster structure | 数据中自然形成的分组模式，聚类分析旨在发现这种结构。 |
| Normalizing constant | 在概率模型中用于确保概率分布总和为1的常数，NML中需计算此常数。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅