Systems of sets such that each set properly intersects at most one other set - Application to cluster analysis
Bertrand, Patrice (2008), Systems of sets such that each set properly intersects at most one other set - Application to cluster analysis, Discrete Applied Mathematics, 156, 8, p. 1220-1236. http://dx.doi.org/10.1016/j.dam.2007.05.023
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)A set X is said to properly intersect a set Y if none of the sets X ∩ Y , X\Y and Y \X is empty. In this paper, we consider collections of subsets such that each member of the collection properly intersects at most one other member. Such collections are hereafter called paired hierarchical collections. The two following combinatorial properties are investigated. First, any paired hierarchical collection is a set of intervals of at least one linear order deﬁned on the ground set. Next, the maximum size of a paired hierarchical collection deﬁned on an n-element set is ⌊5/2 (n − 1)⌋. The properties of these collections are also investigated from the cluster analysis point of view. In the framework of the general bijection deﬁned by Batbedat [Les isomorphismes HTS et HTE (après la bijection de Benzécri–Johnson), Metron 46 (1988) 47–59] and Bertrand [Set systems and dissimilarities, European J. Combin. 21 (2000) 727–743], we characterize the dissimilarities that are induced by weakly indexed paired hierarchical collections. Finally, we propose a proof of the so-called agglomerative paired hierarchical clustering (APHC) algorithm that extends the well-known AHC algorithm in order to allow that some clusters can be merged twice. An implementation and some illustrations of this algorithm and of a variant of it were presented by Chelcea et al. [A new agglomerative 2–3 hierarchical clustering algorithm, in: D. Baier, K.-D. Wernecke (Eds.), Innovations in Classiﬁcation, Data Science, and Information Systems (GfKL 2003), Springer, Berlin, 2004, pp. 3–10 and Un Nouvel Algorithme de Classiﬁcation Ascendante 2–3 Hiérarchique, in: Reconnaissance des Formes et Intelligence Artiﬁcielle (RFIA 2004), vol. 3, Toulouse, France, 2004, pp. 1471–1480. Available at http://www.laas.fr/rﬁa2004/actes/ARTICLES/388.pdf].
Subjects / KeywordsInterval set system; Proper intersection; 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