Geometric methods of accelerating triangle-inequality-based k-means.

One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a set of upper and lower bounds. The goal of this thesis is to further improve the runtime of those algorithms. Namely we improve the way how those bounds are maintained between iterations. By tighter updates of lower bounds we can further decrease the number of distance calculations. The other improvements stated in the thesis include elimination of centroids from the innermost loop of the algorithms when the bounds do not help. The common property of those two proposals is that they require only calculations that are done once per iteration. We also solve a problem that is left as open in the heap algorithm.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Grantor

Baylor University.

Year dc:date.issued

2015

Author dc:creator

• Ryšavý, Petr, 1991-

Advisor dc:contributor.advisor

• Hamerly, Gregory James, 1977-

• Clustering.
• K-means.
• Triangle inequality.

Statement dc:rights

• Baylor University works are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. Contact libraryquestions@baylor.edu for inquiries about permission.

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/2104/9570

OAI identifier oai:identifier

oai:baylor-ir.tdl.org:2104/9570