By the same authors

From the same journal

From the same journal

Learning shape-classes using a mixture of tree-unions

Research output: Contribution to journalArticle



Publication details

JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
DatePublished - Jun 2006
Issue number6
Number of pages14
Pages (from-to)954-967
Original languageEnglish


This paper poses the problem of tree- clustering as that of fitting a mixture of tree unions to a set of sample trees. The tree-unions are structures from which the individual data samples belonging to a cluster can be obtained by edit operations. The distribution of observed tree nodes in each cluster sample is assumed to be governed by a Bernoulli distribution. The clustering method is designed to operate when the correspondences between nodes are unknown and must be inferred as part of the learning process. We adopt a minimum description length approach to the problem of fitting the mixture model to data. We make maximum- likelihood estimates of the Bernoulli parameters. The tree- unions and the mixing proportions are sought so as to minimize the description length criterion. This is the sum of the negative logarithm of the Bernoulli distribution, and a message- length criterion that encodes both the complexity of the union-trees and the number of mixture components. We locate node correspondences by minimizing the edit distance with the current tree unions, and show that the edit distance is linked to the description length criterion. The method can be applied to both unweighted and weighted trees. We illustrate the utility of the resulting algorithm on the problem of classifying 2D shapes using a shock graph representation.

    Research areas

  • structural learning, tree clustering, mixture modelinq, minimum description length, model codes, shock graphs, BAYESIAN NETWORKS, GRAPHS, RECOGNITION, MODELS, SYSTEM

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations