An a contrario approach to hierarchical clustering validity assessment

Frédéric Cao (1) , Julie Delon (2) , Agnès Desolneux (3) , Pablo Musé (2) , Frédéric Sur (2)

1 VISTA - Vision spatio-temporelle et active
2 CMLA - Centre de Mathématiques et de Leurs Applications
3 UPD5 Mathématiques Informatique - Université Paris Descartes - UFR de Mathématiques et Informatique

In this paper we present a method to detect natural groups in a data set, based on hierarchical clustering. A measure of the meaningfulness of clusters, derived from a background model assuming no class structure in the data, provides a way to compare clusters, and leads to a cluster validity criterion. This criterion is applied to every cluster in the nested structure. While all clusters passing the validity test are meaningful in themselves, the set of all of them will probably provide a redundant data representation. By selecting a subset of the meaningful clusters, a good data representation, which also discards outliers, can be achieved. The strategy we propose combines a new merging criterion (also derived from the background model) with a selection of local maxima of the meaningfulness with respect to inclusion, in the nested hierarchical structure.

Mots clés: HIERARCHICAL CLUSTERING; A CONTRARIO MODEL; NUMBER OF FALSE ALARMS; HELMHOLTZ PRINCIPLE; MAXIMALITY

Domaines: Autre [cs.OH]

Frédéric Cao, Julie Delon, Agnès Desolneux, Pablo Musé, Frédéric Sur. An a contrario approach to hierarchical clustering validity assessment. [Research Report] RR-5318, INRIA. 2004, pp.15. ⟨inria-00070682⟩