Nov, 2015

流式和分布式大稀疏数据的 k-Means

PDF
TL;DR一个可证明近似稀疏大数据 K-means 问题的流式算法及其性能提升结果，应用了一种稀疏的 (k, ε) 子集算法，可在不依赖于数据和维度的情况下，精确地计算每个点到 k 个中心的平方距离之和，从而使得在离线设置下的启发式算法的性能得到了大幅提升。
streaming algorithmk-meanssparse big datacoresetperformance improvement
发现论文，激发创造
  • 使用核心集降维海量稀疏数据集

    本文提出了一种解决大规模稀疏矩阵降维问题的实用方法，该方法使用核心集来近似计算矩阵的降维近似值，是计算低秩近似的有效算法。

    Mar, 2015

  • 数据流中的差分隐私聚类

    论文提出了不同隐私性水平的 k-means 和 k-median 流式聚类算法，采用核心集算法作为黑盒子并使用多项式空间达到恒定乘性错误和多项式加性错误。

    Jul, 2023

  • 一维投影聚类的简单、可扩展和有效方法

    非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn)，并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。

    Oct, 2023

  • k 均值和 k 中位数聚类的核心集及其应用

    该研究的主要内容是利用 coreset 技术提高 k-means 和 k-median 聚类的近似算法，并且可以在流式数据中保持聚类结果。

    Oct, 2018

  • 将大数据转化为小数据：k 均值、主成分分析和投影聚类的常量大小核心集

    本研究提出一种称为 coresets 的降维方法，可用于在高维欧几里得空间中降低大量数据点的大小，适用于多种数据分析技术，包括 k-means 聚类、主成分分析和子空间聚类，并允许流式处理或分布式算法，其大小与输入点的数量和维度无关。

    Jul, 2018

  • 公平 k 均值聚类的公平核心集和流算法

    本文研究公平聚类问题，提出一种利用核心集合来显著减小输入数据规模的算法，证明了核心集合的可组合性，提出了 Lloyd 算法的变体，并将其扩展为公平 k-means ++ 聚类算法，实现了这些算法并提供了经验证据，表明我们的方法得以规模化运行。

    Dec, 2018

  • 聚类大数据的收敛时间与准确度权衡

    研究在大型数据集上 k-means 和 k-median 聚类的理论和实际运行限制，通过快速压缩数据并在压缩表示上进行聚类，提供了有效聚类的理论和实践蓝图。

    Apr, 2024

  • 解决大规模数据模型中的公平 k 中心问题

    本文介绍了一项新的流式和分布式算法，用于公平的数据汇总，旨在解决算法公平性方面的研究问题。

    Feb, 2020

  • 针对聚类问题的近优量子核心集构建算法

    该研究在量子计算的框架下，提出了一种在时空复杂度上具有优势的 k - 聚类问题的量子算法，并在算法的基础上得到了一个核心集。

    Jun, 2023

  • 对称张量分解的流式核心集

    本研究重要的优化模块是张量分解，特别是在潜变量模型中。作者介绍了两种新的算法技术：在线过滤和核化，并提供了六种算法来实现不同的核心集大小、更新时间和工作空间的折衷方案，以击败或匹配各种现有算法。在矩阵的情况下，作者的在线行采样算法保证了（1 + ε）的相对误差谱逼近。本研究还展示了张量分解在学习单主题建模中的应用。

    Jun, 2020