Featured event

neon abstract

SILO Seminar – David Gleich

Event Details

When: November 18, 2015, 12:30 PM

Location: 3rd Floor Orchard View Room , Discovery Building

Contact: 608-316-4401, hstampfli@wisc.edu

Non-exhaustive, overlapping k-means clustering

David Gleich

David Gleich, Asst. Prof. CS, Purdue University

Optimizing the k-means objective with Lloyd’s algorithm is a classic strategy to separate a set of datapoint into individual clusters. More recent data in biology and social network necessitates overlapping clustering. I’ll present a generalization of the k-means objective function that incorporates overlapping partitions as well as outlier detection. A weighted, kernel-based variation on this objective is also equivalent to the normalized cut objective on graphs. We’ll see a few algorithms to optimize this objective function including a generalization of Lloyd’s algorithm, a semi-definite relaxation, and a variety of solvers for a non-convex low-rank SDP heuristic. These methods produce state of the art accuracy results on clustering problems where ground-truth clusters are known.
References:
Hou, Whang, Gleich, and Dhillon. Non-exhaustive, overlapping clustering via low-rank semidefinite programming. KDD2015 (http://dx.doi.org/10.1145/2783258.2783398)
Whang, Gleich, Dhillon, Non-exhaustive, overlapping k-means. SDM2015. (http://dx.doi.org/10.1137/1.9781611974010.105

SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.

SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.