Empirical risk approximation : A statistical learning theory of data clustering
k-means data clustering estimates a partition of a vectorial data set in an unsupervised way. The partition assigns data to clusters and it is represented by a set of cluster centers. We apply computational learning theory to discuss the nature of phase transitions in data clustering. The requirement that the partition has to generalize from one data sample set to a second sample set drawn from the same distribution yields a new combinatorial parameter selection criterion for cluster splits. Our analysis demonstrates that maximum entropy based approximations schemes are optimal continuation methods for optimization with build-in control of model complexity.