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

ICMLJun, 2023

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

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang

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

Abstract

$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find sublinear-time →

k-clustering quantum algorithms coresets approximation query complexity

发现论文，激发创造

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

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

Oct, 2018

k-Means 的量子逼近方案

我们给出了在 QRAM 模型中，对于经典 k - 均值聚类问题的量子逼近方案（即对于每个 ε>0，具有（1+ε）- 逼近），其运行时间只有数据点数量的对数多项式依赖。具体而言，对于存储在 QRAM 数据结构中的包含 N 个在 R^d 中的点的数据集 V，我们的量子算法以时间 Γ(O)((2^(Γ(O)(k/ε)))η^2d) 运行，并且以高概率输出一个包含 k 个中心的集合 C，其中 cost (V, C) ≤ (1+ε)・cost (V, C_OPT)。这是第一个具有对 k - 均值问题具有（1+ε）可证逼近保证且具有多项式对数运行时间的量子算法。此外，与先前的无监督学习方法不同，我们的量子算法不需要量子线性代数子程序，并且其运行时间与出现在这些过程中的参数（例如条件数）无关。

Aug, 2023

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

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

Feb, 2018

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

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

Oct, 2023

基于轮廓 Coreset 和变分量子本征求解的聚类

我们提出使用变分量子本征求解器 (VQE) 和定制的 Contour 核心集方法来解决 k-means 聚类问题，与现有的 QAOA + 核心集 k-means 聚类方法相比，我们的 VQE + Contour 核心集方法在高准确性和较低标准差方面表现更好。

Dec, 2023

q-means：一种用于无监督机器学习的量子算法

本研究介绍了 q-means 算法，一种用于聚类的新型量子算法，该算法具有与 $k$-means 类似的收敛性和精度保证，并且输出 $k$ 个集群中心的好近似值。此算法的运行时间呈多项式级别，优于经典算法，尤其适用于大型数据集。

Dec, 2018

一种聚类的新 Coreset 框架

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

Apr, 2021

你知道什么是 q-means 吗？

改进版的 q-means 量子算法和 dequantized 算法，分别以 O ((k^2)/(ε^2)(√k*d + log (Nd))) 和 O ((k^2)/(ε^2)(kd + log (Nd))) 的时间复杂度在近似 k-means 聚类中取得优化，其中 k 代表簇数量，ε 代表误差率，N 代表向量数量，d 代表向量维度。

Aug, 2023

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

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

Jun, 2019

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

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

Jun, 2011