Top-down vs Bottom-up methods of Linkage for Asymmetric Agglomerative Hierarchical Clustering

Algorithms of agglomerative hierarchical clustering using asymmetric similarity measures are studied. We classify linkage methods into two categories of bottom-up methods and top-down methods. The bottom-up methods first defines a similarity measure between two object, and extends it to similarity between clusters. In contrast, top-down methods directly define similarity between clusters. In classical linkage methods based on symmetric similarity measures, the single linakge, complete linkage, and average linkage are bottom-up, while the centroid method and the Ward methods are top-down. We propose two a top down method and a family of bottom-up method using asymmetric similarity measures. A dendrogram which is the output of hierarchical clustering often has reversals. We show conditions that dendrogram have no reversals. It is proved that the proposed methods have no reversals in the dendrograms. Two different techniques to show asymmetry in the dendrogram are used. Examples based on real data show how the methods work.