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

来源：软件学报杂志2017年第12期北京时间：

作者：余冬华,郭茂祖,刘扬,任世军,刘晓燕,刘国军

单位：余冬华，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000111,郭茂祖，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001;北京建筑大学 电气与信息工程学院, 北京 10004402,刘扬，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000103,任世军，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000104,刘晓燕，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000105,刘国军，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000106

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

关键词：数据挖掘;聚类算法;K-medoids;距离不等式

基金资助：国家自然科学基金（61571164，61571163，61671188，61671189，QC2014C071）