Sampling Within k-Means Algorithm to Cluster Large Datasets

Thumbnail Image

Files

REU2011Team2.pdf (145.83 KB)

Links to Files

https://userpages.umbc.edu/~gobbert/papers/REU2011Team2.pdf

Permanent Link

http://hdl.handle.net/11603/11692

Collections

UMBC Mathematics and Statistics Department
UMBC Faculty Collection
UMBC Student Collection

Author/Creator

Author/Creator ORCID

Date

2011

Type of Work

technical report
Text

Department

Program

Citation of Original Publication

Rights

This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.

Subjects

Cluster Large Datasets
sample size
k-means
tolerance and confidence intervals
UMBC High Performance Computing Facility (HPCF)

Abstract

Due to current data collection technology, our ability to gather data has surpassed our ability to analyze it. In particular, k-means, one of the simplest and fastest clustering algorithms, is ill-equipped to handle extremely large datasets on even the most powerful machines. Our new algorithm uses a sample from a dataset to decrease runtime by reducing the amount of data analyzed. We perform a simulation study to compare our sampling based k-means to the standard k-means algorithm by analyzing both the speed and accuracy of the two methods. Results show that our algorithm is significantly more efficient than the existing algorithm with comparable accuracy.