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

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

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

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

合肥工业大学管理学院合肥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

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

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

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

夏春梦,倪志伟,倪丽萍,张霖. 基于密度调整和流形距离的近邻传播算法[J]. 计算机科学, 2017, 44(10): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2017.10.035

XIA Chun-meng, NI Zhi-wei, NI Li-ping and ZHANG Lin. Affinity Propagation Clustering Algorithm Based on Density Adjustment and Manifold Distance[J]. Computer Science, 2017, 44(10): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2017.10.035

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed