An improved K-medoids algorithm based on step increasing and optimizing medoids

This paper proposes an improved K-medoids clustering algorithm which preserves the computational efficiency and simplicity of the simple and fast K-medoids algorithm while improving its clustering performance. The proposed algorithm requires determining the candidate medoids subsets and calculating the distance matrix, then using both of them to incrementally increase the number of cluster and new medoids from 2 to K, as well as selecting two initial medoids. The Rand index, Jaccard index, Adjusted Rand index and F-measure are employed to evaluate how the proposed algorithm compares with three state-of-the-art algorithms: the simple and fast K-medoids (FastK), density peak optimized K-medoids (DPK), density peak optimized K-medoids with a new measure (DPNMK) algorithms. Experimental results on both real and artificial data sets show that the proposed algorithm outperforms the other three algorithms. The complexity of this proposed algorithm was analyzed and found to be lower than DPK and DPNMK, and be similar to FastK.