Apr, 2020

欧几里得空间聚类的核心集：重要性采样几乎是最佳的

PDF
TL;DR本研究提出了一种统一的两阶段重要性采样框架，可构建 (k,z) 聚类问题的 ε-coreset。该算法依赖于将两个形状拟合问题连接起来的新的降维技术，绕过了之前的构造时间和核心集大小的限制，并提供了一个核心集的下界。
发现论文，激发创造
  • 一种聚类的新 Coreset 框架

    本文介绍了一种新的 coresets 框架，可以在欧氏空间、翻倍度量、无小度量和一般的度量情况下同时改善 k - 中位数和 k - 均值聚类等问题的最优解的界限。

    Apr, 2021

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

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

    Oct, 2018

  • 离散几何空间中鲁棒聚类的参数化逼近

    本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

    May, 2023

  • 离线和流式 Coreset 构建的新框架

    本文提出一种改进的 coreset 构建方法，利用 sensitivity sampling 技术，并对 VC dimension 类的函数的采样复杂度进行分析，从而能够更加高效地解决包括聚类等在内的机器学习问题。

    Dec, 2016

  • 分类学习的核心集 - 简化与加强

    给定一种数据矩阵和标签向量，我们使用基于 $l_1$ 拉索 (weight) 的数据子采样方法构建相对误差 Coresets，用于训练包括逻辑损失和铰链损失在内的一系列损失函数的线性分类器，其结果不仅在理论上得到了显著提高，而且在实践中表现优异，可用于主动学习并用于多种训练方案。

    Jun, 2021

  • 逼近和聚类数据的统一框架

    该研究考虑了针对一组正函数的最小化问题，给出了一个压缩表示法（coresets），用于形状拟合（shape fitting）和近似聚类（approxiate clustering）问题。他们将 epsilon-approximations 与 PAC Learning 和 VC dimension 相联系，并给出了一般函数集的 coresets 的线性时间近似计算方法。

    Jun, 2011

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

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

    Jun, 2023

  • 核密度估计的近似最优核心集

    本文提出了一种能够有效构建 coresets 的方法，可以进行内核密度估计，特别适用于正定内核，且适用于机器学习中非常重要的信息距离和 sinc 内核。

    Feb, 2018

  • 具有公平约束的聚类核心集

    本文提出了一种公平的聚类方法，可以对数据点进行聚类而确保每个聚类中各类别比例的公平分配。该方法采用了基于新构建的核心集的方法，并使用该方法高效处理类别复杂、性别等多个敏感类型的数据，并在成人 (Adult)、银行 (Bank)、糖尿病 (Diabetes) 和运动员 (Athlete) 数据集上得到了实证结果。

    Jun, 2019

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

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

    Apr, 2024