• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Systems of sets such that each set properly intersects at most one other set - Application to cluster analysis

Thumbnail
Date
2008
Dewey
Probabilités et mathématiques appliquées
Sujet
Interval set system; Proper intersection; Cluster analysis
Journal issue
Discrete Applied Mathematics
Volume
156
Number
8
Publication date
2008
Article pages
1220-1236
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2007.05.023
URI
https://basepub.dauphine.fr/handle/123456789/1828
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Bertrand, Patrice
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Type
Article accepté pour publication ou publié
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 defined on the ground set. Next, the maximum size of a paired hierarchical collection defined 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 defined 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 Classification, Data Science, and Information Systems (GfKL 2003), Springer, Berlin, 2004, pp. 3–10 and Un Nouvel Algorithme de Classification Ascendante 2–3 Hiérarchique, in: Reconnaissance des Formes et Intelligence Artificielle (RFIA 2004), vol. 3, Toulouse, France, 2004, pp. 1471–1480. Available at http://www.laas.fr/rfia2004/actes/ARTICLES/388.pdf].

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.