你知道什么是 q-means 吗？

Aug, 2023

Do you know what q-means?

João F. Doriguello, Alessandro Luongo, Ewin Tang

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

Abstract

clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's iteration for $k$-means. This iteration takes $N$ vectors $v_1,\dots,v_N\

clustering k-means quantum algorithm q-means time complexity

发现论文，激发创造

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

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

Dec, 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

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

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

Oct, 2023

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

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

Jun, 2023

量子变分和量子启发式聚类

本研究提出了一种基于变分量子电路的量子算法，用于对数据进行聚类；该算法可以将数据分类为多个聚类，并且可以在少量量子比特的嘈杂中间量子计算设备上轻松实现。

Jun, 2022

量子期望最大化算法

本文通过基于 k-means 算法的量子聚类算法，提出了一种基于量子 EM 算法的高斯混合模型算法，证明了该算法的鲁棒性和量子加速优势以及 GMM 在非平凡聚类数据中的优势。

Aug, 2019

基于产品量化码的亿级别聚类算法 (PQk-means)

本文研究针对大规模数据的聚类问题，提出一种基于短 PQ 码的高效聚类方法 PQk-means，能在低内存消耗下进行高维度向量的聚类，并在实验上获得了较好的结果。