Adaptive spectral affinity propagation clustering

doi:10.23919/JSEE.2022.000060

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (3): 647-664.doi: 10.23919/JSEE.2022.000060

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Adaptive spectral affinity propagation clustering

Lin TANG¹(), Leilei SUN^1,²(), Chonghui GUO^1,*(), Zhen ZHANG¹()

¹ Institute of Systems Engineering, Dalian University of Technology, Dalian 116024, China
² School of Computer Science and Engineering, Beihang University, Beijing 100191, China

Received:2020-11-30 Accepted:2022-05-06 Online:2022-06-18 Published:2022-06-24
Contact: Chonghui GUO E-mail:tanglin@dlut.edu.cn;leileisun@buaa.edu.cn;dlutguo@dlut.edu.cn;zhen.zhang@dlut.edu.cn
About author:|TANG Linwas born in 1980. She received her B.S. degree in computer science and technology from Liaoning Technology University in 2003, and M.S. degree in computer application from Dalian University of Technology in 2008. She is currently pursuing her Ph.D. degree on management science and engineering at Dalian University of Technology. Her research interests include text data mining, machine learning, and deep learning. E-mail: tanglin@dlut.edu.cn||SUN Leileiwas born in 1985. He received his B.S. and M.S. degrees in control theory and control engineering from Dalian University of Technology in 2009 and 2012. He received his Ph.D. degree from Institute of Systems Engineering, Dalian University of Technology, in 2017. He was a postdoctoral research fellow from 2017 to 2019 in School of Economics and Management, Tsinghua University. Currently he is an assistant professor of the State Key Laboratory of Software Development Environment and Big Data Brain Computing Lab, Beihang University. His research interests include machine learning and data mining. He has published several papers on IEEE Trans. on Data and Knowledge Engineering, Knowledge and Information Systems, and ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.E-mail: leileisun@buaa.edu.cn||GUO Chonghui was born in 1973. He received his B.S. degree in Mathematics from Liaoning University in 1995, M.S. degree in Operational Research and Control Theory in 1999, and Ph.D. degree in Management Science and Engineering from Dalian University of Technology in 2002. He was a postdoctoral research fellow in the Department of Computer Science in Tsinghua University. Currently he is a professor of the Institute of Systems Engineering, Dalian University of Technology. His research concentrate on data mining and knowledge discovery. He has published over 150 peer-reviewed papers in academic journals and conferences, in addition to five text-books and two monographs. He has been the Principal Investigator on over 10 research projects from the Government and the Industry.E-mail: dlutguo@dlut.edu.cn||ZHANG Zhen was born in 1986. He received his B.S. in engineering management from China University of Petroleum (Eastern China) and Ph.D. degree in management science and engineering from the Dalian University of Technology in 2014. Currently he is an associate professor with the Institute of Systems Engineering, Dalian University of Technology. His current research interests include group decision making, computing with words and big data analysis. He is an associate editor of Kybernetes and Journal of Intelligent & Fuzzy Systems, and an editorial board member of the International Journal of Computational Intelligence Systems.E-mail: zhen.zhang@dlut.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (71771034; 71901011; 71971039) and the Scientific and Technological Innovation Foundation of Dalian (2018J11CY009).

Abstract

Abstract:

Affinity propagation (AP) is a classic clustering algorithm. To improve the classical AP algorithms, we propose a clustering algorithm namely, adaptive spectral affinity propagation (AdaSAP). In particular, we discuss why AP is not suitable for non-spherical clusters and present a unifying view of nine famous arbitrary-shaped clustering algorithms. We propose a strategy of extending AP in non-spherical clustering by constructing category similarity of objects. Leveraging the monotonicity that the clusters’ number increases with the self-similarity in AP, we propose a model selection procedure that can determine the number of clusters adaptively. For the parameters introduced by extending AP in non-spherical clustering, we provide a grid-evolving strategy to optimize them automatically. The effectiveness of AdaSAP is evaluated by experiments on both synthetic datasets and real-world clustering tasks. Experimental results validate that the superiority of AdaSAP over benchmark algorithms like the classical AP and spectral clustering algorithms.

Key words: affinity propagation (AP), Laplacian eigenmap (LE), arbitrary-shaped cluster, model selection

Lin TANG, Leilei SUN, Chonghui GUO, Zhen ZHANG. Adaptive spectral affinity propagation clustering[J]. Journal of Systems Engineering and Electronics, 2022, 33(3): 647-664.

Figures/Tables 21

Fig 1

Table 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Fig 12

Table 2

Table 3

Table 4

Fig 13

Table 5

Fig 14

Fig 15

Fig 16

References 53

1	HAN J W, KAMBER M, PEI J. Data mining: concepts and techniques. 3rd ed. California: Morgan Kaufmann, 2011.
2	JAIN A K. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 2010, 31(8): 651–666.
3	CHEN X L, XIE H R, WANG F L, et al. A bibliometric analysis of natural language processing in medical research. BMC Medical Informatics and Decision Making, 2018, 18(1): 14.
4	ABDOLREZA H. Black hole: a new heuristic optimization approach for data clustering. Information Sciences, 2013, 222(3): 175–184.
5	XU D K, TIAN Y J. A comprehensive survey of clustering algorithms. Annals of Data Science. 2015, 2(2): 165–193.
6	FREY B J, DUECK D Clustering by passing messages between data points. Science, 2007, 315 (5814): 927- 976.
7	KARIV O, HAKIMI S An algorithmic approach to network location problems. I: the p-centers. SIAM Journal on Applied Mathematics, 1979, 37 (3): 513- 538.
8	FREY B J, DUECK D Response to comment on “clustering by passing messages between data points”. Science, 2008, 319 (5864): 726.
9	LI P, JI H F, WANG B L, et al Adjustable preference affinity propagation clustering. Pattern Recognition Letters, 2017, 85 (C): 72- 78.
10	FAN Z Y, JIANG J, WENG S Q, et al Adaptive density distribution inspired affinity propagation clustering. Neural Computing and Applications, 2019, 31 (1): 435- 445.
11	GUAN R C, SHI X H, MARCHESE M, et al Text clustering with seeds affinity propagation. IEEE Trans. on Knowledge and Data Engineering, 2011, 23 (4): 627- 637.
12	KAZANTSEVA A, SZPAKOWICZ S Linear text segmentation using affinity propagation. Proc. of the Conference on Empirical Methods in Natural Language Processing, 2011, 284- 293.
13	LEONE M, SUMEDHA, WEIGT M Clustering by soft-constraint affinity propagation: applications to gene-expression data. Bioinformatics, 2007, 23 (20): 2708- 2715.
14	FARINELLI A, DENITTO M, BICEGO M Biclustering of expression microarray data using affinity propagation. Proc. of the IAPR International Conference on Pattern Recognition in Bioinformatics, 2011, 13- 24.
15	JIA C Y, JIANG Y W, YU J Affinity propagation on identifying communities in social and biological networks. Proc. of the International Conference on Knowledge Science, 2010, 597- 602.
16	LAI D R, NARDINI C, LU H T Partitioning networks into communities by message passing. Physics Review E, 2011, 83 (1): 16115.
17	ARZENO N M, VIKALO H Semi-supervised affinity propagation with soft instance-level constraints. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2015, 37 (5): 1041- 1052.
18	ZHOU R H, LIU Q M, WANG J, et al Modified semi-supervised affinity propagation clustering with fuzzy density fruit fly optimization. Neural Computing and Applications, 2021, 33, 4695- 4712.
19	ANNA K, STAN S Hierarchical topical segmentation with affinity propagation. Proc. of the 25th International Conference on Computational Linguistics, 2014, 37- 47.
20	SUN L L, GUO C H Incremental affinity propagation clustering based on message passing. IEEE Trans. on Knowledge and Data Engineering, 2014, 26 (11): 2731- 2744.
21	SUN L L, GUO C H, LIU C R, et al Fast affinity propagation clustering based on incomplete similarity matrix. Knowledge and Information Systems, 2017, 51 (3): 941- 963.
22	LI Y, GUO C H, SUN L L Fast clustering by affinity propagation based on density peaks. IEEE Access, 2020, 8, 138884- 138897.
23	MEZARD M Where are the exemplars. Science, 2007, 315 (5814): 949- 951.
24	BELKIN M, NIYOGI P Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003, 15 (6): 1373- 1396.
25	BENGIO Y, DELALLEAU O, ROUX N L, et al Learning eigenfunctions links spectral embedding and kernel PCA. Neural Computation, 2004, 16 (10): 2197- 2219.
26	DHILLON I S, GUAN Y Q, KULIS B Kernel K-means: spectral clustering and normalized cuts . Proc. of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, 551- 556.
27	ESTER M, KRIEGEL H P, SANDER J, et al A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. of the Second International Conference on Knowledge Discovery and Data Mining, 1996, 226- 231.
28	FUKUNAGA K, HOSTETLER L D The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Trans. on Information Theory, 1975, 21 (1): 32- 40.
29	CHENG Y Z Mean shift, mode seeking, and clustering. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1995, 17 (8): 790- 799.
30	COMANICIU D, MEER P Mean shift: a robust approach toward feature space analysis. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2002, 24 (5): 603- 619.
31	RODRIGUEZ A, LAIO A Clustering by fast search and find of density peaks. Science, 2014, 344 (6191): 1492- 1496.
32	SUN L L, CHEN G Q, XIONG H, et al Cluster analysis in data-driven management and decisions. Journal of Management Science and Engineering, 2017, 2 (4): 227.
33	KARYPIS G, HAN E, KUMAR V Chameleon: hierarchical clustering using dynamic modeling. IEEE Computer, 1999, 32 (8): 68- 75.
34	SCHOLKOPF B, SMOLA A, MULLER K Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 1998, 10 (5): 1299- 1319.
35	NG A Y, JORDAN M I, WEISS Y On spectral clustering: analysis and an algorithm. Proc. of the 14th International Conference on Neural Information Processing Systems, 2001, 849- 856.
36	WANG L J, DING S F, JIA H J An improvement of spectral clustering an improvement of spectral clustering via message passing and density sensitive similarity. IEEE Access, 2019, 7, 101054- 101062.
37	WANG Y R, DING S F, WANG L J, et al An improved density-based adaptive p-spectral clustering algorithm. International Journal of Machine Learning and Cybernetics, 2020, 3691304.
38	VINH N X, EPPS J, BAILEY J. Information theoretic measures for clustering comparison: is a correction for chance necessary? Journal of Machine Learning Research, 2010, 11: 2837–2854.
39	ARBELAEZ P, MAIRE M, FOWLKES C, et al Contour detection and hierarchical image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2011, 33 (5): 898- 916.
40	PASI F, SAMI S K-means properties on six clustering benchmark datasets . Applied Intelligence, 2018, 48 (12): 4743- 4759.
41	BAGHSHAH M S, SHOURAKI S B Kernel-based metric learning for semi-supervised clustering. Neurocomputing, 2010, 73 (7/9): 1352- 1361.
42	CHEN W F, FENG G C Spectral clustering with discriminant cuts. Knowledge-Based Systems, 2012, 28, 27- 37.
43	FANTI P, SIERANOJA S. K-means properties on six clustering benchmark datasets. Applied Intelligence, 48(12), 4743–4759.
44	FISCHER B, BUHMANN J M Path-based clustering for grouping of smooth curves and texture segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2003, 25 (4): 513- 518.
45	CHANG H, YEUNG D Y Robust path-based spectral clustering. Pattern Recognition, 2008, 41 (1): 191- 203.
46	MARTIN D, FOWLKES C, TAL D, et al. Berkeley segmentation dataset. https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/.
47	AT&T Laboratories Cambridge. The ORL database of faces. https://cam-orl.co.uk/facedatabase.html.
48	GRAHAM D. The UMIST dataset. https://www.visioneng.org.uk/datasets/.
49	RECOGNITION F. Yale face database. http://vision.ucsd.edu/content/yale-face-database.
50	HUANG P, TANG Z M, CHEN C K, et al Local maximal margin discriminant embedding for face recognition. Journal of Visual Communication and Image Representation, 2014, 25 (2): 296- 305.
51	RADUCANU B, DORNAIKA F A supervised non-linear dimensionality reduction approach for manifold learning. Pattern Recognition, 2012, 45 (6): 2432- 2444.
52	JOHNSON A, POLLARD T J, SHEN L, et al MIMIC-III, a freely accessible critical care database. Scientific Data, 2016, 3 (1): 160035.
53	SU L X, ZHANG R M, ZHANG Q, et al The effect of mechanical ventilation on peripheral perfusion index and its association with the prognosis of critically ill patients. Critical Care Medicine, 2019, 47 (5): 685- 690.

Method	Density estimator	s'(i, j)=1
DBSCAN	$\displaystyle\sum\limits_j {\eta ({s_{ij} } - \varepsilon )}$	Density-connected
Mean-shift	$\displaystyle\sum\limits_j {\eta ({s_{ij} } - \varepsilon )}$	Same ending point
DPC	$\displaystyle\sum\limits_j {\eta ({s_{ij} } - \varepsilon )}$	Same density peak

Dataset	Sample	Image	Size	Class
ORL	400	Grey	$ 112\times 92 $	40
UMLST	575	Grey	$ 112\times 92 $	20
Yale	165	Grey	$ 243\times 320 $	15

Dataset	AdaAP	SKM	AdaSAP
ORL	0.913	0.863	0.971
UMLST	0.565	0.729	0.774
Yale	0.637	0.618	0.680

Dataset	AdaAP	SKM	AdaSAP
ORL	93.00	80.26	98.00
UMLST	53.21	65.69	69.43
Yale	64.55	59.87	66.36

Index	Aspect	Indicator
1	Demographic	Age, Gender
2	Vital signs (24-hour average values on admission to ICU)	Heart rate, arterial pressure, body temperature, oxygen saturation, respiratory rate, central venous pressure
3	Blood gas	Base excess, buffer base, hemoglobin, lactate, PCO₂, PH, PO₂, white blood cells
4	Incoming and outgoing	Incoming, outgoing, and balance volumes
5	Patient diagnosis	Simplified acute physioligy score (SAPS), sofa
6	Parameters related to mechanical ventilation	Positive end expiratory pressure (PEEP), fraction of inspiration O₂ (FiO₂), tidal volume (VT), peak pressure, average pressure, inspiratory plateau pressure
7	Patient end results	Whether or not dead in the ICU, alive days from the admission into the ICU

Adaptive spectral affinity propagation clustering

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 21

References 53

Related Articles 0

Recommended Articles

Metrics

Comments