Modified fast k-medoids algorithm to guarantee no empty clusters

The simple and fast k-medoids (Fast-KM) is one partition algorithm that consists of three steps: selecting the initial medoid, updating the medoid, and assigning objects to the final medoids. Though the Fast-KM can adopt any proximity and update the medoid by minimizing the total distance within groups, it ignores empty clusters that may appear. This study aims to modify the Fast-KM algorithm so there are no unallocated groups. The modification was carried out by adding one process in the first steps, namely partitioning similar Fast-KM indicator blocks in ascending order and taking one representative object from each of the first k-blocks as initial medoids. This study used three real datasets from the University of California, Irvine (UCI) Machine Learning Repository: primary tumor data, breast cancer data, and zoo data. The Fast-KM algorithm failed to partition the three datasets according to the number of actual classes, as indicated by the occurrence of unfilled groups. Conversely, for these datasets, besides similar objects (not or as medoids) being in the same group in either the initial group or the final group, the proposed method (Modified Fast-KM) also guarantees no empty clusters.