Order Preserving Hierarchical Clustering

Abstract

Partial orders and directed acyclic graphs are common data structures that arise naturally in numerous applications, and that define order between data points. Examples are orders of tasks in a project plan, transaction orders in distributed ledgers and execution sequences in computer programs, to mention a few. On the other hand, hierarchical clustering is one of the oldest and most used methods for unsupervised classification and exploratory data analysis. In spite of this, few methods are rigged to take into account the information encoded in the order relation when performing hierarchical clustering of partially ordered data. In his research, Daniel R. Bakkelund has developed new mathematical theory and algorithms to include this information in methods for hierarchical clustering, resulting in the concept of "order preserving hierarchical clustering". The efficacy of theories are demonstrated through experiments on real world data, and show that the in comparison with existing methods, the new methods excel both in cluster quality and order preservation.