Just Relax and Come Clustering!: A Convexification of k-Means Clustering
2011 (English)Report (Other academic)
k-means clustering is a popular approach to clustering. It is easy to implement and intuitive but has the disadvantage of being sensitive to initialization due to an underlying nonconvex optimization problem. In this paper, we derive an equivalent formulation of k-means clustering. The formulation takes the form of a L0-regularized least squares problem. We then propose a novel convex, relaxed, formulation of k-means clustering. The sum-of-norms regularized least squares formulation inherits many desired properties of k-means but has the advantage of being independent of initialization.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2011. , 12 p.
LiTH-ISY-R, ISSN 1400-3902 ; 2992
Clustering ; K-means ; Sum-of-norms ; Group-lasso
IdentifiersURN: urn:nbn:se:liu:diva-97752ISRN: LiTH-ISY-R-2992OAI: oai:DiVA.org:liu-97752DiVA: diva2:650707