On Order-Constrained Transitive Distance Clustering

Authors

  • Zhiding Yu Carnegie Mellon University
  • Weiyang Liu Peking University
  • Wenbo Liu Sun Yat-sen University
  • Yingzhen Yang University of Illinois at Urbana-Champaign
  • Ming Li Sun Yat-sen University
  • B. V. K. Vijaya Kumar Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v30i1.10290

Keywords:

Transitive Distance, Clustering, Order-constrained

Abstract

We consider the problem of approximating order-constrained transitive distance (OCTD) and its clustering applications. Given any pairwise data, transitive distance (TD) is defined as the smallest possible "gap" on the set of paths connecting them. While such metric definition renders significant capability of addressing elongated clusters, it is sometimes also an over-simplified representation which loses necessary regularization on cluster structure and overfits to short links easily. As a result, conventional TD often suffers from degraded performance given clusters with "thick" structures. Our key intuition is that the maximum (path) order, which is the maximum number of nodes on a path, controls the level of flexibility. Reducing this order benefits the clustering performance by finding a trade-off between flexibility and regularization on cluster structure. Unlike TD, finding OCTD becomes an intractable problem even though the number of connecting paths is reduced. We therefore propose a fast approximation framework, using random samplings to generate multiple diversified TD matrices and a pooling to output the final approximated OCTD matrix. Comprehensive experiments on toy, image and speech datasets show the excellent performance of OCTD, surpassing TD with significant gains and giving state-of-the-art performance on several datasets.

Downloads

Published

2016-03-02

How to Cite

Yu, Z., Liu, W., Liu, W., Yang, Y., Li, M., & Kumar, B. V. K. V. (2016). On Order-Constrained Transitive Distance Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10290

Issue

Section

Technical Papers: Machine Learning Methods