In this work we formalize a new natural objective (or cost) function
for bi-clustering - Monochromatic bi-clustering. Our objective function is
suitable for detecting meaningful homogenous clusters based on
categorical valued input matrices. Such problems have arisen recently in
systems biology where researchers have inferred functional classifications
of biological agents based on their pairwise interactions. We
analyze the computational complexity of the resulting optimization
problems. We show that finding optimal solutions is NP-hard and
complement this result by introducing a polynomial time
approximation algorithm for this bi-clustering task. This is the first positive
approximation guarantee for bi-clustering algorithms. We also show
that bi-clustering with our objective function can be viewed as a
generalization of correlation clustering.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/3900 |
| Date | January 2008 |
| Creators | Wulff, Sharon Jay |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0016 seconds