Poster
How to tell when a clustering is (approximately) correct using convex relaxations
Marina Meila
Room 210 #56
Keywords: [ Convex Optimization ] [ Combinatorial Optimization ] [ Clustering ]
We introduce the Sublevel Set (SS) method, a generic method to obtain sufficient guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. This method can be instantiated for a variety of clustering loss functions for which convex relaxations exist. Obtaining the guarantees in practice amounts to solving a convex optimization. We demonstrate the applicability of this method by obtaining distribution free guarantees for K-means clustering on realistic data sets.
Live content is unavailable. Log in and register to view live content