Feb, 2024

在亚指数级混合模型中实现极小化极小聚类误差的通用下界和最优速率

HTML
PDF
TL;DR聚类是无监督机器学习中的关键问题，如何通过混合模型来研究聚类是常见的。本文首先通过契诺夫散度建立了聚类任何混合模型的一个普遍下界，然后证明在具有次指数尾部的混合模型中，迭代算法可以达到这个下界；此外，对于更适合使用泊松或负二项式混合模型的数据集，我们研究了属于指数族的混合模型，在这种混合模型中，我们证明了一种改进的Lloyd算法——Bregman硬聚类，是速率最优的。
发现论文，激发创造
  • 聚类的改进谱范数界限

    本文旨在通过改进 Kumar 和 Kannan [2010] 的分离条件，探讨聚类混合分布。本文通过较弱的分离条件和接近度条件，得出了具有低误差和低 k-均值成本的聚类结果，在某些情况下能够改进高斯模型的分离结果。

    Jun, 2012

  • 近似聚类的最优时间界限

    本文研究了基于k-median目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在O（nk）时间内运行的算法来解决k-median问题。

    Dec, 2012

  • 高维稀疏高斯混合模型的极小极大理论

    本文提供了在高维情况下学习高斯混合物的准确最小值界限和基本限制，研究表明，如果存在决定均值分离的随机维度的稀疏子集，则样本复杂度只取决于相关维度的数量和平均分离，可通过简单的计算有效过程来实现；结果为最近结合特征选择和聚类的方法提供了理论基础的第一步。

    Jun, 2013

  • 混合回归的凸问题形式：两个成分的极小极大优化率

    通过凸优化公式，我们解决了双成分混合回归问题，提供了对同时存在随机和对抗噪声下真实解的可行恢复方案，给出了任意噪声和随机噪声下的上限和匹配的极小值下限，表明我们的算法在特定假设下是信息 量论上最优的，这些结果是首个具有恢复成功保障和恢复误差及样本复杂度紧密界限的可行算法。

    Dec, 2013

  • 基于Bregman Power的k均值算法用于聚类指数族数据

    这篇论文介绍了一种基于Bregman距离的聚类算法，相较于Lloyd的K-means算法，在聚类非高斯数据方面有更好的表现，并提供了理论依据和实验验证。

    Jun, 2022

  • 具有最优性保证的对抗鲁棒聚类

    本文提供了一种新的算法，针对子高斯混合数据，能够在存在异常值的情况下，获得最佳错误率的相对较强聚类结果。

    Jun, 2023

  • Lloyd算法在扰动下的一致性

    在无监督学习的背景下，Lloyd算法是最常用的聚类算法之一。本研究证明了在合适的初始化和小扰动的条件下，Lloyd算法在从次高斯混合中扰动的样本上的误聚类率也在O(log(n))次迭代后呈指数级下降的边界。

    Sep, 2023

  • 离散混合模型的最优聚类：二项式、泊松、块模型和多层网络

    本文研究了具有多层网络时聚类网络的基本极限。我们在混合多层随机块模型下展示了最小极大网络聚类错误率，该率采用指数形式，并由组成网络的边概率分布的Renyi散度来描述。我们提出了一种包括基于张量的初始化算法和基于似然的Lloyd算法的新型两阶段网络聚类方法。网络聚类必须与节点社区检测相结合。我们的算法实现了最小极大网络聚类错误率，在MMSBM下还允许极稀疏网络。数值模拟和实际数据实验证明了我们的方法优于现有方法。此外，我们还将我们的方法和分析框架扩展到包括二项式、泊松和多层泊松网络的离散分布混合中，研究了最小极大聚类错误率。在这些离散混合中，这些最优聚类错误率均采用Renyi散度描述的相同指数形式。我们提出的两阶段聚类算法也可以达到这些离散混合中的最小极大聚类错误率。

    Nov, 2023

  • 在最优分离下聚类有界协方差分布混合

    研究了混合有界协方差分布的聚类问题，使用细粒度分离假设；提供了用于聚类任务的多项式时间算法，并指出了在细粒度均值分离假设下精确聚类是信息理论上不可能的；引入了聚类细化的概念并证明了可以高效计算出样本的精确聚类细化；此外，根据先前工作中的一个变体条件，我们的算法输出准确聚类，甚至适用于一般权重的混合物。

    Dec, 2023

  • 混合模型：一个用于基于模型的聚类的Python一站式库，使用各种混合模型

    《Mixture-Models》是一个开源的Python库，用于拟合高斯混合模型及其变种，如Sparimonious GMM、因子分析混合模型、MClust模型、学生t分布混合模型等。它使用各种一阶/二阶优化算法，如梯度下降和牛顿法，通过自动微分工具简化了这些模型的实现和分析，从而帮助扩展这些模型到高维数据。该库提供了用户友好的模型评估工具，如BIC、AIC和对数似然估计。该软件包具有很高的可扩展性，允许用户轻松地添加新的分布和优化技术。我们进行了大规模模拟实验，比较了各种基于梯度的方法与期望最大化算法在各种设置下的性能，并确定相应最适合的方法。

    Feb, 2024