Hierarchical clustering based on ordinal consistency

摘要

Hierarchical clustering is the grouping of objects of interest according to their similarity into a hierarchy, with different levels reflecting the degree of inter-object resemblance. It is an important area in data analysis and pattern recognition. In this paper, we propose a new approach for robust hierarchical clustering based on possibly incomplete and noisy similarity data. Our approach uses a novel perspective in finding the object hierarchy by trying to optimize ordinal consistency between the available similarity data and the hierarchical structure. Using experiments we show that our approach is able to perform more effectively than similar algorithms when there are substantial noises in the data. Furthermore, when similarity-ordering information is only available in the form of incomplete pairwise similarity comparisons, our approach can still be applied directly. We illustrate this by applying our approach to randomly generated hierarchies and phylogenetic tree construction from quartets, an important area in computational biology.