Sage Journals: Discover world-class research

Abstract

This paper combines the graph theory and P system to solve the clustering problem. In order to effectively identify clusters with arbitrary shapes and uneven densities, we combine MkNN clustering algorithm and graph theory to propose a mutual $k$ -nearest neighbors graph (MkNNG) clustering algorithm. In order to further improve the efficiency of MkNNG algorithm, based on the non-determinism and great parallelism of P system, a cell-like P system with multi-promoters and multi-inhibitors named mutual $k$ -nearest neighbors graph P system (MkNNG-P) is designed. And then based on MkNNG-P system, a novel clustering algorithm named MkNNG-P clustering algorithm is proposed, which uses the membrane objects and rules to solve the clustering problem. MkNNG-P algorithm first calculates the dissimilarity between any two nodes in $n-1$ membranes in parallel. After then it uses one membrane to get $k$ -nearest neighbors of $n$ nodes. Finally, one membrane is used to find mutual $k$ -nearest neighbors and construct MkNNG to discover the natural clusters in the data set. Experiments show that MkNNG-P algorithm has the advantages of both MkNNG and P system. It not only can obtain good clustering quality for data of different sizes and shapes without presetting clustering numbers, but also has extremely high computing speed.

Keywords

Membrane computing P system graph theory MkNN clustering algorithm

Get full access to this article

View all access options for this article.

References

Song

Pérez-Jiménez

M.J.

and Pan

, Computational efficiency and universality of timed P systems with membrane creation, Soft Computing 9(11) (2015), 3043–3053.

Song

Zhang

and Pan

, Tissue-like P systems with evolutional symport/antiport rules, Information Sciences 378 (2017), 177–193.

Martín-Vide

Păun

Pazos

et al., Tissue P systems, Theoretical Computer Science 296(2) (2003), 295–326.

Hruschka

E.R.

and Freitas

A.A.

, A survey of evolutionary algorithms for clustering, IEEE Transactions on Systems Man and Cybernetics Part C Applications and Reviews 39(2) (2009), 133–155.

Păun

, Computing with membranes, Journal of Computer and System Sciences 61(1) (2000), 108–143.

Paun

Rozenberg

and Salomaa

, Membrane computing with external output, Fundamenta Informaticae 41(3) (1998), 313–340.

Singh

and Deep

, A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku, Applied Soft Computing 45 (2016), 27–39.

Zhang

et al., A Population-membrane-system-inspired evolutionary algorithm for distribution network reconfiguration, Chinese Journal of Electronics 23(3) (2014), 437–441.

Zhang

and Pan

, A survey of membrane computing as a new branch of natural computing, Chinese Journal of Computers 33(2) (2010), 208–214.

10.

Peng

and Wang

, Optimal multi-level thresholding with membrane computing, Digital Signal Processing 37(1) (2015), 53–64.

11.

Peng

Wang

and Pérez-Jiménez

M.J.

, An unsupervised learning algorithm for membrane computing, Information Sciences 304 (2015), 80–91.

12.

Huang

, Research on Membrane Computing Optimization Methods , Ph.D. Dissertation, Dept Control Science and Engineering, Zhejiang Univ, Hangzhou, China, 2007.

13.

Martinez-del-Amor

M.A.

Garcia-Quismondo

and Macias-Ramos

L.F.

, Simulating P systems on GPU devices: A survey, Fundamenta Informaticae 136(3) (2015), 269–284.

14.

Ionescu

Păun

and Yokomori

, Spiking neural P systems, Fundameta Informaticae 71(2–3) (2006), 279–308.

15.

Sato

Anada

and Tsutsumi

, Formulations of patterns by a graph model for the game of Go, Journal of Computational Methods in Sciences and Engineering 17(1) (2017), 1–11.

16.

Altman

N.S.

, An introduction to kernel and nearest-neighbor nonparametric regression, The American Statistician 46(3) (1992), 175–185.

17.

Ding

and Boykin

, A framework for distributed nearest neighbor classification using Hadoop, Journal of Computational Methods in Sciences and Engineering 17 (2016), 1–9.

18.

Freund

Kari

and Oswald

, Computationally universal P systems without priorities: Two catalysts are sufficient, Theoretical Computer Science J 330(2) (2005), 251–266.

19.

Freund

Oswald

and Paun

, Catalytic and purely catalytic P system and P automata: Control mechnisms for obtaining computational completeness, in: 14th International Conference, CMC14, 2013, pp. 317–320.

20.

Luxburg

U.V.

, A tutorial on spectral clustering, Statistics and Computing 17(4) (2007), 395–416.

21.

Yuan

Zhang

and Pérez-Jiménez

M.J.

, P systems based computing polynomials: Design and formal verification, Natural Computing 15(4) (2016), 591–596.

22.

Liu

and Xue

, A cluster splitting technique by hopfield networks and P systems on simplices, Neural Processing Letters 24(1) (2017), 1–24.

23.

Liu

Zhao

and Sun

, Tissue P systems with cooperating rules, Chinese Journal of Electronics 27(2) (2018), 324–333.

24.

Zeng

Zhang

and Pan

, Homogeneous spiking neural P systems, Fundamenta Informaticae 97 (2009), 275–294.

25.

Zhao

Liu

and Yan

, A grid-based chameleon algorithm based on the tissue-like P system with promoters and inhibitors, Journal of Computational and Theoretical Nanoscience 13(6) (2016), 3652–3658.

26.

Jia

Z.W.

Cui

and Yu

H.J.

, Graph-clustering method based on the dissimilarity, Journal of Shanxi Agricultural University 29(3) (2009), 284–288.

An improved MkNN clustering algorithm based on graph theory and membrane computing

Abstract

Keywords

Get full access to this article

References