In this paper we propose a new graph based P system. The main feature of graph P system is that membrane compartments spread on edges as well as on vertices. These two kinds of compartments are topologically connected with certain communication rules. A new neural computing technique is proposed to solve cluster splitting into finding the equilibrium of Hopfield neural networks. Then we use the new graph P systems to obtain stable status of the neural networks. An example is presented to show the computing efficiency of the new P system with comparison with classical genetic algorithms.
Hinweise
Research is supported by the Natural Science Foundation of China (No. 61472231, 61170038). Other Grants: 201401202, 12YJA630152, 11CGLJ22.
1 Introduction
Membrane computing as one of the most promising biological computing techniques has attracted more and more researchers in natural computing in the last decade. A classical literature in this area is Păun’s book [25]. Roughly speaking, there are two key issues in membrane computing, i.e., the topological structure of compartments, and the computations comprising a set of rules.
There are many categories of P systems as summarized in Păun’s book [25]. In the topological point of view, the most typical P system is the cell-like P system with communication rules and, topologically a tree structure. New communication P systems solving sorting and communication models and synchronous object movement across components are proposed in [5, 30]. Also there are P automata which are devices characterizing non-universal family of languages [26]. Another important P system is the tissue P system which is topologically a graph [25]. There are many tissue P systems such as rule applicability based communication modes [4], and trajectory P systems with evolutionary rules [3]. Spiking neural P systems are extensively studied recently by Pan and his team [17]. For example, Zeng et al. [37] study spiking neural P system with only one neuron simulating register machines, and other smaller weakly universal spiking neural P systems. There are also researches on asynchronous spiking neural P systems with promoters [35], spiking P systems to implement arithmetic operations [20], systems with fuzzy logic and firing mechanism [27], and applications with membrane algorithms [8].
Anzeige
P systems can be dynamic in its topological structure. By using rules that describe the movement and evolution compartments, P systems with active membranes are able to solve complicated combinatory problems in linear time [11]. Dynamic compartments are also applied in a research of Spicher [29]. There are also researches on introducing probabilities in a membrane system with respect to multisets and rules [24]. For applications of P systems we refer to [9], and the Proceedings of CMC15 [12].
For joint study of membrane computing with other optimization techniques, there are evolutionary string object P systems which introduces genetic operations such as crossover and mutation in membrane computing [31]. Alhazov in [1] generalize a splicing P system which joins the Tom Head splicing DNA system with membrane computing. By linking membrane computing with picture grammars, the so-called array P systems are proposed with objects in region as arrays applicable in syntactic analysis of images [6]. There are other works which incorporate Petri nets with spiking Neural P system with anti-spikes (SN PA systems) in order to verify system properties, soundness and simulation [22].
The second focus of this paper is cluster analysis [13, 33, 34, 36]. For example, a graph-skeleton-based clustering method with maximal spanning trees is proposed in [14]. In order to overcome local optima problem, Amiri in [2] proposes a population-based Teaching-Learning-Based-Optimization method without controlling parameters. In [10], the authors present a randomised algorithm for time series clustering, while Chen et al. [7] focus on the prognostic effect of the immunophenotypic clusters of acute myeloid leukemia patients. Research on discriminative spectral clustering can be found in [32]. For dynamic time series clustering we refer to [15]. The Q-statistics is also applied for clustering Non-Hodgkin lymphoma (NHL) in space and time [23]. Applications of cluster analysis in genetic analysis of strawberry [28], the k-means clustering in blogs analysis [19], gene expression data mining [16], joint study of membrane computing with cluster analysis [18].
Although clustering methods are proposed extensively, new technique and new joint research are still important in this big data era due to the vast development of business intelligence and other applications. In the point of membrane computing, we still need new system structure in order to solve new and potential problems. In [18], a new P simplicial P system is proposed. The purpose of this paper is to continue exploring simplicial P systems.
Anzeige
In this paper we will propose a graph based P system. Topologically, this graph P system uses a graph as its data structure. Different with tissue P systems, in graph P system we construct cells (compartments) on edges rather than only on vertices. Vertex cells and edge cells are topologically connected with special communications rules. We propose a novel neural computing technique to transform cluster analysis to the equilibrium of Hopfield neural networks. Computation of the neural network is performed by graph P systems. The new technique provides a cluster splitting method which is the key process of hierarchical cluster analysis. Finally we present an example to show the computation of the new P system. Comparison of genetic algorithm with our method is given which shows that the new method is efficient in computing complexity.
2 Cluster Splitting by Hopfield Neural Networks
In this section, we propose a Hopfield neural network setting for classical clustering problems. Our purpose is to find a new cluster splitting method by Hopfield neural networks. First we suppose the data set to be clustered is \(\Omega =\{\xi _1,\ldots ,\xi _N\}\) with N data points. A similarity measure \(\rho \) is defined on \(\Omega \times \Omega \) which forms similarity matrix \(W=[w_{ij}]_{N\times N}\) where \(w_{ij}=\rho (\xi _i,\xi _j)\).
Classical clustering methods include the partition method, the hierarchical method, the model based method, etc. For hierarchical method there are two categories namely agglomerative and divisive methods, where the latter is more complicated in most occasions. In this paper our focus is the divisive clustering method. In divisive clustering analysis, one of the most difficult problem is to split a cluster into two sub-clusters with specific conditions, i.e., maximum intra-cluster similarity and minimum inter-cluster similarity. If we search all possible splitting examples, it will be NP-complete.
To simplify the problem, we need only to find an efficient method to split the data set \(\Omega \) into two clusters satisfying certain optimal criteria. In order to achieve this task, we use a class label \(x_i=\pm 1\) where \(x_i=1\) indicates one cluster and \(x_i=-1\) indicates another split one. Then we define a vector \(x=[x_1,\ldots ,x_N]^T\) with \(x_i=\pm 1\). To specify the criteria for optimal splitting, an energy function is defined as follows
Now the \(\Omega \) is split into two clusters \(\Omega _1=\{\xi _i| x_i=1\}\) and \(\Omega _2=\{\xi _i| x_i=-1\}\). The energy function E in (2.1) is the sum of intra-cluster weights minus inter-cluster weights, together with a computing constant \(-\frac{1}{2}\). Therefore the minimal solution of E is an optimal cluster splitting solution in the sense of our energy function.
To solve this problem, we now construct a Hopfield neural network \((W,\theta )\) with \(\theta =0\). By standard neural network theory [21], the stable state of the network corresponds to the minimal solution of Eq. (2.1). Suppose the state of the network is x(t) with a discrete time variable t. Then the evolution of x(t) is by the following Eq. (2.2):
Since similarity measure is non-negative, the matrix diagonal of W is positive. By the standard neural network theory [21], the network \((W,\theta )\) is stable in asynchronous mode.
In the following, we always assume that the weight \(w_{ij}\) takes non-negative integers as its values.
3 A Graph Based P System
A basic cell-like P system is defined as a hierarchical arrangement of compartments delimited by membranes. Each compartment may contain a finite multiset of objects and a finite set of rules, as well as a finite set of other compartments. The rules perform transformation and communication operations.
In order to solve the Hopfield neural networks by membrane computing technique, we need to extend a typical P system to simplices. Simplices can be seen as a new class of data structure different with the linear structure, the tree structure, and the graph structure. In topological point of view, these structures are one dimensional. A simplex structure however, can be multi-dimensional. A tissue like P system is a system on graphs. Now we extend membrane membrane structures to edges. Then we obtain a totally new class of P system, called P system on simplices, or simplicial P systems.
A \(k-\)simplex \(\sigma \) is the convex hull of \(k+1\) affinely independent points \(a_0,a_1,\ldots ,a_k\) defined as the set of points in the form \(x=\sum ^k_{i=0}\lambda _ia^i\) where
A face \(\tau \) of \(\sigma \) is a simplex by a subset vertices written by \(\tau <\sigma \). \(\tau \) is called a hyperface if \(\dim \tau =\dim \sigma -1\), denoted by \(\tau \prec \sigma \), while \(\sigma \) is called its parent. Two cells \(\tau _1\) and \(\tau _2\) are incident if \(\tau _1,\tau _2\prec \sigma \), and \(\sigma \) is called the coface of \(\tau _1\) and \(\tau _2\). Two cells \(\sigma _1,\sigma _2\) are called neighbors if they share a common hyperface. A simplicial complex K is a collection of simplices for which \(\sigma \in K\) and \(\tau \prec \sigma \) implies \(\tau \in K\); and \(\sigma _1, \sigma _2\in K\) implies that \(\sigma _1\cap \sigma _2\) is either empty or a face of both. For a k-simplex \(\sigma \), define K to be the collection of \(\sigma \) and all its faces. Then K is a simplicial complex, namely, a simple complex, or simply, a complex.
3.1 Membrane Structures on Graphs
Graph is a simple kind of simplicial complex. Now we will define membrane structures on graphs. Notice that these are different with tissue like P systems.
Suppose \(G=(V,E)\) is a graph where V is the set of vertices and E the set of edges. Define a simplicial complex K as the collection of V and E. Each simplex \(\sigma \in K\) is called a membrane. A membrane in E is maximal since it is not a face of another simplex in K. Evidently, vertices are zero-dimensional cells and hence are elementary membranes. Next we will identify K with the graph G.
If \(\tau \prec \sigma \) is a face of \(\sigma \), then we say that \(\sigma \) is the parent of \(\tau \). If \(\sigma _1,\sigma _2\) are incident, we say there is an upper link (channel) between \(\sigma _1,\sigma _2\). If \(\sigma _1,\sigma _2\) are neighbors, we say there is a lower link between them. An upper link is denoted by \((\sigma _1,\sigma _2)^{\tau }\) where \(\tau \) is their (common) parent, while lower link is written as \((\sigma _1,\sigma _2)_{\tau }\) where \(\tau \) is their common hyperface. Upper link is also written by \((\sigma _1,\sigma _2)^{U}\), or, simply \((\sigma _1,\sigma _2)\), while lower link is denoted by \((\sigma _1,\sigma _2)_{L}\).
Definition 1
A P system on a graph G, called a graph P system, with antiport and symport rules is a construct
where m is the number of cells labeled with \(1,2,\ldots ,m\), O is the alphabet, \(\omega _1,\ldots ,\omega _m\) are initial strings over O of multisets, \(R_1,\ldots ,R_m\) are symport and antiport rules associated with the m membranes, \(ch\subseteq \{(i,j)_R, (i,j)_L : i,j\in \{1,\ldots ,m\}\}\) is the set of links, F(i, j) is a finite set of antiport and/or symport rules associated with the link \((i,j)\in ch\).
3.2 Rules of Graph P Systems
Now we describe rules in graph P systems. For the purpose of this paper, there are mainly four types of communication rules. Each type of rules contains four special operators out, in, up and down.
First suppose there exists an upper link \((\tau _1,\tau _2)^{\sigma }\). A rule in the form of \([(x,y),up]^U\) means that the multiset x and y from \(\tau _1\) and \(\tau _2\) transform into some z and go up to their parent \(\sigma \). Second, for two cells \(\tau \prec \sigma \), antiport rule in \(\tau \) in the form of \([u,out;v,in | \tau \prec \sigma ]\) means that exchanging multiset u inside membrane \(\tau \) with the multiset v outside (both in \(\sigma \)). Thirdly, symport rule \([u,out | \tau \prec \sigma ]\) sends multiset u out of \(\tau \) to \(\sigma \). Symport rule \([u,in | \tau \prec \sigma ]\) works similarly and takes u from \(\sigma \) into \(\tau \).
Combining these rules together we define upper link rule in \(R^{\sigma }(\tau _1,\tau _2)\) in the following forms
Operations of Eq. (3.3) are listed here. Multiset x from cell \(\tau _1\) and y from \(\tau _2\) are removed transformed into z to parent cell \(\sigma \), while simultaneously \(\gamma \) of \(\sigma \) is moved and transformed into \(\alpha \) in \(\tau _1\) and \(\beta \) in \(\tau _2\). Operations of Eq. (3.4) is to move u out to \(\sigma \) while taking v from \(\sigma \) into \(\tau _1\), or \(\tau _2\).
A lower link rule in \(R_{\sigma }(\tau _1,\tau _2)\) has the following forms
Equation (3.5) means that we move x from cell \(\tau _1\) and y from \(\tau _2\) to z into their hyperface \(\sigma \), while simultaneously moving \(\gamma \) from \(\sigma \) to \(\alpha \) up to \(\tau _1\) and \(\beta \) up to \(\tau _2\). Equation (3.6) is similar to Eq. (3.5).
3.3 Configurations and Computations
Now we describe the configurations and computations of the proposed graph P systems. For our purpose, change of membrane structure is not involved. A configuration of a graph P system is the state of the system described by specifying the objects and rules associated to each membrane. The initial state is called initial configuration. Therefore, the multisets represented by \(\omega _i, 1\le i\le d\) in \(\Pi \), constitute the initial configuration of the system.
The system evolves by applying rules in membranes and this evolution is called computation. A computation starts with the multisets specified by \(\omega _1,\ldots ,\omega _m\) in its m cells. During each time unit, rules are applied in a cell. If no rule is applicable for one cell, then no object change occurs in it. The system evolves synchronously for all cells.
When the system has reached a configuration in which no rule is any longer applicable, we say that the computation halts. A configuration is stable if, even if some rules are still applicable, their application does not change the object content of the membranes. The computation is successful if and only if it halts, or it is stable. The result of a halting/stable computation is the number described by the multiplicity of objects present in the cell \(i_0\) in the halting/stable configuration.
4 Rules and Computations of Graph P Systems
In this section we consider a neural network (W, 0) as in Sect. 2 and a P system on a complete graph \(G=(V,E)\) with N nodes. Notice that we always assume that the elements of W are non-negative integers. We use an integer \(N_i\) to denote the sum
where the number of edges (links) are \(m=\frac{1}{2}N(N-1)\), \(\omega _i,R_i\) are initial configurations and rules of(on) node membranes \(\sigma _i\), and \(\omega _{ij},F_{i,j}\) are initial configurations and rules of(on) edge membranes \(\sigma _{ij}\), \(i_0=1\) indicates the output node. The alphabet is shown in Table 1.
where the symbol \(a_i=a_+\) or \(a_-\). As initialization we set \(a_i=a_+\) or \(a_-\) randomly. The initial configuration on edges are empty strings \(\omega _{ij}=\{\lambda \}\).
4.1 Rules with Partial Ordering
All the rules are categorized as several groups. The first group is annihilation rules acting on node cells
Now we discuss computation and halting conditions. The main idea is using a symbol \(\pi _0\) to count the number of running nodes in one cycle and compute the number of stable nodes. When the number of stable nodes equals N, then the whole network is stable. We can send a symbol \(\pi _h\) to output node \(\sigma _1\). Notice that rules are executed in an order.
The total number of loops is written in the symbol \(\pi _\sigma \).
4.2 Configurations and Computations
Now we explain the process of computation in detail. We use \(i_0=1\) to note the output cell. For initial configuration, the multisets of edges are \(\{\lambda \}\) and the node cells have the following multisets.
The the running node of the neural network is \(i=1\). To illustrate the process more clearly, we assume that the current running node is \(i=2\) after the first round of running for \(i=1\). In the first node cell, the symbol \(\pi _\sigma \) notes the number of running rounds for the network. Hence the current configuration is
Actually in one running we only obtain one possible correct node which is noted by the symbol \(\pi _0\). If after all the N nodes are processed we obtain \(\pi _0^N\) correct nodes, then the network is stable. We then send a symbol \(\pi _h\) to the output node the computation is complete. Otherwise we send a continuing symbol \(\pi _c\) to \(\sigma _1\) and continue to the next step. The function of rules \(F_3\) and \(F_5\) is to control the running of current node to the next node.
The next figure (Fig. 1) illustrate the whole computation process when \(N=4\) and \(i=2\).
Fig. 1
A flow chart computation process of a graph P system
×
5 Example and Discussion
In this section we will give an example taken in UCI data set to show the cluster splitting technique by graph P systems. Then we will present some comparison with genetic algorithms. Experiments show that computation by Hopfield neural networks is rather efficient especially in comparison with genetic algorithms.
The Wisconsin breast cancer data set consists 699 samples with 9 attributes. The samples are classified as two categories, the malignant and the benign. The data is shown in Fig. 2 with an added noise of [0, 0.5]. For the purpose of this paper, we choose attribute 2 and 6 and accumulate the data samples using the grid technique. Then the data set \(\Omega =\{\xi _1,\ldots ,\xi _N\}\) is shown in Fig. 3 with \(N=100\) data points. The number of raw data points in \(\xi _i\) is denoted by \(m(\xi _i)\).
Fig. 2
Wisconsin breast cancer data with perturbation. Attribute 2 and 6
Fig. 3
Data nodes of the Wisconsin breast cancer data
×
×
Now we define a similarity measure on the data set. For \(\xi _i,\xi _j\in \Omega \), let \(L(\xi _i,\xi _j)\) be the shortest path length as shown in Fig. 3. Here we always take the unit length between two nodes as one. Similarity measure is defined as follows:
Next we analyze the computation with similarity measure \(\rho (\xi _i,\xi _i)\). Then we obtain the weight matrix \(W=[W_1,W_2,W_3,W_4]^T\) as shown in equations (5.6)(5.7) (5.8)(5.9) (5.10)(5.11) (5.12)(5.13), where each subsequent two equations compose of of the matrices \(W_1,W_2,W_3,W_4\) each, in such a way as \(W_i=[A,B]^T\).
×
×
×
×
×
×
×
×
Now we choose \(L_0=10\). A maximum running time is set to be 500. Then the computation is rather efficient. The next figure Fig. 4 shows the energy curve of the computation. The next experiment shows the energy curve with maximum running time 1000 (Fig. 5).
Fig. 4
Energy curve with maximum running time 500
Fig. 5
Energy curve with maximum running time 1000
×
×
Next we compare the graph P system with traditional genetic algorithms (GA) to see the computation efficiency. First we set GA population size as 10. Mutation probability is \(p=1\) with one-point mutation. The next figure (Fig. 6) shows the running time comparison result. Here we set the maximum running time is 100. The energy comparison is shown in Fig. 7.
Fig. 6
Running time comparison of GA with MC
Fig. 7
Energy comparison of GA with MC
×
×
Now we change some parameters of GA. Let the population size be 100. We choose two individuals each time to be mutated. When the maximum running time is 500, we obtain the energy comparison as shown in Fig. 8. The figure shows clearly that the proposed method in this paper has better performance than GA.
Fig. 8
Energy comparison of GA with MC with running time 500
×
Finally we present another experiment with parameters as the previous one. To make it more clearly we draw the energy comparison in the tail part. Notice that we only use decimal part of the energy value and multiply these values by 1000. Again we obtain a better result (Fig. 9).
Fig. 9
Energy comparison with tail part (decimal_part*1000).
×
6 Conclusion
In this paper we present a new membrane computing model called the graph P system. Topologically, the new system extends traditional P system to more complicated topological structure. In some sense, this means a new membrane computing model is set up with new data structure, namely, simplex structure. The main ingredients of the new structure is that topological data structure turns from one dimensional structure to multidimensional structure. In the simplest case, the graph case namely, we add connections between nodes and edges. This will induce new paradigm of rules in association with this new connections which will hopefully solve more complicated problems by simulating new operations of multisets. However, computing ability of the new P system is still an open problem.
We also present a new solution to clustering splitting problem which is the most difficult task in hierarchical cluster analysis by the Hopfield neural networks. Surprisingly the new method works in a very efficient mode than traditional heuristic optimization method such as genetic algorithms. Computation of the neural networks are done by the proposed graph P system which is new in itself. Finally we will point out that the graph based P system, or more generally the simplex P system, is a promising new direction of membrane computing. We expect new research on this area with more powerful applications.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
