Leveraging Union of Subspace Structure to Improve Constrained Clustering

Many clustering problems in computer vision and other contexts are also classification problems, where each cluster shares a meaningful label. Subspace clustering algorithms in particular are often applied to problems that fit this description, for example with face images or handwritten digits. While it is straightforward to request human input on these datasets, our goal is to reduce this input as much as possible. We present an algorithm for active query selection that allows us to leverage the union of subspace structure assumed in subspace clustering. The central step of the algorithm is in querying points of minimum margin between estimated subspaces; analogous to classifier margin, these lie near the decision boundary. This procedure can be used after any subspace clustering algorithm that outputs an affinity matrix and is capable of driving the clustering error down more quickly than other state-of-the-art active query algorithms on datasets with subspace structure. We demonstrate the effectiveness of our algorithm on several benchmark datasets, and with a modest number of queries we see significant gains in clustering performance.
Laura Balzano is an assistant professor in Electrical Engineering and Computer Science at the University of Michigan. She is an Intel Early Career Faculty Honor Fellow and received an NSF BRIGE award. She received all her degrees in Electrical Engineering: BS from Rice University, MS from the University of California in Los Angeles, and PhD from the University of Wisconsin. She received the Outstanding MS Degree of the year award from the UCLA EE Department, and the Best Dissertation award from the University of Wisconsin ECE Department. Her main research focus is on modeling with highly incomplete or corrupted data, and its applications in networks, environmental monitoring, and computer vision. Her expertise is in statistical signal processing, matrix factorization, and optimization.