On the Optimal Number of Clusters in Histogram Clustering
Clusters in data clustering should be robust to sample fluctuation, i.e., the estimate of cluster parameters on a second sample set should yield qualitatively similar results. This robustness requirement can be quantified by large deviation arguments from statistical learning theory. We use the principle of Empirical Risk Approximation to determine an optimal number of clusters for the case of histogram clustering. The analysis validates stochastic approximation algorithms like Markov Chain Monte Carlo which maximize the entropy for fixed optimization costs.