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
Joint work with Brendan Frey.