Weak Hierarchies: A Central Clustering Structure

The k-weak hierarchies, for k ≥ 2, are the cluster collections such that the intersection of any (k + 1) members equals the intersection of some k of them. Any cluster collection turns out to be a k-weak hierarchy for some integer k. Weak hierarchies play a central role in cluster analysis in several aspects: they are defined as the 2-weak hierarchies, so that they not only extend directly the well-known hierarchical structure, but they are also characterized by the rank of their closure operator which is at most 2. The main aim of this chapter is to present, in a unique framework, two distinct weak hierarchical clustering approaches. The first one is based on the idea that, since clusters must be isolated, it is natural to determine them as weak clusters defined by a positive weak isolation index. The second one determines the weak subdominant quasi-ultrametric of a given dissimilarity, and thus an optimal closed weak hierarchy by means of the bijection between quasi-ultrametrics and (indexed) closed weak hierarchies. Furthermore, we highlight the relationship between weak hierarchical clustering and formal concepts analysis, through which concept extents appear to be weak clusters of some multiway dissimilarity functions.