Home > Vol. 1, No. 1

International Journal of Recent Trends in Engineering (IJRTE)

ISSN 1797-9617

Volume 1,  Number 1,  May 2009

Issue on Computer Science

Page(s): 220-226

A Modified k-means Algorithm to Avoid Empty Clusters

           Malay K. Pakhira

Full text:  PDF

Abstract

The k-means algorithm is one of the most widely used clustering algorithms and has been applied in many fields of science and technology. One of the major problems of the k-means algorithm is that it may produce empty clusters depending on initial center vectors. For static execution of the k-means, this problem is considered insignificant and can be solved by executing the algorithm for a number of times. In situations, where the k-means is used as an integral part of some higher level application, this empty cluster problem may produce anomalous behavior of the system and may lead to significant performance degradation. This paper presents a modified version of the k-means algorithm that efficiently eliminates this empty cluster problem. We have shown that the proposed algorithm is semantically equivalent to the original k-means and there is no performance degradation due to incorporated modification. Results of simulation experiments using several data sets prove our claim.

Index Terms

Empty clusters, initial centers, k-means, modified k-means.

Published by Academy Publisher in cooperation with the ACEEE

@ Copyright 2009 ACADEMY PUBLISHER — All rights reserved