CCE Faculty Articles

A Genetic Algorithm using Hyper-Quadtrees for Low-Dimensional K-Means Clustering

Document Type

Article

Publication Title

IEEE Transactions on Pattern Analysis and Machine Intelligence

ISSN

0162-8828

Publication Date

4-1-2006

Abstract

The k-means algorithm is widely used for clustering because of its computational efficiency. Given n points in d-dimensional space and the number of desired clusters k, k-means seeks a set of k-cluster centers so as to minimize the sum of the squared Euclidean distance between each point and its nearest cluster center. However, the algorithm is very sensitive to the initial selection of centers and is likely to converge to partitions that are significantly inferior to the global optimum. We present a genetic algorithm (GA) for evolving centers in the k-means algorithm that simultaneously identifies good partitions for a range of values around a specified k. The set of centers is represented using a hyper-quadtree constructed on the data. This representation is exploited in our GA to generate an initial population of good centers and to support a novel crossover operation that selectively passes good subsets of neighboring centers from parents to offspring by swapping subtrees. Experimental results indicate that our GA finds the global optimum for data sets with known optima and finds good solutions for large simulated data sets.

DOI

10.1109/TPAMI.2006.66

Volume

28

Issue

4

First Page

533

Last Page

543

Link to Full Text

Find in your library

Share

COinS