Clustering by transitive propagation
Authors:
Preprint
Abstract
We present a global optimization algorithm for clustering data given the ratio of likelihoods that each pair of data points is in the same cluster or in different clusters. To define a clustering solution in terms of pairwise relationships, a necessary and sufficient condition is that belonging to the same cluster satisfies transitivity. We define a global objective function based on pairwise likelihood ratios and a transitivity constraint over all triples, assigning an equal prior probability to all clustering solutions. We maximize the objective function by implementing max-sum message passing on the corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we demonstrate an application inspired by mutational sequencing for decoding random binary words transmitted through a noisy channel.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Facilitated sequence counting and assembly by template mutagenesisProceedings of the National Academy of Sciences, 2014
- Clustering by Passing Messages Between Data PointsScience, 2007
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001
- Partitioning single-molecule maps into multiple populations: algorithms and probabilistic analysisDiscrete Applied Mathematics, 2000
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.The Journal of Philosophy, 1991