This talk will provide an introduction to the unsupervised learning problem of clustering. I will introduce k-means clustering and discuss the well-known computational limitations of optimal clustering. I will also present an impossibility result that provides some intuition into desirable properties of clustering that are feasible, for example through balanced k-means clustering. 

 

The topics discussed in this talk are primarily from Chapter 8 of the Hopcroft-Kannan book: http://www.cs.cornell.edu/jeh/book11April2014.pdf