Sketched Clustering via Hybrid Approximate Message Passing
Sketched Clustering via Hybrid Approximate Message Passing
复制标题
DOI：
10.1109/tsp.2019.2924585
复制
发表时间：
2017-12
影响因子：
5.4
通讯作者：
Evan Byrne;R. Gribonval;Philip Schniter
中科院分区：
文献类型：
--
作者：
Evan Byrne;R. Gribonval;Philip Schniter
在草绘聚类中，首先将$T$样本的数据集草绘成一个中等大小的向量，然后从该向量中提取质心。它的优点包括：1)降低了存储复杂度；2)质心提取复杂度独立于$T$。对于Keriven等人最近提出的可被解释为经验特征函数的随机抽样的草图方法，我们提出了一种基于近似消息传递的草图聚类算法。数值实验表明，在计算复杂度和样本复杂度方面，我们的方法比目前最先进的草图聚类算法CL-OMPR更有效，当$T$较大时，比k-Means++更有效。
In sketched clustering, a dataset of $T$ samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Its advantages include 1) reduced storage complexity and 2) centroid extraction complexity independent of $T$. For the sketching methodology recently proposed by Keriven et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when $T$ is large.