Cyclic exchange neighborhood search technique for the K-means clustering problem

Cyclic Exchange is an application of the cyclic transfers neighborhood search technique for the k-means clustering problem. Neighbors of a feasible solution are obtained by moving points between clusters in a cycle. This method attempts to improve local minima obtained by the well-known Lloyd's algorithm. Although the results did not establish usefulness of Cyclic Exchange, our experiments reveal some insights on the k-means clustering and Lloyd's algorithm. While Lloyd's algorithm finds the best local optimum within a thousand iterations for most datasets, it repeatedly finds better local minima after several thousand iterations for some other datasets. For the latter case, Cyclic Exchange also finds better solutions than Lloyd's algorihtm. Although we are unable to identify the features that lead Cyclic Exchange to perform better, our results verify the robustness of Lloyd's algorithm in most datasets.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Thirathon, Nattavude, 1980-

Advisor dc:contributor.advisor

• James B. Orlin and Nitin Patel.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses 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. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/17981

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/17981