Membrane Clustering: A Novel Clustering Algorithm under Membrane Computing

Membrane Clustering: A Novel Clustering Algorithm under Membrane Computing Hong Peng1, Jiarong Zhang1, Jun Wang2, Tao Wang3, Mario J. P´erez-Jim´enez4, Agust´ın Riscos-N´u˜nez4 1Center for Radio Administration and Technology Development, Xihua University, Chengdu 610039, China [email protected] 2School of Electrical and Information Engineering, Xihua University, Chengdu 610039, China 3School of Electrical Engineering, Southwest Jiaotong University, Chengdu 610031, China 4Research Group of Natural Computing, Department of Computer Science and Artificial Intelligence, University of Seville, Sevilla 41012, Spain Summary. Membrane computing (known as P systems) is a class of distributed parallel computing models, this paper presents a novel algorithm under membrane computing for solving the data clustering problem, called as membrane clustering algorithm. The clustering algorithm is based on a tissue-like P system with a loop structure of cells. The objects of the cells express the candidate cluster centers and are evolved by the evolution rules. Based on the loop membrane structure, the communication rules realize a local neighborhood topology, which helps the co-evolution of the objects and improves the diversity of objects in the system. The tissue-like P system can effectively search for the optimal clustering partition with the help of its parallel computing advantage. The proposed clustering algorithm is evaluated on four artificial data sets and six real-life data sets. Experimental results show that the proposed clustering algorithm is superior or competitive to classical k-means algorithm and several evolutionary clustering algorithms recently reported in the literature. 1 Introduction Data clustering is a fundamental conceptual problem in data mining, which describes the process of grouping data into classes or clusters such that the data in each cluster share a high degree of similarity while being very dissimilar to data from other clusters [1]. Over the past years, a large number of clustering algorithms have been proposed [2, 3, 4], which can be divided roughly as two categories: hierarchical and partitional. Hierarchical clustering proceeds successively by either merging smaller clusters into larger ones or by splitting larger clusters. Partitional 312 H. Peng et al. clustering attempts to directly decompose a data set into several disjointed clusters based on similarity measure, for example, mean square error (MSE). Clustering algorithms have been used in a wide variety of areas, such as pattern recognition, machine learning, image processing, web mining [5, 6]. In the present study, the classical k-means algorithm [7, 8] has received wide attention because of the following two reasons: (i) k-means has been recently elected and listed among the top most influential data mining algorithms [9]; (ii) it is at the same time very simple and quite scalable, as it has linear asymptotic running time with respect to any variable of the problem. However, k-means is sensitive to the initial cluster centers and easy to get stuck at the local optimal solutions. Moreover, k-means takes large time cost to find the global optimal solution when the number of data points is large. In recent years, some evolutionary algorithms have been introduced to overcome the shortcomings of k-means algorithm because of their global optimization capability. Several genetic algorithms (GA)-based clustering algorithms were proposed, which used the two different methods to express the clustering solutions respectively. The first method uses the chromosome directly to encode the cluster number that each data point belongs to [27, 28]. However, this method does not reduce the size of the search space and searching cost of the optimal solution when the data points proliferate. Another method uses a relatively indirect representation, in which the chromosome encodes the cluster centers and each data is subsequently assigned to the closest cluster center [10, 11, 12, 13, 14]. However, most of GA-based clustering algorithms can suffer from the degeneracy when numerous chromosomes represent the same solution. The degeneracy can lead to inefficient coverage of the search space as the same configurations of clusters are repeatedly explored. It is for this reason that some researchers developed the particle swarm optimization (PSO)-based or ant colony optimization (ACO)-based clustering algorithms. Kao et al. have proposed a hybrid technique based on combining the k-means and PSO for cluster analysis [15]. Shelokar et al. have introduced an evolutionary algorithm based on ACO for clustering problem [16]. Niknam et al. have presented a hybrid evolutionary optimization algorithm based on the combination of PSO and ACO for solving the clustering problem [17]. Membrane computing initiated by Pˇaun [18] in 1998, is inspired by the structure and functioning of living cells as well as the interaction of living cells in tissues, organs or neural nets. Membrane computing is a novel class of distributed parallel computing models, and also known as P systems. The computing models usually have three key elements: membrane structure, multisets of objects and rules [19]. Generally, the multisets of objects are placed in compartments surrounded by membranes and evolved by some given rules. In recent years, a large number of variants have been proposed [20, 21, 22, 23]. These efforts have addressed the parallel computing advantage of P systems as well as the high effectiveness of solving a variety of difficult problems, especially, P systems can solve a number of NP-hard problems in linear or polynomial time complexity [24]. Moreover, membrane algorithms, as a variant of P systems, have demonstrated a powerful global A Novel Clustering Algorithm under Membrane Computing 313 optimization performance [25, 26]. This paper focuses on application of membrane computing to data clustering. Our motivation is applying the specially designed elements and inherent mechanisms of P systems to achieve a novel clustering algorithm, called membrane clustering algorithm in this paper. The rest of this paper is organized as follows. Section 2 gives a brief outline of tissue-like P systems. The proposed membrane clustering algorithm is presented in Section 3, and experimental results and analysis are provided in Section 4. Finally, Section 5 draws the conclusions. 2 Tissue-like P systems The P systems first proposed are cell-like P systems in which the membranes are arranged as a rooted tree [18, 19], where the root expresses the skin of the cells (the outermost membrane) and the leafs represent elementary membranes (which do not contain any other membrane). Its biological inspiration is from the morphology of the cells, where small vesicles are surrounded by the large vesicles. For tissue-like P systems, tree-like structure is changed as a general graph. It is from the two biological inspirations: intercellular communication and collaboration between neurons. The intercellular communication is based on symport/antiport rules, which are introduced as the communication rules of tissue-like P systems. In symport rules, objects cooperate to traverse a membrane together in the same direction, whereas in the case of antiport rules, objects residing at both sides of the membrane cross it simultaneously but in opposite directions. Formally, a tissue-like P system (of degree q > 0) with symport/antiport rules is a construct Π= (O, w1, . . . , wq, R1, . . . , Rq, R′, i0) (1) where (1) Ois a finite alphabet, whose symbols are called objects; (2) wi(1 ≤i≤q) is finite set of strings over O, which represents multiset of objects initially present in cell i; (3) Ri(1 ≤i≤q) is finite set of evolution rules in cell i; (4) R′is finite set of communication rules of the form (i, u/v, j), which represents communication rule between cell iand cell j,i=j,i, j = 1,2, . . . , q,u, v ∈O∗; (5) i0indicates the output region of the system. From membrane structure, a tissue-like P system can be viewed as a net implicitly, which consists of the qcells labeled by 1,2, . . . , q respectively. Here, each cell is an elementary membrane. Usually, the environment is labeled by 0. The communication rule of the form (i, u/v, j) indirectly indicates synaptic connection between cell iand cell j. The communication rules determine a virtual graph, where the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. The net structure provides the flexibility of expressing the needed structures from simple to complex when we deal with real-world problems. 314 H. Peng et al. In tissue-like P systems, multisets of objects of the qcells are described by w1, w1, . . . , wq. Suppose any multiset of objects over Ois available in the environment. Generally speaking, a tissue-like P system includes the rules of two types: evolution rules and communication rules. Each cell usually contains one or more evolution rules, while a communication rule is built between two different cells. In above definition, Ri(1 ≤i≤q) is finite set of evolution rules in cell i, whose rule is of the form u→v, u, v ∈O∗. The application of the rule means that uwill be evolved to v. In most of the existing tissue-like P systems and variants, evolution rule of the form is based on string of objects. However, when we apply it to solve real-world problem, we should design the corresponding evolution rules according to domain knowledge of the real-world problem. The communication rule of the form (i, u/v, j) is called as antiport rule. The communication rule (i, u/v, j) can be applied over two cells labeled by iand jwhen uis contained in cell iand v is contained in cell j. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. Note that if either i= 0 or j= 0 then the objects are interchanged between a cell and the environment. If one of uor vin above rule is empty, the rule is called as symport rule, for example, (i, u/λ, j). The application of the rule means that u will be communicated form cell ito cell j. In tissue-like P systems, as usual in the framework of membrane computing, every cell as a computing unit works in a maximally parallel way (a universal clock is considered here). In a computing step, each object in a cell can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e, in each step we can apply a maximal set of rules. A computation in a tissue-like P system of degree dis a sequence of steps which start with the cells 1, . . . , q containing the multisets w1, . . . , wqand where, in each step, one or more rules are applied to the current multisets of symbol objects. A computation is successful if and only if it halts. When it halts, it produces a final result in output cell. 3 The proposed membrane clustering algorithm In this section, we will present in detail the developed membrane clustering algorithm, a novel clustering algorithm under the framework of membrane computing, which is based on a tissue-like P system with a loop structure of cells. As usual, the designed tissue-like P system consists of several cells, each of which contains a object or multiple objects. The cells have some evolution rules to evolve the objects of the system, while communication rules between cell membranes are used to exchange and share the objects. Moreover, the loop structure of cells is indicated indirectly by the communication rules. The tissue-like P system can realize the co-evolution of objects among the cells under the control of evolution rules A Novel Clustering Algorithm under Membrane Computing 315 and communication rules. The role of the tissue-like P system is to search for the optimal cluster centers for a data set to be clustered. In the following, we first describe several basic components, and then provide the proposed tissue-like P system and membrane clustering algorithm. 3.1 Clustering measure Suppose that data set Dhas nsample points, x1, x2, . . . , xn,xi∈Rd(i= 1,2, . . . , n), and is partitioned into kclusters, C1, C2, . . . , Ck. Denote by z1, z2, . . . , zk the corresponding cluster centers. If the distances of sample point xito cluster centers zp(p= 1,2, . . . , k) satisfy ||xi−zj|| ≤ ||xi−zp||, p = 1,2, . . . , k and j=p, (2) then sample point xiis assigned to cluster Cj,i= 1,2, . . . , n. Usually, partitional clustering algorithm searches for the optimal cluster centers in the solution space according to some clustering measure in order to solve data clustering problem. A commonly used clustering measure is M(C1, C2, . . . , Ck) = k ∑ i=1 ∑ xj∈Ci ||xj−zi||.(3) Generally, the smaller the Mvalue, the higher the clustering quality. In this work, the clustering measure is also used to evaluate the objects of the system during object evolution. If the Mvalue of an object is the smaller, the object is the better, otherwise, it is worse. 3.2 Membrane structure The membrane clustering algorithm proposed in this paper is based on a tissuelike P system of degree q, which consists of qcells, shown in Fig. 1. The cells are labeled by 1,2, . . . , q, respectively. The region labeled by 0 is the environment. In this work, the environment is also output region of the system. The directed lines in Fig. 1 indicate the communication of objects between the qcells. Moreover, the qcells will be arranged as a loop topology based on the communication rules described below. As usual in P system, the qcells, as parallel computing units, will run independently. In addition, the environment always stores the best object found so far in the system. When the system halts, the object in the environment will be regarded as the output of whole system. 3.3 Objects In the tissue-like P system, each cell contains several objects. The role of the designed tissue-like P system is to find the optimal cluster centers for a data set, 316 H. Peng et al. 1 2 3 q-1 q ĂĂ 0 Fig. 1. Membrane structure of the designed tissue-like P system. thus each object in cells will express a group of (candidate) cluster centers. Since data set Dhas kcluster centers and each cluster center is a d-dimensional vector, each object in the system is considered as a (k×d)-dimensional real vector of the form z= (z11, z12, . . . , z1d, . . . , zi1, zi2, . . . , zid, . . . , zk1, zk2, . . . , zkd) where zi1, zi2, . . . , zid are dcomponents of ith cluster center zi,i= 1,2, . . . , k. For simplicity, suppose that each cell has the same number of objects, which is denoted by m. Initially, the system will randomly generates minitial objects for each cell. When an initial object zis generated, (k×d) random real numbers are produced repeatedly to form it with the constraint of A1≤zi1≤B1, . . . , Aj≤zij ≤Bj, . . . , Ad≤zid ≤Bd(4) where Ajand Bjare lower bound and upper bound of jth dimensional component of data points, respectively, j= 1,2, . . . , d. 3.4 Rules The tissue-like P system includes the rules of two types: the evolution rules, which aim to evolve the objects in cells and the communication rules, which aim to exchange and share the objects. Evolution rules are used to evolve the objects associated with cluster centers, so the tissue-like P system is able to find the optimal cluster centers for a data set via the evolution of objects. Moreover, communication rules will realize the exchange and sharing of better objects between adjacent cells. Note that in each computing step, the communication rules are executed after the evolution rules. For each cell, the better objects communicated from its two adjacent cells form a subset of objects, called external pool, whose objects will participate its evolution of objects in next computing step (see Fig. 2). As usual in P systems, each cell as an independent computing unit runs in maximum parallel way under the control of a global clock. A Novel Clustering Algorithm under Membrane Computing 317 object pool combination external pool selection rule crossover rule mutation rule new object pool next computing step matching pool Fig. 2. The evolution procedure of objects in a cell. Evolution rules The role of evolution rules is to evolve the objects in cells to generate new objects used in next computing step. During the evolution, each cell maintains the same size (the number of objects). In this work, three known genetic operations (selection, crossover and mutation) [29, 30] are introduced as the evolution rules in cells. In a computing step, all objects (located in object pool) in each cell and the better objects (located in external pool) from its two adjacent cells constitute a matching pool. The objects in external pool are actually the better objects communicated from its two adjacent cells in previous computing step. The objects in matching pool will be evolved by executing selection, crossover and mutation operations in turn. In order to maintain the size of objects in each cell, truncation operation is used to constitute new object pool according to the Mvalues of objects. The objects in new object pool will be regarded as the objects to be evolved in next computing step. Fig. 2 shows the evolution procedure of objects in a cell. In this work, selection operation uses usual rotating wheel method, while crossover operation uses single-point crossover in which the position of crossover point is determined according to crossover probability pc[31]. The single-point mutation is used to realize the mutations of objects. If vis a mutation point determined according to mutation probability pm, its value becomes, after mutating, v′={v±2×δ×v, v = 0 v±2×δ, v = 0 (5) where the signs “+” or “-” occur with equal probability, and δis a real number in the range [0,1], generated with uniform distribution. Communication rules The communication rules are used to exchange the objects between each cell and its two adjacent cells and update the best object found so far in the environment. The tissue-like P system designed in this paper involves the communication rules of two types: 318 H. Peng et al. (1) Antiport communication rule: (i, z/z′, j), i, j = 1,2, . . . , q. The rule indicates that object zis communicated from cell ito cell jand object z′is communicated from cell jto cell i. (2) Symport communication rule: (i, z/λ, 0), i= 1,2, . . . , q. The rule expresses that object zis communicated from cell ito the environment. i-1 i i+1 (b) 1 4 2 3 q q-1 (a) Fig. 3. A loop topology structure of cells and the communication relation between adjacent cells. The communication rules impliedly indicate the connection relationship between cells. Fig. 3 shows the communication relation of objects between cells in the designed tissue-like P system. From a logical point of view, the communication relation shows that the cells form a loop topology, shown in Fig. 3(a). Meanwhile, this also reflects a neighborhood structure of the communication of objects, namely, each cell only exchanges and shares the objects with its two adjacent cells, shown in Fig. 3(b). After the objects are evolved, each cell (such as cell i) transmits its several best objects into adjacent cells (such as cells i−1 and i+ 1) and retrieves several best objects from adjacent cells (such as cells i−1 and i+ 1) by using the communication rule, constituting the matching pool of objects in next computing step. The special logical structure can bring the following benefits: (1) The co-evolution of objects in the qcells can accelerate the convergence of the proposed clustering algorithm. (2) The object sharing mechanism of the local neighborhood structure can enhance the diversity of objects in the entire system. The communication of objects not only occurs between cells, but also appears between cell and the environment. The global best object found so far in whole system is stored always in the environment. After objects are evolved, each cell communicates its best object found in current computing step into the environment to update the global best object. The update strategy used in the tissue-like P A Novel Clustering Algorithm under Membrane Computing 319 system is that if the communicated object is better than the global best object, the global best object is substituted, otherwise it is discarded. 3.5 Halt condition In this paper, maximum execution step number is used as the halt condition of the tissue-like P system, that is, the tissue-like P system will continue to run until it reaches the maximum execution step number. When the system halts, the best object in the environment is regarded as the system output, which is the found optimal cluster centers. 3.6 The proposed clustering algorithm According to the components discussed above, the designed tissue-like P system can be formally described as follows. It is a tissue-like P system of degree q, Π= (Z1, . . . , Zq, R1, . . . , Rq, R′, io) where (1) Ziis the set of mobjects in cell i, where each object zis a (k×d)-dimensional vector, 1 ≤i≤q; (2) Riis the finite set of evolution rules, 1 ≤i≤q. Each Ricontains three evolution rules: selection, crossover and mutation rules; (3) R′is the finite set of communication rules with the following forms: (a) Antiport communication rule, (i, z/z′, j), i, j = 1,2, . . . , q,i=j. The rule is used to communicate the objects between an cell and its two adjacent cells; (b) Symport communication rule, (i, z/λ, 0), i= 1,2, . . . , q. The rule is used to communicate the objects between cell and the environment. (4) io= 0 indicates that the environment is the output region of whole system. Based on the tissue-like P system, the proposed membrane clustering algorithm is summarized in Table 1. 4 Experiment results and analysis In this section, the proposed membrane clustering algorithm is evaluated on ten data sets and compared with classical k-means algorithm and several clustering algorithms based on evolutionary algorithms, including GA [10], PSO [15] and ACO [16]. In order to test the robustness of these clustering algorithms, we repeat the experiments 50 times for each data set. 326 H. Peng et al. existing evolutionary clustering techniques, two inherent mechanisms of membrane computing are exploited to realize the membrane clustering algorithm, including evolution and communication mechanisms. For this purpose, a tissue-like P system consisting of qcells is designed, in which each cell as parallel computing unit runs in maximally parallel way and each object of the system expresses a group of candidate cluster centers. Moreover, the communication rules impliedly realize a local neighborhood structure, namely, each cell exchanges and shares the best objects with its two adjacent cells. Under the control of evolution and communication mechanisms of objects, the tissue-like P system is able to search for the optimal cluster centers for a data set to be clustered. In addition, the local neighborhood structure can guide the exploitation of the optimal object and enhance the diversity of evolution objects. Therefore, the membrane clustering presented in this paper can be viewed as a successful instance for building a bridge between membrane computing and data clustering. Acknowledgements This work was partially supported by the National Natural Science Foundation of China (Grant No. 61170030), the Chunhui Project Foundation of the Education Department of China (Nos. Z2012025 and Z2012031), and the Sichuan Key Technology Research and Development Program (No. 2013GZX0155), China. References 1. J.A. Hartigan, Clustering Algorithm, New York: Wiley, 1975. 2. A.K. Jain, R.C. Dubes, Algorithms for Clustering Data, Prentice-Hall, Engiewood Cliffs, NJ, 1988. 3. R. Xu, D. Wunsch, Survey of clustering algorithm, IEEE Trans. Neural Networks 16(3) (2005) 645-678. 4. A.K. Jain, Data clustering: 50 years beyond k-means, Pattern Recognition Letters 31 (2010) 651-666. 5. B. Everitt, S. Landau, M. Leese, Cluster Analysis, Arnold, London, 2001. 6. S. Saha, S. Bandyopadhyay, A symmetry based multiobjective clustering technique for automatic evolution of clusters, Pattern Recognition 43 (2010) 738-751. 7. T. Kanungo, D. Mount, N.S. Netanyahu, C. Piatko, R. Silverman, A. Wu, An efficient k-means clustering algorithm: analysis and implementation, IEEE Trans. Pattern Anal. Mach.Intell. 24(7) (2002) 881-892. 8. D. Steinley, K-meams clustering: A half-century synchesis, British Journal of Mathematical and Statistics Psychology 59(34) (2006) 1-34. 9. X. Wu, Top ten algorithms in data mining, Taylor & Francis, 2009. 10. S. Bandyopdhyay, U. Maulik, An evolutionary technique based on k-means algorithm for optimal clustering in RN, Inf. Sci. 146 (2002) 221-237. 11. S. Bandyopdhyay, S. Saha, GAPS: a clustering method using a new point symmetrybased distance measure, Pattern Recognition 40 (2007) 3430-3451. A Novel Clustering Algorithm under Membrane Computing 327 12. M. Laszlo, S. Mukherjee, A genetic algorithm that exchanges neighboring centers for k-means clustering, Pattern Recognition Lett. 28 (2007) 2359-2366. 13. D. Chang, X. Zhang, C. Zheng, A genetic algorithm with gene rearrangment for k-means clustering, Pattern Recognition 42 (2009) 1210-1222. 14. C.D. Nguyen, K.J. Cios, GAKREM: A novel hybrid clustering algorithm, Information Sciences 178 (2008) 4205-4227. 15. Y.T. Kao, E. Zahara, I.W. Kao, A hybridized approach to data clustering, Expert Systems with Applications 34(3) (2008) 1754-1762. 16. P.S. Shelokar, V.K. Jayaraman, B.D. Kulkarni, An ant colony approach for clustering, Analytica Chimica Acta 509(2) (2004) 187-195. 17. T. Niknam, B. Amiri, An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis, Applied Soft Computing 10 (2010) 183-197. 18. Gh. Pˇaun, Computing with membranes, Journal of Computer System Sciences 61(1) (2000) 108-143. 19. Gh. Pˇaun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010. 20. M. Ionescu, Gh. Pˇaun, T. Yokomori, Spiking neural P systems, Fundameta Informaticae 71(2-3) (2006) 279-308. 21. R. Freund, Gh. Pˇaun, M.J. P´erez-Jim´enez, Tissue-like P systems with channel-states, Theoretical Computer Science 330(1) (2005) 101-116. 22. H. Peng, J. Wang, M.J. P´erez-Jim´enez, H. Wang, J. Shao, T. Wang, Fuzzy reasoning spiking neural P system for fault diagnosis, Information Sciences 235 (2013) 106-116. 23. J. Wang, P. Shi, H. Peng, Mario J. P´erez-Jim´enez, T. Wang, Weighted fuzzy spiking neural P systems, IEEE Transactions on Fuzzy Systems 21(2) (2013) 209-220. 24. Gh. Pˇaun, M.J. P´erez-Jim´enez, Membrane computing: Brief introduction, recent results and applications, BioSystems 85 (2006) 11-22. 25. L. Huang, I. Suh, A. Abraham, Dynamic mul-objective optimization based on membrane computing for control of time-varying unstable plants, Information Sciences, 181(11) (2011) 2370-2391. 26. G. Zhang, J. Cheng, M. Gheorghe, Q. Meng, A hybrid approach based on different evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems, Applied Soft Computing, 13(3) (2013) 1528-1542. 27. C.A. Murthy, N. Chowdhury, In search of optimal clusters using genetic algorithms, Parttern Recognition Letters 17 (1996) 825-832. 28. U. Maulik, S. Bandyopadhyay, Genetic algorithm based clustering technique, Pattern Recognition 33 (2000) 1455-1465. 29. E. Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, 1998. 30. L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991. 31. Z. Michalewicz, Genetic Algorithm + Data Structure = Evolution Program, Springer, New York, 1996. 32. http://www.ics.uci.edu/∼mlearn/MLRepository.html. 33. R.A. Fisher, The use of multiple measurements in taxonomic problems, Ann. Eugenics 3 (1936) 179-188. 34. S.K. Pal, D.D. Majumder, Fuzzy sets and decision making approaches in vowel and speaker recognition, IEEE Trans. Systems, Man Cybernet. SMC-7 (1977) 625-629. 35. M. Clerc, J. Kennedy, The particle swarm explosion stability and convergence in a multi-dimensional complex space, IEEE Trans. Evolutionary Comput. 6(1) (2002) 58-73.