An interval convexity-based framework for multilevel clustering with applications to single-linkage clustering
Bertrand, Patrice; Diatta, Jean (2022), An interval convexity-based framework for multilevel clustering with applications to single-linkage clustering. https://basepub.dauphine.psl.eu/handle/123456789/24063
TypeDocument de travail / Working paper
Series titleCahier de recherche CEREMADE, Université Paris Dauphine-PSL
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 as convexities induced by interval functions satisfying specific properties, thus giving rise to a unifying framework for characterizing multilevel clustering models. Here, we show that this unifying framework can be relevant to data mining practice. First, we provide a 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 computing recursively a sequence of path-based dissimilarities which decreases from an arbitrary dissimilarity downto its subdominant ultrametric. We prove that these path-based dissimilarities define two sequences of nested families of interval convexities. One sequence increases from the Apresjan hierarchy to the single-link hierarchy, and the other 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 an arbitrary dissimilarity are discussed.
Subjects / KeywordsApresjan hierarchy; Interval convexity; Single-link hierarchy; Weak hierarchy; Path-based dissimilarities
Showing items related by title and author.
Bertrand, Patrice; Diatta, Jean (2017) Article accepté pour publication ou publié
Bertrand, Patrice; Diatta, Jean (2013) Article accepté pour publication ou publié
Bertrand, Patrice; Diatta, Jean (2014-09) Communication / Conférence
Bertrand, Patrice; Diatta, Jean (2019) Communication / Conférence
Bertrand, Patrice; Diatta, Jean (2022) Communication / Conférence