  We address the new problem of estimating a piece-wise constant signal with
the purpose of detecting its change points and the levels of clusters. Our
approach is to model it as a nonparametric penalized least square model
selection on a family of models indexed over the collection of partitions of
the design points and propose a computationally efficient algorithm to
approximately solve it. Statistically, minimizing such a penalized criterion
yields an approximation to the maximum a posteriori probability (MAP)
estimator. The criterion is then analyzed and an oracle inequality is derived
using a Gaussian concentration inequality. The oracle inequality is used to
derive on one hand conditions for consistency and on the other hand an adaptive
upper bound on the expected square risk of the estimator, which statistically
motivates our approximation. Finally, we apply our algorithm to simulated data
to experimentally validate the statistical guarantees and illustrate its
behavior.
