基于距离不等式的K-medoids聚类算法

K-Medoids Clustering Algorithm Based on Distance Inequality

研究加速K-medoids聚类算法,首先以PAM(partitioning around medoids)、TPAM(triangular inequality elimination criteria PAM)算法为基础给出两个加速引理,并基于中心点之间距离不等式提出两个新加速定理.同时,以O(n+K^2)额外内存空间开销辅助引理、定理的结合而提出加速SPAM(speed up PAM)聚类算法,使得K-medoids聚类算法复杂度由O(K(n-K)~2)降低至O((n-K)~2).在实际及人工模拟数据集上的实验结果表明:相对于PAM,TPAM,FKMEDOIDS(fast K-medoids)等参考算法均有改进,运行时间比PAM至少提升0.828倍.

This paper presents a research on speeding up K-medoids clustering algorithm. Firstly, two acceleration lemmas are given based on partitioning around medoids （PAM） and triangular inequality elimination criteria PAM （TPAM） algorithms. Then two new acceleration theorems are proposed based on distance inequality between center points. Combining the lemmas with the theorems with the aid of additional memory space O（n＋K^2）, the speed up partitioning around medoids （SPAM） algorithm is constructed, reducing the time complexity from O（K（n-K）2） to O（（n-K）^2）. Experimental results on both real-world and artificial datasets show that the SPAM algorithm outperforms PAM, TPAM and FKEMDOIDS approaches by at least 0.828 times over PAM in terms of running time.