Multi-View Hierarchical Clustering using Optimal Transport

Abstract

With the growing availability of multi-view data, development of multi-view clustering algorithms has gained prominence among researchers. However, most of these algorithms are either based on subspace, graph or spectral clustering techniques, with very few works done in terms of hierarchical clustering. In this work, we aim to develop a Multi-View Agglomerative Hierarchical Clustering algorithm which uses Optimal Transport (OT) for calculating distances between clusters. This takes into consideration the entire data distribution of the clusters, unlike traditional single or complete linkage techniques. When incorporated naively in hierarchical clustering, OT imposes high time complexity. To tackle this we have a Nearest Neighbor Agglomeration (NNA) step which merges multiple clusters in each iteration using chains of first nearest neighbors. This subsequently results in very few iterations and we show that incorporating OT in this setup still leads to relatively low time complexity. Before NNA we have a Cosine or Euclidean Distance Integration (CDI/EDI) step, which essentially calculates the distance between two data samples as the average over their distances in all the views. Extensive experiments performed on both single-view and multi-view datasets illustrate the efficiency of our algorithm when compared to other state-of-the-art single-view hierarchical clustering and multi-view clustering algorithms respectively.