Abstract | ||
---|---|---|
Sub-dominant theory provides efficient tools for clustering. However, it classically works only for ultrametrics and ad hoc extensions like Jardine and Sibson's 2-ultrametrics. In this paper we study the extension of the notion of sub-dominant to other distance models in classification accounting for overlapping clusters.We prove that a given dissimilarity admits one and only one lower-maximal quasi-ultrametric and one and only one lower-maximal weak k-ultrametric. In addition, we also prove the existence of (several) lower-maximal strongly Robinsonian dissimilarities. The construction of the lower-maximal weak k-ultrametric (for k = 2) and quasi-ultrametric can be performed in polynomial time. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.dam.2005.09.011 | Discrete Applied Mathematics |
Keywords | Field | DocType |
dissimilarity,robinsonian dissimilarity,quasi-ultrametric,lower-maximal weak k-ultrametric,strongly robinsonian dissimilarities,lower-maximal quasi-ultrametric,efficient tool,sub-dominant,distance model,classification accounting,overlapping cluster,numerical taxonomy,polynomial time,sub-dominant theory | Numerical taxonomy,Combinatorics,Cluster analysis,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
154 | 7 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.57 | 5 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
François Brucker | 1 | 39 | 4.04 |