An interval convexity-based framework for multilevel clustering with applications to single-linkage clustering
Bertrand, Patrice; Diatta, Jean (2024), An interval convexity-based framework for multilevel clustering with applications to single-linkage clustering, Discrete Applied Mathematics, 342, p. 38-63. 10.1016/j.dam.2023.08.003
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Laboratoire d'Informatique et de Mathématiques [LIM]
Abstract (EN)Hierarchies of sets, and most multilevel clustering models, have been characterized asconvexities induced by interval functions satisfying specific properties, thus giving riseto a unifying framework for characterizing multilevel clustering models. Here, we showthat this unifying framework can be relevant to data mining practice. First, we providea flexible characterization of hierarchies and weak hierarchies as interval convexities.Second, we investigate the Apresjan hierarchy and the Bandelt and Dress weak hierarchy,and characterize them as interval convexities. Third, we propose a method for computingrecursively a sequence of path-based dissimilarities which decreases from an arbitrarydissimilarity downto its subdominant ultrametric. We prove that these path-baseddissimilarities define two sequences of nested families of interval convexities. Onesequence increases from the Apresjan hierarchy to the single-link hierarchy, and theother from a subset of the single-link hierarchy to the Bandelt and Dress weak hierarchy.Applications to the simplification and validation of the single-link hierarchy of anarbitrary dissimilarity are discussed.
Subjects / KeywordsApresjan hierarchy; Interval convexity; Single-link hierarchy; Weak hierarchy; Path-based dissimilarities
Showing items related by title and author.