Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D

01/25/2017

∙

by   Allan Grønlund, et al.

∙

0

∙

share

The k-Means clustering problem on n points is NP-Hard for any dimension d> 2, however, for the 1D case there exist exact polynomial time algorithms. Previous literature reported an O(kn^2) time dynamic programming algorithm that uses O(kn) space. We present a new algorithm computing the optimal clustering in only O(kn) time using linear space. For k = Ω( n), we improve this even further to n 2^O(√( n k)) time. We generalize the new algorithm(s) to work for the absolute distance instead of squared distance and to work for any Bregman Divergence as well.