An Arithmetic-Based Deterministic Centroid Initialization Method for the k-Means Clustering Algorithm

<p>One of the greatest challenges in k-means clustering is positioning the initial cluster centers, or centroids, as close to optimal as possible, and doing so in an amount of time deemed reasonable. Traditional fc-means utilizes a randomization process for initializing these centroids, and poor initialization can lead to increased numbers of required clustering iterations to reach convergence, and a greater overall runtime. This research proposes a simple, arithmetic-based deterministic centroid initialization method which is much faster than randomized initialization. Preliminary experiments suggest that this collection of methods, referred to herein as the sharding centroid initialization algorithm family, often outperforms random initialization in terms of the required number of iterations for convergence and overall time-related metrics and is competitive or better in terms of the reported mean sum of squared errors (SSE) metric. Surprisingly, the sharding algorithms often manage to report more advantageous mean SSE values in the instances where their performance is slower than random initialization.</p>

Name thesis:degree_name

Computer Science - Applied Computing Track

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

TSYS School of Computer Science

Year dc:date.available

2016

Author dc:creator

• Mayo, Matthew Michael

• K-means
• Randomized Initialization
• Sum of Squared Errors (SSE)
• Centroid
• Computer Engineering
• Theory and Algorithms

Language dc:language

English

Repository record dc:identifier

https://csuepress.columbusstate.edu/theses_dissertations/241

OAI identifier oai:identifier

oai:csuepress.columbusstate.edu:theses_dissertations-1231