The k-weak hierarchical representations: an extension of the indexed closed weak hierarchies
Bertrand, Patrice; Janowitz, Melvin F. (2003), The k-weak hierarchical representations: an extension of the indexed closed weak hierarchies, Discrete Applied Mathematics, 127, 2, p. 199-220. http://dx.doi.org/10.1016/S0166-218X(02)00206-8
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Janowitz, Melvin F.
Center for Discrete Mathematics and Theoretical Computer Science [Rutgers] [DIMACS]
Abstract (EN)Several approaches have been proposed for the purpose of proving that different classes of dissimilarities (e.g. ultrametrics) can be represented by certain types of stratified clusterings which are easily visualized (e.g. indexed hierarchies). These approaches differ in the choice of the clusters that are used to represent a dissimilarity coefficient. More precisely, the clusters may be defined as the maximal linked subsets, also called ML-sets; equally they may be defined as a particular type of 2-ball. In this paper, we first introduce the notion of a k-ball, thereby extending the notion of a 2-ball. For an arbitrary dissimilarity coefficient, we establish some properties of the k-balls that pinpoint the connection between them and the ML-sets. We also introduce the (2,k)-point condition (kgreater-or-equal, slanted1) which is an extension of the Bandelt four-point condition.For kgreater-or-equal, slanted2, we prove that the dissimilarities satisfying the (2,k)-point condition are in one–one correspondence with a class of stratified clusterings, called k-weak hierarchical representations, whose main characteristic is that the intersection of (k+1) arbitrary clusters may be reduced to the intersection of some k of these clusters.
Subjects / KeywordsDiscrete Mathematics; Cluster Analysis
Showing items related by title and author.
Decomposition of the Rand index in order to assess both the stability and the number of clusters of a partition El Moubarki, Lassad; Bertrand, Patrice; Bel Mufti, Ghazi (2012) Document de travail / Working paper