Skip to main content

On order-constrained transitive distance clustering

Publication ,  Conference
Yu, Z; Liu, W; Yang, Y; Li, M; Kumar, BVKV
Published in: 30th AAAI Conference on Artificial Intelligence, AAAI 2016
January 1, 2016

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.

Duke Scholars

Published In

30th AAAI Conference on Artificial Intelligence, AAAI 2016

Publication Date

January 1, 2016

Start / End Page

2293 / 2299
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Yu, Z., Liu, W., Yang, Y., Li, M., & Kumar, B. V. K. V. (2016). On order-constrained transitive distance clustering. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016 (pp. 2293–2299).
Yu, Z., W. Liu, Y. Yang, M. Li, and B. V. K. V. Kumar. “On order-constrained transitive distance clustering.” In 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2293–99, 2016.
Yu Z, Liu W, Yang Y, Li M, Kumar BVKV. On order-constrained transitive distance clustering. In: 30th AAAI Conference on Artificial Intelligence, AAAI 2016. 2016. p. 2293–9.
Yu, Z., et al. “On order-constrained transitive distance clustering.” 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 2293–99.
Yu Z, Liu W, Yang Y, Li M, Kumar BVKV. On order-constrained transitive distance clustering. 30th AAAI Conference on Artificial Intelligence, AAAI 2016. 2016. p. 2293–2299.

Published In

30th AAAI Conference on Artificial Intelligence, AAAI 2016

Publication Date

January 1, 2016

Start / End Page

2293 / 2299