Improved K-medoids Algorithm Based on Similarity Calculation Formula

doi:10.3969/j.issn.1006-2475.2019.05.021

Abstract

Abstract: In the traditional K-medoids clustering algorithm, similarity is generally measured only by distance. This metric is based on independent and identically distributed attributes of data objects. But most real data object attributes are associated. Therefore, this article introduces the non-independent and identical distribution calculation formula. The traditional distance calculation similarity method is replaced. At the same time, since the non-independent and identical distribution formulas are calculated according to the frequency of the attribute values, but numerical data are not sensitive to frequency, so, numerical data are clustered and replaced by attribute columns before the introduction of formulas. Experimental results show that this method can improve the clustering accuracy of algorithm.

Key words: clustering, PAM algorithm, similarity

CLC Number:

TP301.6

HAN Bing， JIANG He. Improved K-medoids Algorithm Based on Similarity Calculation Formula[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.05.021.

References

［1］ HAN J, KAMBER M, TUNG A K H. Spatial clustering methods in data mining: A survey［M］// Geographic Data Mining and Knowledge Discovery. Taylor and Francis Inc., 2001:188-217.
［2］田盛丰. 聚类分析方法［J］. 计算机研究与发展, 1992(3):16-20.
［3］周恩波,毛善君,李梅,等. GPU加速的改进PAM聚类算法研究与应用［J］. 地球信息科学学报, 2017,19(6):782-791.
［4］陈志强,刘钊,张建辉. 聚类分析中PAM算法的分析与实现［J］. 计算机与现代化, 2003(9):1-3.
［5］王世卿,张书春. 基于网格结构的快速PAM算法［J］. 计算机工程与设计, 2011,32(3):952-954.
［6］ KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: An Introduction to Cluster Analysis［M］. John Wiley & Sons, Inc., 1990.
［7］ CHU S C, RODDICK J F, PAN J S. An efficient K-medoids-based algorithm using previous medoid index, triangular inequality elimination criteria, and partial distance search［C］// International Conference on Data Warehousing and Knowledge Discovery. 2002:63-72.
［8］吴景岚,朱文兴. 基于k中心点的迭代局部搜索聚类算法［C］// 第21届中国数据库学术会议论文集 (研究报告篇). 2004:503-509.
［9］余建桥,张帆. 基于数据场改进的PAM聚类算法［J］. 计算机科学, 2005,32(1):165-167.
［10］PARK H S, JUN C H. A simple and fast algorithm for K-medoids clustering［J］. Expert Systems with Applications, 2009,36(2):3336-3341.
［11］PARDESHI B, TOSHNIWAL D. Improved k-medoids clustering based on cluster validity index and object density［C］// 2010 IEEE 2nd International Advance Computing Conference(IACC). 2010:379-384.
［12］谢娟英,郭文娟,谢维信. 基于邻域的K中心点聚类算法［J］. 陕西师范大学学报(自然科学版), 2012,40(4):16-22.
［13］谢娟英,高瑞. 方差优化初始中心的K-medoids聚类算法［J］. 计算机科学与探索, 2015,9(8):973-984.
［14］谢娟英,屈亚楠. 密度峰值优化初始中心的K-medoids聚类算法［J］. 计算机科学与探索, 2016,10(2):230-247.
［15］路浩,倪世宏,查翔,等. 基于递减概率初始点选择K中心点进化算法［J］. 计算机仿真, 2014,31(9):314-318.
［16］颜宏文,周雅梅,潘楚. 基于宽度优先搜索的K-medoids聚类算法［J］. 计算机应用, 2015,35(5):1302-1305.
［17］罗德超，吴文亮，姬应江,等. 一种基于K均值预处理回溯的PAM算法［J］. 软件, 2011,32(4):95-99.
［18］杨志,罗可. 一种改进的基于粒子群的粗糙K-medoids算法［J］. 计算机工程与应用, 2014,50(20):110-114.
［19］何云斌,张志超,万静,等. 不确定数据聚类的U-PAM算法和UM-PAM算法的研究［J］. 计算机科学, 2016,43(6):263-269.
［20］余冬华,郭茂祖,刘扬,等. 基于距离不等式的K-medoids聚类算法［J］. 软件学报, 2017,28(12):3115-3128.
［21］赖向阳,宫秀军,韩来明. 一种MapReduce架构下基于遗传算法的K-Medoids聚类［J］. 计算机科学, 2017,44(3):23-26.
［22］CAO L. Non-IID Learning/Non-IIDness Learning: Learning from Non-IID Data［R］. University of Technology Sydney, Australia, 2011.
［23］WANG C, CAO L, WANG M, et al. Coupled nominal similarity in unsupervised learning［C］// Proceedings of the 20th ACM Conference on Information and Knowledge Management. 2011:973-978.
［24］CAO L. Coupling learning of complex interactions［J］. Information Processing & Management, 2015,51(2):167-186.
［25］赵湘民,陈曦,潘楚. 基于稠密区域的K-medoids聚类算法［J］. 计算机工程与应用, 2016,52(16):85-89.

[1]	WANG Hong-jie, XU Sheng-chao. Clustering Method of Cloud Platform Abnormal Transmission Data Based on Hilbert Similarity [J]. Computer and Modernization, 2023, 0(09): 27-31.
[2]	WANG Hong, GE Hong. Cross Modal Hash Retrieval Based on Attention Mechanism and Semantic Similarity [J]. Computer and Modernization, 2023, 0(08): 44-53.
[3]	WANG Yi-cheng, ZHANG Guo-liang, ZHANG Zi-jie, . Small Object Detection Method Based on Improved YOLOv5 [J]. Computer and Modernization, 2023, 0(05): 100-105.
[4]	MA Yu-juan, HAN Jian-ning, SHI Shao-jie, CAO Shang-bin, YANG Zhi-xiu. Improved Kmeans Segmentation Algorithm for Brain Tumor Based on HMRF [J]. Computer and Modernization, 2023, 0(03): 1-5.
[5]	HONG Tao, ZHU Peng-yu, GUO Bo, WANG Jing-Yu. Communication Fault Diagnosis Knowledge Base Construction and Iteration Based on Semi-supervised Clustering [J]. Computer and Modernization, 2023, 0(02): 28-33.
[6]	LIU Xing-jian, YANG Xiao-fu, HU Lei. A Semi-supervised Model with Non-negative Matrix Factorization for Multiplex Network Clustering [J]. Computer and Modernization, 2023, 0(02): 83-88.
[7]	WEN Zi-xin, LI Shao-ying, WANG Bin-cheng, LIU Bo, . Face Clustering Method Based on Nearest Neighborhood Aggregation [J]. Computer and Modernization, 2022, 0(12): 81-87.
[8]	GUAN Yun-peng, LIU Yu-long. Categorical Data Clustering Based on Extraction of Associations from Co-association Matrix [J]. Computer and Modernization, 2022, 0(11): 1-8.
[9]	ZHANG Zi-xuan, SHA Xiu-yan, XIAO Fei, SU Bao-chan, SUI Yu-lu, MENG Zi-chen. Research and Application of Hesitant Fuzzy Canopy-K-means Clustering Algorithm [J]. Computer and Modernization, 2022, 0(11): 17-21.
[10]	DING Xu-dong, YANG Dong-run, LIU Hui, ZHAO Xing-kai, ZHANG Ying, SUN Mei, . A Data-driven Online Modeling Method for Evaporators [J]. Computer and Modernization, 2022, 0(11): 22-31.
[11]	LIU Guo-li, XU Hong-nan, TAN You-qian. Collaborative Filtering Recommendation Algorithm Combined with Expert Trust [J]. Computer and Modernization, 2022, 0(11): 60-68.
[12]	TIAN Feng, DENG Xiao-ping, ZHANG Gui-qing, WANG Bao-yi. A Non-intrusive Load Monitoring Method Based on Improved kNN Algorithm and Transient Steady State Features [J]. Computer and Modernization, 2022, 0(10): 29-35.
[13]	CHEN Guang-fu, LIAN Yan-ping, . Link Prediction in Directed Network Combining Node Centrality and Degree-related Clustering [J]. Computer and Modernization, 2022, 0(08): 36-42.
[14]	ZENG Yi-bin, GE Hong. Cross-modal Retrieval Based on Context Fusion and Multi-similarity Learning [J]. Computer and Modernization, 2022, 0(08): 50-56.
[15]	SHEN Zhi, XU Li, FU Xiang-yuan. Traffic Sign Detection in Blurred Light Scenes Based on Improved YOLO v4 [J]. Computer and Modernization, 2022, 0(07): 27-32.