Entropical K-means for clustering and an alternating algorithm
摘要
In this paper, we generalize the entropical optimal transport to the free entropical optimal transport, and use the latter as our tool for studying the nonpolynomial (NP)-hard problem of K-means. In fact, the semi-free entropical optimal transport conducts us to introduce a new entropical cost function of K-means for the clustering of a dataset or more generally for finding some good approximation of K-barycenters of a general probability distribution, instead of the least square cost in the classic K-means. The new entropical cost function leads naturally to a new probabilistic algorithm (called entropical K-means or EK-means simply, a probabilistic regularization of Lloyd’s K-means), which is different from the known ones, and very fast in computation. Our free entropical optimal transport approach and algorithm for K-means work not only for distributions of data in the continuum space ℝd, but also for distributions of discrete data.