一种聚类的新 Coreset 框架
本研究提出了一种统一的两阶段重要性采样框架,可构建 (k,z) 聚类问题的 ε-coreset。该算法依赖于将两个形状拟合问题连接起来的新的降维技术,绕过了之前的构造时间和核心集大小的限制,并提供了一个核心集的下界。
Apr, 2020
该文提出了一种叫做 “通用弱核心集” 的概念,用于约束聚类设置中,与最近的约束设置下核心集构建结合使用,能够给出更大的数据压缩、概念上更简单,适用于广泛的约束 $k$- 中位数和 $k$- 均值问题。
May, 2023
提出了一种轻量级 coresets 算法,用于 k-means 聚类和 Bregman 聚类,能同时允许乘性和加性误差,在计算效率和结果集大小方面优于现有方法,并可用于统计 k-means 聚类的计算小型模型的摘要。
Feb, 2017
本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用,提出了相应的算法,其中在特殊的欧几里得空间中得到了较好的近似结果。
May, 2023
本研究提出一种称为 coresets 的降维方法,可用于在高维欧几里得空间中降低大量数据点的大小,适用于多种数据分析技术,包括 k-means 聚类、主成分分析和子空间聚类,并允许流式处理或分布式算法,其大小与输入点的数量和维度无关。
Jul, 2018
本文提出了一种公平的聚类方法,可以对数据点进行聚类而确保每个聚类中各类别比例的公平分配。该方法采用了基于新构建的核心集的方法,并使用该方法高效处理类别复杂、性别等多个敏感类型的数据,并在成人 (Adult)、银行 (Bank)、糖尿病 (Diabetes) 和运动员 (Athlete) 数据集上得到了实证结果。
Jun, 2019
本文研究 coresets 和机器学习领域中的最新进展,提出了一种理论上可行的框架来创建分类问题的 coresets,应用到了 $k$-means 聚类问题,同时总结了当前在 MLE 混合模型、贝叶斯非参数模型、主成分分析、回归和经验风险最小化等领域中已有的 coreset 构建算法。
Mar, 2017
本文提出一种改进的 coreset 构建方法,利用 sensitivity sampling 技术,并对 VC dimension 类的函数的采样复杂度进行分析,从而能够更加高效地解决包括聚类等在内的机器学习问题。
Dec, 2016
本文针对公平聚类提出了一种基于随机抽样的核心集构建法,使得可以在一般度量空间中获得公平聚类的第一个核心集,以及在欧氏空间中实现核心集大小不呈指数级增长的公平聚类。此外,还推导了针对受限聚类问题的核心集构造方案,并通过此方案提出了一些新的近似算法。
Jul, 2020