Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. (arXiv:1701.07204v2 [cs.DS] UPDATED)

The $k$-Means clustering problem on $n$ points is NP-Hard for any dimension $d\ge 2$, however, for the 1D case there exist exact polynomial time algorithms. Previous literature reported an $O(kn^2)$ dynamic programming algorithm that uses $O(kn)$ space. We present a new algorithm improving this to $O(n\log n+ kn)$ time and optimal $O(n)$ space. We generalize our algorithm to work for the absolute distance instead of squared distance and to work for any Bregman Divergence as well.

from cs.AI updates on arXiv.org http://ift.tt/2k5Hxo1
via IFTTT