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

Oct, 2018

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

Coresets for $k$-Means and $k$-Median Clustering and their Applications

Sariel Har-Peled, Soham Mazumdar

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

Abstract

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\eps}{{\varepsilon}} \newcommand{\coreset}{{\mathcal{S}}} $ In this paper, we show the existence of small coresets for the problems of computing $k$-median and $k$-means clustering for points in low dimension. In other words

coreset k-means clustering k-median clustering approximation streaming

发现论文，激发创造

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

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

Jun, 2019

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

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

Jun, 2023

通用弱核心集

该文提出了一种叫做 “通用弱核心集” 的概念，用于约束聚类设置中，与最近的约束设置下核心集构建结合使用，能够给出更大的数据压缩、概念上更简单，适用于广泛的约束 $k$- 中位数和 $k$- 均值问题。

May, 2023

基于轻量级核心集的可扩展 k 均值聚类

提出了一种轻量级 coresets 算法，用于 k-means 聚类和 Bregman 聚类，能同时允许乘性和加性误差，在计算效率和结果集大小方面优于现有方法，并可用于统计 k-means 聚类的计算小型模型的摘要。

Feb, 2017

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

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

Dec, 2016

一种聚类的新 Coreset 框架

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

Apr, 2021

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

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

Feb, 2018

通过链接实现内核密度估计的更强核心集界限

应用偏差方法和串联方法提供改进的核函数广泛类别 Coreset 复杂性的界限，并给出对于高斯核和拉普拉斯核，在数据集均匀有界的情况下，产生 O (√d/ε√loglog (1/ε)) 大小的 Coreset 的随机多项式时间算法，这是以前的技术所不可能的改进。此外，对于恒定的 d，我们得到 O (1/ε√loglog (1/ε)) 大小的拉普拉斯核的 Coreset。最后，我们给出了指数核、Hellinger 核和 JS 核 Coreset 复杂性的最佳已知界限，其中 1/α 是核的带宽参数。

Oct, 2023

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

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

Apr, 2020

多重 $\ell_p$ 回归的核心集

通过构建核心集，我们实现了对多个响应的多元回归目标的近似，并得到了关于样本数量和子空间逼近的几乎最优的界限。

Jun, 2024