Careful seeding for the k-medoids algorithm with incremental k++ cluster construction
The k-medoids algorithm is a popular variant of the k-means algorithm and
widely used in pattern recognition and machine learning. A main drawback of the
k-medoids algorithm is that it can be trapped in local optima. An improved
k-medoids algorithm (INCKM) was recently proposed to overcome this drawback,
based on constructing a candidate medoids subset with a parameter choosing
procedure, but it may fail when dealing with imbalanced datasets. In this
paper, we propose a novel incremental k-medoids algorithm (INCKPP) which
dynamically increases the number of clusters from 2 to k through a
nonparametric and stochastic k-means++ search procedure. Our algorithm can
overcome the parameter selection problem in the improved k-medoids algorithm,
improve the clustering performance, and deal with imbalanced datasets very
well. But our algorithm has a weakness in computation efficiency. To address
this issue, we propose a fast INCKPP algorithm (called INCKPP$_{sample}$) which
preserves the computational efficiency of the simple and fast k-medoids
algorithm with an improved clustering performance. The proposed algorithm is
compared with three state-of-the-art algorithms: the improved k-medoids
algorithm (INCKM), the simple and fast k-medoids algorithm (FKM) and the
k-means++ algorithm (KPP). Extensive experiments on both synthetic and real
world datasets including imbalanced datasets illustrate the effectiveness of
the proposed algorithm.