Timezone: »

 
Poster
How to tell when a clustering is (approximately) correct using convex relaxations
Marina Meila

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #56
in Thu Poster Session B »

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.

Keywords: Clustering · Combinatorial Optimization · Convex Optimization
[ Paper] 

Author Information

Marina Meila (University of Washington)

More from the Same Authors