Clustering using Belief Propagation and Linear Programming

Speaker: Delbert Dueck

While many clustering methods assume clusters are described by parameters or points in a vector space, an alternative approach is to identify a set of training cases as 'exemplars' and then assign every other training case to an exemplar. An advantage of this approach is that all that is needed as input is a matrix containing measures of how suitable each training case is as an exemplar for every other training case. This approach removes the need to compute sufficient statistics and can accommodate measures of similarity or uncertainty that are not based on formal probability models. Recently, we introduced an algorithm we call 'affinity propagation' which can be used to solve instances of this NP-hard clustering problem. In this talk, I'll describe this algorithm, demonstrate its effectiveness in several application areas (exon-detection, image segmentation, characterization of airline flight and trade flow information), and compare it to the linear programming alternatives.

Joint work with Brendan Frey.