基于相似度计算公式改进的K-中心点算法

doi:10.3969/j.issn.1006-2475.2019.05.021

计算机与现代化

基于相似度计算公式改进的K-中心点算法

（齐鲁工业大学(山东省科学院)计算机科学与技术学院，山东济南250353）

收稿日期:2018-11-28 出版日期:2019-05-14 发布日期:2019-05-14
作者简介:韩冰(1993-),女,山东莱芜人,硕士研究生,研究方向:数据挖掘,E-mail: binghan93@126.com; 姜合(1964-),男,教授, 硕士,研究方向:数据挖掘,数据库,数据仓库。
基金资助:
山东省自然科学基金资助项目(ZR2012FM032)

Improved K-medoids Algorithm Based on Similarity Calculation Formula

(School of Computer Science and Technology, Qilu University of Technology(Shandong Academy of Sciences), Jinan 250353, China)

Received:2018-11-28 Online:2019-05-14 Published:2019-05-14

摘要/Abstract

摘要： 在传统K-中心点聚类算法中，相似性一般仅仅用距离来进行度量，这种度量方法均基于对象属性之间是独立同分布的，但大多数真实数据对象属性之间都相关联的，因此，本文将引用非独立同分布计算公式，对传统距离计算相似度方法进行替换。同时，由于此公式会依据属性值的频率来进行计算，但数值型数据对于频率并不敏感，因此，本文在引入公式之前，将数值型数据按属性列进行聚类与替换。实验结果表明，本文方法可以提高算法的聚类精度。

关键词: 聚类, PAM算法, 相似度

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

中图分类号:

TP301.6

韩冰，姜合. 基于相似度计算公式改进的K-中心点算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.05.021.

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.

参考文献

［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]	王秋忆, 周浩, 郑婷婷. 改进RetinaNet的电力设备目标检测方法[J]. 计算机与现代化, 2024, 0(01): 47-52.
[2]	王宏杰, 徐胜超. 基于希尔伯特相似度的云平台异常传输数据聚类方法[J]. 计算机与现代化, 2023, 0(09): 27-31.
[3]	韩雪. 基于约束聚类和粒子群算法的多路径规划[J]. 计算机与现代化, 2023, 0(08): 7-11.
[4]	孙子雨, 任燃, 魏曦哲. 基于DTW-TCN的股票分类及预测研究[J]. 计算机与现代化, 2023, 0(08): 31-37.
[5]	王鸿, 葛红. 基于注意力机制和语义相似度的跨模态哈希检索[J]. 计算机与现代化, 2023, 0(08): 44-53.
[6]	王艺成, 张国良, 张自杰, . 基于改进YOLOv5的小目标检测方法[J]. 计算机与现代化, 2023, 0(05): 100-105.
[7]	马瑜涓, 韩建宁, 史韶杰, 曹尚斌, 杨志秀. 基于HMRF的改进Kmeans脑肿瘤分割算法[J]. 计算机与现代化, 2023, 0(03): 1-5.
[8]	洪涛, 朱鹏宇, 郭波, 王敬宇. 基于半监督聚类的通信缺陷研判知识库构建及迭代技术[J]. 计算机与现代化, 2023, 0(02): 28-33.
[9]	刘兴建, 杨晓夫, 胡磊. 基于非负矩阵分解的半监督模型用于多层网络聚类[J]. 计算机与现代化, 2023, 0(02): 83-88.
[10]	文紫鑫, 李少英, 王斌成, 刘博, . 基于近邻关系聚合的人脸聚类方法[J]. 计算机与现代化, 2022, 0(12): 81-87.
[11]	关云鹏, 刘玉龙. 基于从共现矩阵提取关联的类别型数据聚类[J]. 计算机与现代化, 2022, 0(11): 1-8.
[12]	张子璇, 沙秀艳, 肖霏, 粟宝婵, 隋雨陆, 孟子宸. 基于犹豫模糊Canopy-K均值聚类算法的研究与应用[J]. 计算机与现代化, 2022, 0(11): 17-21.
[13]	丁绪东, 杨东润, 刘慧, 赵星凯, 张迎, 孙梅, . 数据驱动的蒸发器在线建模方法[J]. 计算机与现代化, 2022, 0(11): 22-31.
[14]	刘国丽, 徐洪楠, 谭有倩. 结合专家信任的协同过滤推荐算法研究[J]. 计算机与现代化, 2022, 0(11): 60-68.
[15]	田丰, 邓晓平, 张桂青, 王保义. 基于改进kNN算法与暂稳态特征的非侵入式负荷监测方法[J]. 计算机与现代化, 2022, 0(10): 29-35.

基于相似度计算公式改进的K-中心点算法

Improved K-medoids Algorithm Based on Similarity Calculation Formula

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价