计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 187-192, 215.doi: 10.11896/j.issn.1002-137X.2017.10.035

• 人工智能 • 上一篇    下一篇

基于密度调整和流形距离的近邻传播算法

夏春梦,倪志伟,倪丽萍,张霖   

  1. 合肥工业大学管理学院 合肥230009;合肥工业大学过程优化与智能决策教育部重点实验室 合肥230009,合肥工业大学管理学院 合肥230009;合肥工业大学过程优化与智能决策教育部重点实验室 合肥230009,合肥工业大学管理学院 合肥230009;合肥工业大学过程优化与智能决策教育部重点实验室 合肥230009,北京航空航天大学自动化科学与电气工程学院 北京100191
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家“863”云制造主题项目(2015AA042101),国家自然科学基金重大研究计划培育项目(91546108),国家自然科学基金项目(71271071,71301041)资助

Affinity Propagation Clustering Algorithm Based on Density Adjustment and Manifold Distance

XIA Chun-meng, NI Zhi-wei, NI Li-ping and ZHANG Lin   

  • Online:2018-12-01 Published:2018-12-01

摘要: 针对近邻传播聚类算法在构造相似度矩阵时因对多重尺度和任意形状数据敏感而聚类效果不理想的缺陷,提出一种基于密度调整和流形距离的近邻传播算法。该算法将“领域密度”和“流形理论”的思想引入近邻传播算法,利用基于密度调整和流形的距离更好地刻画了样本空间的真实分布状况,解决了相似度矩阵不能充分表示数据之间内在关系的问题,在一定程度上提高了近邻传播聚类算法的聚类效果。通过在人工数据集和标准数据集上进行实验对比,验证了算法的有效性和优越性。

关键词: 近邻传播聚类,密度调整,流形相似度,多重尺度数据集,任意形状数据集

Abstract: As affinity propagation(AP)clustering is sensitive to the dataset with scaling parameter and various form while calculating the similarity matrix and the cluster result is not ideal,an affinity propagation clustering algorithm based on density adjustment and manifold distance was proposed.The algorithm introduces local density of data and manifold theory into affinity propagation clustering,and uses a way of distance measure based on manifold structure and density adjustment to describe the clusters’ actual structure better,making up the similarity matrix’s deficiency.At the same time,the algorithm is more efficient.Simulation experiment was done on artificial datasets and standard datasets.The result shows the effectiveness and superiority of proposed algorithm.

Key words: Affinity propagation clustering,Density adjustment,Manifold similarity,Multi-scale dataset,Various form dataset

[1] JAIN A K.Data clustering:50 years beyond K-means [J].Pattern Recognition Letters,2010,31(8):651-666.
[2] MACQUEEN J.Some Methods for Classification and Analysis of Mulitivariate Observations[C]∥Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley,University of California Press,1967:281-297.
[3] PARK H S,JUN C H.A simple and fast algorithm for K-medoids clustering[J].Expert System with Applications,2009,36(2):3336-3341.
[4] LIU Y,HOU T,LIU F.Improving fuzzy c-means method forunbalanced dataset[J].Electronics Letters,2015,23(51):1880-1882.
[5] FREY B J,DUECK D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.
[6] FREY B J,DUECK D.Response to comment on“Clustering by passing messages between data points”[J].Science,2008,319(5864):726.
[7] XIAO Y,YU J.Semi-Supervised Clustering Based on AffinityPropagation Algorithm[J].Journal of Software,2008,9(11):2803-2813.(in Chinese) 肖宇,于剑.基于近邻传播算法的半监督聚类[J].软件学报,2008,19(11):2803-2813.
[8] NI Z W,JING T T,NI L P.Affinity Propagation Hierarchical Optimization Algorithm[J].Computer Science,2015,42(3):195-200.(in Chinese) 倪志伟,荆婷婷,倪丽萍.一种近邻传播的层次优化算法[J].计算机科学,2015,42(3):195-200.
[9] LIU L,JIN S H,JIAO L C,et al.Manifold Affinity Propagation Clustering for PolSAR Image Classification[J].Journal of Signal Processing,2016,2(2):135-141.(in Chinese) 刘璐,靳少辉,焦李成,等.采用流形近邻传播聚类的极化SAR图像分类[J].信号处理,2016,32(2):135-141.
[10] ZHANG T,WU R B.Multiple extended target tracking usingAP clustering[J].Control and Decision,2016,31(4):764-768.(in Chinese) 章涛,吴仁彪.近邻传播观测聚类的多扩展目标跟踪算法[J].控制与决策,2016,31(4):764-768.
[11] GUO K,GUO W Z,QIU Q R,et al.Community detection algorithm based on local affinity propagation and user profile[J].Journal on Communications,2015,36(2):72-83.(in Chinese) 郭昆,郭文忠,邱启荣,等.基于局部近邻传播及用户特征的社区识别算法[J].通信学报,2015,36(2):72-83.
[12] ZHANG Z,WANG B Q,LI X T,et al.Semi-supervised Traffic Identification Based on Affinity Propagation[J].Acta Automatica Sinica,2013,39(7):1100-1109.(in Chinese) 张震,汪斌强,李向涛,等.基于近邻传播学习的半监督流量分类方法[J].自动化学报,2013,39(7):1100-1109.
[13] DONG J,WANG S P,XIONG F L.Affinity Propagation Clustering Based on Variable-Similarity Measure[J].Journal of Electronics and Information Technology,2010,32(3):509-514.(in Chinese) 董俊,王锁萍,熊范纶.可变相似性度量的近邻传播聚类[J].电子与信息学报,2010,32(3):509-514.
[14] WANG K J,ZHANG J Y,LI D,et al.Adaptive Affinity Propagation Clustering[J].Acta Automatica Sinica,2007,33(12):1242-1246.(in Chinese) 王开军,张军英,李丹,等.自适应仿射传播聚类[J].自动化学报,2007,3(12):1242-1246.
[15] ZELNIK-MANOR L,PERONA P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2005,17:1601-1608.
[16] WANG Y L,CHEN B,WANG X L,et al.Improved adaptive spectral clustering algorithm based on density adjustment[J].Control and Decision,2014,29(9):1683-1687.(in Chinese) 王雅琳,陈斌,王晓丽,等.基于密度调整的改进自适应谱聚类算法[J].控制与决策,2014,29(9):1683-1687.
[17] SEUNG H S,LEE D D.The manifold ways of perception[J].Science,2000,0(5500):2263-2269.
[18] LIU S L,YAN D Q.A new global embedding algorithm[J].Acta Automatica Sinica,2011,7(7):828-835.(in Chinese) 刘胜蓝,闫德勤.一种新的全局嵌入降维算法[J].自动化学报,2011,7(7):828-835.
[19] ZHANG S W,LEI Y K.Modified locally linear discriminant embedding for plant leaf recognition[J].Neurocomputing,2011,4(14/15):2284-2290.
[20] LI Y M,NI L P,FANG Q H,et al.Research of Text Data Streams Clustering Algorithm Based on Affinity Propagation[J].Computer Science,2016,43(5):223-229.(in Chinese) 李一鸣,倪丽萍,方清华,等.基于近邻传播的文本数据流聚类算法研究[J].计算机科学,2016,43(5):223-229.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .