  Finding a set of nested partitions of a dataset is useful to uncover relevant
structure at different scales, and is often dealt with a data-dependent
methodology. In this paper, we introduce a general two-step methodology for
model-based hierarchical clustering. Considering the integrated classification
likelihood criterion as an objective function, this work applies to every
discrete latent variable models (DLVMs) where this quantity is tractable. The
first step of the methodology involves maximizing the criterion with respect to
the partition. Addressing the known problem of sub-optimal local maxima found
by greedy hill climbing heuristics, we introduce a new hybrid algorithm based
on a genetic algorithm efficiently exploring the space of solutions. The
resulting algorithm carefully combines and merges different solutions, and
allows the joint inference of the number $K$ of clusters as well as the
clusters themselves. Starting from this natural partition, the second step of
the methodology is based on a bottom-up greedy procedure to extract a hierarchy
of clusters. In a Bayesian context, this is achieved by considering the
Dirichlet cluster proportion prior parameter $\alpha$ as a regularization term
controlling the granularity of the clustering. A new approximation of the
criterion is derived as a log-linear function of $\alpha$, enabling a simple
functional form of the merge decision criterion. This second step allows the
exploration of the clustering at coarser scales. The proposed approach is
compared with existing strategies on simulated as well as real settings, and
its results are shown to be particularly relevant. A reference implementation
of this work is available in the R package greed accompanying the paper.
