Campuses:

k-means clustering

Thursday, September 15, 2016 - 9:00am - 9:50am
Rachel Ward (The University of Texas at Austin)
In the first part of the talk, we discuss an semidefinite programming relaxation of the k-means clustering problem. We show that even when the SDP is not tight, its solution produces a denoised copy of the original set of points, and can be combined with a rounding scheme to produce a set of k centers with improved stability guarantees under subgaussian mixture model compared to previous algorithms.
Wednesday, January 27, 2016 - 3:15pm - 4:05pm
Rachel Ward (The University of Texas at Austin)
The k-means clustering objective is known to be hard to minimize in general, requiring an exhaustive search over all possible partitions of a given set of data into k clusters. At the same time, fast alternating minimization algorithms act as effective surrogates for the k-means optimization problem in practice, despite only being guaranteed in general to converge to local minimizers. As a compromise between accuracy and speed, we consider a semidefinite programming relaxation of the k-means optimization problem, followed by rounding if necessary.
Subscribe to RSS - k-means clustering