A Spectral Clustering Algorithm Improved by P Systems

Guangchun Chen, Juan Hu, Hong Peng, Jun Wang, Xiangnian Huang


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.


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

Full Text:



Buiu, C.; Vasile, C.; Arsene, O. (2012); Development of membrane controllers for mobile robots, Information Sciences, 187, 33-51, 2012.

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

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.

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.

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.

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.

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.

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.

Garcia-Quismondo, M.; Levin, M.; Lobo-Fernández, D. (2017); Modeling regenerative processes with Membrane Computing, Information Sciences, 381, 229-249, 2017.

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.

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

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.

Luxburg, U.V. (2007); A tutorial on spectral clustering, Statistics and Computing, 17(4), 395-416, 2007.

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

Pan, L.; Wang, J.; Hoogeboom, H.J. (2012); Spiking neural P systems with astrocytes, Neural Computation, 24(3), 805-825, 2012.

Pan, L.; P un, G. (2009); Spiking neural p systems with anti-spikes, International Journal of Computers Communications & Control, 4(3), 273-282, 2009.

Paun, G. (2000); Computing with membranes, Journal of Computer System Sciences, 61(1), 108-143, 2000.

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Shi, J.; Malik, J. (2000); Normalized cuts and image segmentation, IEEE Transactions on pattern analysis and machine intelligence, 22(8), 888-905, 2000.

Song, T.; Pan, L., P un, G. (2014), Spiking neural P systems with rules on synapses, Theoretical Computer Science, 529, 82-95, 2014.

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.

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.

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.

Wang, J.; Shi, P.; Peng, H. (2016); Membrane computing model for IIR filter design, Information Sciences, 329, 164-176, 2016.

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.

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.

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.

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.

Zeng, X.; Zhang, X.; Song, T.; Pan, L. (2014); Spiking neural P systems with thresholds, Neural Computation, 26(7), 1340-1361, 2014.

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.

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.

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.

Zhang G.; Liu, C.; Rong, H. (2010); Analyzing radar emitter signals with membrane algorithms, Mathematical and Computer Modelling, 52, 1997-2010, 2010.

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.

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

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.

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.

DOI: https://doi.org/10.15837/ijccc.2018.5.3238

Copyright (c) 2018 Hong Peng

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]

INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2016: IF=1.374. .

IJCCC is indexed in Scopus from 2008 (CiteScore 2017 = 1.04; SNIP2017 = 0.616, SJR2017 =0.326):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.