On order-constrained transitive distance clustering

Zhiding Yu, Weiyang Liu, Wenbo Liu, Yingzhen Yang, Ming Li, B. V.K.Vijaya Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publication30th AAAI Conference on Artificial Intelligence, AAAI 2016
PublisherAAAI press
Number of pages7
ISBN (Electronic)9781577357605
StatePublished - 2016
Externally publishedYes
Event30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, United States
Duration: Feb 12 2016Feb 17 2016

Publication series

Name30th AAAI Conference on Artificial Intelligence, AAAI 2016


Other30th AAAI Conference on Artificial Intelligence, AAAI 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'On order-constrained transitive distance clustering'. Together they form a unique fingerprint.

Cite this