Power k-Means Clustering
Jason Xu · Kenneth Lange

Thu Jun 13th 09:40 -- 10:00 AM @ Room 104

Clustering is a fundamental task in unsupervised machine learning. Lloyd's 1957 algorithm for k-means clustering remains one of the most widely used due to its speed and simplicity. As greedy approaches, Lloyd's algorithm and its variants are sensitive to initialization and often fall short at a poor solution. This paper explores an alternative to Lloyd's algorithm that retains its simplicity and mitigates its tendency to get trapped by local minima. Called power k-means, our method embeds the k-means problem in a continuous class of similar, better behaved problems with fewer local minima. Power k-means anneals its way toward the solution of ordinary k-means by way of majorization-minimization (MM), sharing the appealing descent property and low complexity of Lloyd's algorithm. Further, our method complements widely used seeding strategies, reaping marked improvements when used in conjunction. These merits are demonstrated on a suite of simulated and real data examples

Author Information

Jason Xu (Duke University)
Kenneth Lange (UCLA)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors