# An Extended Clustering Membrane System Based on Particle Swarm Optimization and Cell-Like P System with Active Membranes

Authors: Lin Wang; Xiyu Liu; Minghe Sun; Jianhua Qu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

An extended clustering membrane system using a cell-like P system with active membranes based on particle swarm optimization (PSO), named PSO-CP, is designed, developed, implemented, and tested. The purpose of PSO-CP is to solve clustering problems. In PSO-CP, evolution rules based on the standard PSO mechanism are used to evolve the objects and communication rules are adopted to accelerate convergence and avoid prematurity. Subsystems of membranes are generated and dissolved by the membrane creation and dissolution rules, and a modified PSO mechanism is developed to help the objects escape from local optima. Under the control of the evolution-communication mechanism, the extended membrane system can effectively search for the optimal partitioning and improve the clustering performance with the help of the distributed parallel computing model. This extended clustering membrane system is compared with five existing PSO clustering approaches using ten benchmark clustering problems, and the computational results demonstrate the effectiveness of PSO-CP.


---

## Body

## 1. Introduction

The scopes and scales of datasets are growing exponentially with the advent of new sources of data generation. This growing tendency produces a serious challenge for discovering knowledge from data. Data clustering is one of the important techniques used in data mining [1]. It aims to put similar data points into the same group or cluster using the characteristics of the data without any prior knowledge about the groups or clusters. Therefore, the implicit patterns or knowledge can be extracted through data clustering [2]. Traditional data clustering approaches can be categorized into partition clustering, hierarchical clustering, density clustering, and grid clustering [3]. These clustering methods have low time complexity and are easy to implement, but also produce highly skewed dendrograms that may not reflect the true structures of the datasets [4, 5]. Therefore, some evolutionary approaches have been introduced to solve clustering problems in recent years [6], such as genetic algorithms [7], particle swarm optimization (PSO) [8], differential evolution (DE) [9], artificial bee colony (ABO) [10], and ant colony optimization (ACO) [11], among others. PSO is one of the global optimization techniques based on the intelligence strategy of the population, and many works have been done to use PSO to solve clustering problems.Netjinda et al. [12] presented a PSO approach, named starling PSO (SPSO), which is inspired by the collective response behavior of starling birds. The collective information of the neighbors is used to replace the local information in history, and subpopulations are generated when the premature phenomenon appears. Song et al. [13] proposed an improved PSO procedure based on the features of the clustered data. An environment factor is added to the velocity adjustment in PSO to improve the global searching ability, which is represented by the cluster centers of the partitioning results. Liu et al. [14] developed a modified coevolutionary multiswarm optimizer based on a new velocity updating and similarity detection mechanism. Lassad et al. [15] designed a PSO procedure with new adaptive inertia weight and time acceleration coefficients for solving fuzzy clustering problems. Asgarali and Abdolreza [16] introduced a K-harmonic means clustering approach, which integrates the improved cuckoo search and PSO. Pereira de Gusmão and de Carvalho [17] proposed two hybrid clustering methods for multiview relational data, taking advantages of the global convergence ability of PSO and the local exploitation of hard clustering algorithms in the update of the position vectors in PSO. Manju and Kumar [18] developed a new sustainable clustering method based on PSO with a mutation operator for clustering of the data generated from different networks. Huang et al. [19] designed a memetic clustering approach based on PSO and the gravitational search algorithm using the hybrid operation and a diversity enhancement as the two main mechanisms. Zhang et al. [20] presented a new clustering approach based on PSO with a leader updating mechanism and ring topology for multimodal multiobjective optimization.Although PSO has shown a great potential in solving clustering problems, it still has some limitations, such as being easily falling into local optima and exhibiting the premature phenomena. Furthermore, the computational complexity of the PSO clustering approaches may increase quickly as the number of data points in the dataset increases [21]. Therefore, more studies are needed to improve the performance of PSO for clustering.Membrane computing, also known as membrane systems or P systems, is a novel approach of bio-inspired computing initiated by Păun [22]. It seeks to discover novel biological computing models from the structure of biological cells as well as the cooperation of cells in tissues and organs. Parallel computation in membrane systems can avoid the increase in time consumption with the increase in the number of data points. Therefore, membrane systems are suitable for solving clustering problems [23]. Research shows that some models of P systems present the same computing power as Turing machines and are more efficient to some extent [24]. Spiking neural P systems are a kind of neural-like P systems in membrane computing. It provides a class of parallel computing models [25]. Many variants of spiking neural P systems have been proposed [26, 27] and have been applied to various real-world problems [28, 29].Xue and Liu [30] developed a new communication P system for solving clustering problems. Liu and Xue [31] proposed a new cluster splitting technique based on Hopfield neural networks and P systems. Liu et al. [32] presented an improved Apriori algorithm, named ECTPPT-Apriori, based on evolution-communication tissue-like P systems with promoters and inhibitors. Peng et al. [33] designed a tissue-like membrane system with a fully connected structure using an inherent mechanism to deal with automatic clustering problems. Peng et al. [34] developed an extended membrane system with active membranes, in which a modified differential evolution mechanism is used to find the optimal cluster centers in clustering problems. Peng et al. [35] introduced a multiobjective clustering framework using a tissue-like membrane system for fuzzy clustering problems. Wang et al. [36] proposed a new cell-like P clustering system using a modified genetic algorithm to evolve the objects and using communication rules in the cell-like P system to enhance the diversity of the populations.The traditional evolution mechanism is easily trapped into local optima, called the premature phenomenon, which is a main limitation of PSO for solving optimization problems. Many previous studies paid close attention to improving the global searching ability and avoiding prematurity. Membrane systems are distributed parallel computing models and can effectively avoid the prematurity and improve the global searching ability of PSO. Over the past years, a variety of membrane systems integrated with PSO have been proposed and proved powerful and efficient in solving optimization problems. Xiao et al. [37] proposed a hybrid membrane evolutionary algorithm, which combines a one-level membrane structure with a PSO local search algorithm. Xiao et al. [38] developed an improved dynamic membrane evolutionary algorithm based on PSO and DE to solve constrained engineering design problems. Singh and Deep [39] designed a new multiple-PSO based membrane algorithm with seven different membranes for solving real-life problems. Elkhani et al. [40] proposed a kernel P system and introduced multiobjective binary PSO to feature selection and classification methods with time efficiency on GPU. Furthermore, the inherent mechanism based on communication rules between different cells or membranes can accelerate convergence of PSO. Therefore, membrane systems are used to enhance the clustering performance of PSO in this study. Each cell or membrane in a membrane system, as an independent computing unit, can be regarded as a subpopulation of particles in PSO, and the cooperation of subpopulations can be viewed as the communication between membranes [41].This work focuses on the development of a membrane computing model, as an extended membrane system, to solve clustering problems and overcome the limitations mentioned above. A new clustering method based on membrane systems and the PSO mechanism is proposed. This membrane system with active membranes has a dynamic membrane structure during evolution and computation. The velocity updating mechanism of PSO is used as the basic evolution rules for the objects in the elementary membranes. Another evolution rule based on the fitness Euclidean-distance ratio (FER) [42] method is introduced for the objects to escape the local optima in the membranes of the subsystems. The communication mechanism in membranes is adopted to transport the best objects in order to accelerate the convergence of the P system. This system is evaluated using 10 benchmark clustering problems to verify the validity and performance of the extended clustering membrane system.The rest of this paper is organized as follows. The clustering problems are described in Section2. The framework of cell-like P systems with active membranes is given in Section 3. These concepts are related to the development of the proposed extended clustering membrane system. Section 4 describes the details of the extended clustering membrane system based on cell-like P systems and the PSO mechanism. Experimental results on benchmark clustering problems are reported in Section 5. Section 6 provides conclusions and outlines future research directions.


## 2. Data Clustering

In this section, the basic concepts of data clustering problems are described in detail. LetX=x1,x2,…,xN be a dataset containing N unlabelled data points. Data point i, for i=1,2,…,N, is represented by xi=xi1,xi2,…,xid with d representing the dimension of the data. The purpose of a clustering problem is to find a partition of the dataset with similar data points in the same cluster. The partition result is represented by C=c1,c2,…,cK, where K is the number of clusters and ck is cluster k, for k=1,2,…,K. The vector of the cluster centers is represented by Z=z1,z2,…,zK with zk representing the cluster center of ck [43].A partition must satisfy some conditions, such as the data points in the same cluster should be similar as much as possible and the data points in different clusters should be different as much as possible. Usually, a clustering technique may search in the solution space to find the optimal cluster centers based on some clustering measures. A commonly used clustering measure, called the fitness function, is defined as follows:(1)fc1,c2,…,cK=∑i=1N∑j=1Kωijxi−zj,where ωij is the associated weight for data point xi to belong to the cluster j. If the data point xi is allocated to cluster j, ωij=1; otherwise, ωij=0. A clustering process is to separate the data points into the corresponding clusters that can be viewed as an optimization problem, and the purpose of the optimization problem is to find a partition or a set of cluster centers to minimize the fitness function (1), i.e.,(2)minc1,c2,…,cKf=minfc1,c2,…,cK=min∑i=1N∑j=1Kωijxi−zj.In addition, the value of the fitness functionf is used to evaluate the performance of clustering techniques and to compare the quality of objects or potential solutions. When two objects are compared, the one with a smaller value of the fitness function is better than the other.


## 3. Cell-Like P Systems

### 3.1. The Basic Cell-Like P Systems

Cell-like P systems are a class of membrane systems, which abstract computing models from cell structures and functions or from the group collaboration of cells. Research shows that the computation ability of simple cell-like P systems is equal to that of Turing machines [44]. The usual cell-like P systems have a tree membrane structure, that is, a simple graph. Each membrane contains a set of objects or symbols that can be evolved and communicated by evolution and communication rules. A basic cell-like P system can be expressed as the following tuple:(3)∏=O,H,μ,w1,…,wq,R,R′,i0,where q≥1 is the degree of the system; O is a finite set of alphabets, whose symbols are called objects, i.e., u and v represent different objects in the alphabets, where u,v∈O; H is a finite set of labels for the membranes; μ is the membrane structure consisting of q membranes and its regions are labelled by the elements of H; w1,…,wq are the multisets of objects placed in the regions of the membranes, with wi∈O, for 1≤i≤q; R represents multiple but finite sets of evolution rules associated with the membranes; R′ represents multiple but finite sets of communication rules between different membranes; and i0 is the output region or output membrane in the P system [45].A cell-like P system is a hierarchy ofq membranes or cells where each membrane or cell may contain one or more other membranes or cells. A membrane or cell contains many objects in the system, and an object u represents a potential solution in the search space, where u∈O. A membrane is called an elementary membrane if it does not contain any other membranes. An elementary membrane has no children membranes in the system. A membrane is called a nonelementary membrane if it contains other membranes. A membrane is called a skin membrane if it is not contained in any other membranes. The skin membrane has no parent membrane in the system. The degree of the system is the number of elementary membranes in the system. A cell-like P system is mainly composed of three parts: membrane structure, objects, and rules. Figure 1(a) gives a graphical representation of a simple cell-like P system, in which membranes are labelled from 0 to 9. These membranes are arranged by a hierarchical structure which can be represented as a tree diagram as shown in Figure 1(b).Figure 1
An example of cell-like P system.
(a)
(b)In Figure1(a), membrane 0 is the skin membrane which is not contained in any other membranes and membrane 1 is the parent membrane of membranes 4 and 5 and is a nonelementary membrane. Membrane 4 is an elementary membrane which does not contain any other membranes. The tree structure in Figure 1(b) is an abstract from the cell-like P system in Figure 1(a). The nodes in the tree represent the membranes, the leaf nodes represent the elementary membranes, and the root node 0 represents the skin membrane 0. A node in a layer is the parent of the nodes following it in the next layer, and the nodes in the next layer are the children of the node in the layer above. The degree of this cell-like P system is 6. Specially, a membrane only communicates with its parent membrane and children membranes, if it has any, and there are not existing communication rules between the sibling membranes.A cell-like P system usually has two types of rules: evolution rulesR and communication rules R′. Evolution rules are of the form R=u⟶v, for u,v∈O, which means that a copy of object u will be evolved to object v. Communication rules are of the form R′=u⟶v,inh, for h∈H and u,v∈O, which means that a copy of object u will be changed to object v and transported into membrane h. The object is modified in the communication process, and membrane h is the parent or child membrane of the membrane where originally u was.


### 3.2. An Extended Cell-Like P System with Active Membranes

The evolution and communication rules in the cell-like P systems only execute on objects, but not on membranes. The objects will be changed and moved based on the evolution-commutation rules, but the membranes will not change during the evolution and computation. Therefore, an extended cell-like P system with active membranes is introduced to overcome this restriction. This extended P system contains not only evolution and communication rules for objects but also evolution rules for membranes.There are two types of membrane evolution rules: creation rules and dissolution rules. Membrane creation rules are of the formuh⟶vh1,…,vhsn, for h,h1,…,hsn∈H and u,v∈O, which means that membrane h1 to hsn are created and a copy of object u in membrane h is evolved to v and transported to these newly created membranes, where sn is the number of newly created membranes. Membrane dissolution rules are of the form uh⟶λ, for u,λ∈O, which means that the membrane will be dissolved, and object u in membrane h will disappear, where λ is a special symbol that represents no objects in the membrane. Therefore, the extended cell-like P system with active membranes has a dynamic membrane structure in the evolution and computation process [46].


## 3.1. The Basic Cell-Like P Systems

Cell-like P systems are a class of membrane systems, which abstract computing models from cell structures and functions or from the group collaboration of cells. Research shows that the computation ability of simple cell-like P systems is equal to that of Turing machines [44]. The usual cell-like P systems have a tree membrane structure, that is, a simple graph. Each membrane contains a set of objects or symbols that can be evolved and communicated by evolution and communication rules. A basic cell-like P system can be expressed as the following tuple:(3)∏=O,H,μ,w1,…,wq,R,R′,i0,where q≥1 is the degree of the system; O is a finite set of alphabets, whose symbols are called objects, i.e., u and v represent different objects in the alphabets, where u,v∈O; H is a finite set of labels for the membranes; μ is the membrane structure consisting of q membranes and its regions are labelled by the elements of H; w1,…,wq are the multisets of objects placed in the regions of the membranes, with wi∈O, for 1≤i≤q; R represents multiple but finite sets of evolution rules associated with the membranes; R′ represents multiple but finite sets of communication rules between different membranes; and i0 is the output region or output membrane in the P system [45].A cell-like P system is a hierarchy ofq membranes or cells where each membrane or cell may contain one or more other membranes or cells. A membrane or cell contains many objects in the system, and an object u represents a potential solution in the search space, where u∈O. A membrane is called an elementary membrane if it does not contain any other membranes. An elementary membrane has no children membranes in the system. A membrane is called a nonelementary membrane if it contains other membranes. A membrane is called a skin membrane if it is not contained in any other membranes. The skin membrane has no parent membrane in the system. The degree of the system is the number of elementary membranes in the system. A cell-like P system is mainly composed of three parts: membrane structure, objects, and rules. Figure 1(a) gives a graphical representation of a simple cell-like P system, in which membranes are labelled from 0 to 9. These membranes are arranged by a hierarchical structure which can be represented as a tree diagram as shown in Figure 1(b).Figure 1
An example of cell-like P system.
(a)
(b)In Figure1(a), membrane 0 is the skin membrane which is not contained in any other membranes and membrane 1 is the parent membrane of membranes 4 and 5 and is a nonelementary membrane. Membrane 4 is an elementary membrane which does not contain any other membranes. The tree structure in Figure 1(b) is an abstract from the cell-like P system in Figure 1(a). The nodes in the tree represent the membranes, the leaf nodes represent the elementary membranes, and the root node 0 represents the skin membrane 0. A node in a layer is the parent of the nodes following it in the next layer, and the nodes in the next layer are the children of the node in the layer above. The degree of this cell-like P system is 6. Specially, a membrane only communicates with its parent membrane and children membranes, if it has any, and there are not existing communication rules between the sibling membranes.A cell-like P system usually has two types of rules: evolution rulesR and communication rules R′. Evolution rules are of the form R=u⟶v, for u,v∈O, which means that a copy of object u will be evolved to object v. Communication rules are of the form R′=u⟶v,inh, for h∈H and u,v∈O, which means that a copy of object u will be changed to object v and transported into membrane h. The object is modified in the communication process, and membrane h is the parent or child membrane of the membrane where originally u was.


## 3.2. An Extended Cell-Like P System with Active Membranes

The evolution and communication rules in the cell-like P systems only execute on objects, but not on membranes. The objects will be changed and moved based on the evolution-commutation rules, but the membranes will not change during the evolution and computation. Therefore, an extended cell-like P system with active membranes is introduced to overcome this restriction. This extended P system contains not only evolution and communication rules for objects but also evolution rules for membranes.There are two types of membrane evolution rules: creation rules and dissolution rules. Membrane creation rules are of the formuh⟶vh1,…,vhsn, for h,h1,…,hsn∈H and u,v∈O, which means that membrane h1 to hsn are created and a copy of object u in membrane h is evolved to v and transported to these newly created membranes, where sn is the number of newly created membranes. Membrane dissolution rules are of the form uh⟶λ, for u,λ∈O, which means that the membrane will be dissolved, and object u in membrane h will disappear, where λ is a special symbol that represents no objects in the membrane. Therefore, the extended cell-like P system with active membranes has a dynamic membrane structure in the evolution and computation process [46].


## 4. An Extended Clustering Membrane System

An extended membrane system with active membranes, called the particle swarm optimization cell-like P system (PSO-CP), is introduced to solve clustering problems. This system has two main mechanisms: the evolution-communication mechanism for objects and the evolution mechanism for membranes. More details about PSO-CP are given in the following.


### 4.1. Initialization

#### 4.1.1. The Initial Membrane Structure

The membrane structure of PSO-CP is built dynamically through membrane creation and dissolution rules during the evolution and computation process. Therefore, the number of membranes will change. Specifically, PSO-CP starts with an initial membrane structure and then the membrane evolution mechanism will control the structure and the number of membranes. The initial membrane structure of a PSO-CP is graphically depicted in Figure2.Figure 2
The initial structure of a PSO-CP.In Figure2, the PSO-CP with a three-layer nesting structure contains a skin membrane 0, a nonelementary membrane 1, and elementary membranes 2 to q. These membranes are labelled from 0 to q. The nonelementary membrane, also called the comparison membrane, is labelled 1, whose role is to find the best object in the elementary membranes during the current evolution process and output the best object to the outmost membrane. Membrane 1 is the parent of the elementary membranes 2 to q, and elementary membranes 2 to q are the children of nonelementary membrane 1. The outmost membrane, labelled 0, is the skin membrane, whose role is to store the best object in the system during the current evolution and computation process.


#### 4.1.2. Object Representation

In the PSO-CP, an object is a set of clustering centers representing a feasible solution. Therefore, the objects represent the sets of clustering results. Each objectu, u∈O, is designed as a composite K×d dimensional vector [47] of the following form:(4)u=z1,z2,…,zK=z11,z12,…,z1d,…,zk1,zk2,…,zkd,…,zK1,zK2,…,zKd,where zk=zk1,zk2,…,zkd corresponds to the cluster center of cluster k and d, as mentioned earlier, represents the dimension of the data points. Hence, an object u, with u=z1,z2,…,zK, represents a set of cluster centers. As usual, each membrane has at least one object. To ensure the same computation complexity of each elementary membrane, all elementary membranes have the same number of objects, denoted by m. The number of objects in the whole P system is represented by M, i.e., M=m×q.


#### 4.1.3. Initial Objects

As mentioned above, each elementary membrane in the PSO-CP has the same number of objects. When the evolution and computation process starts, each elementary membrane also has the same number of initial objects. An objectu represents a set of cluster centers. Dimension j of object up represented by upj is generated randomly between xjmin and xjmax, where xjmin and xjmax are the minimum and maximum values of dimension j of the search space. Therefore, upj∈xjmin,xjmax, for p=1,2,…,m and j=1,2,…,d. The values of xjmin and xjmax are determined by using the following equation:(5)xjmin=minxiji=1,2,…,N,xjmax=maxxiji=1,2,…,N,forj=1,2,…,d.After initialization, the fitness value of each object is calculated using (1). In membrane o, for o=2,3,…,q, the initial best with the lowest fitness value for up, denoted by uplbest0 and called the local best, is determined for p=1,2,…,m. The initial best with the lowest fitness value in history among all objects in membrane o, denoted by uogbest0 and called the global best, is also determined. The local best and the global best refer to the positions of the objects. The object that found the global best is the global best object.


### 4.2. The Evolution and Communication Rules for the Objects

#### 4.2.1. Evolution Rules for the Objects

The PSO-CP has two types of evolution rules: the basic evolution and the local evolution rules.(1) The Basic Evolution Rules. In this work, the standard PSO [48] is used to search for the optimal solutions in the elementary membranes 2 to q. The evolution of objects is achieved only within elementary membranes, and the basic evolution rules only execute on objects contained in elementary membranes 2 to q. Let upt and Vpt represent the position and velocity of up at time t in elementary membrane o, for o=2,3,…,q. The velocity of up at time t+1 is determined by using the following equation:(6)Vpt+1=wVpt+c1r1uplbestt−upt+c2r2uogbestt−upt,where w is the inertia weight, c1 and c2 represent the local and global learning factors, which control the influence of the local best and the global best object, t is the time or iteration counter, and r1 and r2 are two uniform random numbers [49]. The local best of up is denoted by uplbestt and the global best in the elementary membrane o is denoted by uogbestt at iteration t. For notational convenience, the global best object is also denoted by uogbestt at iteration t.The position ofup at time t+1 is determined by using the following equation:(7)upt+1=upt+Vpt+1.The local best ofup at time t+1 is updated according to the following equation:(8)uplbestt+1=upt+1,fupt+1<fuplbestt,uplbestt,otherwise..The global best in membraneo at iteration t+1 is updated according to the following equation:(9)uogbestt+1=uplbestt+1,fuplbestt+1<fuogbestt,uogbestt,otherwise..The inertia weight is updated dynamically to enhance the global searching ability of the objects and to avoid prematurity. A linear increasing approach, given by (10), is used to update the inertia weight:(10)wt=wmin+wmax−wmin∗ttmax,where wmin and wmax represent the minimum and maximum of the inertia weight and tmax is the maximum number of iterations.(2) The Local Evolution Rules. A local search strategy based on the FER is adopted in local evolution rules for the objects. The approaches of updating the velocity and position of an object are modified. The local evolution of the objects is achieved only within a subsystem of membranes to help objects escape from local optima, and the local evolution rules only execute on objects contained in the membranes of the subsystem. The modified velocity is determined by using the following equation:(11)Vpt+1=χVpt+r3uplbestt−upt+r4upnbestt−upt,and the modified position is determined by using the following equation:(12)upt+1=upt+Vpt+1,where χ is a constriction coefficient used to prevent an object from evolving too far away from the search space and is given by χ=2/2−φmax−φmax2−4φmax and r3 and r4 are two random numbers uniformly distributed between 0,φmax/2. In the above, φmax is a positive constant with φmax=4.1 [42]. In (11), upnbestt represents the best neighbor of up in the neighborhood, where the neighborhood is a subset of objects in the current evolution process. The objects in a membrane of the subsystem are listed in a decreasing order of the FER values. The value of the FER for a given up and any other up′, for p′≠p and p′=1,2,…,m, is determined by using the following equation:(13)FERupt,up′t=αfuplbestt−fup′lbesttuplbestt−up′lbestt,where uplbestt−up′lbestt is the Euclidean distance between uplbestt and up′lbestt at the current iteration t. Apparently, up and up′ only exist in the same membrane o. In (13), α represents a control parameter given by α=D/fuoworstt−fuogbestt, where uoworstt represents the worst objects with the highest value of the fitness function in membrane o, uogbestt represents the best object in the same membrane o, and D is the size of the data space given by D=∑j=1Txjmax−xjmin2 with T=Kd. The best neighbor upnbestt of up has the greatest FER value among all neighbors in the neighborhood.


#### 4.2.2. The Communication Rules

The communication rules in the PSO-CP realize the exchange and sharing of the global best objects among elementary membranes 2 toq and nonelementary membrane 1 as well as between nonelementary membrane 1 and skin membrane 0. This communication only exists between children membranes and the parent membrane. In order to enhance the global searching ability of the objects, the PSO-CP has two types of communication rules, i.e., the communication rules in the elementary membranes and the communication rules in the nonelementary membranes.(1)
Ro′=uogbestt⟶upolbestt,in1, for o=2,3,…,qA copy of the global best objectuogbestt in elementary membrane o is evolved to be the local best object upolbestt and is sent to nonelementary membrane 1 at iteration t. Note that the global best object uogbestt still stays in elementary membrane o. Therefore, nonelementary membrane 1 only contains q−1 objects from the q−1 elementary membranes at iteration t. Nonelementary membrane 1 will select the best object among these local best objects from the elementary membranes as the global best object u1gbestt.(2)
R1′=upolbestt⟶urlbestt,ino+1, for o=2,3,…,q−1 and r=1,2,…,mA copy of the local best objectupolbestt in nonelementary membrane 1 is evolved to be the local best urlbestt of ur and is sent to elementary membrane o+1 at iteration t. The selection of ur is based on a random strategy in membrane o+1. Specially, R1′=upqlbestt⟶urlbestt,in2, a copy of the local best object upqlbestt is evolved to be the local best urlbestt of ur in elementary membrane 2, while the selection of ur is based on a random strategy. At the same time, membrane 1 will transport a copy of the global best object u1gbestt to the skin membrane 0 and evolve it to the local best object u0lbestt, i.e., R1′=u1gbestt⟶u0lbestt,in0. If the local best object u0lbestt at iteration t is better than the global best object u0gbestt+1 at iteration t−1 in the skin membrane 0, the local best object u0lbestt will become the global best object u0gbestt at iteration t. Thus, the skin membrane 0 always holds the global best object of the whole membrane system at iteration t and will output it to the environment at the end of the evolution and computation process. In addition, the local best object u0lbest0 from nonelementary membrane 1 will be placed into the skin membrane 0 as the best object u0gbest0 at the beginning of the process. Figure 3 graphically depicts the communication rules in the PSO-CP. The red arrows represent the directions of the communicated information. The exchange and transmission of global information is achieved by the execution of communication rules between nonelementary and elementary membranes.Figure 3
The communication rules in the PSO-CP.


### 4.3. Creation and Dissolution Rules for Membranes

Membrane rules form the evolution mechanism of membrane systems, which are different from the traditional evolution and communication rules of the objects. The PSO-CP uses two types of membrane rules: membrane creation and dissolution rules [50]. The membrane rules only change the elementary membranes, while the nonelementary and skin membranes always stay the same in the evolution and computation process.


#### 4.3.1. Membrane Creation Rules

The membrane creation rules are of the formuo⟶uo,uo1,…,uosn, where u∈O. The creation rules are executed when the stagnation condition is detected. The stagnation condition is when the global best in the elementary membranes cannot be further improved for limit iterations. When the membrane creation rules are executed, a subsystem of membrane o is created. This subsystem consists of sn membranes, each of which is independent of the others.When a new subsystem is created, all the objects in the current elementary membraneo are copied into each of the membranes in the subsystem. The local evolution rules for objects are adopted in membranes o1 to osn of the subsystem. After one evolution, each membrane will transport a copy of the global best object uoggbest, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 will then select the best object vogbest among the global best objects uoggbest in the membranes of the subsystem and the global best object uogbest in elementary membrane o and retain the best membrane containing the global best object to continue the following evolution and computation process.Figure4 shows an example of membrane creation. At iteration t, a new subsystem of elementary membrane 3 is created when the global best object cannot be further improved for limit iterations, and this subsystem consists of sn membranes. All the objects in membrane 3 are copied to the membranes of this subsystem. The local evolution rules for objects are used to evolve the objects in each membrane in the subsystem. At the same time, elementary membrane 3 continues to evolve. After one evolution, each membrane in the subsystem will transport a copy of the global best object u3ggbestt, for g=1,2,⋯,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. The membrane containing the global best object v3gbestt+1 will be kept and will be used to replace elementary membrane 3.Figure 4
An example of membrane creation.


#### 4.3.2. Membrane Dissolution Rules

During the evolution and computation process of the PSO-CP, the membranes will be dissolved through the membrane dissolution rules, but dissolution happens only on elementary membranes and the ones in their corresponding subsystems. The PSO-CP destroys a subsystem by the membrane dissolution rules when the best object in a subsystem or in the corresponding elementary membrane is found after one evolution. The membrane dissolution rules are of the formu⟶λ.Membrane dissolution happens in membraneog of the subsystem and the corresponding elementary membrane o, for g=1,2,…,sn and o=2,3,…,q. After one evolution, each membrane in the subsystem will transport a copy of the global best object uoggbest to nonelementary membrane 1. If the global best object vogbest is from membrane og in the subsystem and is better than the global best object uogbest of the corresponding elementary membrane o and other global best objects uog′gbest in the membranes of the subsystem, elementary membrane o and other membranes og′ g′≠g in the subsystem will be dissolved through the membrane dissolution rules. Membrane og in the subsystem will replace elementary membrane o and will continue to perform the subsequent evolutions and computations with the same evolution and communication rules in elementary membrane o. Otherwise, if the global best object vogbest is from the global best object uogbest in elementary membrane o, all the membranes o1 to osn in the subsystem will be dissolved.Figure5 shows an example of membrane dissolution. At iteration t, the subsystem of elementary membrane 3 is generated, which contains sn membranes. After one evolution, each membrane will transport a copy of the global best object u3ggbestt+1, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. Assume that the global best object v3gbestt+1 comes from membrane 1 in the subsystem. Therefore, membrane 1 in the subsystem replaces elementary membrane 3 and elementary membrane 3 and all other membranes 3g′ g′≠1 in the subsystem are dissolved. After replacing elementary membrane 3, membrane 1 in the subsystem is the new elementary membrane 3 which will continue to perform the subsequent evolutions and computations.Figure 5
An example of membrane dissolution.


### 4.4. Halting and Output

The PSO-CP is a parallel computing system, all elementary membranes and their corresponding subsystems work in parallel, and each membrane including elementary membranes and membranes in their subsystems are parallel computing units. The extended clustering membrane system starts running from the initial membrane structure withq−1 elementary membranes containing the initial objects. Each object represents a set of cluster centers. These objects will be evolved based on the basic evolution rules. The elementary membranes and nonelementary membranes interact through the communication rules, and the global best object in nonelementary membrane 1 will be transported to the skin membrane 0. A subsystem will be generated based on the membrane creation rules when an elementary membrane is trapped into a local optimum, and the local evolution rules are used to evolve the objects in membranes of the subsystem. After one evolution, the membrane with the best object among the membranes in the subsystem and the corresponding elementary membrane will be kept and others will be dissolved based on the membrane dissolution rules. The evolution and communication rules for objects and the creation and dissolution rules for membranes will execute iteratively during the evolution and computation process. These computing tasks are performed iteratively. The extended clustering membrane system will continue to execute until the halting condition is satisfied, which is the maximum number of iterations has been reached. When the system halts, the last global best object stored in skin membrane 0 is output to the environment and the set of cluster centers of the clustering problem is regarded as the final computed result.


### 4.5. Complexity Analysis

In this subsection, the complexity of the PSO-CP is analyzed. As defined earlier,N is the number of data points in the datasets, m represents the number of objects in an elementary membrane, q represents the number of elementary membranes in the system, and tmax represents the maximum number of iterations. In the initialization process, the local best and global best in each of the elementary membranes 2 to q need to be found in maximal parallel. The complexity of initialization is then Om. The basic evolution rules in the elementary membranes are executed in parallel. The time needed by executing a basic evolution rule for an object is N. Hence, the time needed by one evolution in an elementary membrane is mN. The communication rules between elementary membranes and nonelementary membranes are also executed in parallel, and the time needed by executing a communication rule is 2. The time needed by a membrane in a subsystem is mm+N. Thus, the time needed by the membranes in a subsystem and the corresponding elementary membrane is mm+N. As a result, the time needed by each iteration is mm+N+2. The total time needed by the PSO-CP is m+tmaxmm+N+2. Because m≪N, the complexity of the PSO-CP can be simplified to OtmaxmN.


## 4.1. Initialization

### 4.1.1. The Initial Membrane Structure

The membrane structure of PSO-CP is built dynamically through membrane creation and dissolution rules during the evolution and computation process. Therefore, the number of membranes will change. Specifically, PSO-CP starts with an initial membrane structure and then the membrane evolution mechanism will control the structure and the number of membranes. The initial membrane structure of a PSO-CP is graphically depicted in Figure2.Figure 2
The initial structure of a PSO-CP.In Figure2, the PSO-CP with a three-layer nesting structure contains a skin membrane 0, a nonelementary membrane 1, and elementary membranes 2 to q. These membranes are labelled from 0 to q. The nonelementary membrane, also called the comparison membrane, is labelled 1, whose role is to find the best object in the elementary membranes during the current evolution process and output the best object to the outmost membrane. Membrane 1 is the parent of the elementary membranes 2 to q, and elementary membranes 2 to q are the children of nonelementary membrane 1. The outmost membrane, labelled 0, is the skin membrane, whose role is to store the best object in the system during the current evolution and computation process.


### 4.1.2. Object Representation

In the PSO-CP, an object is a set of clustering centers representing a feasible solution. Therefore, the objects represent the sets of clustering results. Each objectu, u∈O, is designed as a composite K×d dimensional vector [47] of the following form:(4)u=z1,z2,…,zK=z11,z12,…,z1d,…,zk1,zk2,…,zkd,…,zK1,zK2,…,zKd,where zk=zk1,zk2,…,zkd corresponds to the cluster center of cluster k and d, as mentioned earlier, represents the dimension of the data points. Hence, an object u, with u=z1,z2,…,zK, represents a set of cluster centers. As usual, each membrane has at least one object. To ensure the same computation complexity of each elementary membrane, all elementary membranes have the same number of objects, denoted by m. The number of objects in the whole P system is represented by M, i.e., M=m×q.


### 4.1.3. Initial Objects

As mentioned above, each elementary membrane in the PSO-CP has the same number of objects. When the evolution and computation process starts, each elementary membrane also has the same number of initial objects. An objectu represents a set of cluster centers. Dimension j of object up represented by upj is generated randomly between xjmin and xjmax, where xjmin and xjmax are the minimum and maximum values of dimension j of the search space. Therefore, upj∈xjmin,xjmax, for p=1,2,…,m and j=1,2,…,d. The values of xjmin and xjmax are determined by using the following equation:(5)xjmin=minxiji=1,2,…,N,xjmax=maxxiji=1,2,…,N,forj=1,2,…,d.After initialization, the fitness value of each object is calculated using (1). In membrane o, for o=2,3,…,q, the initial best with the lowest fitness value for up, denoted by uplbest0 and called the local best, is determined for p=1,2,…,m. The initial best with the lowest fitness value in history among all objects in membrane o, denoted by uogbest0 and called the global best, is also determined. The local best and the global best refer to the positions of the objects. The object that found the global best is the global best object.


## 4.1.1. The Initial Membrane Structure

The membrane structure of PSO-CP is built dynamically through membrane creation and dissolution rules during the evolution and computation process. Therefore, the number of membranes will change. Specifically, PSO-CP starts with an initial membrane structure and then the membrane evolution mechanism will control the structure and the number of membranes. The initial membrane structure of a PSO-CP is graphically depicted in Figure2.Figure 2
The initial structure of a PSO-CP.In Figure2, the PSO-CP with a three-layer nesting structure contains a skin membrane 0, a nonelementary membrane 1, and elementary membranes 2 to q. These membranes are labelled from 0 to q. The nonelementary membrane, also called the comparison membrane, is labelled 1, whose role is to find the best object in the elementary membranes during the current evolution process and output the best object to the outmost membrane. Membrane 1 is the parent of the elementary membranes 2 to q, and elementary membranes 2 to q are the children of nonelementary membrane 1. The outmost membrane, labelled 0, is the skin membrane, whose role is to store the best object in the system during the current evolution and computation process.


## 4.1.2. Object Representation

In the PSO-CP, an object is a set of clustering centers representing a feasible solution. Therefore, the objects represent the sets of clustering results. Each objectu, u∈O, is designed as a composite K×d dimensional vector [47] of the following form:(4)u=z1,z2,…,zK=z11,z12,…,z1d,…,zk1,zk2,…,zkd,…,zK1,zK2,…,zKd,where zk=zk1,zk2,…,zkd corresponds to the cluster center of cluster k and d, as mentioned earlier, represents the dimension of the data points. Hence, an object u, with u=z1,z2,…,zK, represents a set of cluster centers. As usual, each membrane has at least one object. To ensure the same computation complexity of each elementary membrane, all elementary membranes have the same number of objects, denoted by m. The number of objects in the whole P system is represented by M, i.e., M=m×q.


## 4.1.3. Initial Objects

As mentioned above, each elementary membrane in the PSO-CP has the same number of objects. When the evolution and computation process starts, each elementary membrane also has the same number of initial objects. An objectu represents a set of cluster centers. Dimension j of object up represented by upj is generated randomly between xjmin and xjmax, where xjmin and xjmax are the minimum and maximum values of dimension j of the search space. Therefore, upj∈xjmin,xjmax, for p=1,2,…,m and j=1,2,…,d. The values of xjmin and xjmax are determined by using the following equation:(5)xjmin=minxiji=1,2,…,N,xjmax=maxxiji=1,2,…,N,forj=1,2,…,d.After initialization, the fitness value of each object is calculated using (1). In membrane o, for o=2,3,…,q, the initial best with the lowest fitness value for up, denoted by uplbest0 and called the local best, is determined for p=1,2,…,m. The initial best with the lowest fitness value in history among all objects in membrane o, denoted by uogbest0 and called the global best, is also determined. The local best and the global best refer to the positions of the objects. The object that found the global best is the global best object.


## 4.2. The Evolution and Communication Rules for the Objects

### 4.2.1. Evolution Rules for the Objects

The PSO-CP has two types of evolution rules: the basic evolution and the local evolution rules.(1) The Basic Evolution Rules. In this work, the standard PSO [48] is used to search for the optimal solutions in the elementary membranes 2 to q. The evolution of objects is achieved only within elementary membranes, and the basic evolution rules only execute on objects contained in elementary membranes 2 to q. Let upt and Vpt represent the position and velocity of up at time t in elementary membrane o, for o=2,3,…,q. The velocity of up at time t+1 is determined by using the following equation:(6)Vpt+1=wVpt+c1r1uplbestt−upt+c2r2uogbestt−upt,where w is the inertia weight, c1 and c2 represent the local and global learning factors, which control the influence of the local best and the global best object, t is the time or iteration counter, and r1 and r2 are two uniform random numbers [49]. The local best of up is denoted by uplbestt and the global best in the elementary membrane o is denoted by uogbestt at iteration t. For notational convenience, the global best object is also denoted by uogbestt at iteration t.The position ofup at time t+1 is determined by using the following equation:(7)upt+1=upt+Vpt+1.The local best ofup at time t+1 is updated according to the following equation:(8)uplbestt+1=upt+1,fupt+1<fuplbestt,uplbestt,otherwise..The global best in membraneo at iteration t+1 is updated according to the following equation:(9)uogbestt+1=uplbestt+1,fuplbestt+1<fuogbestt,uogbestt,otherwise..The inertia weight is updated dynamically to enhance the global searching ability of the objects and to avoid prematurity. A linear increasing approach, given by (10), is used to update the inertia weight:(10)wt=wmin+wmax−wmin∗ttmax,where wmin and wmax represent the minimum and maximum of the inertia weight and tmax is the maximum number of iterations.(2) The Local Evolution Rules. A local search strategy based on the FER is adopted in local evolution rules for the objects. The approaches of updating the velocity and position of an object are modified. The local evolution of the objects is achieved only within a subsystem of membranes to help objects escape from local optima, and the local evolution rules only execute on objects contained in the membranes of the subsystem. The modified velocity is determined by using the following equation:(11)Vpt+1=χVpt+r3uplbestt−upt+r4upnbestt−upt,and the modified position is determined by using the following equation:(12)upt+1=upt+Vpt+1,where χ is a constriction coefficient used to prevent an object from evolving too far away from the search space and is given by χ=2/2−φmax−φmax2−4φmax and r3 and r4 are two random numbers uniformly distributed between 0,φmax/2. In the above, φmax is a positive constant with φmax=4.1 [42]. In (11), upnbestt represents the best neighbor of up in the neighborhood, where the neighborhood is a subset of objects in the current evolution process. The objects in a membrane of the subsystem are listed in a decreasing order of the FER values. The value of the FER for a given up and any other up′, for p′≠p and p′=1,2,…,m, is determined by using the following equation:(13)FERupt,up′t=αfuplbestt−fup′lbesttuplbestt−up′lbestt,where uplbestt−up′lbestt is the Euclidean distance between uplbestt and up′lbestt at the current iteration t. Apparently, up and up′ only exist in the same membrane o. In (13), α represents a control parameter given by α=D/fuoworstt−fuogbestt, where uoworstt represents the worst objects with the highest value of the fitness function in membrane o, uogbestt represents the best object in the same membrane o, and D is the size of the data space given by D=∑j=1Txjmax−xjmin2 with T=Kd. The best neighbor upnbestt of up has the greatest FER value among all neighbors in the neighborhood.


### 4.2.2. The Communication Rules

The communication rules in the PSO-CP realize the exchange and sharing of the global best objects among elementary membranes 2 toq and nonelementary membrane 1 as well as between nonelementary membrane 1 and skin membrane 0. This communication only exists between children membranes and the parent membrane. In order to enhance the global searching ability of the objects, the PSO-CP has two types of communication rules, i.e., the communication rules in the elementary membranes and the communication rules in the nonelementary membranes.(1)
Ro′=uogbestt⟶upolbestt,in1, for o=2,3,…,qA copy of the global best objectuogbestt in elementary membrane o is evolved to be the local best object upolbestt and is sent to nonelementary membrane 1 at iteration t. Note that the global best object uogbestt still stays in elementary membrane o. Therefore, nonelementary membrane 1 only contains q−1 objects from the q−1 elementary membranes at iteration t. Nonelementary membrane 1 will select the best object among these local best objects from the elementary membranes as the global best object u1gbestt.(2)
R1′=upolbestt⟶urlbestt,ino+1, for o=2,3,…,q−1 and r=1,2,…,mA copy of the local best objectupolbestt in nonelementary membrane 1 is evolved to be the local best urlbestt of ur and is sent to elementary membrane o+1 at iteration t. The selection of ur is based on a random strategy in membrane o+1. Specially, R1′=upqlbestt⟶urlbestt,in2, a copy of the local best object upqlbestt is evolved to be the local best urlbestt of ur in elementary membrane 2, while the selection of ur is based on a random strategy. At the same time, membrane 1 will transport a copy of the global best object u1gbestt to the skin membrane 0 and evolve it to the local best object u0lbestt, i.e., R1′=u1gbestt⟶u0lbestt,in0. If the local best object u0lbestt at iteration t is better than the global best object u0gbestt+1 at iteration t−1 in the skin membrane 0, the local best object u0lbestt will become the global best object u0gbestt at iteration t. Thus, the skin membrane 0 always holds the global best object of the whole membrane system at iteration t and will output it to the environment at the end of the evolution and computation process. In addition, the local best object u0lbest0 from nonelementary membrane 1 will be placed into the skin membrane 0 as the best object u0gbest0 at the beginning of the process. Figure 3 graphically depicts the communication rules in the PSO-CP. The red arrows represent the directions of the communicated information. The exchange and transmission of global information is achieved by the execution of communication rules between nonelementary and elementary membranes.Figure 3
The communication rules in the PSO-CP.


## 4.2.1. Evolution Rules for the Objects

The PSO-CP has two types of evolution rules: the basic evolution and the local evolution rules.(1) The Basic Evolution Rules. In this work, the standard PSO [48] is used to search for the optimal solutions in the elementary membranes 2 to q. The evolution of objects is achieved only within elementary membranes, and the basic evolution rules only execute on objects contained in elementary membranes 2 to q. Let upt and Vpt represent the position and velocity of up at time t in elementary membrane o, for o=2,3,…,q. The velocity of up at time t+1 is determined by using the following equation:(6)Vpt+1=wVpt+c1r1uplbestt−upt+c2r2uogbestt−upt,where w is the inertia weight, c1 and c2 represent the local and global learning factors, which control the influence of the local best and the global best object, t is the time or iteration counter, and r1 and r2 are two uniform random numbers [49]. The local best of up is denoted by uplbestt and the global best in the elementary membrane o is denoted by uogbestt at iteration t. For notational convenience, the global best object is also denoted by uogbestt at iteration t.The position ofup at time t+1 is determined by using the following equation:(7)upt+1=upt+Vpt+1.The local best ofup at time t+1 is updated according to the following equation:(8)uplbestt+1=upt+1,fupt+1<fuplbestt,uplbestt,otherwise..The global best in membraneo at iteration t+1 is updated according to the following equation:(9)uogbestt+1=uplbestt+1,fuplbestt+1<fuogbestt,uogbestt,otherwise..The inertia weight is updated dynamically to enhance the global searching ability of the objects and to avoid prematurity. A linear increasing approach, given by (10), is used to update the inertia weight:(10)wt=wmin+wmax−wmin∗ttmax,where wmin and wmax represent the minimum and maximum of the inertia weight and tmax is the maximum number of iterations.(2) The Local Evolution Rules. A local search strategy based on the FER is adopted in local evolution rules for the objects. The approaches of updating the velocity and position of an object are modified. The local evolution of the objects is achieved only within a subsystem of membranes to help objects escape from local optima, and the local evolution rules only execute on objects contained in the membranes of the subsystem. The modified velocity is determined by using the following equation:(11)Vpt+1=χVpt+r3uplbestt−upt+r4upnbestt−upt,and the modified position is determined by using the following equation:(12)upt+1=upt+Vpt+1,where χ is a constriction coefficient used to prevent an object from evolving too far away from the search space and is given by χ=2/2−φmax−φmax2−4φmax and r3 and r4 are two random numbers uniformly distributed between 0,φmax/2. In the above, φmax is a positive constant with φmax=4.1 [42]. In (11), upnbestt represents the best neighbor of up in the neighborhood, where the neighborhood is a subset of objects in the current evolution process. The objects in a membrane of the subsystem are listed in a decreasing order of the FER values. The value of the FER for a given up and any other up′, for p′≠p and p′=1,2,…,m, is determined by using the following equation:(13)FERupt,up′t=αfuplbestt−fup′lbesttuplbestt−up′lbestt,where uplbestt−up′lbestt is the Euclidean distance between uplbestt and up′lbestt at the current iteration t. Apparently, up and up′ only exist in the same membrane o. In (13), α represents a control parameter given by α=D/fuoworstt−fuogbestt, where uoworstt represents the worst objects with the highest value of the fitness function in membrane o, uogbestt represents the best object in the same membrane o, and D is the size of the data space given by D=∑j=1Txjmax−xjmin2 with T=Kd. The best neighbor upnbestt of up has the greatest FER value among all neighbors in the neighborhood.


## 4.2.2. The Communication Rules

The communication rules in the PSO-CP realize the exchange and sharing of the global best objects among elementary membranes 2 toq and nonelementary membrane 1 as well as between nonelementary membrane 1 and skin membrane 0. This communication only exists between children membranes and the parent membrane. In order to enhance the global searching ability of the objects, the PSO-CP has two types of communication rules, i.e., the communication rules in the elementary membranes and the communication rules in the nonelementary membranes.(1)
Ro′=uogbestt⟶upolbestt,in1, for o=2,3,…,qA copy of the global best objectuogbestt in elementary membrane o is evolved to be the local best object upolbestt and is sent to nonelementary membrane 1 at iteration t. Note that the global best object uogbestt still stays in elementary membrane o. Therefore, nonelementary membrane 1 only contains q−1 objects from the q−1 elementary membranes at iteration t. Nonelementary membrane 1 will select the best object among these local best objects from the elementary membranes as the global best object u1gbestt.(2)
R1′=upolbestt⟶urlbestt,ino+1, for o=2,3,…,q−1 and r=1,2,…,mA copy of the local best objectupolbestt in nonelementary membrane 1 is evolved to be the local best urlbestt of ur and is sent to elementary membrane o+1 at iteration t. The selection of ur is based on a random strategy in membrane o+1. Specially, R1′=upqlbestt⟶urlbestt,in2, a copy of the local best object upqlbestt is evolved to be the local best urlbestt of ur in elementary membrane 2, while the selection of ur is based on a random strategy. At the same time, membrane 1 will transport a copy of the global best object u1gbestt to the skin membrane 0 and evolve it to the local best object u0lbestt, i.e., R1′=u1gbestt⟶u0lbestt,in0. If the local best object u0lbestt at iteration t is better than the global best object u0gbestt+1 at iteration t−1 in the skin membrane 0, the local best object u0lbestt will become the global best object u0gbestt at iteration t. Thus, the skin membrane 0 always holds the global best object of the whole membrane system at iteration t and will output it to the environment at the end of the evolution and computation process. In addition, the local best object u0lbest0 from nonelementary membrane 1 will be placed into the skin membrane 0 as the best object u0gbest0 at the beginning of the process. Figure 3 graphically depicts the communication rules in the PSO-CP. The red arrows represent the directions of the communicated information. The exchange and transmission of global information is achieved by the execution of communication rules between nonelementary and elementary membranes.Figure 3
The communication rules in the PSO-CP.


## 4.3. Creation and Dissolution Rules for Membranes

Membrane rules form the evolution mechanism of membrane systems, which are different from the traditional evolution and communication rules of the objects. The PSO-CP uses two types of membrane rules: membrane creation and dissolution rules [50]. The membrane rules only change the elementary membranes, while the nonelementary and skin membranes always stay the same in the evolution and computation process.


### 4.3.1. Membrane Creation Rules

The membrane creation rules are of the formuo⟶uo,uo1,…,uosn, where u∈O. The creation rules are executed when the stagnation condition is detected. The stagnation condition is when the global best in the elementary membranes cannot be further improved for limit iterations. When the membrane creation rules are executed, a subsystem of membrane o is created. This subsystem consists of sn membranes, each of which is independent of the others.When a new subsystem is created, all the objects in the current elementary membraneo are copied into each of the membranes in the subsystem. The local evolution rules for objects are adopted in membranes o1 to osn of the subsystem. After one evolution, each membrane will transport a copy of the global best object uoggbest, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 will then select the best object vogbest among the global best objects uoggbest in the membranes of the subsystem and the global best object uogbest in elementary membrane o and retain the best membrane containing the global best object to continue the following evolution and computation process.Figure4 shows an example of membrane creation. At iteration t, a new subsystem of elementary membrane 3 is created when the global best object cannot be further improved for limit iterations, and this subsystem consists of sn membranes. All the objects in membrane 3 are copied to the membranes of this subsystem. The local evolution rules for objects are used to evolve the objects in each membrane in the subsystem. At the same time, elementary membrane 3 continues to evolve. After one evolution, each membrane in the subsystem will transport a copy of the global best object u3ggbestt, for g=1,2,⋯,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. The membrane containing the global best object v3gbestt+1 will be kept and will be used to replace elementary membrane 3.Figure 4
An example of membrane creation.


### 4.3.2. Membrane Dissolution Rules

During the evolution and computation process of the PSO-CP, the membranes will be dissolved through the membrane dissolution rules, but dissolution happens only on elementary membranes and the ones in their corresponding subsystems. The PSO-CP destroys a subsystem by the membrane dissolution rules when the best object in a subsystem or in the corresponding elementary membrane is found after one evolution. The membrane dissolution rules are of the formu⟶λ.Membrane dissolution happens in membraneog of the subsystem and the corresponding elementary membrane o, for g=1,2,…,sn and o=2,3,…,q. After one evolution, each membrane in the subsystem will transport a copy of the global best object uoggbest to nonelementary membrane 1. If the global best object vogbest is from membrane og in the subsystem and is better than the global best object uogbest of the corresponding elementary membrane o and other global best objects uog′gbest in the membranes of the subsystem, elementary membrane o and other membranes og′ g′≠g in the subsystem will be dissolved through the membrane dissolution rules. Membrane og in the subsystem will replace elementary membrane o and will continue to perform the subsequent evolutions and computations with the same evolution and communication rules in elementary membrane o. Otherwise, if the global best object vogbest is from the global best object uogbest in elementary membrane o, all the membranes o1 to osn in the subsystem will be dissolved.Figure5 shows an example of membrane dissolution. At iteration t, the subsystem of elementary membrane 3 is generated, which contains sn membranes. After one evolution, each membrane will transport a copy of the global best object u3ggbestt+1, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. Assume that the global best object v3gbestt+1 comes from membrane 1 in the subsystem. Therefore, membrane 1 in the subsystem replaces elementary membrane 3 and elementary membrane 3 and all other membranes 3g′ g′≠1 in the subsystem are dissolved. After replacing elementary membrane 3, membrane 1 in the subsystem is the new elementary membrane 3 which will continue to perform the subsequent evolutions and computations.Figure 5
An example of membrane dissolution.


## 4.3.1. Membrane Creation Rules

The membrane creation rules are of the formuo⟶uo,uo1,…,uosn, where u∈O. The creation rules are executed when the stagnation condition is detected. The stagnation condition is when the global best in the elementary membranes cannot be further improved for limit iterations. When the membrane creation rules are executed, a subsystem of membrane o is created. This subsystem consists of sn membranes, each of which is independent of the others.When a new subsystem is created, all the objects in the current elementary membraneo are copied into each of the membranes in the subsystem. The local evolution rules for objects are adopted in membranes o1 to osn of the subsystem. After one evolution, each membrane will transport a copy of the global best object uoggbest, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 will then select the best object vogbest among the global best objects uoggbest in the membranes of the subsystem and the global best object uogbest in elementary membrane o and retain the best membrane containing the global best object to continue the following evolution and computation process.Figure4 shows an example of membrane creation. At iteration t, a new subsystem of elementary membrane 3 is created when the global best object cannot be further improved for limit iterations, and this subsystem consists of sn membranes. All the objects in membrane 3 are copied to the membranes of this subsystem. The local evolution rules for objects are used to evolve the objects in each membrane in the subsystem. At the same time, elementary membrane 3 continues to evolve. After one evolution, each membrane in the subsystem will transport a copy of the global best object u3ggbestt, for g=1,2,⋯,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. The membrane containing the global best object v3gbestt+1 will be kept and will be used to replace elementary membrane 3.Figure 4
An example of membrane creation.


## 4.3.2. Membrane Dissolution Rules

During the evolution and computation process of the PSO-CP, the membranes will be dissolved through the membrane dissolution rules, but dissolution happens only on elementary membranes and the ones in their corresponding subsystems. The PSO-CP destroys a subsystem by the membrane dissolution rules when the best object in a subsystem or in the corresponding elementary membrane is found after one evolution. The membrane dissolution rules are of the formu⟶λ.Membrane dissolution happens in membraneog of the subsystem and the corresponding elementary membrane o, for g=1,2,…,sn and o=2,3,…,q. After one evolution, each membrane in the subsystem will transport a copy of the global best object uoggbest to nonelementary membrane 1. If the global best object vogbest is from membrane og in the subsystem and is better than the global best object uogbest of the corresponding elementary membrane o and other global best objects uog′gbest in the membranes of the subsystem, elementary membrane o and other membranes og′ g′≠g in the subsystem will be dissolved through the membrane dissolution rules. Membrane og in the subsystem will replace elementary membrane o and will continue to perform the subsequent evolutions and computations with the same evolution and communication rules in elementary membrane o. Otherwise, if the global best object vogbest is from the global best object uogbest in elementary membrane o, all the membranes o1 to osn in the subsystem will be dissolved.Figure5 shows an example of membrane dissolution. At iteration t, the subsystem of elementary membrane 3 is generated, which contains sn membranes. After one evolution, each membrane will transport a copy of the global best object u3ggbestt+1, for g=1,2,…,sn, to nonelementary membrane 1. Nonelementary membrane 1 selects the global best object v3gbestt+1 among the global best objects u3ggbestt+1 in the membranes of the subsystem and the global best object u3gbestt+1 in elementary membrane 3. Assume that the global best object v3gbestt+1 comes from membrane 1 in the subsystem. Therefore, membrane 1 in the subsystem replaces elementary membrane 3 and elementary membrane 3 and all other membranes 3g′ g′≠1 in the subsystem are dissolved. After replacing elementary membrane 3, membrane 1 in the subsystem is the new elementary membrane 3 which will continue to perform the subsequent evolutions and computations.Figure 5
An example of membrane dissolution.


## 4.4. Halting and Output

The PSO-CP is a parallel computing system, all elementary membranes and their corresponding subsystems work in parallel, and each membrane including elementary membranes and membranes in their subsystems are parallel computing units. The extended clustering membrane system starts running from the initial membrane structure withq−1 elementary membranes containing the initial objects. Each object represents a set of cluster centers. These objects will be evolved based on the basic evolution rules. The elementary membranes and nonelementary membranes interact through the communication rules, and the global best object in nonelementary membrane 1 will be transported to the skin membrane 0. A subsystem will be generated based on the membrane creation rules when an elementary membrane is trapped into a local optimum, and the local evolution rules are used to evolve the objects in membranes of the subsystem. After one evolution, the membrane with the best object among the membranes in the subsystem and the corresponding elementary membrane will be kept and others will be dissolved based on the membrane dissolution rules. The evolution and communication rules for objects and the creation and dissolution rules for membranes will execute iteratively during the evolution and computation process. These computing tasks are performed iteratively. The extended clustering membrane system will continue to execute until the halting condition is satisfied, which is the maximum number of iterations has been reached. When the system halts, the last global best object stored in skin membrane 0 is output to the environment and the set of cluster centers of the clustering problem is regarded as the final computed result.


## 4.5. Complexity Analysis

In this subsection, the complexity of the PSO-CP is analyzed. As defined earlier,N is the number of data points in the datasets, m represents the number of objects in an elementary membrane, q represents the number of elementary membranes in the system, and tmax represents the maximum number of iterations. In the initialization process, the local best and global best in each of the elementary membranes 2 to q need to be found in maximal parallel. The complexity of initialization is then Om. The basic evolution rules in the elementary membranes are executed in parallel. The time needed by executing a basic evolution rule for an object is N. Hence, the time needed by one evolution in an elementary membrane is mN. The communication rules between elementary membranes and nonelementary membranes are also executed in parallel, and the time needed by executing a communication rule is 2. The time needed by a membrane in a subsystem is mm+N. Thus, the time needed by the membranes in a subsystem and the corresponding elementary membrane is mm+N. As a result, the time needed by each iteration is mm+N+2. The total time needed by the PSO-CP is m+tmaxmm+N+2. Because m≪N, the complexity of the PSO-CP can be simplified to OtmaxmN.


## 5. Experimental Results and Analysis

Computational experiments are conducted to evaluate the effectiveness of the PSO-CP. The datasets used in this study are introduced first. Four artificial datasets [51] are then used to tune the parameters in the PSO-CP. The clustering performance of the PSO-CP is compared with those of currently existing approaches using ten test datasets [52]. All clustering methods, including the PSO-CP, are implemented using MATLAB 2016b, and all the experiments are conducted on a Dell desktop computer with an Intel 4.00 GHz i7-8550U processor and 8 GB of RAM in the Windows 10 environment.


### 5.1. Datasets

Four artificial datasets and ten test datasets are used in the experiments. The four artificial datasets are used to tune the parameters of the PSO-CP, and the ten test datasets are used to test the clustering performance of the PSO-CP as compared with those of five other clustering approaches. The ten test datasets including three artificial datasets and seven real-life datasets have been used by researchers as benchmarks to test their clustering approaches. These datasets are briefly described below.The seven artificial datasets,Data_5_2, Size_5, Square4, LineBlobs, Data_4_3, Data_9_2, and Square1, are manually generated and have been used in the existing literature. The seven real-life datasets, Iris, Newthyroid, Seeds, Yeast, Glass, Wine, and Lung Cancer, are from the UCI Machine Learning Repository. More details about these datasets are presented in Tables 1 and 2.Table 1
Properties of the artificial datasets.
Datasets
Data
Feature
Class
Data_5_2
250
2
5
Size_5
1000
2
4
Square4
1000
2
4
LineBlobs
266
3
4
Data_4_3
400
3
4
Data_9_2
900
2
9
Square1
1000
2
4Table 2
Properties of the real-life datasets.
Datasets
Data
Feature
Class
Iris
150
4
3
Newthyroid
215
5
3
Seeds
210
7
3
Yeast
1484
8
10
Glass
214
9
6
Wine
178
13
3
Lung Cancer
32
56
3TheLung Cancer dataset is high dimensional. It contains 32 data points, has 56 independent features, and describes three types of lung cancers. The Yeast dataset consists of 1484 data points and has 8 features. The Iris and Glass datasets are not linearly separable in the Euclidean space. These datasets with different characteristics in shape, size, compactness, and symmetry are used to evaluate the performance of the PSO-CP quantitatively.


### 5.2. Parameter Settings

The number of membranes in the subsystems and the number of elementary membranes play important roles in the performance of the PSO-CP. The values of these parameters have critical influences on the performance of the PSO-CP in solving clustering problems. This section focuses on checking the influences of two parameters, i.e., the number of elementary membranesq−1 and the number of membranes sn in the subsystems, with four artificial datasets.


#### 5.2.1. Number of Elementary Membranes

In order to evaluate the effects of the number of elementary membranes on clustering performance, the PSO-CP with two different degrees, i.e., 2 and 5, are used to find the optimal clustering centers for these datasets, using the fitness function to measure clustering quality [34]. The PSO-CP with each degree ran 30 times on each dataset and the mean (Mean) and standard deviation (S.D.) of the fitness values are reported. The S.D. shows the robustness and stability of the clustering technique.Parameters of the PSO-CP not tested in this experiment are kept at the same values for the fairness in the comparisons. In the PSO-CP, the number of objects may affect the quality of the clustering results. In order to avoid the influence of the number of objects, the number of objects in the system is set to the same value, i.e.,M=100. The maximum number of iterations is set to tmax=100, and the values of the learning factors in the basic and local evolution rules are set to c1=c2=2. The number of membranes in the subsystem is set to sn=6. The values of the lower and upper limits of the inertia weight are set to wmin=0.4 and wmax=1.2, respectively. For the detection of the stagnation condition of an elementary membrane, the number of iterations is set to limit=2. The values of Mean and S.D. of the fitness function obtained by the PSO-CP with two degrees are reported in Table 3.Table 3
Performance of the PSO-CP with different degrees measured by the values of Mean and S.D. of the fitness function.
Datasets
q
=
3
q
=
6
Mean
S.D.
Mean
S.D.
Data_5_2
326.7537
0.5323
326.5707
0.1594
Size_5
2499.3796
15.1835
2499.2712
14.7658
Square4
2367.7321
0.2262
2367.7097
0.2652
LineBlobs
20.6297
0.0018
20.6294
0.0016Table3 gives the results of the PSO-CP with different degrees on the four artificial datasets. The best values of Mean and S.D. for each dataset are highlighted. The results show that the PSO-CP obtained smaller Mean and smaller S.D. when q−1=5 elementary membranes are used. These results also show the PSO-CP with q−1=5 has better robustness. Figure 6 gives more details about the clustering performance of the PSO-CP on two datasets, i.e., Data_5_2 and Size_5. The clustering performance of the PSO-CP may remarkably improve with the increase in the number of elementary membranes.Figure 6
Boxplots of the values of the fitness function for 30 runs by the PSO-CP with different degrees: (a)Data_5_2 and (b) Size_5.
(a)
(b)


#### 5.2.2. Number of Membranes in the Subsystem

The number of membranes in the subsystem also has an important influence on the performance of the PSO-CP. In order to tune the number of membranes, the clustering performances of the PSO-CP withsn=6, 10, and 14 are examined [12]. The parameters of the PSO-CP which are not tested in this experiment are kept at the same values. The values of Mean and S.D. of the fitness function are presented in Table 4.Table 4
Performance of the PSO-CP with different number of membranes in the subsystems measured by the values of Mean and S.D. of the fitness function.
Datasets
s
n
=
6
s
n
=
10
s
n
=
14
Mean
S.D.
Mean
S.D.
Mean
S.D.
Data_5_2
326.5707
0.1594
326.5702
0.1210
326.7454
0.4251
Size_5
2499.2712
14.7658
2496.0993
11.2346
2497.4146
11.9762
Square4
2367.7097
0.2652
2367.6292
0.1411
2367.8010
0.2982
LineBlobs
20.6294
0.0016
16.7426
0.0362
16.7937
0.0391The PSO-CP with each different number of membranes in the subsystem ran 30 times on each dataset. The Mean and S.D. of the values of the fitness function for each number of membranes in the subsystem on each dataset are presented in Table4. The PSO-CP shows best performance on these datasets when sn=10. Figure 7 gives the boxplots of the values of the fitness function for each number of membranes in the subsystem for two datasets Data_5_2 and Size_5. Considering results for all four datasets, the PSO-CP with sn=10 has the best overall performance.Figure 7
Boxplots of the values of the fitness function for 30 runs of the PSO-CP with different number of membranes in the subsystem: (a)Data_5_2 and (b) Size_5.
(a)
(b)


### 5.3. Comparison with Other Clustering Approaches

To evaluate the effectiveness of the PSO-CP, its performance is compared with those of the standard particle swarm optimization (PSO) [49], fitness-distance ratio-particle swarm optimization (FDR-PSO) [53], fitness-Euclidean ratio-particle swarm optimization (FER-PSO) [42], starling particle swarm optimization (SPSO) [12], and environment particle swarm optimization (EPSO) [13] on the ten test datasets. Although there are many other advanced PSO clustering approaches, the ones used for comparison are the major references for the development of, and are more relevant to, the PSO-CP. The neighbor of the particle with the best FDR or FER value is selected in the FDR-PSO and FER-PSO approaches to replace the local best for velocity updating. A mechanism is used to lead the search out of a local optimum when stagnation occurs in the SPSO approach, and the implementation of the environment factor in the EPSO approach is similar to the active membranes in this study.Table5 reports the parameter values of all the comparative clustering approaches used in the experiments. The information of neighbors is used to guide the search direction of the particle, and the number of neighbors has important influence on the performance of the SPSO approach. The SPSO approach copies the current population to multipopulations when the cumulative number of iterations reaches a previously set threshold, called stagnant limit meaning that the particle in the population is trapped into a local optimum. The number of subpopulations is a decisive factor of the convergent rate in the approach. This operation of population is similar to the creation and dissolution of membranes in the PSO-CP. The velocity control of FER-PSO is an adjustable parameter to balance the previous velocity and the current velocity of the particle, and the learning factor controls the influence of the environmental factor in EPSO. The values of all these adjustable parameters in these approaches are the best values reported in the respective publications.Table 5
Parameter settings of the comparative clustering approaches used in the experiments.
Parameters
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Population (M)
100
100
100
100
100
100
t
max
100
100
100
100
100
100
c
1, c2
2, 2
2, 2
0.68, 0.68
2, 2
2, 2
2, 2
c
3
N
N
N
N
2
N
r
1, r2
(0, 1)
(0, 1)
(0.2, 0.5)
(0, 1)
(0, 1)
(0, 1)
(wmin, wmax)
1
1
1.37
(0.2, 0.4)
(0.4, 0.6)
(0.4, 1.2)
Neighbors
N
N
N
7
N
N
Subsystem (Subpopulations)
N
N
N
14
N
10
Velocity control
N
N
4.1
N
N
N
Stagnant limit
N
N
N
2
N
2
Degrees
N
N
N
N
N
5Each clustering approach, including the PSO-CP, ran 50 times for each dataset. Simple statistics including the worst value (Worst), the best value (Best), the Mean, and the S.D. of the fitness function are used as the evaluation criteria. The experimental environment is the same for all these comparative clustering approaches.Figure8 shows the convergence of these clustering approaches on the ten test datasets for typical runs of these approaches. The fitness value obtained by the PSO-CP declines faster at the beginning of the evolution process and then obtains fine convergence for each dataset. The values of the fitness function of PSO, FDR-PSO, and FER-PSO decrease slowly at the beginning of the evolution process and do not apparently have better convergence performance than other approaches. Because the neighbor with the best FDR and FER values is used to replace the local best of the particle, the convergence of FDR-PSO and FER-PSO is not as fast as that of PSO. Although SPSO and EPSO show better performance than the above clustering approaches, they are also easily trapped into local optima, as shown in parts (b), (g), (h), and (j) of Figure 8. Therefore, the PSO-CP has better convergence speed and higher clustering quality than the comparative approaches for all these datasets, as shown in Figure 8.Figure 8
Convergence of the approaches on the ten test datasets in terms of fitness values. (a)Data_4_3. (b) Data_9_2. (c) Square1. (d) Iris. (e) Newthroid. (f) Seeds. (g) Yeast. (h) Glass. (i) Wine. (j) Lung Cancer.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)Simple statistics of the fitness function values of these clustering approaches on these datasets are reported in Table6. Results in Table 6 show that the PSO-CP has the overall best performance on these ten test datasets. Because of the characteristics of the test datasets, some clustering approaches performed better on some specific datasets with smaller mean values, but the performance of the PSO-CP on these test datasets is considered comparable. Compared with other clustering approaches, the PSO-CP is more robust with smaller values of S.D. of the fitness function values, and its performance is more stable than PSO through the use of the extended cell-like P system.Table 6
Performances of the comparative clustering approaches on the ten test datasets measured by the values of the fitness function.
Datasets
Parameters
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Best
826.6171
819.7949
898.7706
749.5980
749.6758
749.6927
Worst
1850.0014
1482.8549
1360.0130
1288.8033
751.8741
749.8452
Mean
1320.8028
1137.2361
1074.4874
1067.7040
750.4022
749.7642
S.D.
286.2578
208.0353
135.2255
259.7331
0.5539
0.0444
Data_9_2
Best
701.0206
666.3878
672.0371
590.8895
592.3423
590.9903
Worst
821.5692
769.4857
746.3306
656.6909
647.1212
591.2978
Mean
772.3889
724.7441
709.6785
610.6185
605.4559
591.1481
S.D.
28.2783
24.5240
24.8687
24.73122
17.5056
0.0668
Square1
Best
2505.3057
2502.2471
2500.4159
2491.2407
2491.3787
2491.2439
Worst
3640.3065
2675.2805
2576.7491
2491.2410
2491.2379
2492.9382
Mean
2877.8554
2554.4594
2528.9649
2491.2410
2491.6646
2491.4117
S.D.
356.5662
45.1811
22.6925
3.42E-12
0.2295
0.2239
Iris
Best
98.7842
99.5456
100.9861
96.6555
96.6751
96.7218
Worst
158.0786
139.0893
129.3110
127.6677
97.4857
96.9734
Mean
122.9807
120.0652
111.1305
98.4060
96.9072
96.7981
S.D.
17.9146
9.8442
8.9548
6.8960
0.2477
0.0606
Newthroid
Best
1960.8256
1964.3799
1971.9836
1939.0783
1912.8158
1884.2624
Worst
3335.1916
2536.9953
2387.9253
2425.7106
2086.3923
1913.2869
Mean
2506.2474
2236.3322
2126.8844
2174.3161
1980.1139
1901.4620
S.D.
327.3508
151.6784
106.9792
138.9515
43.2650
6.3795
Seeds
Best
350.0677
338.9096
338.8187
313.8338
312.0655
311.9079
Worst
488.4095
430.6464
430.1311
330.3819
319.5618
312.2222
Mean
408.3179
365.8090
363.9724
320.2067
314.4442
312.0261
S.D.
38.4531
22.1887
20.6664
4.3349
1.8426
0.0693
Yeast
Best
377.4794
379.6469
369.5542
334.8136
310.6105
236.4264
Worst
398.8870
385.1700
383.2536
380.2217
369.7602
242.9336
Mean
383.7480
382.2182
380.7361
366.4061
346.1302
239.2609
S.D.
5.0879
1.8023
3.0165
12.5515
18.2818
1.9088
Glass
Best
323.8897
313.9315
320.6142
295.7293
268.7450
212.4726
Worst
505.9255
408.4166
396.4361
374.6702
298.358
213.3599
Mean
392.0423
363.3179
351.4392
316.4029
285.3853
212.9749
S.D.
38.8437
31.4624
21.2513
19.4952
8.63419
0.2531
Wine
Best
16478.4314
16425.3324
16394.2432
16303.2915
16297.6997
16294.4696
Worst
18718.6492
16863.3335
16765.0099
16360.8555
16321.6502
16311.2132
Mean
17242.4999
16612.5659
16530.1668
16326.2498
16308.3558
16301.2990
S.D.
551.5428
134.3416
109.0889
18.4980
7.9560
4.48774
Lung Cancer
Best
153.9672
164.5567
161.0568
147.5225
135.4626
125.6519
Worst
169.6352
178.3152
172.3457
152.6790
141.9717
125.6683
Mean
160.3950
170.2530
167.3035
149.1543
138.4026
125.6621
S.D.
3.6903
3.8259
3.2550
1.3824
1.8706
0.0045To investigate the performance of the PSO-CP, the average values of the fitness function are compared with those of the other clustering approaches and the Friedman test is used in the comparison. The null hypothesis is that all the clustering approaches in this experiment have the same performance for any one dataset. Mathematically, the Friedman test works as follows [54].In the Friedman test, the ten test datasets are treated as a random sample and each clustering approach is considered as a treatment. The average fitness values of the clustering approaches on each dataset are ranked from the largest to the smallest [55]. The rank of clustering approach j on clustering problem i is denoted by rij. The mean of these ranks is 1/2p+1, in this case 3.5, where p is the number of treatments. The Friedman test statistic χr2 is given in the following form:(14)χr2=12npp+1∑p=1p∑i=1nrij2−3np+1,where n is the number of rows, i.e., datasets, 10 in this case. The Friedman test statistic follows a chi-squared distribution with p−1 degrees of freedom.The ranks of the fitness values obtained by the clustering approaches for each dataset are presented in Table7. The PSO-CP is ranked highest, i.e., nine out of the ten test datasets. The Friedman test statistic χr2 is computed using Table 7, and the result is χr2=46.2286. With p−1=5 degrees of freedom, the critical value is χ2=11.07 at the significance level α=0.05. Hence, the conclusion of the Friedman test is to reject the null hypothesis, i.e., the treatment levels are significantly different. In this case, the different clustering approaches obtained significantly different fitness function values.Table 7
Ranks of the average values for the six clustering methods (Mean) and computation of the Friedman test statistic.
Datasets
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
6
5
4
3
2
1
Data_9_2
6
5
4
3
2
1
Square1
6
5
4
1
3
2
Iris
6
5
4
3
2
1
Newthyroid
6
5
3
4
2
1
Seeds
6
5
4
3
2
1
Yeast
6
5
4
3
2
1
Glass
6
5
4
3
2
1
Wine
6
5
4
3
2
1
Lung Cancer
4
6
5
3
2
1
Total rank
58
51
40
29
21
11
Average rank
5.8
5.1
4.0
2.9
2.1
1.1
Deviation
2.3
1.6
0.5
–0.6
–1.4
–2.4In clustering problems, theF-measure is sometimes used to measure the quality of clustering [35]. Each data point in a dataset belongs to a specific class, i.e., has a specific label, in reality although the label is usually unknown for clustering problems. Let bl represent class l in reality and ck represent cluster k obtained by a clustering approach, for l,k=1,2,⋯,K. The number of data points belonging to bl is denoted by bl, the number of data points belonging to ck is denoted by ck, and the number of the data points belonging to both bl and ck is denoted by bl∩ck. The precision of class l and cluster k is defined as follows:(15)Pbl,ck=bl∩ckck.The recall of classl and cluster k is defined as follows:(16)Rbl,ck=bl∩ckbl.TheF-measure of class l and cluster k is given in the following form:(17)Fbl,ck=2Pbl,ckRbl,ckPbl,ck+Rbl,ck.The clustering results of a good clustering approach should be close to the actual classes in the dataset [56]. The overall F-measure of the clustering results is given in the following form:(18)F=∑l=1KblNFbl=∑l=1KblNmax1≤k≤KFbl,ck.When clustering approaches are compared, the approach with a larger value of theF-measure is more effective.Table8 provides the Mean and S.D. of the values of the F-measure of the comparative clustering approaches on the ten test datasets. As the results in Table 8 show, the PSO-CP clearly has the best overall performance according to the F-measure among all these clustering approaches.Table 8
F-measure of the ten test datasets obtained by the comparative clustering approaches.
Datasets
Statistics
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Mean
0.9489
0.9000
0.7753
0.8500
1
1
S.D.
0.1025
0.1257
0.1381
0.1257
0
0
Data_9_2
Mean
0.7951
0.7924
0.7174
0.8853
0.9015
0.9209
S.D.
0.0460
0.0454
0.0560
0.0510
0.0446
0.0024
Square1
Mean
0.9893
0.9886
0.9734
0.9890
0.9890
0.9890
S.D.
0.0014
0.0021
0.0223
4.56E − 16
4.56E − 16
4.56E − 16
Iris
Mean
0.8383
0.7833
0.7887
0.8903
0.8977
0.9003
S.D.
0.0918
0.0997
0.1111
0.0534
0.0032
0.0070
Newthyroid
Mean
0.7437
0.7386
0.7570
0.7630
0.7616
0.7988
S.D.
0.0417
0.0320
0.0370
0.0378
0.0177
0.0122
Seeds
Mean
0.8721
0.8671
0.8069
0.8950
0.8945
0.8952
S.D.
0.0541
0.0534
0.1017
0.0063
0.0017
1.14E − 16
Yeast
Mean
0.3188
0.3166
0.3228
0.3437
0.3748
0.5171
S.D.
0.0075
0.0046
0.0105
0.0217
0.0204
0.0158
Glass
Mean
0.4402
0.4334
0.4308
0.4717
0.5061
0.5843
S.D.
0.0391
0.0496
0.0460
0.0285
0.0149
0.0010
Wine
Mean
0.7096
0.7104
0.7084
0.7143
0.7166
0.7169
S.D.
0.0041
0.0050
0.0075
0.0052
0.0039
0.0038
Lung Cancer
Mean
0.4172
0.4266
0.4594
0.4641
0.5312
0.5625
S.D.
0.0233
0.0355
0.0487
0.0659
0.0641
1.12E − 17The classification of a data point is correct or accurate if it is clustered into the right class or cluster [56]. Therefore, the classification rate represented by A, also called clustering accuracy, for the test datasets is also used to evaluate the performance of the clustering approaches. The classification rate of a dataset is defined as the proportion of correctly classified data points in a dataset, as shown in the following equation:(19)A=EN,where E is the number of correctly classified data points. Table 9 provides the classification rates of the comparative clustering approaches on the ten test datasets. Although the PSO-CP obtained a classification rate lower than that of FER-PSO on the Square1 dataset, it obtained better classification rates on all other test datasets than the other clustering approaches. Overall, the PSO-CP has the highest means of classification rates among the six comparative clustering techniques.Table 9
Classification rates of the ten test datasets obtained by the comparative clustering approaches.
Datasets
Statistics
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Mean
0.6746
0.8618
0.9230
0.7732
1
1
S.D.
0.2019
0.1830
0.1640
0.1948
0
0
Data_9_2
Mean
0.7157
0.7873
0.7918
0.8820
0.8993
0.9211
S.D.
0.0530
0.0474
0.0461
0.0560
0.0496
0.0024
Square1
Mean
0.9731
0.9886
0.9893
0.9890
0.9890
0.9890
S.D.
0.0232
0.0021
0.0014
2.28E − 16
2.28E − 16
2.28E − 16
Iris
Mean
0.7204
0.7774
0.8392
0.8832
0.8965
0.8992
S.D.
0.1954
0.1300
0.0941
0.0806
0.0031
0.0073
Newthyroid
Mean
0.6555
0.5690
0.6001
0.6510
0.6564
0.6860
S.D.
0.1462
0.1637
0.0877
0.1512
0.0528
0.0194
Seeds
Mean
0.8021
0.8573
0.8746
0.8949
0.8945
0.8954
S.D.
0.1145
0.0944
0.0446
0.0066
0.0021
2.36E − 11
Yeast
Mean
0.2125
0.0956
0.1477
0.2227
0.2255
0.4247
S.D.
0.0985
0.0710
0.0900
0.0910
0.1080
0.0241
Glass
Mean
0.2904
0.3263
0.3461
0.4036
0.4715
0.5518
S.D.
0.1551
0.1004
0.1151
0.1165
0.0783
0.0039
Wine
Mean
0.7200
0.7216
0.7209
0.7250
0.7270
0.7273
S.D.
0.0068
0.0044
0.0036
0.0047
0.0034
0.0034
Lung Cancer
Mean
0.4122
0.2471
0.2323
0.4178
0.5432
0.5790
S.D.
0.1356
0.1273
0.1291
0.1329
0.0873
1.92E − 17The Friedman test is also applied to the Means of the classification rates. The computed Friedman test statistic isχr2=50.4. With p−1=5 degrees of freedom, the critical value is χ2=11.07 at the significance level α=0.05. Therefore, these clustering approaches obtained significantly different classification rates.Compared with other improved PSO procedures, the PSO-CP has better values of theF-measure and better classification rates. Therefore, the extended cell-like P system helps the PSO-CP improve its clustering performance, and the introduction of membrane systems gives a new way for PSO to solve clustering problems.


## 5.1. Datasets

Four artificial datasets and ten test datasets are used in the experiments. The four artificial datasets are used to tune the parameters of the PSO-CP, and the ten test datasets are used to test the clustering performance of the PSO-CP as compared with those of five other clustering approaches. The ten test datasets including three artificial datasets and seven real-life datasets have been used by researchers as benchmarks to test their clustering approaches. These datasets are briefly described below.The seven artificial datasets,Data_5_2, Size_5, Square4, LineBlobs, Data_4_3, Data_9_2, and Square1, are manually generated and have been used in the existing literature. The seven real-life datasets, Iris, Newthyroid, Seeds, Yeast, Glass, Wine, and Lung Cancer, are from the UCI Machine Learning Repository. More details about these datasets are presented in Tables 1 and 2.Table 1
Properties of the artificial datasets.
Datasets
Data
Feature
Class
Data_5_2
250
2
5
Size_5
1000
2
4
Square4
1000
2
4
LineBlobs
266
3
4
Data_4_3
400
3
4
Data_9_2
900
2
9
Square1
1000
2
4Table 2
Properties of the real-life datasets.
Datasets
Data
Feature
Class
Iris
150
4
3
Newthyroid
215
5
3
Seeds
210
7
3
Yeast
1484
8
10
Glass
214
9
6
Wine
178
13
3
Lung Cancer
32
56
3TheLung Cancer dataset is high dimensional. It contains 32 data points, has 56 independent features, and describes three types of lung cancers. The Yeast dataset consists of 1484 data points and has 8 features. The Iris and Glass datasets are not linearly separable in the Euclidean space. These datasets with different characteristics in shape, size, compactness, and symmetry are used to evaluate the performance of the PSO-CP quantitatively.


## 5.2. Parameter Settings

The number of membranes in the subsystems and the number of elementary membranes play important roles in the performance of the PSO-CP. The values of these parameters have critical influences on the performance of the PSO-CP in solving clustering problems. This section focuses on checking the influences of two parameters, i.e., the number of elementary membranesq−1 and the number of membranes sn in the subsystems, with four artificial datasets.


### 5.2.1. Number of Elementary Membranes

In order to evaluate the effects of the number of elementary membranes on clustering performance, the PSO-CP with two different degrees, i.e., 2 and 5, are used to find the optimal clustering centers for these datasets, using the fitness function to measure clustering quality [34]. The PSO-CP with each degree ran 30 times on each dataset and the mean (Mean) and standard deviation (S.D.) of the fitness values are reported. The S.D. shows the robustness and stability of the clustering technique.Parameters of the PSO-CP not tested in this experiment are kept at the same values for the fairness in the comparisons. In the PSO-CP, the number of objects may affect the quality of the clustering results. In order to avoid the influence of the number of objects, the number of objects in the system is set to the same value, i.e.,M=100. The maximum number of iterations is set to tmax=100, and the values of the learning factors in the basic and local evolution rules are set to c1=c2=2. The number of membranes in the subsystem is set to sn=6. The values of the lower and upper limits of the inertia weight are set to wmin=0.4 and wmax=1.2, respectively. For the detection of the stagnation condition of an elementary membrane, the number of iterations is set to limit=2. The values of Mean and S.D. of the fitness function obtained by the PSO-CP with two degrees are reported in Table 3.Table 3
Performance of the PSO-CP with different degrees measured by the values of Mean and S.D. of the fitness function.
Datasets
q
=
3
q
=
6
Mean
S.D.
Mean
S.D.
Data_5_2
326.7537
0.5323
326.5707
0.1594
Size_5
2499.3796
15.1835
2499.2712
14.7658
Square4
2367.7321
0.2262
2367.7097
0.2652
LineBlobs
20.6297
0.0018
20.6294
0.0016Table3 gives the results of the PSO-CP with different degrees on the four artificial datasets. The best values of Mean and S.D. for each dataset are highlighted. The results show that the PSO-CP obtained smaller Mean and smaller S.D. when q−1=5 elementary membranes are used. These results also show the PSO-CP with q−1=5 has better robustness. Figure 6 gives more details about the clustering performance of the PSO-CP on two datasets, i.e., Data_5_2 and Size_5. The clustering performance of the PSO-CP may remarkably improve with the increase in the number of elementary membranes.Figure 6
Boxplots of the values of the fitness function for 30 runs by the PSO-CP with different degrees: (a)Data_5_2 and (b) Size_5.
(a)
(b)


### 5.2.2. Number of Membranes in the Subsystem

The number of membranes in the subsystem also has an important influence on the performance of the PSO-CP. In order to tune the number of membranes, the clustering performances of the PSO-CP withsn=6, 10, and 14 are examined [12]. The parameters of the PSO-CP which are not tested in this experiment are kept at the same values. The values of Mean and S.D. of the fitness function are presented in Table 4.Table 4
Performance of the PSO-CP with different number of membranes in the subsystems measured by the values of Mean and S.D. of the fitness function.
Datasets
s
n
=
6
s
n
=
10
s
n
=
14
Mean
S.D.
Mean
S.D.
Mean
S.D.
Data_5_2
326.5707
0.1594
326.5702
0.1210
326.7454
0.4251
Size_5
2499.2712
14.7658
2496.0993
11.2346
2497.4146
11.9762
Square4
2367.7097
0.2652
2367.6292
0.1411
2367.8010
0.2982
LineBlobs
20.6294
0.0016
16.7426
0.0362
16.7937
0.0391The PSO-CP with each different number of membranes in the subsystem ran 30 times on each dataset. The Mean and S.D. of the values of the fitness function for each number of membranes in the subsystem on each dataset are presented in Table4. The PSO-CP shows best performance on these datasets when sn=10. Figure 7 gives the boxplots of the values of the fitness function for each number of membranes in the subsystem for two datasets Data_5_2 and Size_5. Considering results for all four datasets, the PSO-CP with sn=10 has the best overall performance.Figure 7
Boxplots of the values of the fitness function for 30 runs of the PSO-CP with different number of membranes in the subsystem: (a)Data_5_2 and (b) Size_5.
(a)
(b)


## 5.2.1. Number of Elementary Membranes

In order to evaluate the effects of the number of elementary membranes on clustering performance, the PSO-CP with two different degrees, i.e., 2 and 5, are used to find the optimal clustering centers for these datasets, using the fitness function to measure clustering quality [34]. The PSO-CP with each degree ran 30 times on each dataset and the mean (Mean) and standard deviation (S.D.) of the fitness values are reported. The S.D. shows the robustness and stability of the clustering technique.Parameters of the PSO-CP not tested in this experiment are kept at the same values for the fairness in the comparisons. In the PSO-CP, the number of objects may affect the quality of the clustering results. In order to avoid the influence of the number of objects, the number of objects in the system is set to the same value, i.e.,M=100. The maximum number of iterations is set to tmax=100, and the values of the learning factors in the basic and local evolution rules are set to c1=c2=2. The number of membranes in the subsystem is set to sn=6. The values of the lower and upper limits of the inertia weight are set to wmin=0.4 and wmax=1.2, respectively. For the detection of the stagnation condition of an elementary membrane, the number of iterations is set to limit=2. The values of Mean and S.D. of the fitness function obtained by the PSO-CP with two degrees are reported in Table 3.Table 3
Performance of the PSO-CP with different degrees measured by the values of Mean and S.D. of the fitness function.
Datasets
q
=
3
q
=
6
Mean
S.D.
Mean
S.D.
Data_5_2
326.7537
0.5323
326.5707
0.1594
Size_5
2499.3796
15.1835
2499.2712
14.7658
Square4
2367.7321
0.2262
2367.7097
0.2652
LineBlobs
20.6297
0.0018
20.6294
0.0016Table3 gives the results of the PSO-CP with different degrees on the four artificial datasets. The best values of Mean and S.D. for each dataset are highlighted. The results show that the PSO-CP obtained smaller Mean and smaller S.D. when q−1=5 elementary membranes are used. These results also show the PSO-CP with q−1=5 has better robustness. Figure 6 gives more details about the clustering performance of the PSO-CP on two datasets, i.e., Data_5_2 and Size_5. The clustering performance of the PSO-CP may remarkably improve with the increase in the number of elementary membranes.Figure 6
Boxplots of the values of the fitness function for 30 runs by the PSO-CP with different degrees: (a)Data_5_2 and (b) Size_5.
(a)
(b)


## 5.2.2. Number of Membranes in the Subsystem

The number of membranes in the subsystem also has an important influence on the performance of the PSO-CP. In order to tune the number of membranes, the clustering performances of the PSO-CP withsn=6, 10, and 14 are examined [12]. The parameters of the PSO-CP which are not tested in this experiment are kept at the same values. The values of Mean and S.D. of the fitness function are presented in Table 4.Table 4
Performance of the PSO-CP with different number of membranes in the subsystems measured by the values of Mean and S.D. of the fitness function.
Datasets
s
n
=
6
s
n
=
10
s
n
=
14
Mean
S.D.
Mean
S.D.
Mean
S.D.
Data_5_2
326.5707
0.1594
326.5702
0.1210
326.7454
0.4251
Size_5
2499.2712
14.7658
2496.0993
11.2346
2497.4146
11.9762
Square4
2367.7097
0.2652
2367.6292
0.1411
2367.8010
0.2982
LineBlobs
20.6294
0.0016
16.7426
0.0362
16.7937
0.0391The PSO-CP with each different number of membranes in the subsystem ran 30 times on each dataset. The Mean and S.D. of the values of the fitness function for each number of membranes in the subsystem on each dataset are presented in Table4. The PSO-CP shows best performance on these datasets when sn=10. Figure 7 gives the boxplots of the values of the fitness function for each number of membranes in the subsystem for two datasets Data_5_2 and Size_5. Considering results for all four datasets, the PSO-CP with sn=10 has the best overall performance.Figure 7
Boxplots of the values of the fitness function for 30 runs of the PSO-CP with different number of membranes in the subsystem: (a)Data_5_2 and (b) Size_5.
(a)
(b)


## 5.3. Comparison with Other Clustering Approaches

To evaluate the effectiveness of the PSO-CP, its performance is compared with those of the standard particle swarm optimization (PSO) [49], fitness-distance ratio-particle swarm optimization (FDR-PSO) [53], fitness-Euclidean ratio-particle swarm optimization (FER-PSO) [42], starling particle swarm optimization (SPSO) [12], and environment particle swarm optimization (EPSO) [13] on the ten test datasets. Although there are many other advanced PSO clustering approaches, the ones used for comparison are the major references for the development of, and are more relevant to, the PSO-CP. The neighbor of the particle with the best FDR or FER value is selected in the FDR-PSO and FER-PSO approaches to replace the local best for velocity updating. A mechanism is used to lead the search out of a local optimum when stagnation occurs in the SPSO approach, and the implementation of the environment factor in the EPSO approach is similar to the active membranes in this study.Table5 reports the parameter values of all the comparative clustering approaches used in the experiments. The information of neighbors is used to guide the search direction of the particle, and the number of neighbors has important influence on the performance of the SPSO approach. The SPSO approach copies the current population to multipopulations when the cumulative number of iterations reaches a previously set threshold, called stagnant limit meaning that the particle in the population is trapped into a local optimum. The number of subpopulations is a decisive factor of the convergent rate in the approach. This operation of population is similar to the creation and dissolution of membranes in the PSO-CP. The velocity control of FER-PSO is an adjustable parameter to balance the previous velocity and the current velocity of the particle, and the learning factor controls the influence of the environmental factor in EPSO. The values of all these adjustable parameters in these approaches are the best values reported in the respective publications.Table 5
Parameter settings of the comparative clustering approaches used in the experiments.
Parameters
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Population (M)
100
100
100
100
100
100
t
max
100
100
100
100
100
100
c
1, c2
2, 2
2, 2
0.68, 0.68
2, 2
2, 2
2, 2
c
3
N
N
N
N
2
N
r
1, r2
(0, 1)
(0, 1)
(0.2, 0.5)
(0, 1)
(0, 1)
(0, 1)
(wmin, wmax)
1
1
1.37
(0.2, 0.4)
(0.4, 0.6)
(0.4, 1.2)
Neighbors
N
N
N
7
N
N
Subsystem (Subpopulations)
N
N
N
14
N
10
Velocity control
N
N
4.1
N
N
N
Stagnant limit
N
N
N
2
N
2
Degrees
N
N
N
N
N
5Each clustering approach, including the PSO-CP, ran 50 times for each dataset. Simple statistics including the worst value (Worst), the best value (Best), the Mean, and the S.D. of the fitness function are used as the evaluation criteria. The experimental environment is the same for all these comparative clustering approaches.Figure8 shows the convergence of these clustering approaches on the ten test datasets for typical runs of these approaches. The fitness value obtained by the PSO-CP declines faster at the beginning of the evolution process and then obtains fine convergence for each dataset. The values of the fitness function of PSO, FDR-PSO, and FER-PSO decrease slowly at the beginning of the evolution process and do not apparently have better convergence performance than other approaches. Because the neighbor with the best FDR and FER values is used to replace the local best of the particle, the convergence of FDR-PSO and FER-PSO is not as fast as that of PSO. Although SPSO and EPSO show better performance than the above clustering approaches, they are also easily trapped into local optima, as shown in parts (b), (g), (h), and (j) of Figure 8. Therefore, the PSO-CP has better convergence speed and higher clustering quality than the comparative approaches for all these datasets, as shown in Figure 8.Figure 8
Convergence of the approaches on the ten test datasets in terms of fitness values. (a)Data_4_3. (b) Data_9_2. (c) Square1. (d) Iris. (e) Newthroid. (f) Seeds. (g) Yeast. (h) Glass. (i) Wine. (j) Lung Cancer.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)Simple statistics of the fitness function values of these clustering approaches on these datasets are reported in Table6. Results in Table 6 show that the PSO-CP has the overall best performance on these ten test datasets. Because of the characteristics of the test datasets, some clustering approaches performed better on some specific datasets with smaller mean values, but the performance of the PSO-CP on these test datasets is considered comparable. Compared with other clustering approaches, the PSO-CP is more robust with smaller values of S.D. of the fitness function values, and its performance is more stable than PSO through the use of the extended cell-like P system.Table 6
Performances of the comparative clustering approaches on the ten test datasets measured by the values of the fitness function.
Datasets
Parameters
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Best
826.6171
819.7949
898.7706
749.5980
749.6758
749.6927
Worst
1850.0014
1482.8549
1360.0130
1288.8033
751.8741
749.8452
Mean
1320.8028
1137.2361
1074.4874
1067.7040
750.4022
749.7642
S.D.
286.2578
208.0353
135.2255
259.7331
0.5539
0.0444
Data_9_2
Best
701.0206
666.3878
672.0371
590.8895
592.3423
590.9903
Worst
821.5692
769.4857
746.3306
656.6909
647.1212
591.2978
Mean
772.3889
724.7441
709.6785
610.6185
605.4559
591.1481
S.D.
28.2783
24.5240
24.8687
24.73122
17.5056
0.0668
Square1
Best
2505.3057
2502.2471
2500.4159
2491.2407
2491.3787
2491.2439
Worst
3640.3065
2675.2805
2576.7491
2491.2410
2491.2379
2492.9382
Mean
2877.8554
2554.4594
2528.9649
2491.2410
2491.6646
2491.4117
S.D.
356.5662
45.1811
22.6925
3.42E-12
0.2295
0.2239
Iris
Best
98.7842
99.5456
100.9861
96.6555
96.6751
96.7218
Worst
158.0786
139.0893
129.3110
127.6677
97.4857
96.9734
Mean
122.9807
120.0652
111.1305
98.4060
96.9072
96.7981
S.D.
17.9146
9.8442
8.9548
6.8960
0.2477
0.0606
Newthroid
Best
1960.8256
1964.3799
1971.9836
1939.0783
1912.8158
1884.2624
Worst
3335.1916
2536.9953
2387.9253
2425.7106
2086.3923
1913.2869
Mean
2506.2474
2236.3322
2126.8844
2174.3161
1980.1139
1901.4620
S.D.
327.3508
151.6784
106.9792
138.9515
43.2650
6.3795
Seeds
Best
350.0677
338.9096
338.8187
313.8338
312.0655
311.9079
Worst
488.4095
430.6464
430.1311
330.3819
319.5618
312.2222
Mean
408.3179
365.8090
363.9724
320.2067
314.4442
312.0261
S.D.
38.4531
22.1887
20.6664
4.3349
1.8426
0.0693
Yeast
Best
377.4794
379.6469
369.5542
334.8136
310.6105
236.4264
Worst
398.8870
385.1700
383.2536
380.2217
369.7602
242.9336
Mean
383.7480
382.2182
380.7361
366.4061
346.1302
239.2609
S.D.
5.0879
1.8023
3.0165
12.5515
18.2818
1.9088
Glass
Best
323.8897
313.9315
320.6142
295.7293
268.7450
212.4726
Worst
505.9255
408.4166
396.4361
374.6702
298.358
213.3599
Mean
392.0423
363.3179
351.4392
316.4029
285.3853
212.9749
S.D.
38.8437
31.4624
21.2513
19.4952
8.63419
0.2531
Wine
Best
16478.4314
16425.3324
16394.2432
16303.2915
16297.6997
16294.4696
Worst
18718.6492
16863.3335
16765.0099
16360.8555
16321.6502
16311.2132
Mean
17242.4999
16612.5659
16530.1668
16326.2498
16308.3558
16301.2990
S.D.
551.5428
134.3416
109.0889
18.4980
7.9560
4.48774
Lung Cancer
Best
153.9672
164.5567
161.0568
147.5225
135.4626
125.6519
Worst
169.6352
178.3152
172.3457
152.6790
141.9717
125.6683
Mean
160.3950
170.2530
167.3035
149.1543
138.4026
125.6621
S.D.
3.6903
3.8259
3.2550
1.3824
1.8706
0.0045To investigate the performance of the PSO-CP, the average values of the fitness function are compared with those of the other clustering approaches and the Friedman test is used in the comparison. The null hypothesis is that all the clustering approaches in this experiment have the same performance for any one dataset. Mathematically, the Friedman test works as follows [54].In the Friedman test, the ten test datasets are treated as a random sample and each clustering approach is considered as a treatment. The average fitness values of the clustering approaches on each dataset are ranked from the largest to the smallest [55]. The rank of clustering approach j on clustering problem i is denoted by rij. The mean of these ranks is 1/2p+1, in this case 3.5, where p is the number of treatments. The Friedman test statistic χr2 is given in the following form:(14)χr2=12npp+1∑p=1p∑i=1nrij2−3np+1,where n is the number of rows, i.e., datasets, 10 in this case. The Friedman test statistic follows a chi-squared distribution with p−1 degrees of freedom.The ranks of the fitness values obtained by the clustering approaches for each dataset are presented in Table7. The PSO-CP is ranked highest, i.e., nine out of the ten test datasets. The Friedman test statistic χr2 is computed using Table 7, and the result is χr2=46.2286. With p−1=5 degrees of freedom, the critical value is χ2=11.07 at the significance level α=0.05. Hence, the conclusion of the Friedman test is to reject the null hypothesis, i.e., the treatment levels are significantly different. In this case, the different clustering approaches obtained significantly different fitness function values.Table 7
Ranks of the average values for the six clustering methods (Mean) and computation of the Friedman test statistic.
Datasets
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
6
5
4
3
2
1
Data_9_2
6
5
4
3
2
1
Square1
6
5
4
1
3
2
Iris
6
5
4
3
2
1
Newthyroid
6
5
3
4
2
1
Seeds
6
5
4
3
2
1
Yeast
6
5
4
3
2
1
Glass
6
5
4
3
2
1
Wine
6
5
4
3
2
1
Lung Cancer
4
6
5
3
2
1
Total rank
58
51
40
29
21
11
Average rank
5.8
5.1
4.0
2.9
2.1
1.1
Deviation
2.3
1.6
0.5
–0.6
–1.4
–2.4In clustering problems, theF-measure is sometimes used to measure the quality of clustering [35]. Each data point in a dataset belongs to a specific class, i.e., has a specific label, in reality although the label is usually unknown for clustering problems. Let bl represent class l in reality and ck represent cluster k obtained by a clustering approach, for l,k=1,2,⋯,K. The number of data points belonging to bl is denoted by bl, the number of data points belonging to ck is denoted by ck, and the number of the data points belonging to both bl and ck is denoted by bl∩ck. The precision of class l and cluster k is defined as follows:(15)Pbl,ck=bl∩ckck.The recall of classl and cluster k is defined as follows:(16)Rbl,ck=bl∩ckbl.TheF-measure of class l and cluster k is given in the following form:(17)Fbl,ck=2Pbl,ckRbl,ckPbl,ck+Rbl,ck.The clustering results of a good clustering approach should be close to the actual classes in the dataset [56]. The overall F-measure of the clustering results is given in the following form:(18)F=∑l=1KblNFbl=∑l=1KblNmax1≤k≤KFbl,ck.When clustering approaches are compared, the approach with a larger value of theF-measure is more effective.Table8 provides the Mean and S.D. of the values of the F-measure of the comparative clustering approaches on the ten test datasets. As the results in Table 8 show, the PSO-CP clearly has the best overall performance according to the F-measure among all these clustering approaches.Table 8
F-measure of the ten test datasets obtained by the comparative clustering approaches.
Datasets
Statistics
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Mean
0.9489
0.9000
0.7753
0.8500
1
1
S.D.
0.1025
0.1257
0.1381
0.1257
0
0
Data_9_2
Mean
0.7951
0.7924
0.7174
0.8853
0.9015
0.9209
S.D.
0.0460
0.0454
0.0560
0.0510
0.0446
0.0024
Square1
Mean
0.9893
0.9886
0.9734
0.9890
0.9890
0.9890
S.D.
0.0014
0.0021
0.0223
4.56E − 16
4.56E − 16
4.56E − 16
Iris
Mean
0.8383
0.7833
0.7887
0.8903
0.8977
0.9003
S.D.
0.0918
0.0997
0.1111
0.0534
0.0032
0.0070
Newthyroid
Mean
0.7437
0.7386
0.7570
0.7630
0.7616
0.7988
S.D.
0.0417
0.0320
0.0370
0.0378
0.0177
0.0122
Seeds
Mean
0.8721
0.8671
0.8069
0.8950
0.8945
0.8952
S.D.
0.0541
0.0534
0.1017
0.0063
0.0017
1.14E − 16
Yeast
Mean
0.3188
0.3166
0.3228
0.3437
0.3748
0.5171
S.D.
0.0075
0.0046
0.0105
0.0217
0.0204
0.0158
Glass
Mean
0.4402
0.4334
0.4308
0.4717
0.5061
0.5843
S.D.
0.0391
0.0496
0.0460
0.0285
0.0149
0.0010
Wine
Mean
0.7096
0.7104
0.7084
0.7143
0.7166
0.7169
S.D.
0.0041
0.0050
0.0075
0.0052
0.0039
0.0038
Lung Cancer
Mean
0.4172
0.4266
0.4594
0.4641
0.5312
0.5625
S.D.
0.0233
0.0355
0.0487
0.0659
0.0641
1.12E − 17The classification of a data point is correct or accurate if it is clustered into the right class or cluster [56]. Therefore, the classification rate represented by A, also called clustering accuracy, for the test datasets is also used to evaluate the performance of the clustering approaches. The classification rate of a dataset is defined as the proportion of correctly classified data points in a dataset, as shown in the following equation:(19)A=EN,where E is the number of correctly classified data points. Table 9 provides the classification rates of the comparative clustering approaches on the ten test datasets. Although the PSO-CP obtained a classification rate lower than that of FER-PSO on the Square1 dataset, it obtained better classification rates on all other test datasets than the other clustering approaches. Overall, the PSO-CP has the highest means of classification rates among the six comparative clustering techniques.Table 9
Classification rates of the ten test datasets obtained by the comparative clustering approaches.
Datasets
Statistics
Clustering Approaches
PSO
FDR-PSO
FER-PSO
SPSO
EPSO
PSO-CP
Data_4_3
Mean
0.6746
0.8618
0.9230
0.7732
1
1
S.D.
0.2019
0.1830
0.1640
0.1948
0
0
Data_9_2
Mean
0.7157
0.7873
0.7918
0.8820
0.8993
0.9211
S.D.
0.0530
0.0474
0.0461
0.0560
0.0496
0.0024
Square1
Mean
0.9731
0.9886
0.9893
0.9890
0.9890
0.9890
S.D.
0.0232
0.0021
0.0014
2.28E − 16
2.28E − 16
2.28E − 16
Iris
Mean
0.7204
0.7774
0.8392
0.8832
0.8965
0.8992
S.D.
0.1954
0.1300
0.0941
0.0806
0.0031
0.0073
Newthyroid
Mean
0.6555
0.5690
0.6001
0.6510
0.6564
0.6860
S.D.
0.1462
0.1637
0.0877
0.1512
0.0528
0.0194
Seeds
Mean
0.8021
0.8573
0.8746
0.8949
0.8945
0.8954
S.D.
0.1145
0.0944
0.0446
0.0066
0.0021
2.36E − 11
Yeast
Mean
0.2125
0.0956
0.1477
0.2227
0.2255
0.4247
S.D.
0.0985
0.0710
0.0900
0.0910
0.1080
0.0241
Glass
Mean
0.2904
0.3263
0.3461
0.4036
0.4715
0.5518
S.D.
0.1551
0.1004
0.1151
0.1165
0.0783
0.0039
Wine
Mean
0.7200
0.7216
0.7209
0.7250
0.7270
0.7273
S.D.
0.0068
0.0044
0.0036
0.0047
0.0034
0.0034
Lung Cancer
Mean
0.4122
0.2471
0.2323
0.4178
0.5432
0.5790
S.D.
0.1356
0.1273
0.1291
0.1329
0.0873
1.92E − 17The Friedman test is also applied to the Means of the classification rates. The computed Friedman test statistic isχr2=50.4. With p−1=5 degrees of freedom, the critical value is χ2=11.07 at the significance level α=0.05. Therefore, these clustering approaches obtained significantly different classification rates.Compared with other improved PSO procedures, the PSO-CP has better values of theF-measure and better classification rates. Therefore, the extended cell-like P system helps the PSO-CP improve its clustering performance, and the introduction of membrane systems gives a new way for PSO to solve clustering problems.


## 6. Conclusions

An extended membrane system combining an extended cell-like P system and the PSO mechanism, called the PSO-CP, is developed to solve clustering problems. This extended P system under the framework of membrane computing, using a cell-like P system with active membranes, integrates the rules for objects and membranes. Different from the existing evolutionary clustering techniques, the PSO-CP uses basic evolution rules for objects based on the standard velocity and position updating rules of the particles in PSO and the communication rules for objects to transfer the best objects between membranes. Subsystems containing membranes are specially designed to avoid prematurity, and a modified evolution mechanism for objects is used to evolve objects in the subsystems. The PSO-CP is evaluated on ten test datasets from the Artificial Datasets and the UCI Machine Learning Repository, and the computational results clearly exhibit the effectiveness of this proposed membrane system in solving clustering problems as compared with five existing PSO clustering methods.P systems, as parallel computing models, are highly effective and efficient in solving optimization problems with linear or polynomial complexity. These parallel computing models based on evolution mechanisms provide new ways for solving clustering problems. The extended membrane system uses the cell-like P system as the computation structure, and the communication rules between membranes are single directional. Although these single directional communication rules are simple and easy to implement, bidirectional communication rules may be introduced in future studies to further accelerate the convergence and improve the diversity of populations. Some more complicated communication structures between different membranes may be used in future studies to improve the performance of the approach. Furthermore, the experiments only used small datasets from the Artificial Datasets and the UCI Machine Learning Repository, and the proposed approach may have some limitations on high dimensional and large datasets. Future studies may test the effectiveness of the PSO-CP using large datasets. Balancing the local and global search abilities is also a hard problem to resolve in future studies. Future studies may also focus on extended membrane systems based on tissue-like P systems and other bio-inspired computing models. More studies are needed to apply these extended membrane systems to solve automatic and multiobjective clustering problems.



---

*Source: 5097589-2020-01-31.xml*