An improved K-medoids algorithm based on step increasing and optimizing medoids. (February 2018) - Yu, Donghua; Liu, Guojun; Guo, Maozu; Liu, Xiaoyan
Highlights: The proposed clustering algorithm improves performance and preserves efficiency. We propose a candidate medoids subset to optimize the clustering medoids. We propose increasing the medoid methods in a step-wise fashion. Results report better performances than classical methods. Abstract: 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.