A Spectral Clustering Algorithm Improved by P Systems

  • Guangchun Chen School of Computer and Software Engineering Xihua University, Chengdu, 610039, Sichuan, China
  • Juan Hu Xiangnian Huang School of Computer and Software Engineering Xihua University, Chengdu, 610039, Sichuan, China
  • Hong Peng Xihua University
  • Jun Wang School of Electrical and Information Engineering Xihua University, Chengdu, 610039, Sichuan, China
  • Xiangnian Huang School of Computer and Software Engineering Xihua University, Chengdu, 610039, Sichuan, China

Abstract

Using spectral clustering algorithm is diffcult to find the clusters in the cases that dataset has a large difference in density and its clustering effect depends on the selection of initial centers. To overcome the shortcomings, we propose a novel spectral clustering algorithm based on membrane computing framework, called MSC algorithm, whose idea is to use membrane clustering algorithm to realize the clustering component in spectral clustering. A tissue-like P system is used as its computing framework, where each object in cells denotes a set of cluster centers and velocity-location model is used as the evolution rules. Under the control of evolutioncommunication mechanism, the tissue-like P system can obtain a good clustering partition for each dataset. The proposed spectral clustering algorithm is evaluated on three artiffcial datasets and ten UCI datasets, and it is further compared with classical spectral clustering algorithms. The comparison results demonstrate the advantage of the proposed spectral clustering algorithm.

References

[1] Buiu, C.; Vasile, C.; Arsene, O. (2012); Development of membrane controllers for mobile robots, Information Sciences, 187, 33-51, 2012.
https://doi.org/10.1016/j.ins.2011.10.007

[2] Chan, P.K.; Schlag, M.D.F.; Zien, J.Y. (1993); Spectral k-way ratio-cut partitioning and clustering, DAC, 749-754, 1993.

[3] Colomer, A.M.; Margalida, A.; Pérez-Jiménez, M.J. (2013); Population dynamics P system (PDP) models: a standarized protocol for describing and applying novel bio-inspired computing tools, Plos One, 4, 1-13, 2013.

[4] Díaz-Pernil, D.; Berciano, A.; Pe-a-Cantillana, F.; Gutiérrez-Naranjo, M.A. (2013); Segmenting images with gradient-based edge detection using membrane computing, Pattern Recognition Letters, 34(8), 846-855, 2013.
https://doi.org/10.1016/j.patrec.2012.10.014

[5] Díaz-Pernil, D.; Pe-a-Cantillana, F.; Gutiérrez-Naranjo, M.A. (2013); A parallel algorithm for skeletonizing images by using spiking neural P systems, Neurocomputing, 115, 81-91, 2013.
https://doi.org/10.1016/j.neucom.2012.12.032

[6] Ding, C.; He, X.; Zha, H.; Gu, M.; Simon, H. (2001); Spectral min-max cut for graph partitioning and data clustering, Technical Report TR-2001-XX, Lawrence Berkeley National La1boratory, University of California, Berkeley, CA, 2001.

[7] Dzitac, I. (2015); Impact of membrane computing and P systems in ISI WoS. celebrating the 65th birthday of Gheorghe P un, International Journal of Computers Communications & Control, 10(5), 617-626, 2015.
https://doi.org/10.15837/ijccc.2015.5.2024

[8] Freund, R.; Paun, G.; Pérez-Jiménez, M.J. (2005); Tissue-like P systems with channel-states, Theoretical Computer Science, 330, 101-116, 2005.
https://doi.org/10.1016/j.tcs.2004.09.013

[9] Garcia-Quismondo, M.; Levin, M.; Lobo-Fernández, D. (2017); Modeling regenerative processes with Membrane Computing, Information Sciences, 381, 229-249, 2017.
https://doi.org/10.1016/j.ins.2016.11.017

[10] Gheorghe, M.; Manca, V.; Romero-Campero, F.J. (2010); Deterministic and stochastic P systems for modelling cellular processes, Natural Computing, 9(2), 457-473, 2010.
https://doi.org/10.1007/s11047-009-9158-4

[11] Ionescu, M.; P un G.; Yokomori, T. (2006); Spiking neural P systems, Fundamenta Informaticae, 71, 279-308, 2006.

[12] Liu, X.; Zhao, Y.; Sun, W. (2016); K-medoids-based consensus clustering based on cell-like P systems with promoters and inhibitors, Bio-inspired Computing - Theories and Applications, 95-108, 2016.

[13] Luxburg, U.V. (2007); A tutorial on spectral clustering, Statistics and Computing, 17(4), 395-416, 2007.
https://doi.org/10.1007/s11222-007-9033-z

[14] Ng, A.Y., Jordan, M., Weiss, Y. (2001); On spectral clustering: analysis and an algorithm, Proc Nips, 849-856, 2001.

[15] Pan, L.; Wang, J.; Hoogeboom, H.J. (2012); Spiking neural P systems with astrocytes, Neural Computation, 24(3), 805-825, 2012.
https://doi.org/10.1162/NECO_a_00238

[16] Pan, L.; P un, G. (2009); Spiking neural p systems with anti-spikes, International Journal of Computers Communications & Control, 4(3), 273-282, 2009.
https://doi.org/10.15837/ijccc.2009.3.2435

[17] Paun, G. (2000); Computing with membranes, Journal of Computer System Sciences, 61(1), 108-143, 2000.
https://doi.org/10.1006/jcss.1999.1693

[18] Paun, G.; Rozenberg, G.; Salomaa, A. (2010); The Oxford Handbook of Membrance Computing, Oxford Unversity Press, New York, 2010.

[19] Paun, G. (2016); Membrane computing and economics: a general view, International Journal of Computers Communications & Control, 11(1), 105-112, 2016.

[20] Peng, H.; Shi, P.; Wang, J.; Riscos-Nú-ez, A.; Pérez-Jiménez, M.J. (2017); Multiobjective fuzzy clustering approach based on tissue-like membrane systems, Knowledge-Based Systems, 125, 74-82, 2017.
https://doi.org/10.1016/j.knosys.2017.03.024

[21] Peng, H.; Wang, J.; Ming, J.; Shi, P.; Pérez-Jiménez, M.J.; Yu, W.; Tao, C. (2018); Fault diagnosis of power systems using intuitionistic fuzzy spiking neural P systems, IEEE Transaction on Smart Grid, 2018.

[22] Peng, H.; Wang, J.; Pérez-Jiménez, M.J. (2015); Optimal multi-level thresholding with membrane computing, Digital Signal Processing, 37, 53-64, 2015.
https://doi.org/10.1016/j.dsp.2014.10.006

[23] Peng, H.; Wang, J.; Pérez-Jiménez, M.J.; Riscos-Nú-ez, A. (2014); The framework of P systems applied to solve optimal watermarking problem, Signal Processing, 101, 256-265, 2014.
https://doi.org/10.1016/j.sigpro.2014.02.020

[24] Peng, H.; Wang, J.; Pérez-Jiménez, M.J.; Riscos-Nú-ez, A. (2015); An unsupervised learning algorithm for membrane computing, Information Sciences, 304(20), 80-91, 2015.

[25] Peng, H.; Wang, J.; Pérez-Jiménez, M.J.; Shi, P. (2013); A novel image thresholding method based on membrane computing and fuzzy entropy, Journal of Intelligent and Fuzzy Systems, 24(2), 229-237, 2013.

[26] Peng, H.; Wang, J.; Pérez-Jiménez, M.J.; Wang, H.; Shao, J.; Wang, T. (2013); Fuzzy reasoning spiking neural P system for fault diagnosis, Information Sciences, 235(20), 106-116, 2013.

[27] Peng, H.; Wang, J.; Shi, P.; Pérez-Jiménez, M.J.; Riscos-Nú-ez, A. (2016); An extended membrane system with active membrane to solve automatic fuzzy clustering problems, International Journal of Neural Systems, 26, 1-17, 2016.

[28] Peng, H.; Wang, J.; Shi, P.; Pérez-Jiménez, M.J.; Riscos-Nú-ez, A. (2017); Fault diagnosis of power systems using fuzzy tissue-like P systems, Integrated Computer-Aided Engineering, 24, 401-411, 2017.
https://doi.org/10.3233/ICA-170552

[29] Peng, H.; Wang, J.; Shi, P.; Riscos-Nú-ez, A.; Pérez-Jiménez, M.J. (2015); An automatic clustering algorithm inspired by membrane computing, Pattern Recognition Letters, 68(15), 34-40, 2015.

[30] Perona, P.; Freeman, W. (1998); A factorization approach to grouping, Computer Vision ECCV'98, Springer, 655-670, 1998.

[31] Shi, J.; Malik, J. (2000); Normalized cuts and image segmentation, IEEE Transactions on pattern analysis and machine intelligence, 22(8), 888-905, 2000.
https://doi.org/10.1109/34.868688

[32] Song, T.; Pan, L., P un, G. (2014), Spiking neural P systems with rules on synapses, Theoretical Computer Science, 529, 82-95, 2014.
https://doi.org/10.1016/j.tcs.2014.01.001

[33] Tu, M.; Wang, J.; Peng, H.; Shi, P. (2014); Application of adaptive fuzzy spiking neural P systems in fault diagnosis of power systems, Chin. Jour. Elect., 23(1), 87-92, 2014.

[34] Wang, J.; Peng, H. (2013); Adaptive fuzzy spiking neural P systems for fuzzy inference and learning, International Journal of Computer Mathematics, 90(4), 857-868, 2013.
https://doi.org/10.1080/00207160.2012.743653

[35] Wang, J.; Peng, H.; Tu, M.; Pérez-Jiménez, M.J. (2016); A fault diagnosis method of power systems based on an improved adaptive fuzzy spiking neural P systems and PSO algorithms, Chin. Jour. Elect., 25(2), 320-327, 2016.
https://doi.org/10.1049/cje.2016.03.019

[36] Wang, J.; Shi, P.; Peng, H. (2016); Membrane computing model for IIR filter design, Information Sciences, 329, 164-176, 2016.
https://doi.org/10.1016/j.ins.2015.09.011

[37] Wang, J.; Shi, P.; Peng, H.; Pérez-Jiménez, M.J.; Wang, T. (2013); Weighted fuzzy spiking neural P system, IEEE Trans. Fuzzy Syst., 21(2), 209-220, 2013.
https://doi.org/10.1109/TFUZZ.2012.2208974

[38] Wang, T.; Zhang, G.X.; Zhao, J.B.; He, Z.Y.; Wang, J., Pérez-Jiménez, M.J. (2015); Fault diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems, IEEE Trans. Power Syst., 30(3), 1182-1194, 2015.
https://doi.org/10.1109/TPWRS.2014.2347699

[39] Xiong, G.; Shi, D.; Zhu, L.; Duan, X. (2013); A new approach to fault diagnosis of power systems using fuzzy reasoning spiking neural P systems, Mathematical Problems in Engineering, 2013(1), 211-244, 2013.

[40] Yahya, R.I.; Hasan, S.; George, L.E.; Alsalibi, B. (2015); Membrane computing for 2D image segmentation, International Journal of Advances in Soft Computing and its Application, 7(1), 35-50, 2015.

[41] Zeng, X.; Zhang, X.; Song, T.; Pan, L. (2014); Spiking neural P systems with thresholds, Neural Computation, 26(7), 1340-1361, 2014.
https://doi.org/10.1162/NECO_a_00605

[42] Zhang, G.; Cheng, J.; Gheorghe, M.; Meng, Q. (2013); A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems, Applied Soft Computing, 13(3), 1528-1542, 2013.
https://doi.org/10.1016/j.asoc.2012.05.032

[43] Zhang, G.; Gheorghe, M.; Li, Y. (2012); A membrane algorithm with quantum-inspired subalgorithms and its application to image processing, Natural Computing, 11(4), 701-717, 2012.
https://doi.org/10.1007/s11047-012-9320-2

[44] Zhang, G.; Gheorghe, M.; Pan, L.; Pérez-Jiménez, M.J. (2014); Evolutionary membrane computing: a comprehensive survey and new results, Information Sciences, 279, 528-551, 2014.
https://doi.org/10.1016/j.ins.2014.04.007

[45] Zhang G.; Liu, C.; Rong, H. (2010); Analyzing radar emitter signals with membrane algorithms, Mathematical and Computer Modelling, 52, 1997-2010, 2010.
https://doi.org/10.1016/j.mcm.2010.06.002

[46] Zhang, X.; Pan, L.; P un, A. (2015); On the universality of axon P systems, IEEE Transactions on Neural Networks and Learning Systems, 26(11), 2816-2829, 2015.
https://doi.org/10.1109/TNNLS.2015.2396940

[47] Zhang, G.; Pérez-Jiménez, M.J.; Gheorghe, M. (2017); Real-life Applications With Membrane Computing, Springer, 2017.

[48] Zhang, G.; Rong, H.; Neri, F.; Pérez-Jiménez, M.J. (2014); An optimization spiking neural P system for approximately solving combinatorial optimization problems, International Journal of Neural Systems, 24, 1-16, 2014.

[49] Zhao, Y.; Liu, X.; Qu, J. (2012); The k-medoids clustering algorithm by a class of P system, Journal of Information & Computational Science, 9(18), 5777-5790, 2012.
Published
2018-09-29
How to Cite
CHEN, Guangchun et al. A Spectral Clustering Algorithm Improved by P Systems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 13, n. 5, p. 759-771, sep. 2018. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/3238>. Date accessed: 08 mar. 2021. doi: https://doi.org/10.15837/ijccc.2018.5.3238.

Keywords

machine learning, spectral clustering, membrane computing, tissue-like P systems