A Streaming Algorithm for k-Means with Approximate Coreset
Min Li, Dachuan Xu, Dongmei Zhang, Tong Zhang · Asia Pacific Journal of Operational Research · 2019
For computing the [Formula: see text]-means clustering of the streaming and distributed big sparse data, we present an algorithm to obtain the sparse coreset for the [Formula: see text]-means in polynomial time. This algorithm is mainly based on the explicit form of the center of mass and the approximate [Formula: see text]-means. Because of the existence of the approximation, the coreset of the output inevitably has a factor, which can be controlled to be a very small constant.