The early stop heuristic: A new convergence criterion for K-means

In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, t...

Full description

Saved in:
Bibliographic Details
Main Authors: Mexicano, A., Rodríguez, R., Cervantes, S., Montes, P., Jiménez, M., Almanza, N., Abrego, A.
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Convergence
Criteria
Experimentation
Heuristic
Iterative methods
Reduction
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, an enhanced version of the K-Means algorithm that incorporates a new convergence criterion is presented. The largest centroid displacement at each iteration was used as mean to define whether the algorithm stops or not its execution. Computational experiments showed that in general, the Early Stop Heuristic is able to reduce the execution time of the standard version without a significant quality reduction. According to the experimentation, the Early Stop Heuristic reached a time reduction up to 87.06% only a quality reduction of 2.46% for the Transactions dataset, the worst case occurred when the Skin instance was grouped into 200 clusters obtaining a 79.04% in reduction time, and a 4.27% in quality reduction.
ISSN:0094-243X
1551-7616
DOI:10.1063/1.4952103